TweetFollow Us on Twitter

Mar 99 Challenge

Volume Number: 15 (1999)
Issue Number: 3
Column Tag: Programmer's Challenge

Mar 99 Programmer's Challenge

by Bob Boonstra, Westford, MA

Terrain Traversal

You're on foot with cargo to deliver, and a mountain range between you and your destination. You have no map, nothing except a set of elevation readings provided by a meticulous surveyor that you met at a pub in the last town. And oh, how you hate to climb. Fortunately, this month's Challenge comes to the rescue once again with an efficient and labor saving solution to your problem.

The prototype for the code you should write to solve this Challenge is:

#if defined(__cplusplus)
extern "C" {
#endif

typedef long PointNum, TriangleNum;

typedef struct Point2D {
   double x;                    /* x coordinate */
   double y;                    /* y coordinate */
} Point2D;

typedef struct Point3D {
   PointNum thePointNum;        /* point number */
   Point2D thePoint;            /* x and y coordinates */
   double ht;                   /* point height (z coordinate) */
} Point3D;

typedef struct Triangle {
   TriangleNum theTriangleNum;  /* triangle number */
   PointNum thePoints[3];       /* numbers of points comprising triangle */
} Triangle;

typedef struct Segment {
   TriangleNum theTriangleNum;  /* segment is part of triangle with this number */
   Point2D startingPoint;       /* x,y coordinates of segment start */
   Point2D endingPoint;         /* x,y coordinates of segment end */
} Segment;

long /*numTriangles*/ InitTerrainMap(
   const Point3D thePoints[],   /* input points */
   long numPoints,              /* number of input points */
   Triangle theTriangles[]   /* output triangles constructed from thePoints */
);

long /*numSegments*/ FindAPath(
   const Point3D thePoints[],   /* input points (input to InitTerrainMap) */
   long numPoints,                /* number of input points */
   const Triangle theTriangles[], /* input triangles (from InitTerrainMap) */
   long numTriangles,             /* number of input triangles */
   const Point2D pathStart,       /* input starting point x,y */
   const Point2D pathEnd,         /* input ending point x,y */
   Segment theSegments[]       /* output segments from pathStart to pathEnd */
);

void TermTerrainMap(void);

#if defined(__cplusplus)
}
#endif

Your InitTerrainMap routine is provided a set of points (thePoints), numbered between 1 and numPoints, that define the terrain to be traversed. It is required to divide the terrain into a set of non-overlapping triangles (theTriangles) that will be provided to FindAPath and return the number of triangles created. InitTerrainMap can divide the terrain into any set of triangles, provided that each of thePoints is a member of at least one triangle, and that none of thePoints is strictly inside of any triangle, measured in the x-y plane. Thus, given points (0,1), (1,-1),(-1,1), and (0,0), the triangle formed by (0,1),(1,-1), and (0,0) would be legal, but the triangle formed by (0,1), (1,-1), and (-1,-1) would not be allowed, because (0,0) is strictly inside the latter.

After InitTerrainMap is called, FindAPath will be called an average of 5 times to generate a sequence of theSegments that traverse a route from pathStart to pathEnd. FindAPath is provided the same set of thePoints given to InitTerrainMap, as well as theTriangles produced by InitTerrainMap. Each segment created by FindAPath crosses from a point along one edge of a triangle to another point along an edge of the same triangle. The startingPoint and endingPoint of each segment must be inside or on the boundary of the same triangle (theTriangleNum). The startingPoint of segment 0 must be pathStart, the endingPoint of segment j must be identical to the startingPoint of segment j+1, and the endingPoint of the last segment must be pathEnd. The starting and ending points pathStart and pathEnd will be in the set of thePoints given to InitTerrainMap, and therefore will be vertices in at least one of theTriangles.

After traversal of some number of paths across the terrain, TermTerrainMap will be called, where you should dispose of any dynamically allocated storage.

Unfortunately, the surveyor who provided us with thePoints in our terrain map was not considerate enough to put them on a regular x-y grid. However, he was limited in the amount of storage he had with him on his mapping expedition, so we know that there will be no more than 32K points in any given terrain map.

The winner will be the solution that minimizes the amount of work required to reach the destination, where work is a combination of distance traveled and elevation change. Specifically, the total work is the sum of the work expended on each segment, which is calculated as the distance traveled in the x-y plane, plus ten times the absolute value of the elevation change from the starting and ending points of the segment. In addition, there will be a penalty of 10% for each second of execution time required to compute a solution. There is no storage constraint for this Challenge, except that your solution must run on a 128MB machine.

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

Three Months Ago Winner

The December Word Neighbors Challenge was intended to be a little easier than some recent Challenges, but apparently that was not the case. The Challenge was to find all occurrences of a set of words that occurred within a specified distance of one another in a body of text. The problem had enough subtle complications that none of the four solutions submitted by the deadline completed all of my test cases correctly. The solution by Randy Boring, however, performed correctly with a two-line code change. It also was the most efficient submission and exhibits some interesting techniques, so I chose to publish that solution. The code change, while small, was algorithmically significant, so no prizes or points are going to be awarded for this Challenge. Ludovic Nicolle and Gregory Sadetsky did submit a correct solution, but it was submitted after the deadline. Since they described the code as the "ugliest I have ever written in my entire life", I decided against publishing that solution.

The problem complication that tripped up two of the solutions had to do with treatment of overlapping matches. The problem requirement was to find all occurrences of the search words in the text where the distance between search words is less than a specified amount. No word in the text was allowed to be part of more than one match, and the solutions were required to return the location of the first matching word. The fact that search words need not be immediately adjacent allows the match sequences to overlap. As an example, if the problem is to find a case insensitive and order independent match of the words "a", "b", "c", "d", "e", and "f" within a distance of 4 or fewer intervening words in the following text:

c.2.D.4.b.B.7.B.a.B.D.d.C.14.B.e.f.F.F.A.b.F.a.c.E.d

