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
$105.22
Apple Inc.
+0.39
MSFT
$46.13
Microsoft Corpora
+1.11
GOOG
$539.78
Google Inc.
-4.20

MacTech Search:
Community Search:

Software Updates via MacUpdate

OS X Server 4.0 - For OS X 10.10 Yosemit...
Designed for OS X and iOS devices, OS X Server makes it easy to share files, schedule meetings, synchronize contacts, develop software, host your own website, publish wikis, configure Mac, iPhone,... Read more
TotalFinder 1.6.12 - Adds tabs, hotkeys,...
TotalFinder is a universally acclaimed navigational companion for your Mac. Enhance your Mac's Finder with features so smart and convenient, you won't believe you ever lived without them. Tab-based... Read more
BusyCal 2.6.3 - Powerful calendar app wi...
BusyCal is an award-winning desktop calendar that combines personal productivity features for individuals with powerful calendar sharing capabilities for families and workgroups. BusyCal's unique... Read more
calibre 2.7 - 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
Skitch 2.7.3 - Take screenshots, annotat...
With Skitch, taking, annotating, and sharing screenshots or images is as fun as it is simple.Communicate and collaborate with images using Skitch and its intuitive, engaging drawing and annotating... Read more
Delicious Library 3.3.2 - Import, browse...
Delicious Library allows you to import, browse, and share all your books, movies, music, and video games with Delicious Library. Run your very own library from your home or office using our... Read more
Art Text 2.4.8 - Create high quality hea...
Art Text is an OS X application for creating high quality textual graphics, headings, logos, icons, Web site elements, and buttons. Thanks to multi-layer support, creating complex graphics is no... Read more
Live Interior 3D Pro 2.9.6 - Powerful an...
Live Interior 3D Pro is a powerful yet very intuitive interior designing application. View Video Tutorials It has every feature of Live Interior 3D Standard, plus some exclusive ones: Create multi... Read more
The Hit List 1.1.7 - Advanced reminder a...
The Hit List manages the daily chaos of your modern life. It's easy to learn - it's as easy as making lists. And it's powerful enough to let you plan, then forget, then act when the time is right.... Read more
jAlbum Pro 12.2.4 - Organize your digita...
jAlbum Pro has all the features you love in jAlbum, but comes with a commercial license. With jAlbum, you can create gorgeous custom photo galleries for the Web without writing a line of code!... Read more

Latest Forum Discussions

See All

Rami Ismail Opens Up distribute​() for D...
Rami Ismail Opens Up distribute​() for Developers Posted by Jessica Fisher on October 24th, 2014 [ permalink ] Rami Ismail, Chief Executive of Business and Development at indie game studio | Read more »
Great Hitman GO Goes on Sale and Gets Ne...
Great Hitman GO Goes on Sale and Gets New Update – Say That Three Times Fast Posted by Jessica Fisher on October 24th, 2014 [ permalink ] | Read more »
Rival Stars Basketball Review
Rival Stars Basketball Review By Jennifer Allen on October 24th, 2014 Our Rating: :: RESTRICTIVE BUT FUNUniversal App - Designed for iPhone and iPad Rival Stars Basketball is a fun mixture of basketball and card collecting but its... | Read more »
Rubicon Development Makes Over a Dozen o...
Rubicon Development Makes Over a Dozen of Their Games Free For This Weekend Only Posted by Jessica Fisher on October 24th, 2014 [ permalink ] | Read more »
I Am Dolphin Review
I Am Dolphin Review By Jennifer Allen on October 24th, 2014 Our Rating: :: NEARLY FIN-TASTICUniversal App - Designed for iPhone and iPad Swim around and eat nearly everything that moves in I Am Dolphin, a fun Ecco-ish kind of game... | Read more »
nPlayer looks to be the ultimate choice...
Developed by Newin Inc, nPlayer may seem like your standard video player – but is aiming to be the best in its field by providing high quality video play performance and support for a huge number of video formats and codecs. User reviews include... | Read more »
Fighting Fantasy: Caverns of the Snow Wi...
Fighting Fantasy: Caverns of the Snow Witch Review By Jennifer Allen on October 24th, 2014 Our Rating: :: CLASSY STORYTELLINGUniversal App - Designed for iPhone and iPad Fighting Fantasy: Caverns of the Snow Witch is a sterling... | Read more »
A Few Days Left (Games)
A Few Days Left 1.01 Device: iOS Universal Category: Games Price: $3.99, Version: 1.01 (iTunes) Description: Screenshots are in compliance to App Store's 4+ age rating! Please see App Preview for real game play! **Important: Make... | Read more »
Toca Boo (Education)
Toca Boo 1.0.2 Device: iOS Universal Category: Education Price: $2.99, Version: 1.0.2 (iTunes) Description: BOO! Did I scare you!? My name is Bonnie and my family loves to spook! Do you want to scare them back? Follow me and I'll... | Read more »
Intuon (Games)
Intuon 1.1 Device: iOS Universal Category: Games Price: $.99, Version: 1.1 (iTunes) Description: Join the battle with your intuition in a new hardcore game Intuon! How well do you trust your intuition? Can you find a needle in a... | Read more »

