TweetFollow Us on Twitter

Nov 00 Challenge

Volume Number: 16 (2000)
Issue Number: 11
Column Tag: Programmer's Challenge

Programmer's Challenge

by Bob Boonstra, Westford, MA

FreeCell

Those of you who spend time on the Dark Side might have encountered a solitaire game called FreeCell packaged with a prominent operating system by Mr. Bill. Your Challenge this month is to produce a FreeCell player.

The prototype for the code you should write is:

typedef enum {
   kNoSuit=0, kSpade, kHeart, kDiamond, kClub
} Suit;

typedef enum {
   kNoSpot=0, 
   kAce, k2, k3, k4, k5, k6, k7, k8, k9, k10,
   kJack, kQueen, kKing
} Spot;

typedef struct Card {
   Suit   suit;   /* the suit of the card, kSpade .. kClub */
   Spot   spot;   /* the spot of the card, kAce .. kKing */
} Card;

typedef enum {   /* places to move cards from */
   sFreeCellA=2,sFreeCellB,sFreeCellC,sFreeCellD,
   sTableau0=6,sTableau1,sTableau2,sTableau3,sTableau4,sTableau5,sTableau6,sTableau7
} Source;

typedef enum {   /* places to move cards to */
   dHome=1,
   dFreeCellA=2,dFreeCellB,dFreeCellC,dFreeCellD,
   dTableau0=6,dTableau1,dTableau2,dTableau3,
   dTableau4,dTableau5,dTableau6,dTableau7
} Destination;

typedef struct Move {   /* move a card from theSource to theDestination */
   Source theSource;
   Destination theDestination;
} Move;

typedef struct Tableau {   /* each Tableau can contain 0..13 cards */
   Card theCard[13];
} Tableau;

long /* numMoves */ FreeCell(
   const Tableau   theTableau[8],   /* the cards as initially dealt */
   Move theMoves[],      /* return your moves in order here */
   long   maxMoves          /* storage is preallocated for maxMoves
   theMoves */
);

The FreeCell game is different from many solitaire games in a couple of respects. First, all of the cards are visible, so winning the game is more a matter of strategy than of luck. Second, while there are FreeCell deals that cannot be solved, nearly every game can be won, as contrasted with less than half of other popular solitaire games.

FreeCell starts with the playing Cards dealt face up into 8 piles called Tableaus. All 52 Cards are used, which means that the first four Tableaus receive seven Cards, and the remaining four Tableaus receive six Cards. The object of the game is to move all of the Cards onto four "Home" piles, one for each Suit, played in order from Ace up to King. You also have available four temporary locations, or "Free Cells", each of which can hold one Card. A Move consists of one of the following:

  • moving an Ace from a Free Cell or from the top of a Tableau to an empty Home pile
  • moving the next higher Card of a Suit from a Free Cell or from the top of a Tableau to the Home pile for that Suit
  • moving a Card from the top of a Tableau to an empty Free Cell
  • moving a Card from the top of a Tableau or a Free Cell to an empty Tableau
  • moving a Card from the top of a Tableau or from a Free Cell to the top of a Tableau, where the Suit of the Card on top of the destination Tableau has the opposite color of the Card being moved, and where the Spot of the Card on top of the destination Tableau is one higher than the Spot of the Card being moved.

Cards can be moved to or from a Free Cell, but each Free Cell can hold only one Card. Cards can be moved to the Home piles, never back from the Home piles. Cards can be moved to or from the top of a Tableau, but they can only be moved to a Tableau if the Suit colors alternate and if the Card value (Spot) decreases by one. Any Card from a Free Cell or the top of another Tableau may be placed on an empty Tableau.

Your FreeCell routine will be called with the Cards dealt into the 8 Tableaus. Your task is to generate a sequence of Moves that solve the puzzle, returning them in theMoves. Each Move consists of a Source and a Destination. It is not necessary to specify the Card being moved, because the Source uniquely identifies the Card at any given point in the game. FreeCell should return the number of Moves generated, or zero if you are unable to solve the puzzle.

Your solution will be awarded 10,000 points for each puzzle it solves correctly, and penalized 1 point for each millisecond of processor time required to solve the puzzle.

This will be a native PowerPC Challenge, using the CodeWarrior Pro 5 environment. Solutions may be coded in C, C++, or Pascal.

This Challenge was suggested by Peter Lewis, who wins 2 Challenge points for the suggestion. More information on the game FreeCell can be found at http://www.freecell.org.