the correct solution is to return the matches starting at character 0 and character 4, as indicated below:

text:     c.2.D.4.b.B.7.B.a.B.D.d.C.14.B.e.f.F.F.A.b.F.a.c.E.d
match1:   c----b----a---d----e-f
match2:   --D-----B-----C-----F--A-----E

Because of the correctness issues, I did not run the full set of evaluation test cases that I had originally planned. In putting together a collection of digitized text to use for testing, I found my way to the Project Gutenberg site at <http://sailor.gutenberg.org/gutenberg/>, home to a large and growing collection of digitized literature. It has been quite a while since I read "Twenty Thousand Leagues Under The Sea", and it was something of a surprise to rediscover, courtesy of this Challenge, the fact that Captain Nemo doesn't appear until the second half of the book.

Randy's solution is sparsely commented, but there are some interesting features to notice. Noticing that the problem statement called for numerous searches for each set of text, Randy parses the text in his InitText routine, creating a UniqueSummary table of each unique word in the text, and a WordInstance table entry for each word occurrence in the text. To save space, Randy kept pointers back to the text only in the UniqueSummary table, not in the WordInstance table, which cost him the Challenge win. The problem has been corrected in the published solution by adding a word pointer to the WordInstance table, increasing storage requirements, in order to provide the required output. To make word comparisons efficient, Randy hashes each word in the Hash function, and uses that hash to compare words in the FindUniqueWord function.

In searching for a match, Randy divides the code into four cases, based on whether the search is case sensitive or not, and on whether the order of the search words is to be preserved or not. The solution then performs a recursive search of the word instance table to determine if a match exists within the specified distance.

The table below lists, for each of the solutions submitted, the total execution time, the types of errors that turned up in the evaluation, the code and data size, and the programming language. 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 (msec)Memory Alloc.ErrorsCode SizeData SizeLang
Randy Boring (83)262Original*B708834132C++
Ed Agoff334OriginalA32124236C++
Ernst Munter (430)2022NewA114321624C++
Ludovic Nicolle (48) /
Gregory Sadetsky (2) 120964NewLate9676434C
P.B. -NewCRASH5176539C++

A - problems with overlapping matches
B - incorrect return values before correction; correction required revised memory allocation

Top Contestants

Listed here are the Top Contestants for the Programmer's Challenge, including everyone who has accumulated 20 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.

  1. Munter, Ernst 204
  2. Saxton, Tom 79
  3. Boring, Randy 56
  4. Mallett, Jeff 50
  5. Rieken, Willeke 47
  6. Maurer, Sebastian 40
  7. Heithcock, JG 37
  8. Cooper, Greg 34
  9. Murphy, ACC 34
  10. Lewis, Peter 31
  11. Nicolle, Ludovic 27
  12. Brown, Pat 20
  13. Day, Mark 20
  14. Higgins, Charles 20
  15. Hostetter, Mat 20

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 place20 points
2nd place10 points
3rd place7 points
4th place4 points
5th place2 points
finding bug2 points
suggesting Challenge2 points

Here is the corrected version of Randy's Word Neighbors solution:

Nearby.cp
Copyright © 1998 Randy Boring

// Corrections by JRB marked by the following define
#define JRB_CORRECTION 1

#include <MacTypes.h>
#include "Nearby.h"

#define SINGLEWORDALLOWED   0   // can't find a _nearby_ single word!
#define DEBUG   0
#if DEBUG
#include <iostream>
using namespace std;
#endif

WordInstance
typedef struct WordInstance {
   unsigned long   mark:1;      // has been used in a found set
   unsigned long   usi:18;      // index of our unique summary
      // a quarter million unique words should be enough
   unsigned long   hint:13;     // partial summary
#if JRB_CORRECTION
   char *word;
#endif
   } Inst, StackElem, *Stack, *Set;

#define kHintSize   13       // only the presence of upper or lower
#define kHintMask   0x1FFF   // p umlh sirn aote are in the hint
#define isMarked(w)   ((w).mark)
#define Mark(wp)   (wp->mark = 1)
#define UnMark(wp)   (wp->mark = 0)
#define WordsAreExactlyEqual(w1,w2)   ((w1).usi == (w2).usi)

UniqueSummary
typedef struct UniqueSummary {
   unsigned long         unused:1;
   unsigned long         lowerNumbers:5;
   unsigned long         lowerLetters:26;
   unsigned long         unused2:1;
   unsigned long         upperNumbers:5;
   unsigned long         upperLetters:26;
   struct UniqueSummary   *next;   // of same hash
   char               *word;
   } US, *HashList;
#define USIndex(w)         (gUS - w)
#define USfromIndex(i)      (&gUS[-(i)])
#if !JRB_CORRECTION
#define TextPosition(ip)   (USfromIndex((ip)->usi)->word - gText)
#else
#define TextPosition(ip)   ((ip)->word - gText)
#endif

#define MAXHASH         0x00002000L   // 8K entries of 4 bytes = 32K
#define MAXSEARCHWORDS   100
#define MAXSTACK      MAXSEARCHWORDS

static HashList gHashTable[MAXHASH];
static long gTotalInstances;

static US *gUS, *gUSLast;
static Inst *gInstp, *gInstpLast;
static long gDist;
static char *gText;
static long gTextLength;

#define kX   (0x100)     // illegal input
#define kD   (0x80)      // delimiter
#define kN   (0x40)      // numeric
#define kU   (0x20)      // upper case (or 5-9)
#define kM   (0x1F)      // mask of bit index within category

#define NotDelimType(typ)   (((typ) & (kX | kD)) == 0)
#define NotDelim(c)         (((gCharType[c]) & (kX | kD)) == 0)
#define IsDelimType(typ)   (((typ) & (kX | kD)) != 0)
#define IsDelim(c)         (((gCharType[c]) & (kX | kD)) != 0)

