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
$103.30
Apple Inc.
+0.80
MSFT
$45.09
Microsoft Corpora
-0.34
GOOG
$577.33
Google Inc.
+5.73

MacTech Search:
Community Search:

Software Updates via MacUpdate

TextSoap 7.4.0 - Flexible text editing u...
TextSoap is for people who work with text. TextSoap effortlessly cleans up text from endlessly different formats. Wash away unwanted characters, spaces, tabs. Fix paragraphs with hard returns at the... Read more
NetShade 6.0.2 - Browse privately using...
NetShade is an Internet security tool that conceals your IP address on the web. NetShade routes your Web connection through either a public anonymous proxy server, or one of NetShade's own dedicated... Read more
Mac DVDRipper Pro 5.0 - Copy, backup, an...
Mac DVDRipper Pro is the DVD backup solution that lets you protect your DVDs from scratches, save your batteries by reading your movies from your hard disk, manage your collection with just a few... Read more
pwSafe 3.1 - Secure password management...
pwSafe provides simple and secure password management across devices and computers. pwSafe uses iCloud to keep your password databases backed-up and synced between Macs and iOS devices. It is... Read more
StatsBar 1.8 - Monitor system processes...
StatsBar gives you a comprehensive and detailed analysis of the following areas of your Mac: CPU usage Memory usage Disk usage Network and bandwidth usage Battery power and health (MacBooks only)... Read more
Path Finder 6.5.5 - Powerful, award-winn...
Path Finder is a file browser that combines the familiar Finder interface with the powerful utilities and innovative features. Just a small selection of the Path Finder 6 feature set: Dual pane... Read more
QuarkXPress 10.2.1 - Desktop publishing...
With QuarkXPress, you can communicate in all the ways you need to -- and always look professional -- in print and digital media, all in a single tool. Features include: Easy to Use -- QuarkXPress is... Read more
Skype 6.19.0.450 - Voice-over-internet p...
Skype allows you to talk to friends, family and co-workers across the Internet without the inconvenience of long distance telephone charges. Using peer-to-peer data transmission technology, Skype... Read more
Capo 3.1.2 - Slow down and learn to play...
Capo lets you slow down your favorite songs so you can hear the notes and learn how they are played. With Capo, you can quickly tab out your songs atop a highly-detailed OpenCL-powered spectrogram... Read more
VueScan 9.4.41 - 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

Latest Forum Discussions

See All

Modern Combat 5 Gets a Major Multiplayer...
Modern Combat 5 Gets a Major Multiplayer Update Posted by Jessica Fisher on September 2nd, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
Alien Creeps TD Review
Alien Creeps TD Review By Jennifer Allen on September 2nd, 2014 Our Rating: :: EXPENSIVE DEFENSESUniversal App - Designed for iPhone and iPad Alien Creeps TD would be a fun if unremarkable Tower Defense game, but its heavy focus on... | Read more »
The Journey Down: Chapter Two Review
The Journey Down: Chapter Two Review By Jennifer Allen on September 2nd, 2014 Our Rating: :: DARK YET ENTICINGUniversal App - Designed for iPhone and iPad It’s a little dark, in every sense of the word, but The Journey Down:... | Read more »
Function Space, a Social Network App for...
Function Space, a Social Network App for Science, Launches on iOS Posted by Ellis Spice on September 2nd, 2014 [ permalink ] | Read more »
Stupidfast – How Taylor Martinez Switche...
How do you make an Endless Running game more than just another Endless Running game? By adding real life prizes to it, of course! That’s the thinking behind StupidFast: a game designed for football enthusiasts, and the brainchild of former college... | Read more »
Little Raiders: Robin’s Revenge Review
Little Raiders: Robin’s Revenge Review By Jennifer Allen on September 2nd, 2014 Our Rating: :: CASUAL RAIDINGUniversal App - Designed for iPhone and iPad Combining simple combat with village building is a potent combination for... | Read more »
Treasure Tombs: Ra Deal Coming from Bulk...
Treasure Tombs: Ra Deal Coming from Bulkypix and Dark Tonic This Fall Posted by Jessica Fisher on September 2nd, 2014 [ permalink ] Dark Tonic and | Read more »
Pirate Bash Review
Pirate Bash Review By Nadia Oxford on September 2nd, 2014 Our Rating: :: BAD PIRATES, GOOD TIMESUniversal App - Designed for iPhone and iPad Pirate Bash’s turn-based battles add an intriguing twist to a typical physics game.   | Read more »
Tiny Tower Vegas Review
Tiny Tower Vegas Review By Jennifer Allen on September 2nd, 2014 Our Rating: :: STEADY DEVELOPMENTUniversal App - Designed for iPhone and iPad Build a huge tower again but Vegas-style in Tiny Tower Vegas.   | Read more »
The Manhattan Project Review
The Manhattan Project Review By Andrew Fisher on September 2nd, 2014 Our Rating: :: ROCKET SCIENCEUniversal App - Designed for iPhone and iPad The Manhattan Project offers a great Euro-style gameplay experience, but it is totally... | Read more »

Price Scanner via MacPrices.net

Apple Cuts iPad mini Prices; Non-apple Vendor...
Digitimes’ Max Wang and Joseph Tsai report that Apple is cooperating with US-based retailers including Best Buy and Amazon to cut iPad mini prices, and that channel retailers believe other brand... Read more
Apple refurbished iPads available for up to $...
Apple is offering Certified Refurbished iPad Airs for up to $140 off MSRP. Apple’s one-year warranty is included with each model, and shipping is free. Stock tends to come and go with some of these... Read more
Are We Now In The Post-Post-PC Era?
A longtime and thoroughgoing laptop aficionado, I was more than a little dismayed by Steve Jobs’s declaration back in 2010 when he sprang the iPad on an unsuspecting world. that we’d entered a “post-... Read more
PC Outlook Improves, But 2014 Shipments Still...
According to the International Data Corporation (IDC) Worldwide Quarterly PC Tracker, worldwide PC shipments are expected to fall by -3.7 percent in 2014. To hat’s actually an improvement from the... Read more
IDC Lowers Tablet Sales Projections for 2014...
Following a second consecutive quarter of softer than expected demand, International Data Corporation (IDC) has lowered its worldwide tablet plus 2-in-1 forecast for 2014 to 233.1 million units. The... Read more
Apple now offering refurbished 21-inch 1.4GHz...
The Apple Store is now offering Apple Certified Refurbished 21″ 1.4GHz iMacs for $929 including free shipping plus Apple’s standard one-year warranty. Their price is $170 off the cost of new models,... Read more
Save $50 on the 2.5GHz Mac mini, on sale for...
B&H Photo has the 2.5GHz Mac mini on sale for $549.99 including free shipping. That’s $50 off MSRP, and B&H will also include a free copy of Parallels Desktop software. NY sales tax only. Read more
Save up to $300 on an iMac with Apple refurbi...
The Apple Store has Apple Certified Refurbished iMacs available for up to $300 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free. These are the best prices on... Read more
The Rise of Phablets
Carlisle & Gallagher Consulting Group, a businesses and technology consulting firm focused solely on the financial services industry, has released an infographic depicting the convergence of... Read more
Bad Driver Database App Allows Good Drivers t...
Bad Driver Database 1.4 by Facile Group is a new iOS and Android app that lets users instantly input and see how many times a careless, reckless or just plain stupid driver has been added to the... 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...
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...
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...
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
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
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.