Three Months Ago Winner

Congratulations once again to Ernst Munter (Kanata, Ontario) for submitting the winning entry to the August Longest Word Sort Challenge. Ernst's entry was the fastest of the seven entries submitted, and was just under 40% faster than the second-place entry by Jonny Taylor.

The Longest Word Sort Challenge required contestants to sort a sequence of lines of text based on the length of words in each line. The line with the longest word was to be considered greater than any other line. Among lines with longest words of the same length, the comparison was to be based on the next longest word, etc. Among lines with words of exactly the same length, the order was to be based on an alphanumeric comparison of words, in order of length, and then in order of occurrence.

The key to Ernst's solution is the LineDescriptor that he uses to profile each line of text. The LineDescriptor contains a packed description of the number of words of each length contained in the line. This allows Ernst to compare lines by comparing the numeric line profile values, using a single subtraction in the LineDescriptor::IsLessThan routine to compare the number of words of several lengths. In the event the LineDescriptors match exactly, the CompText routine compares the words of each line as text, in order of word length. This Challenge allowed the use of assembly language, and Ernst used one line of it in the BitsNeeded routine, which is used by Text::ComputeFieldSizes to calculate the width of the packed field needed to hold the number of words of a particular length.

Jonny Taylor's second-place solution uses a combination of sorting techniques, starting with a radix sort to partially sort the list based on the lengths of the 16 longest words in each line, and then using a quicksort algorithm to sort groups of lines with identical word lengths. Jan Schotsman's third place solution uses a merge sort to compare groups of up to 32 lines, starting with a comparison of the lengths of the 16 longest words in each line, and resorting to a more careful comparison when necessary. This Challenge certainly produces an interesting variety of approaches to an unusual sorting problem. The table below lists, for each of the solutions submitted, the cumulative execution time in milliseconds. It also provides the code size, data size, and programming language used for each entry. As usual, the number in parentheses after the entrant's name is the total number of Challenge points earned in all Challenges prior to this one.

NameTime (msecs)Code SizeData SizeLang
Ernst Munter (631)1683384330C++
Jonny Taylor (26)2721406844C
Jan E. Schotsman337725656C
Rob Shearer (47)41742616965C++
Darrell Walisser6304124128C
Ladislav Hala (7)63831282429C
Ron Nepsund (47)9726492501C

Top Contestants

Listed here are the Top Contestants for the Programmer's Challenge, including everyone who has accumulated 10 or more points during the past two years. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants.

Rank Name Points
1. Munter, Ernst 243
2. Saxton, Tom 106
3. Maurer, Sebastian 68
4. Rieken, Willeke 65
5. Shearer, Rob 51
6. Boring, Randy 50
7. Taylor, Jonathan 36
8. Brown, Pat 20

... and the Top Contestants Awaiting Their First Win

Starting this month, in order to give some recognition to other participants in the Challenge, we are also going to list the high scores for contestants who have accumulated points without taking first place in a Challenge. Listed here are all of those contestants who have accumulated 6 or more points during the past two years.

9. Downs, Andrew 12
10. Jones, Dennis 12
12. Duga, Brady 10
13. Fazekas, Miklos 10
15. Selengut, Jared 10
16. Strout, Joe 10
17. Wihlborg, Claes 9
18. Hala, Ladislav 7
20. Schotsman, Jan 7
21. Widyyatama, Yudhi 7
22. Heithcock, JG 6

There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2) being the first person to find a bug in a published winning solution or, (3) being the first person to suggest a Challenge that I use. The points you can win are:

1st place 20 points
2nd place 10 points
3rd place 7 points
4th place 4 points
5th place 2 points
finding bug 2 points
suggesting Challenge 2 points

Here is Ernst's winning Longest Word Sort solution:

LongestWordSort.cp
Copyright © 2000
Ernst Munter, Kanata, ON, Canada

