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
$98.77
Apple Inc.
-0.26
MSFT
$44.00
Microsoft Corpora
+0.03
GOOG
$589.11
Google Inc.
-1.49

MacTech Search:
Community Search:

Software Updates via MacUpdate

OS X Yosemite Wallpaper 1.0 - Desktop im...
OS X Yosemite Wallpaper is the gorgeous new background image for Apple's upcoming OS X 10.10 Yosemite. This wallpaper is available for all screen resolutions with a source file that measures 5,418... Read more
Acorn 4.4 - Bitmap image editor. (Demo)
Acorn is a new image editor built with one goal in mind - simplicity. Fast, easy, and fluid, Acorn provides the options you'll need without any overhead. Acorn feels right, and won't drain your bank... Read more
Bartender 1.2.20 - Organize your menu ba...
Bartender lets you organize your menu bar apps. Features: Lets you tidy your menu bar apps how you want. See your menu bar apps when you want. Hide the apps you need to run, but do not need to... Read more
TotalFinder 1.6.2 - 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
Vienna 3.0.0 RC 2 :be5265e: - RSS and At...
Vienna is a freeware and Open-Source RSS/Atom newsreader with article storage and management via a SQLite database, written in Objective-C and Cocoa, for the OS X operating system. It provides... Read more
VLC Media Player 2.1.5 - Popular multime...
VLC Media Player is a highly portable multimedia player for various audio and video formats (MPEG-1, MPEG-2, MPEG-4, DivX, MP3, OGG, ...) as well as DVDs, VCDs, and various streaming protocols. It... Read more
Default Folder X 4.6.7 - Enhances Open a...
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
TinkerTool 5.3 - Expanded preference set...
TinkerTool is an application that gives you access to additional preference settings Apple has built into Mac OS X. This allows to activate hidden features in the operating system and in some of the... Read more
Audio Hijack Pro 2.11.0 - Record and enh...
Audio Hijack Pro drastically changes the way you use audio on your computer, giving you the freedom to listen to audio when you want and how you want. Record and enhance any audio with Audio Hijack... Read more
Intermission 1.1.1 - Pause and rewind li...
Intermission allows you to pause and rewind live audio from any application on your Mac. Intermission will buffer up to 3 hours of audio, allowing users to skip through any assortment of audio... Read more

Latest Forum Discussions

See All

To The End Review
To The End Review By Lee Hamlet on July 29th, 2014 Our Rating: :: A VICIOUS CYCLEUniversal App - Designed for iPhone and iPad To The End will test players’ patience, timing, and dedication as they try to navigate all 13 levels in... | Read more »
Traps n’ Gemstones Review
Traps n’ Gemstones Review By Campbell Bird on July 28th, 2014 Our Rating: :: CASTLEVANIA JONESUniversal App - Designed for iPhone and iPad Fight mummies, dig tunnels, and ride a runaway minecart to discover ancient secrets in this... | Read more »
The Phantom PI Mission Apparition Review
The Phantom PI Mission Apparition Review By Jordan Minor on July 28th, 2014 Our Rating: :: GHOSTS BUSTEDUniversal App - Designed for iPhone and iPad The Phantom PI is an exceedingly clever and well-crafted adventure game.   | Read more »
More Stubies Are Coming Your Way in a Ne...
More Stubies Are Coming Your Way in a New Update Posted by Jessica Fisher on July 28th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »
The Great Prank War Review
The Great Prank War Review By Nadia Oxford on July 28th, 2014 Our Rating: :: PRANKING IS SERIOUS BUSINESSUniversal App - Designed for iPhone and iPad Though short, The Great Prank War offers an interesting and fun mix of action and... | Read more »
Marvel Contest of Champions Announced at...
Marvel Contest of Champions Announced at Comic-Con Posted by Jennifer Allen on July 28th, 2014 [ permalink ] Announced over the weekend at San Diego Comic-Con was the fairly exciting looking Marvel Contest of Champions. | Read more »
Teenage Mutant Ninja Turtles Review
Teenage Mutant Ninja Turtles Review By Jennifer Allen on July 28th, 2014 Our Rating: :: DULL SWIPINGUniversal App - Designed for iPhone and iPad The pizza power is weak when it comes to this Teenage Mutant Ninja Turtles game.   | Read more »
Exploration Focused Puzzle Game Beatbudd...
Exploration Focused Puzzle Game Beatbuddy Set to Make Transition from PC to iOS this September Posted by Jennifer Allen on July 28th, 2014 [ permalink ] | Read more »
PlanetHD
PlanetHD By Nadia Oxford on July 28th, 2014 Our Rating: :: SPACE MADNESSUniversal App - Designed for iPhone and iPad PlanetHD will keep players busy for a while, though its unpredictable physics are a handful to deal with.   | Read more »
This Week at 148Apps: July 21-25, 2014
Another Week of Expert App Reviews   At 148Apps, we help you sort through the great ocean of apps to find the ones we think you’ll like and the ones you’ll need. Our top picks become Editor’s Choice, our stamp of approval for apps with that little... | Read more »