gCharType
static /* const */ short gCharType[
#if DEBUG
   256
#else
   128
#endif
   ] = {
   /* these aren't legal input (0x00-0x1F), except tab, lf, cr */
   kX,kX,kX,kX,kX,kX,kX,kX, kX,kD,kD,kX,kX,kD,kX,kX,
   kX,kX,kX,kX,kX,kX,kX,kX, kX,kX,kX,kX,kX,kX,kX,kX,
   /* begin rest of legal input with 0x20 (space) */
   kD,kD,kD,kD,kD,kD,kD,kD, kD,kD,kD,kD,kD,kD,kD,kD,
   0x40,0x41,0x42,0x43,0x44,   // 'lower' digits 0-4
   0x60,0x61,0x62,0x63,0x64,   // 'upper' digits 5-9
   kD,kD,kD,kD,kD,kD,
   kD,      // ASCII 0x40
   
   0x23,   // A=3   etoanris hlmup are renumbered as most common
   0x2D,   // B   01234567 89ABC
   0x2E,   // C
   0x2F,   // D
   0x20,   // E=0
   0x30,   // F
   0x31,   // G
   0x28,   // H=8
   0x26,   // I=6
   0x32,   // J
   0x33,   // K
   0x29,   // L=9
   0x2A,   // M=A
   0x24,   // N=4
   0x22,   // O=2
   0x2C,   // P=C
   0x34,   // Q
   0x25,   // R=5
   0x27,   // S=7
   0x21,   // T=1
   0x2B,   // U=B
   0x35,   // V
   0x36,   // W
   0x37,   // X
   0x38,   // Y
   0x39,   // Z   ASCII 0x5A
   
   kD,kD,kD,kD,kD,
   kD,      // ASCII 0x60
   
   0x03,   // a=3   etoanris hlmup are renumbered as most common
   0x0D,   // b   01234567 89ABC
   0x0E,   // c
   0x0F,   // d
   0x00,   // e=0
   0x10,   // f
   0x11,   // g
   0x08,   // h=8
   0x06,   // i=6
   0x12,   // j
   0x13,   // k
   0x09,   // l=9
   0x0A,   // m=A
   0x04,   // n=4
   0x02,   // o=2
   0x0C,   // p=C
   0x14,   // q
   0x05,   // r=5
   0x07,   // s=7
   0x01,   // t=1
   0x0B,   // u=B
   0x15,   // v
   0x16,   // w
   0x17,   // x
   0x18,   // y
   0x19,   // z   ASCII 0x7A
   
   kD,kD,kD,kD,   // ASCII 0x7E is last legal delimiter
   kX      // ASCII 0x7F
#if DEBUG
   ,
   /* these aren't legal input! 0x80 - 0xFF */
   kX,kX,kX,kX,kX,kX,kX,kX, kX,kX,kX,kX,kX,kX,kX,kX,
   kX,kX,kX,kX,kX,kX,kX,kX, kX,kX,kX,kX,kX,kX,kX,kX,
   kX,kX,kX,kX,kX,kX,kX,kX, kX,kX,kX,kX,kX,kX,kX,kX,
   kX,kX,kX,kX,kX,kX,kX,kX, kX,kX,kX,kX,kX,kX,kX,kX,
   kX,kX,kX,kX,kX,kX,kX,kX, kX,kX,kX,kX,kX,kX,kX,kX,
   kX,kX,kX,kX,kX,kX,kX,kX, kX,kX,kX,kX,kX,kX,kX,kX,
   kX,kX,kX,kX,kX,kX,kX,kX, kX,kX,kX,kX,kX,kX,kX,kX,
   kX,kX,kX,kX,kX,kX,kX,kX, kX,kX,kX,kX,kX,kX,kX,kX
#endif
   };

static StackElem gStack[MAXSTACK];

#if DEBUG
static long gUniqueHashEntries;

static int alreadyAllocated = true;   // ensures we init it at first
#endif

//----//----//----//----//----//----
static void
FreeStack(Stack *ioStack)
{
#if DEBUG
   *ioStack = nil;
   alreadyAllocated = false;
#else
#pragma unused (ioStack)
#endif
}

//----//----//----//----//----//----
static Stack
NewStack(void)
{
#if DEBUG
   if (alreadyAllocated)
      DebugStr("\p already allocated!");
   else
      alreadyAllocated = true;
#endif
   return gStack;   // only works once, of course
}

//----//----//----//----//----//----
static void
InitStack(void)
{
#if DEBUG
   alreadyAllocated = false;
#endif
}

//----//----//----//----//----//----
static /* inline */ void
StackPush(Stack *ioStack, StackElem e)
{
#if DEBUG
   if ((*ioStack - gStack) >= MAXSTACK)
      DebugStr("\p blew stack up!");
   else
#endif
//   *ioStack++ = e;
   **ioStack = e;
   (*ioStack)++;
}

//----//----//----//----//----//----
// Return the element at the top of the stack and pop it off
static /* inline */ StackElem
StackPopTop(Stack *ioStack)
{
#if DEBUG
   if (*ioStack <= gStack)
      {
      DebugStr("\p poked bottom of stack!");
      return **ioStack;   // no good choice here
      }
   else
#endif
   return *(-*ioStack);
}

//----//----//----//----//----//----
static /* inline */ int
StackIsEmpty(const Stack inStack)
{
   return (inStack == gStack);
}

//----//----//----//----//----//----
static /* inline */ int
SetIsSizeOne(const Set inSet)
{
   return (inSet == gStack + 1);
}

//----//----//----//----//----//----
#define SetAdd(s,w)   StackPush(s,w)

//----//----//----//----//----//----
static void
SetRemove(Set *ioSet, Inst *toRemove)
{
   // remove top element, and overwrite toRemove element
   *toRemove = StackPopTop(ioSet);
}