/*

The Problem
—————-
Text is to be sorted by lines, with the lengths of words as well as the
text itself determining the order of lines.

Solution
————
The text is analyzed, and a line descriptor derived for each line. The
line descriptor contains a profile which lists the frequency of words by
length for the referenced line.  This profile is the primary key for the
sort.  Text comparisons only come into play when the profiles are
identical.

To reduce the main sort effort, lines are pre-sorted into groups which
share the same longest word length.

Each group is then sorted with heap sort, where the first phase (of
inserting the line into a heap) is combined with making a copy of the
line of text into a temporary pre-sorted text, i.e. by line group.  The
second phase of the heap sort is then combined with copying the result
back to the external text array, in the final order.
 
Optimizations
——————-
Memory accesses are minimized by copying the text just once to temporary
storage and back, as part of the sorting opration. 

The sorting itself is conducted with short line descriptors, based on
bit-packed profiles.  In most cases, a line descriptor will be 16 or 20
bytes long.

The number of comparisons is reduced (further economizing on memory
access) by using a combination of distribution sort (by line group) and
heap sort within each line group segment.  Null and null-word lines
remain in the original order and are already sorted by the distribution
sort.

Most functions are written as inlined, but the compiler will not
necessarily inline them, using its own "smart"ness.  This is not
necessarily optimal. I have forced it not to inline Pop() and
CompText().  This allows the compiler then to inline other function,
reducing the number of function calls overall.
 
Assumptions
—————-
TextToSort should end with a Mac newline character (0x0d); Any text
beyond the last newline character will not be sorted.

No assumptions are made for limits except that the longest word must be
less than 128 characters long.  Lines may be of any length and contain
any number of words.
*/

#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "LongestWordSort.h"

#define MAXLENGTH    127   // no word longer than MAXLENGTH chars is expected

typedef unsigned char uchar;
typedef unsigned short ushort;
typedef unsigned long ulong;

enum {
   kMaxLength=MAXLENGTH,
   kArraySize=1+MAXLENGTH,
   kEOL=0x0d,
   kAlnumType=0,
   kWhiteType=1,
   kEOLtype=2,
   kCaseSensitive=0xFF,
   kNoCase=0xDF,
   kSignBit=0x80000000
};

static uchar kCaseMask[2] = {kNoCase,kCaseSensitive};
static ulong gCaseMask;
static ulong gDescending;

inline long Max(long a,long b)
// Algebraic method of selecting greater of two longs, avoids branch stalls
{
   long D = (a-b) >> 31;
   long notD = ~D;
   return (b & D) | (a & notD);
}

BitsNeeded
inline long BitsNeeded(ulong x)
// Returns number of bits needed to encode range 0 to x
{
   // this simple intrinsic is just what the job needs
   return 32 - __cntlzw(x);
/*
   // platform independent method:
   int n=0;
   while(x) { x >>= 1; n++;}
   return n;
*/
}

// Private version of the table from ctype, to include a code for EndOfLine (kEOL)
static struct CharType {
   uchar T[256];
   CharType()
   {
      for (long c=0;c<256;c++)
         T[c]=(isalnum(c))?kAlnumType:kWhiteType;
      T[kEOL]=kEOLtype;
   }
} gCharType;

struct LineDescriptor
//    A LineDescriptor characterises one line of text, 
//   containing all information needed for efficient sorting 
struct LineDescriptor;
typedef LineDescriptor* LineDescriptorPtr;
struct LineDescriptor {
   uchar*   textRef;         // pointer to start of line in copy of text
   ulong   lineLength;         // number of chars of this line
   ushort   longestWordLength;   // length of the longest word in this line
   ushort   profileLength;      // number of longs in profile
   long   profile[1];         // packed, number of words per length
   
   ulong LineLength() const {return lineLength;}
   
   long Init(uchar* lineStart,ulong lineLen,ulong longest,
      ulong lengthDist[],uchar fieldWidth[])
// Initializes the fields for one line.
// Returns the length of the struct, which includes the variable-size profile
   {
      textRef=lineStart;
      lineLength=lineLen;
      longestWordLength=longest;
// Builds the line profile by packing the number of words, by length, 
// into a string of 31-bit values for efficient comparison later.
      long* prof=profile;
      ulong acc=0;
      ulong fill=0;
      for (long len=longest;len>0;—len)
      {
         long numBits=fieldWidth[len];            
         long value=lengthDist[len];   
         fill+=numBits;
         if (fill > 31)
         {
            fill=numBits;
            *prof++=acc;
            acc=value;
         } else 
         {
            acc = value | (acc << numBits);
         }
         lengthDist[len]=0;
      }
      *prof++=acc;
      profileLength=prof-profile;
      return (sizeof(LineDescriptor) - sizeof(ulong)) +
         sizeof(ulong) * profileLength;
   }
   
LineDescriptor::IsLessThan
   ulong IsLessThan(const LineDescriptor& other) const
// Returns true if this line should be "before" the other line (ascending)
   {   
// Compare line profiles first:
      const long* A=profile;                           
      const long* B=other.profile;
      long pLength=profileLength;
      
      // there is always at least one profile word to compare
      long delta = (*A - *B);
      if (delta)                                 
         return delta & kSignBit;                     
                                                
      while (—pLength) {
         delta = *++A - *++B;                        
         if (delta)
            return delta & kSignBit;
      } 
                                 
// Both profiles are equal: must compare on the basis of text:
      delta=CompText(other);                           
      if (delta)
         return  delta & kSignBit;
                                                
//  The text is exactly the same: 
//    Compare on the basis of the original line order
//    But reverse if descending to compensate for reverse CopyBack
      return gDescending ^ ((textRef - other.textRef) & kSignBit);
   }
   