Price Scanner via MacPrices.net

Apple updates MacBook Pros with slightly fast...
Apple updated 13″ and 15″ Retina MacBook Pros today with slightly faster Haswell processors. 13″ models now ship with 8GB of RAM standard, while 15″ MacBook Pros ship with 16GB across the board. Most... Read more
Apple drops price on 13″ 2.5GHz MacBook Pro b...
The Apple Store has dropped their price for the 13″ 2.5GHz MacBook Pro by $100 to $1099 including free shipping. Read more
Apple drops prices on refurbished 2013 MacBoo...
The Apple Store has dropped prices on Apple Certified Refurbished 13″ and 15″ 2013 MacBook Pros, with model now available starting at $929. Apple’s one-year warranty is standard, and shipping is free... Read more
iOS 8 and OS X 10.10 To Support DuckDuckGo As...
Writing for Quartz, Dan Frommer reports that Apple’s forthcoming iOS 8 and OS X 10.10 operating systems version updates will allow users to select DuckDuckGo as their default search engine. He notes... Read more
U.K. Hospital Using iPods and iPads To Record...
British news journal GazetteLive’s. Ian McNeal notes that the old “an apple a day keeps the doctor away” proverb is being turned on its head at http://southtees.nhs.uk/hospitals/james-cook/ James... Read more
13-inch 2.5GHz MacBook Pro on sale for $1099,...
Best Buy has the 13″ 2.5GHz MacBook Pro available for $1099.99 on their online store. Choose free shipping or free instant local store pickup (if available). Their price is $100 off MSRP. Price is... Read more
Roundup of Apple refurbished MacBook Pros, th...
The Apple Store has Apple Certified Refurbished 13″ and 15″ MacBook Pros available for up to $400 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free. Their prices... Read more
Record Mac Shipments In Q2/14 Confound Analys...
A Seeking Alpha Trefis commentary notes that Apple’s fiscal Q3 2014 results released July 22, beat market predictions on earnings, although revenues were slightly lower than anticipated. Apple’s Mac’... Read more
Intel To Launch Core M Silicon For Use In Not...
Digitimes’ Monica Chen and Joseph Tsai, report that Intel will launch 14nm-based Core M series processors specifically for use in fanless notebook/tablet 2-in-1 models in Q4 2014, with many models to... Read more
Apple’s 2014 Back to School promotion: $100 g...
 Apple’s 2014 Back to School promotion includes a free $100 App Store Gift Card with the purchase of any new Mac (Mac mini excluded), or a $50 Gift Card with the purchase of an iPad or iPhone,... Read more

Jobs Board

Sr Software Lead Engineer, *Apple* Online S...
Sr Software Lead Engineer, Apple Online Store Publishing Systems Keywords: Company: Apple Job Code: E3PCAK8MgYYkw Location (City or ZIP): Santa Clara Status: Full 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
Sr. Product Leader, *Apple* Store Apps - Ap...
**Job Summary** Imagine what you could do here. At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring 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
*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
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.