Hash
// Generate a case-insensitive hash from the characters of 
//   the null-terminated string
//   h1 is sum of w[i-1] * w[i] where w[-1] = 1
//   h2 is simple sum of w[i]
//   result puts h2 in upper 6 bits of a 13 bit word
static long
Hash(char *w, char **outDelim)
{
   long h1 = 0, h2 = 0, lastNum = 1, thisNum;
   char cw = *w;   // assumes first char not null
   do   {
      if (cw >= 'a')      // is lowercase
         thisNum = cw - ('a' - 1);
      else if (cw >= 'A')   // is uppercase
         thisNum = cw - ('A' - 1);
      else            // is digit
         thisNum = cw;
      cw = *++w;   // the next char
      h1 += lastNum * thisNum;
      h2 += thisNum;
      lastNum = thisNum;
      } while (cw);
   *outDelim = w;
   return (h1 + (h2 << 7)) & 0x00001FFF;
}

//----//----//----//----//----//----
// Returns whether the hash table entry at h is valid
static /* inline */ int
ValidHashEntry(long h)
{
   return (gHashTable[h] != nil);
}

//----//----//----//----//----//----
static void
HashAdd(US *inUSp, long h)
{
   if (ValidHashEntry(h))
      {   // append to existing hash table list
      inUSp->next = gHashTable[h];
      gHashTable[h] = inUSp;
      }
   else {   // add new hash table entry
      gHashTable[h] = inUSp;
#if DEBUG
      gUniqueHashEntries++;
#endif
      }
}

//----//----//----//----//----//----
static void
InitHash(void)
{
   double fr0 = 0.0, fr1 = 0.0, fr2 = 0.0, fr3 = 0.0;
   long count = sizeof(gHashTable) >> 5;
   double *p = (double *) gHashTable;
   do   {
      -count;
      *p = fr0;
      *(p + 1) = fr1;
      *(p + 2) = fr2;
      *(p + 3) = fr3;
      p += 4;
      } while (count);
#if DEBUG
   gUniqueHashEntries = 0;
#endif
}

#if DEBUG
static void
PrintHashTable(void)
{
   long i;
   for (i = 0; i < MAXHASH; i++)
      if (ValidHashEntry(i))
         {
         cout << "h = " << i;
         HashList e = gHashTable[i];
         long ct = 0;
         do   {
            cout << ", " << e->word;
            e = e->next;
            ++ct;
            } while (e);
         cout << endl << "  ct = " << ct << endl;
         }
}
#endif

EqualStrings
// Return true if the strings are exactly equal
// This is like strcmp (ignoring less or greater)
// Assumes first char of w is not null
static int
EqualStrings(char *w, char *u)
{
   char cw = *w, cu = *u;
   do   {
      if (cw != cu)
         return 0;
      cw = *++w;
      cu = *++u;
      } while (cw);
   return 1;
}

EqualStringsNCS
// Return true if the strings are equal, ignoring case
// Assumes first char of w is not null
static int
EqualStringsNCS(char *w, char *u)
{
   char cw = *w, cu = *u;
   do   {
      if (cw >= 'a')       // cw is lowercase
         cw -= ('a' - 'A');   // uppercase it
      if (cu >= 'a')       // cu is lowercase
         cu -= ('a' - 'A');   // uppercase it
      if (cw != cu)
         return 0;
      cw = *++w;
      cu = *++u;
      } while (cw);
   return 1;
}

CreateSummary
// Record the presence of each kind of alphanumeric char in
//   the word
// And point to the actual word for final exact check
static void
CreateSummary(char *w, US *usp)
{
   long lowN = 0, lowL = 0, upN = 0, upL = 0;
   short cwtype;
   char cw = *w;
   cwtype = gCharType[cw];
   usp->word = w;
   do   {
      long presenceBit;
      int isUpper, isNumber;   // NOT mutually exclusive
      cw = *++w;
      presenceBit = 0x0001 << (cwtype & kM);
      isUpper = cwtype & kU;
      isNumber = cwtype & kN;
      cwtype = gCharType[cw];
      if (isUpper)   // upper case letter or high number
         if (isNumber)   // number
            upN |= presenceBit;
         else
            upL |= presenceBit;
      else if (isNumber)
         lowN |= presenceBit;
      else
         lowL |= presenceBit;
      } while (NotDelimType(cwtype));
   
   usp->unused = 0;
   usp->upperNumbers = upN;
   usp->upperLetters = upL;
   usp->unused2 = 0;
   usp->lowerNumbers = lowN;
   usp->lowerLetters = lowL;
   usp->next = nil;
}

FindUniqueWord
// Return the UniqueWordSummary for the word, w, if any
static US *
FindUniqueWord(char *w, long *outHash, char **outDelim)
{
   unsigned short h = Hash(w, outDelim);
   US *usp = gHashTable[h];
   *outHash = h;
   if (!ValidHashEntry(h))
      return nil;
   while (usp && !EqualStrings(w, usp->word))
      usp = usp->next;
   return usp;
}

AddWord
// Find word w in hash table (or add it, if unique) and 
// Build instance pointer and add it
// Return ptr to next char after word ends (its delimiter)
static char *   // next character after word
AddWord(char *w)
{
   long h;
   char *afterWord;
   US *theUSp = FindUniqueWord(w, &h, &afterWord);
   if (!theUSp)   // new unique word, add it
      {
      theUSp = gUSLast;
      -gUSLast;
#if DEBUG
      if ((Ptr)theUSp < (Ptr)gInstpLast)
         DebugStr("\p dictionary ran into the index!");
#endif
      CreateSummary(w, theUSp);
      HashAdd(theUSp, h);
      }
   Inst theInst;
   theInst.mark = 0;
   theInst.usi = USIndex(theUSp);
   theInst.hint = (theUSp->upperLetters | theUSp->lowerLetters)
         & kHintMask;
#if JRB_CORRECTION
   theInst.word = w;
#endif
   *gInstpLast++ = theInst;
   return afterWord;
}

InitText
// Index each word in the text
static void
InitText(char *text, long length)
{
   char *stop = text + length;
   // skip illegals and delimiters
   while (IsDelim(*text))
      ++text;
   while (text < stop)
      {
      text = AddWord(text);
      while (IsDelim(*text) && text < stop)
         ++text;
      }
}