   static long CompWords(const uchar* w1,
      const uchar* w2,long len,long caseMask)
// Simple string comparison, character by character, case sensitive as required
   {
      for (long i=0;i<len;i++) 
      {
         long c1=*w1++ & caseMask;
         long c2=*w2++ & caseMask;
         long delta=c1-c2;
         if (delta) return delta;
      } 
      return 0;
   }
   
   LineDescriptor::LocateNext
static const uchar* LocateNext(const uchar* start,long length) 
// Returns the next word of the specified length 
   {
      ulong c=*start,len=0;
      const uchar* word=start;
      for (;;)
      {
         long charType=gCharType.T[c];
         c=*++start;
         if (charType==kAlnumType)    // is alnum
         {
            if (len==0) word=start-1;
            len++;   
         } else 
         {
            if (len==length)      // lengths match: found it
                  break;
            
            if (charType==kEOLtype)   // reached end of the line
               return 0;
            len=0;
         }
      }
      return word;
   }
   
   void Write(uchar* outText) const
   {
// Note: memcpy is faster than strncpy or character by character copy.
      memcpy(outText,textRef,lineLength);
   }
   
   long CompText(const LineDescriptor& other) const;
};

LineDescriptor::CompText
long LineDescriptor::CompText(const LineDescriptor& other) const
// Returns result of comparing the line as text, longest words first
{   
   for (long len=longestWordLength;len>0;len—)
   {
      const uchar* w1=textRef;
      const uchar* w2=other.textRef;
      for (;;)
      {
         if (0==(w1=LocateNext(w1,len))) 
            break; // no word of this length found
            
         w2=other.LocateNext(w2,len);         
         // if w1 exists, w2 must exist 
          long d=CompWords(w1,w2,len,gCaseMask);            
         if (d)
            return (d);
         w1 = w1+len;
         w2 = w2+len;
      }
   }                                             
   return 0;
}

struct Segment   
// The priority queue (Heap) structure is used for sorting the line descriptors.
// Sorting occurs in two phases: Insert() and Pop()
// We build a separate heap for each lineGroup segment (which shares a common 
// longest word length).  This reduces the size of the individual heaps, resulting in 
// fewer comparisons overall.  
struct Segment {
   LineDescriptorPtr*    heapBase;
   ulong   heapSize;
   ulong   maxHeapSize;
   uchar*   nextLineDesc;
   ulong   lineDescSize;

// Just keep track of the line count, to prepare correct heap size                  
   void AddLine(){maxHeapSize++;}
   
   ulong MemRequired(ulong profileLongs,ulong profileBits)
   {
// Returns the amount of memory required for lineDescs and their index (=heap)
      if (maxHeapSize==0) return 0;
      ulong profileSizeInLongs=profileLongs+(31+profileBits)/32;
      ulong profileBytes=4*profileSizeInLongs;
      
      lineDescSize=
         profileBytes + (sizeof(LineDescriptor) - sizeof(ulong));
      return
         lineDescSize * maxHeapSize +             // for linedescs
         sizeof(LineDescriptorPtr*) * (1+maxHeapSize);// for heap index
   }
   
   uchar* Init(uchar* memPool)
   {
// Grabs memory from the pool for lineDescs and the heap; returns updated pool
      if (maxHeapSize>0)
      {
         nextLineDesc=memPool;
         memPool += maxHeapSize * lineDescSize;
      
         heapBase=(LineDescriptorPtr*) memPool;
         memPool += sizeof(LineDescriptorPtr*) * (1+maxHeapSize);
      }
      return memPool;
   }      
   
   LineDescriptorPtr GetLineDesc() 
// Walks the index memory to assign consecutive lineDesc indices
   {
      LineDescriptorPtr next=LineDescriptorPtr(nextLineDesc);
      nextLineDesc += lineDescSize;
      return next;
   }
   