Price Scanner via MacPrices.net

Weekend sale: 13-inch 128GB MacBook Air for $...
Best Buy has the 2014 13-inch 1.4GHz 128GB MacBook Air on sale for $849.99, or $150 off MSRP, on their online store. Choose free home shipping or free local store pickup (if available). Price valid... Read more
Nimbus Note Cross=Platform Notes Utility
Nimbus Note will make sure you never forget or lose your valuable data again. Create and edit notes, save web pages, screenshots and any other type of data – and share it all with your friends and... Read more
NewerTech’s Snuglet Makes MagSafe 2 Power Con...
NewerTech has introduced the Snuglet, a precision-manufactured ring designed to sit inside your MagSafe 2 connector port, providing a more snug fit to prevent your power cable from unintentional... Read more
Apple Planning To Sacrifice Gross Margins To...
Digitimes Research’s Jim Hsiao says its analysts believe Apple is planning to sacrifice its gross margins to save its tablet business, which has recently fallen into decline. They project that Apple’... Read more
Who’s On Now? – First Instant-Connect Search...
It’s nighttime and your car has broken down on the side of the highway. You need a tow truck right away, so you open an app on your iPhone, search for the closest tow truck and send an instant... Read more
13-inch 2.5GHz MacBook Pro on sale for $949,...
Best Buy has the 13″ 2.5GHz MacBook Pro available for $949.99 on their online store. Choose free shipping or free instant local store pickup (if available). Their price is $150 off MSRP. Price is... Read more
Save up to $125 on Retina MacBook Pros
B&H Photo has the new 2014 13″ and 15″ Retina MacBook Pros on sale for up to $125 off MSRP. Shipping is free, and B&H charges NY sales tax only. They’ll also include free copies of Parallels... Read more
Apple refurbished Time Capsules available sta...
The Apple Store has certified refurbished Time Capsules available for up to $60 off MSRP. Apple’s one-year warranty is included with each Time Capsule, and shipping is free: - 2TB Time Capsule: $255... Read more
Textilus New Word, Notes and PDF Processor fo...
Textilus is new word-crunching, notes, and PDF processor designed exclusively for the iPad. I haven’t had time to thoroughly check it out yet, but it looks great and early reviews are positive.... Read more
WD My Passport Pro Bus-Powered Thunderbolt RA...
WD’s My Passport Pro RAID solution is powered by an integrated Thunderbolt cable for true portability and speeds as high as 233 MB/s. HighlightsOverviewSpecifications Transfer, Back Up And Edit In... Read more

Jobs Board

*Apple* Solutions Consultant - Apple Inc. (U...
…important role that the ASC serves is that of providing an excellent Apple Customer Experience. Responsibilities include: * Promoting Apple products and solutions 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
*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
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.