FixTextAndCountInsts
// Return count of word instances and length of input text
// Null-terminate each word instance in the text
//   Allowed since 'text' is not const char *
//   Helpful since it simplifies all word ending detection
static long
FixTextAndCountInsts(char *text, long *outLength)
{
   long ct = 0;
   char *textStart = text;
                  // find beginning of first word
   while (IsDelim(*text))
      ++text;
   while (*text)
      {
                  // find end of word
      while (NotDelim(*text))
         ++text;
      ++ct;         // count the word
      if (*text == 0)
         break;
      *text++ = 0;   // null-terminate the word
                  // find beginning of next word
      while (*text && IsDelim(*text))
         ++text;
      }
   *outLength = text - textStart;
   return ct;
}

//----//----//----//----//----//----
// A Set is implemented as a Stack (for now)
#define FillSet(s,w,n)   FillStackBackwards(s,w,n)
#define NewSet()      NewStack()
#define FreeSet(s)      FreeStack(s)

Initialize
pascal void Initialize(
   char *text,                /* NULL terminated text to be searched */
   long distance,             /* max distance between nearby words */
   void *privateStorage,      /* private storage for your use */
   long storageBytes          /* number of bytes in privateStorage */
   )
{
   InitHash();
   InitStack();
   gTotalInstances = FixTextAndCountInsts(text, &gTextLength);
   
   /* from gTotalInstances we can guess what strategy to use */
   
   // InitInstances (left to right from beginning, 
postincrementing)
   gInstpLast = (Inst *) privateStorage;
   gInstp = gInstpLast;
   // InitUniqueSummaries (right to left from end, postdecrementing)
   // masking with 0xFFFFFFFC gives us 4-Byte alignment
   gUS = ((US *) (((unsigned long) privateStorage + storageBytes) & 0xFFFFFFFC)) - 1;
   gUSLast = gUS;
   InitText(text, gTextLength);
   gText = text;
   gDist = distance + 1;   // distance allowed is 0 through distance
#if DEBUG
   if (gTotalInstances != gInstpLast - gInstp)
      DebugStr("\p gTotalInstances != gInstpLast - gInstp");
   PrintHashTable();
   cout << "# of words total in input text:
                             " << gTotalInstances << endl;
   cout << "# of unique words in input text:
                             " << gUS - gUSLast << endl;
   cout << "# of hash table entries used:   
                             = " << gUniqueHashEntries << endl;
#endif
}

FillStackBackwards
static void
FillStackBackwards(Stack *ioStack, char *words[], long numWords)
{
   for (int i = numWords - 1; i >= 0; -i)
      {
      long dummy;   // we don't need the returned hash value
      char *dummy2;
      Inst elem;
      US *wUSp;
      wUSp = FindUniqueWord(words[i], &dummy, &dummy2);
#if DEBUG
      if (nil == wUSp)
         {
         DebugStr("\p find word not in text!");
         continue;
         }
#endif
      elem.mark = 0;
      elem.usi = USIndex(wUSp);
      elem.hint = (wUSp->upperLetters | wUSp->lowerLetters)
         & kHintMask;
      StackPush(ioStack, elem);
      }
}

WordsAreEqualExceptCase
// Return true if the words are same except for case
//   1. hints of Inst will be same if words same 
//   2. summaries will have same bitfields of char presence
//      but for case (OR upper and lower fields before compare)
//   3. words will be letter-for-letter the same (ignoring case)
static int
WordsAreEqualExceptCase(Inst w1, Inst w2)
{
   if (w1.hint != w2.hint)
      return 0;   // they have different common letters
   US *u1 = USfromIndex(w1.usi), *u2 = USfromIndex(w2.usi);
   unsigned long u1letters = u1->lowerLetters | u1-
                                >upperLetters;
   unsigned long u2letters = u2->lowerLetters | u2-
                                >upperLetters;
   if (u1letters != u2letters)
      return 0;
   if ((u1->lowerLetters | u1->upperLetters)
      != (u2->lowerLetters | u2->upperLetters))
      return 0;
   if (u1->lowerNumbers != u2->lowerNumbers)
      return 0;
   if (u1->upperNumbers != u2->upperNumbers)
      return 0;
   return (EqualStringsNCS(u1->word, u2->word));
}

FindInSetCS
// Find the set element (a search word modelled as an Inst)
//   that is the same as inst, case-sensitive
static Inst *
FindInSetCS(Set inSet, Inst inst)
{
   -inSet;
   do   {
      if (WordsAreExactlyEqual(*inSet, inst))
         return inSet;
      } while (inSet->gStack);
   return nil;
}

FindInSetNCS
// Find the set element (a search word modelled as an Inst)
//   that is the same as inst, ignoring case
static Inst *
FindInSetNCS(Set inSet, Inst inst)
{
   -inSet;
   do   {
      if (WordsAreExactlyEqual(*inSet, inst) ||
            WordsAreEqualExceptCase(*inSet, inst))
         return inSet;
      } while (inSet->gStack);
   return nil;
}

FindNextIOMatchCS
static int
FindNextIOMatchCS(Inst *currInstp, Stack st, long maxDist)
{
   long currDist = maxDist;
   Inst w = StackPopTop(&st);
   int atBottom = StackIsEmpty(st);
   
   do   {
      Inst currW = *currInstp;
      if (isMarked(currW))
         goto nextInst;
      if (WordsAreExactlyEqual(currW, w)) // this word matches!
         if (atBottom)
            {   // we found a set!
            Mark(currInstp);
            StackPush(&st, w);   // restore our stack item
            return 1;
            }
         else // recurse to see if we can finish finding a set
         if (FindNextIOMatchCS(currInstp + 1, st, maxDist))
            {   // set found by recursion
            Mark(currInstp);
            StackPush(&st, w);   // restore our stack item
            return 1;
            }
         else {   // no set found by recursion
            StackPush(&st, w);   // restore our stack item
            return 0;
            }
   nextInst:
      -currDist;
      ++currInstp;
      } while (currDist);
   
   // no matching word found within max distance
   StackPush(&st, w);   // restore our stack item
   return 0;
}