   void Insert(LineDescriptorPtr k) 
// Inserts one line, while maintaining the heap property
   {
       long i=++heapSize;
       long j=i>>1;
       LineDescriptorPtr z;
       while (j && (k->IsLessThan(*(z=heapBase[j])))) 
       {   
            heapBase[i]=z;     
             i=j;
            j=i>>1;
       }
       heapBase[i]=k;    
     }
     
   uchar* CopyBack(uchar* textToSort)
// Pops one line off the heap, and copies the referenced line to the output.
// When descending, lines are copied starting at the end of the output.
// Returns the updated output text pointer, in preparation for the next copy.
   {
      if (0==heapSize)
         return textToSort;
         
      if (gDescending)
      {
         uchar* endText=textToSort;
         do {
            LineDescriptorPtr textLine=Pop();
            uchar* outText=endText - textLine->LineLength();
            textLine->Write(outText);
            endText=outText;
         } while(heapSize);
         return endText;
      } else
      {
         uchar* outText=textToSort;
         do {
            LineDescriptorPtr textLine=Pop();
            textLine->Write(outText);
            outText+=textLine->LineLength();
         } while(heapSize);
         return outText;
      }
   }
   
   LineDescriptorPtr Pop();
};

Segment::Pop
LineDescriptorPtr Segment::Pop() 
//   The node at heapBase[1] has the lowest weight.
//   It is popped from the heap and returned.  
//  The heap is adjusted to maintain the heap property.
{
    LineDescriptorPtr rc=heapBase[1];
      LineDescriptorPtr k=heapBase[heapSize—];
    if (heapSize<=1) {
         heapBase[1]=k;            
         return rc;
      }
      long i=1,j=2;
      while (j<=heapSize) 
      {
         if ((j<heapSize)
       && (heapBase[j+1]->IsLessThan(*heapBase[j])))
            j++;
         if (k->IsLessThan(*heapBase[j]))
            break;
         heapBase[i]=heapBase[j];  
         i=j;j+=j;
      }
      heapBase[i]=k;        
      return rc;
}
   
struct Text
struct Text {
   uchar*    theText;
   ulong   textSize;
   uchar*   copyText;
   ulong   gNumLines;
   ulong   gLongest;
   
   uchar*   lineDescMemory;
      
// highest number of words of length x in a line:
   ulong   lengthDist[kArraySize];
   ulong   tempLengthDist[kArraySize];
   
// one segment of lineDescriptors for each possible lineGroup
   Segment   segment[kArraySize];
   
// size (=numChars) of each text segment by longestWord line group:
   ulong   segmentSize[kArraySize];
   
// start of each text segment by longestWord line group
   uchar*   segmentStart[kArraySize];
   
// width of profile fields in bits for each possible word length
   uchar   fieldWidth[kArraySize];

   Text(char *textToSort,long numChars) :
         theText((uchar*)textToSort),
         textSize(numChars),
         copyText(new uchar[numChars])
   {
// Constructor analyzes text and computes text profile, prior to sorting.
// Determines the division of the text into line groups.
      memset(lengthDist,0,sizeof(lengthDist) 
         + sizeof(tempLengthDist) 
         + sizeof(segment) 
         + sizeof(segmentSize));
      Analyze();
      ComputeFieldSizes();
      lineDescMemory=GetLineDescMemory();   
   }
   ~Text()
   {
      delete [] lineDescMemory;
      delete [] copyText;
   }
   
   void Sort()
// Does the actual sorting of the segments:
   {
// Scans the text a second time while inserting lines in segments heaps.
// This constitutes the first phase of sorting.
      Presort();
      
// Zero-word lines will be in the original order in line group 0,
// They can just be copied en bloc, to the front or back end of the output.
      uchar* dest=theText;
      if (gDescending)
      {
         dest += textSize-segmentSize[0];
         memcpy(dest,copyText,segmentSize[0]);
      } else 
      {
         memcpy(dest,copyText,segmentSize[0]);
         dest += segmentSize[0];
      }
   
// The remaining lines are popped from each segment heap,  
// starting with the linegroup with the shortest longest words.
// This completes the second phase of sorting. 
      for (long len=1;len<=gLongest;len++)
      {
         dest=segment[len].CopyBack(dest);
      }
   }
   void Analyze();
   void ComputeFieldSizes();
   uchar* GetLineDescMemory();
   void Presort();
};

Text::Analyze
void Text::Analyze()
// Scans the original text and collects statistics such as 
//      - the number of lines
//      - the number of words by length
//      - the size of each line group (lines with the same max-length)
//      - the longest word in the whole text
// The loop in this routine relies on finding a 0x0d character at text end. 
{
   ulong   len=0,longest=0,numLines=0;
   ulong   globalLongest=0;
   uchar*   text=theText;
   ulong   c=*text;
   uchar*   lineStart=text;
   ulong   numChars=textSize;
   for (;;)
   {
      long charType=gCharType.T[c];
      c=*++text;
      if (charType==kAlnumType) len++;   // part of a word
      else 
      {
         if (len)                  // register the word
         {
            tempLengthDist[len]++; 
            longest=Max(longest,len);
            len=0;
         }
      
         if (charType==kEOLtype)         // register the line
         {
            for (long l=0;l<=longest;l++)
            {
               if (lengthDist[l] < tempLengthDist[l])
                  lengthDist[l] = tempLengthDist[l];      
               tempLengthDist[l]=0;
            }
            segment[longest].AddLine();
            globalLongest=Max(globalLongest,longest);
            ulong lineLength=text-lineStart;
            segmentSize[longest]+=lineLength;
            numChars -= lineLength;
            numLines++;
            
            if (numChars <= 0)
               break;
            longest=0;   
            lineStart=text;
         }
      } 
   }
   gNumLines = numLines;
   gLongest  = globalLongest;
}

Text::ComputeFieldSizes
void Text::ComputeFieldSizes()
// Computes the minimum field widths for profiles, for each word length
// also devides the text copy into segments, one per line group
{
   uchar* start=copyText;
   for (long len=0;len<=gLongest;len++)
   {
      fieldWidth[len] = BitsNeeded(lengthDist[len]);
      segmentStart[len]=start;
      start+=segmentSize[len];
   }
}

Text::GetLineDescMemory
uchar* Text::GetLineDescMemory()
// Allocates the memory required for the variable size line descriptors 
// and sets up the lineGroup segments.
// Note: In the interest of not fragmenting the memory heap unnecesssarily,
//       this memory is allocated as a single chunk, and then divided
//       out among the segments for line descriptors and index arrays.
{   
   ulong memRequired=0;
   
   ulong profileBits=0,profileLongs=0;
   for (long len=1;len<=gLongest;len++)
   {
      long fWidth=fieldWidth[len];
      if (fWidth)
      {
         // accumulate total bits to cover fields up to length len
         profileBits += fWidth;
         if (profileBits > 31)
         {
            profileLongs++;
            profileBits=fWidth;
         }
         
         // if segment[len] is not empty, reserve memory for it 
         memRequired += 
               segment[len].MemRequired(profileLongs,profileBits);
      } 
   }

// Allocate all required memory ..
   uchar* allocated=new uchar[memRequired];
   memset(allocated,0,memRequired);
   
// .. and divide it among active segments
   uchar* memPool=allocated;
   for (long len=1;len<=gLongest;len++)
      memPool=segment[len].Init(memPool);
   
   return allocated;
}

Text::Presort
void Text::Presort()
// Second scan of the text:
//      assigns and initializes a line descriptor for each line, 
//      and inserts it in the selected segment 
{
   uchar* text=theText;
   ulong len=0,longest=0;
   memset(tempLengthDist+1,0,gLongest*sizeof(ulong));
   uchar* lineStart=text;
   ulong c=*text;
   long numLines=gNumLines;
   for (;;)
   {
      long charType=gCharType.T[c];
      c=*++text;
      if (charType==kAlnumType) len++;
      else 
      {
         if (len)            // register the word
         {
            tempLengthDist[len]++;
            longest=Max(longest,len);
            len=0;
         }
      
         if (charType==kEOLtype)      // register the line
         {
            —numLines;
            ulong lineLength=text-lineStart;
                  
            uchar* copyDest=segmentStart[longest];
            memcpy(copyDest,lineStart,lineLength);
            segmentStart[longest] = copyDest+lineLength;
            lineStart=text;
            
            if (longest)         // make a new line descriptor
            {
               LineDescriptorPtr lineDesc =
                  segment[longest].GetLineDesc();
            
               // note side effect: Init clears tempLengthDist
               lineDesc->Init(copyDest,lineLength,longest,
                  tempLengthDist,fieldWidth);
                  
               segment[longest].Insert(lineDesc);
               
               longest=0;
            } // else, no need to do anything (no words in line) 
            if (numLines<=0)
               break;
         }
      } 
   }
}