FindIOMatchesCS
static long
FindIOMatchesCS(Stack st, long maxToFind, long matchPositions[])
{
   Inst *currInstp;
   Inst *lastInstp = gInstpLast;
   Inst w = StackPopTop(&st);
   long count = 0;
#if SINGLEWORDALLOWED
   int atBottom = StackIsEmpty(st);
#endif
   
   for (currInstp = gInstp; currInstp < lastInstp; ++currInstp)
      if (isMarked(*currInstp))   // already used in a found set
         UnMark(currInstp);
      else {
         if (WordsAreExactlyEqual(*currInstp, w))
            {
#if SINGLEWORDALLOWED
            if (atBottom) // only one search word!
               matchPositions[count++] = TextPosition(currInstp);
            else // recurse
#endif
            if (FindNextIOMatchCS(currInstp + 1, st, gDist))
               matchPositions[count++] = TextPosition(currInstp);
            if (count == maxToFind)
               break;
            }
         }
   return count;
}

FindNextIOMatchNCS
static int
FindNextIOMatchNCS(Inst *currInstp, Stack st, long maxDist)
{
   long currDist = maxDist;
   Inst w = StackPopTop(&st);
   int atBottom = StackIsEmpty(st);
   
   do   {
      Inst currW = *currInstp;
      if (isMarked(currW))
         goto nextInst;
      if (WordsAreExactlyEqual(currW, w) ||
            WordsAreEqualExceptCase(currW, w))
            // this word matches!
         if (atBottom)
            {   // we found a set!
            Mark(currInstp);
            StackPush(&st, w);   // restore our stack item
            return 1;
            }
         else // recurse to see if we can finish finding a set
         if (FindNextIOMatchCS(currInstp + 1, st, maxDist))
            {   // set found by recursion
            Mark(currInstp);
            StackPush(&st, w);   // restore our stack item
            return 1;
            }
         else {   // no set found by recursion
            StackPush(&st, w);   // restore our stack item
            return 0;
            }
   nextInst:
      -currDist;
      ++currInstp;
      } while (currDist);
   
   // no matching word found within max distance
   StackPush(&st, w);   // restore our stack item
   return 0;
}

FindIOMatchesNCS
static long
FindIOMatchesNCS(Stack st, long maxToFind, long matchPositions[])
{
   Inst *currInstp;
   Inst *lastInstp = gInstpLast;
   Inst w = StackPopTop(&st);
   long count = 0;
#if SINGLEWORDALLOWED
   int atBottom = StackIsEmpty(st);
#endif
   
   for (currInstp = gInstp; currInstp < lastInstp; ++currInstp)
      if (isMarked(*currInstp))   // already used in a found set
         UnMark(currInstp);
      else {
         if (WordsAreExactlyEqual(*currInstp, w) ||
            WordsAreEqualExceptCase(*currInstp, w))
            {
#if SINGLEWORDALLOWED
            if (atBottom) // only one search word!
               matchPositions[count++] = TextPosition(currInstp);
            else // recurse
#endif
            if (FindNextIOMatchNCS(currInstp + 1, st, gDist))
               matchPositions[count++] = TextPosition(currInstp);
            if (count == maxToFind)
               break;
            }
         }
   return count;
}

FindNearbyInOrder
static long
FindNearbyInOrder(            /* return number of matches found */
   char *words[],             /* words to find in text */
   long numWords,             /* number of words */
   Boolean caseSensitive,     /* true if match is case sensitive */
   long matchPositions[],     /* position in text of first word in match */
   long maxMatches            /* max number of matches to return */
   )
{
   Stack st = NewStack();
   long found = 0;
   FillStackBackwards(&st, words, numWords);
   if (caseSensitive)
      found = FindIOMatchesCS(st, maxMatches, matchPositions);
   else
      found = FindIOMatchesNCS(st, maxMatches, matchPositions);
   FreeStack(&st);
   return found;
}

FindNextAOMatchCS
static int
FindNextAOMatchCS(Inst *currInstp, Set st, long maxDist)
{
   long currDist = maxDist;
   int atBottom = SetIsSizeOne(st);
   
   do   {
      Inst currW = *currInstp;
      if (isMarked(currW))
         goto nextInst;
      Inst *saveInstp = FindInSetCS(st, currW);
      if (saveInstp != nil)   // found a match
         {
         Inst saveInst = *saveInstp;   // only needed in NCS
         SetRemove(&st, saveInstp);
         if (atBottom) // last search word
            {   // we found a set!
            Mark(currInstp);
            SetAdd(&st, saveInst);   // restore our set item
            return 1;
            }
         else // recurse to see if we can finish finding a set
         if (FindNextAOMatchCS(currInstp + 1, st, maxDist))
            {   // set found by recursion
            Mark(currInstp);
            SetAdd(&st, saveInst);   // restore our set item
            return 1;
            }
         //else    // no set found by recursion
         SetAdd(&st, saveInst);
         }
   nextInst:
      -currDist;
      ++currInstp;
      } while (currDist);
   
   // no matching word found within max distance
   return 0;
}

FindAOMatchesCS
static long
FindAOMatchesCS(Set st, long maxToFind, long matchPositions[])
{
   long count = 0;
   Inst *currInstp;
   Inst *lastInstp = gInstpLast;
#if SINGLEWORDALLOWED
   int atBottom = SetIsSizeOne(st);
#endif
   for (currInstp = gInstp; currInstp < lastInstp; ++currInstp)
      if (isMarked(*currInstp))   // already used in a found set
         UnMark(currInstp);
      else {
         Inst *saveInstp = FindInSetCS(st, *currInstp);
         if (saveInstp != nil)   // found a match
            {
            Inst saveInst = *saveInstp;
            SetRemove(&st, saveInstp);
#if SINGLEWORDALLOWED
            if (atBottom) // only one search word!
               matchPositions[count++] = TextPosition(currInstp);
            else // recurse
#endif
            if (FindNextAOMatchCS(currInstp + 1, st, gDist))
               matchPositions[count++] = TextPosition(currInstp);
            SetAdd(&st, saveInst);
            if (count == maxToFind)
               break;
            }
         }
   return count;
}