LongestWordSort
void LongestWordSort(
   char *textToSort,      /* the text to be sorted */
   long numChars,         /* the length of the text in bytes */
   Boolean descending,    /* sort in descending order if true */
   Boolean caseSensitive  /* sort is case sensitive if true */
) {
// Just to be sure, let's ignore all text beyond the last CR
   while (numChars && (kEOL != textToSort[numChars-1]))
      numChars—;

   if (numChars==0) return; // quit if there is no text to sort
   
// Make sort parameters global
   gDescending=(descending)?kSignBit:0;
      gCaseMask=kCaseMask[caseSensitive];
      
// Initialize ..
   Text* T=new Text(textToSort,numChars);
// and sort: 
   T->Sort();
   delete T;   
}

 
AAPL
$100.11
Apple Inc.
-0.64
MSFT
$46.44
Microsoft Corpora
+0.03
GOOG
$576.36
Google Inc.
-0.74

MacTech Search:
Community Search:

Software Updates via MacUpdate

SyncTwoFolders 2.0.5 - Syncs two user-sp...
SyncTwoFolders simply synchronizes two folders. It supports synchronization across mounted network drives and it is a possibility to run a simulation showing in a log what will be done. Please visit... Read more
FinderPop 2.5.7 - Classic Mac utility, n...
FinderPop is a Universal preference pane that extends OS X's contextual menus using a FinderPop Items folder much as the Apple Menu Items folder used to do for the Apple menu. It has other features... Read more
VueScan 9.4.45 - Scanner software with a...
VueScan is a scanning program that works with most high-quality flatbed and film scanners to produce scans that have excellent color fidelity and color balance. VueScan is easy to use, and has... Read more
LibreOffice 4.3.2.2 - Free Open Source o...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more
calibre 2.4 - Complete e-library managem...
Calibre is a complete e-book library manager. Organize your collection, convert your books to multiple formats, and sync with all of your devices. Let Calibre be your multi-tasking digital... Read more
Default Folder X 4.6.9b1 - Enhances Open...
Default Folder X attaches a toolbar to the right side of the Open and Save dialogs in any OS X-native application. The toolbar gives you fast access to various folders and commands. You just click... Read more
Beamer 2.0.4 - Stream any movie file fro...
Beamer streams to your Apple TV.... Plays any movie file - Just like the popular desktop movie players, Beamer accepts all common formats, codecs and resolutions. AVI, MKV, MOV, MP4, WMV, FLV. To... Read more
Adobe Premiere Elements 13.0 - Consumer...
Adobe Premiere Elements just got better. Now you can create quick movies from favorite parts of your clips or tell big life stories in full-on productions. Add motion inside movie titles, punch up... Read more
Boom 1.9.2 - System-wide volume booster...
Boom is a system-wide volume booster and equalizer that effortlessly improves the sound of your Mac. Using Boom is easy. It works like the volume controls of your Mac to boost the sound; making it a... Read more
Amadeus Pro 2.1.7 - Multitrack sound rec...
Amadeus Pro lets you use your Mac computer for any audio-related task, such as live audio recording, digitizing tapes and records, converting between a variety of sound formats, etc. Thanks to its... Read more

Latest Forum Discussions

See All