FindNextAOMatchNCS
static int
FindNextAOMatchNCS(Inst *currInstp, Stack st, 
      long maxDist)
{
   long currDist = maxDist;
   int atBottom = SetIsSizeOne(st);
   
   do   {
      Inst currW = *currInstp;
      if (isMarked(currW))
         goto nextInst;
      Inst *saveInstp = FindInSetNCS(st, currW);
      if (saveInstp != nil)   // found a match
         {
         Inst saveInst = *saveInstp;   // only needed in NCS
         SetRemove(&st, saveInstp);
         if (atBottom) // last search word
            {   // we found a set!
            Mark(currInstp);
            SetAdd(&st, saveInst);   // restore our set item
            return 1;
            }
         else // recurse to see if we can finish finding a set
         if (FindNextAOMatchNCS(currInstp + 1, st, maxDist))
            {   // set found by recursion
            Mark(currInstp);
            SetAdd(&st, saveInst);   // restore our set item
            return 1;
            }
         //else    // no set found by recursion
         SetAdd(&st, saveInst);
         }
   nextInst:
      -currDist;
      ++currInstp;
      } while (currDist);
   
   // no matching word found within max distance
   return 0;
}

FindAOMatchesNCS
static long
FindAOMatchesNCS(Set st, long maxToFind, long matchPositions[])
{
   long count = 0;
   Inst *currInstp;
   Inst *lastInstp = gInstpLast;
#if SINGLEWORDALLOWED
   int atBottom = SetIsSizeOne(st);
#endif
   for (currInstp = gInstp; currInstp < lastInstp; ++currInstp)
      if (isMarked(*currInstp))   // already used in a found set
         UnMark(currInstp);
      else {
         Inst *saveInstp = FindInSetNCS(st, *currInstp);
         if (saveInstp != nil)   // found a match
            {
            Inst saveInst = *saveInstp;
            SetRemove(&st, saveInstp);
#if SINGLEWORDALLOWED
            if (atBottom) // only one search word!
               matchPositions[count++] = TextPosition(currInstp);
            else // recurse
#endif
            if (FindNextAOMatchNCS(currInstp + 1, st, gDist))
               matchPositions[count++] = TextPosition(currInstp);
            SetAdd(&st, saveInst);
            if (count == maxToFind)
               break;
            }
         }
   return count;
}

FindNearbyAnyOrder
static long
FindNearbyAnyOrder(            /* return number of matches found */
   char *words[],              /* words to find in text */
   long numWords,              /* number of words */
   Boolean caseSensitive,      /* true if match is case sensitive */
   long matchPositions[],      /* position in text of first word in match */
   long maxMatches             /* max number of matches to return */
   )
{
   Set st = NewSet();
   long found = 0;
   FillSet(&st, words, numWords);
   if (caseSensitive)
      found =  FindAOMatchesCS(st, maxMatches, matchPositions);
   else
      found =  FindAOMatchesNCS(st, maxMatches, matchPositions);
   FreeSet(&st);
   return found;
}

FindNearby
pascal long FindNearby(      /* return number of matches found */
   char *words[],            /* words to find in text */
   long numWords,            /* number of words */
   Boolean caseSensitive,    /* true if match is case sensitive */
   Boolean preserveOrder,    /* true if words must be found in order */
   long matchPositions[],    /* position in text of first word in match */
   long maxMatches           /* max number of matches to return */
   )
{
   if (preserveOrder)
      return FindNearbyInOrder(words, numWords, caseSensitive, 
            matchPositions, maxMatches);
   else
      return FindNearbyAnyOrder(words, numWords, caseSensitive, 
            matchPositions, maxMatches);
}
 

Community Search:
MacTech Search:

Software Updates via MacUpdate

OmniOutliner Pro 4.2 - Pro version of th...
OmniOutliner Pro is a flexible program for creating, collecting, and organizing information. Give your creativity a kick start by using an application that's actually designed to help you think. It's... Read more
VLC Media Player 2.2.1 - 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
Nisus Writer Pro 2.1.1 - Multilingual wo...
Nisus Writer Pro is a powerful multilingual word processor, similar to its entry level products, but brings new features such as table of contents, indexing, bookmarks, widow and orphan control,... Read more
Tinderbox 6.2.0 - Store and organize you...
Tinderbox is a personal content management assistant. It stores your notes, ideas, and plans. It can help you organize and understand them. And Tinderbox helps you share ideas through Web journals... Read more
OmniOutliner 4.2 - Organize your ideas,...
OmniOutliner is a flexible program for creating, collecting, and organizing information. Give your creativity a kick start by using an application that's actually designed to help you think. It's... Read more
Things 2.5.4 - Elegant personal task man...
Things is a task management solution that helps to organize your tasks in an elegant and intuitive way. Things combines powerful features with simplicity through the use of tags and its intelligent... Read more
NeoOffice 2014.10 - Mac-tailored, OpenOf...
NeoOffice is a complete office suite for OS X. With NeoOffice, users can view, edit, and save OpenOffice documents, PDF files, and most Microsoft Word, Excel, and PowerPoint documents. NeoOffice 3.x... Read more
iPhoto Library Manager 4.2 - Manage mult...
iPhoto Library Manager allows you to organize your photos among multiple iPhoto libraries, rather than having to store all of your photos in one giant library. You can browse the photos in all your... Read more
Web Snapper 3.3.8 - Capture entire Web p...
Web Snapper lets you capture Web pages exactly as they appear in your browser. You can send them to a file as images or vector-based, multi-page PDFs. It captures the whole Web page - eliminating the... Read more
TeamViewer 10.0.41404 - Establish remote...
TeamViewer gives you remote control of any computer or Mac over the Internet within seconds, or can be used for online meetings. Find out why more than 200 million users trust TeamViewer! Free for... Read more

Chainsaw Warrior: Lords of the Night has...
It's time to put the Darkness back in its place now that Chainsaw Warrior: Lords of the Night has officially made it to iOS. | Read more »
A World of Ice and Fire Lets You Stalk 2...
George R. R. Martin’s A World of Ice and Fire, by Random House, is a mobile guide to the epic series. The new update gives you the Journeys map feture that will let you track the movements of 25 different characters. But don't worry, you can protect... | Read more »
Gameloft Announces Battle Odyssey, a New...
Battle Odyssey, Gameloft's newest puzzle RPG, is coming to the App Store next week. Set in the world of Pondera, you will need to control the power of the elements to defend the world from evil. You'll be able to entlist over 500 allies to aid you... | Read more »
Fusion - HDR Camera (Photography)
Fusion - HDR Camera 1.0.0 Device: iOS Universal Category: Photography Price: $1.99, Version: 1.0.0 (iTunes) Description: Fusion creates HDR (high dynamic range) photos by capturing different exposures and then combining them into one... | Read more »
Sago Mini Toolbox (Education)
Sago Mini Toolbox 1.1 Device: iOS Universal Category: Education Price: $2.99, Version: 1.1 (iTunes) Description: Come build with the Sago Mini friends! Use a wrench, try a saw, or hammer some nails. From sewing hand puppets to... | Read more »
You Should Probably Grab Hitman GO While...
Hitman GO is a surprisingly cool (yet also incredibly drastic) departure from the Hitman series. It's well worth playing for any puzzle game fans out there, and at the moment you can get your hands - or garrotte if you will - on it for a mere $0.99... | Read more »
IFTTT is Bringing Do Button and Do Note...
IFTTT has announced Do Button and Do Note for the Apple Watch. Do Button lets you make your own personalized button that can connect to things like your Google Drive, control the temperature in your home with Nest Thermostat, or turn the lights on... | Read more »
How Many Days, Hours, and Minutes Are Le...
Countdown, by Yves Tscherry, is now available on the App Store. The app keeps track of countdowns to your favorite things such as someones birthday or days till the New Year. You can display the time in seconds, minutes, hours, days, weeks, months,... | Read more »
The All-New Misfit 2.0 App is Available...
Misfit has just given their app a complete overhaul. Misfit 2.0 now has a brand new interface with a sleek design and is easier to navigate. You'll be able to sync your Misfit device and look up health and fitness information faster than ever before... | Read more »
Halo: Spartan Strike (Games)
Halo: Spartan Strike 1.0 Device: iOS Universal Category: Games Price: $5.99, Version: 1.0 (iTunes) Description: Delve into 30 challenging missions through cities and jungles using a devastating arsenal of weapons, abilities and... | Read more »

Price Scanner via MacPrices.net

TigerText Introduces First Secure Enterprise...
TigerText, a provider of secure, real-time messaging for the enterprise, has announced the launch of TigerText for the Apple Watch. TigerText for the Apple Watch enables users to securely send and... Read more
The Conservation Fund Partners with Apple To...
The Conservation Fund has announced that it will partner with Apple to help protect working forests in the United States. The Apple initiative will conserve more than 36,000 acres of working... Read more
Clearance 13-inch 2.6GHz Retina MacBook Pro a...
B&H Photo has clearance 2014 13″ 2.6GHz/128GB Retina MacBook Pros now available for $1099, or $200 off original MSRP. Shipping is free, and B&H charges NY sales tax only. Read more
Apple refurbished 2014 13-inch Retina MacBook...
The Apple Store has Apple Certified Refurbished 2014 13″ Retina MacBook Pros available for up to $400 off original MSRP, starting at $979. An Apple one-year warranty is included with each model, and... Read more
iMacs on sale for up to $205 off MSRP, NY tax...
B&H Photo has 21″ and 27″ iMacs on sale for up to $205 off MSRP including free shipping plus NY sales tax only: - 21″ 1.4GHz iMac: $1019 $80 off - 21″ 2.7GHz iMac: $1189 $110 off - 21″ 2.9GHz... Read more
Sale! 16GB iPhone 5S for $1 with service
Best Buy is offering 16GB iPhone 5Ss for $1.00 with 2-year activation at a participating cellular provider. Choose free home shipping and activation, or buy online and activate during in-store pickup... Read more
Apple refurbished 2014 MacBook Airs available...
The Apple Store has Apple Certified Refurbished 2014 MacBook Airs available starting at $679. An Apple one-year warranty is included with each MacBook, and shipping is free. These are currently the... Read more
27-inch 3.5GHz 5K iMac on sale for $2349, sav...
 Adorama has the 27″ 3.5GHz 5K iMac in stock today and on sale for $2349 including free shipping plus NY & NJ sales tax only. Their price is $150 off MSRP. For a limited time, Adorama will... Read more
Save up to $380 on an iMac with Apple refurbi...
The Apple Store has Apple Certified Refurbished iMacs available for up to $380 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free: - 27″ 3.5GHz 5K iMac – $2119 $... Read more
iFixIt Teardown Awards 12-IInch Retina MacBoo...
iFixIt has posted its illustrated teardown of the new 12-inch MacBook Retina. They note that this new MacBook is less than half the thickness of the last Apple notebook called just “MacBook” back in... 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
Communication Manager - *Apple* Pay - Apple...
**Job Summary** This position works within the Apple Pay Merchant Solutions team to create, as well as oversee the development of, materials for use by Apple Pay 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
Marketing Program Manager, *Apple* Retail O...
**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
Engineering Manager for *Apple* Maps on the...
…the Maps App Team get to take part in just about any new feature in Apple Maps, often contributing a majority of the feature work. In our day-to-day engineering work, we Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.