This Week at 148Apps: September 22-26, 2...
Your Source For The Latest App Reviews   | Read more »
Kill Shot Review
Kill Shot Review By Jennifer Allen on September 29th, 2014 Our Rating: :: OCCASIONAL MISFIRESUniversal App - Designed for iPhone and iPad Kill Shot is often satisfying, but its more than pushy in-app purchases will leave you... | Read more »
It Came From Canada: Vainglory
I’m going to be straight you with folks. I don’t know much about MOBAs, and I’m certainly no professional. That means I don’t know how well Vainglory, the upcoming multiplayer online battle arena showcased in the most recent Apple keynote, compares... | Read more »
The Tunnel – An Endless Fall Review
The Tunnel – An Endless Fall Review By Nadia Oxford on September 29th, 2014 Our Rating: :: FREE FALLIN' Universal App - Designed for iPhone and iPad The Tunnel – An Endless Fall is a bit harder to get the hang of than most “endless... | Read more »
Ubisoft Launches Just Dance Now in the A...
Ubisoft Launches Just Dance Now in the App Store Worldwide Posted by Jessica Fisher on September 29th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
For Better, or for Worse? How the New Ap...
With the release of iOS 8 (finally), Apple has made some noticeable changes on the App Store – bundles, videos, and Testflight integration, to name a few. Many of these additions will make things friendlier for App Store shoppers, but how has it... | Read more »
Asphalt Overdrive Review
Asphalt Overdrive Review By Jennifer Allen on September 29th, 2014 Our Rating: :: SHORT LIVED ADRENALINEUniversal App - Designed for iPhone and iPad Asphalt Overdrive is a fairly simple auto-running racing game, but one that’s... | Read more »
Kritika: Wrath of the Pirate King Update...
Kritika: Wrath of the Pirate King Update Introduces New Class: Shadow Mage. Posted by Jessica Fisher on September 29th, 2014 [ permalink ] | Read more »
Vampire Tribunals Review
Vampire Tribunals Review By Campbell Bird on September 29th, 2014 Our Rating: iPhone App - Designed for the iPhone, compatible with the iPad Hunt other vampires in the “real world” in this location-based multiplayer game.   | Read more »
Simogo Tease The Sailor’s Dream Via Thei...
Simogo Tease The Sailor’s Dream Via Their New Trailer Posted by Ellis Spice on September 29th, 2014 [ permalink ] A new trailer has arrived for the newest title from Device 6 and | Read more »

Price Scanner via MacPrices.net

MacBook Airs on sale for $100 off MSRP, start...
Best Buy has the new 2014 MacBook Airs on sale for $100 off MSRP on their online store. Choose free home shipping or free local store pickup (if available). Prices valid for online orders only, in-... Read more
Apple Releases OS X Mavericks bash Update 1.0...
Apple has released a patch update for OS X Mavericks users to address the recently-detected “Shellshock” security bug in BSD UNIX’s bash shell. Apple says only a few Mac users who had manually... Read more
Pivotal Payments Ready for Apple Pay – FlexPo...
Pivotal Payments, a provider of merchant services and global payment processing solutions, has announced its proprietary FlexPoint platform will support credit and debit transactions through Apple’s... Read more
iStabilizer Announces Tabarm — First Friction...
iStabilizer, a specialist in universal lightweight compact tripods, steady cams, dollies, mounts, and remotes for smartphones, tablets, and cameras, announced today the iStabilizer tabArm, the first... Read more
IStabilizer Flex Smartphone Tripod Wins Usa T...
iStabilizer, a specialist in universal lightweight compact tripods, steady cams, and other products for smartphones, tablets, and cameras, has announced today that its iStabilizer Flex smartphone... Read more
13-inch 2.8GHz Retina MacBook Pro on sale for...
B&H Photo has the new 2014 13″ 2.8GHz Retina MacBook Pro on sale for $1699.99 including free shipping plus NY sales tax only. They’ll also include free copies of Parallels Desktop and LoJack for... Read more
15-inch Retina MacBook Pros on sale for up to...
B&H Photo has the new 2014 15″ Retina MacBook Pros on sale for up to $150 off MSRP. Shipping is free, and B&H charges NY sales tax only. They’ll also include free copies of Parallels Desktop... Read more
Get Down to Business On Your iPad With Free N...
Utah based Poem LLC has introduced Nexticy 1.0, a full-featured, affordable (Free) forms application for iPad. Nexticy makes it ‘way easy’ to create, store, retrieve and analyze paper-like forms of... Read more
13-inch Retina MacBook Pros on sale for $100...
Best Buy has 13-inch 2.6GHz Retina MacBook Pros on sale for $100 off MSRP on their online store. Choose free shipping or free local store pickup (if available). Prices are for online orders only, in-... Read more
Reports Outline Claimed 12-Inch Macbook Air D...
Blogger Jack March says that according to information he’s received from an anonymous “source familiar with Apple’s plans,” the next-generation MacBook Air will launch in mid-2015 and be available... Read more

Jobs Board

*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
*Apple* Retail - Multiple Positions (US) - A...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
Senior Event Manager, *Apple* Retail Market...
…This senior level position is responsible for leading and imagining the Apple Retail Team's global event strategy. Delivering an overarching brand story; in-store, Read more
*Apple* Solutions Consultant (ASC) - Apple (...
**Job Summary** The ASC is an Apple employee who serves as an Apple brand ambassador and influencer in a Reseller's store. The ASC's role is to grow Apple Read more
Project Manager / Business Analyst, WW *Appl...
…a senior project manager / business analyst to work within our Worldwide Apple Fulfillment Operations and the Business Process Re-engineering team. This role will work Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.