Fun and games - Data Structures and Problem Solving Using Java - page 429

1 /**
2 * Search the grid from a starting point and direction.
3 * @return number of matches
4 */
5 private int solveDirection( int baseRow, int baseCol,
6 int rowDelta, int colDelta )
7 {
8 String charSequence = "";
9 int numMatches = 0;
10 int searchResult;
11
12 charSequence += theBoard[ baseRow ][ baseCol ];
13
14 for( int i = baseRow + rowDelta, j = baseCol + colDelta;
15 i >= 0 && j >= 0 && i < rows && j < columns;
16 i += rowDelta, j += colDelta )
17 {
18 charSequence += theBoard[ i ][ j ];
19 searchResult = prefixSearch( theWords, charSequence );
20
21 if( searchResult == theWords.length )
22 break;
23 if( !theWords[ searchResult ].startsWith( charSequence ) )
24 break;
25
26 if( theWords[ searchResult ].equals( charSequence ) )
27 {
28 numMatches++;
29 System.out.println( "Found " + charSequence + " at " +
30 baseRow + " " + baseCol + " to " +
31 i + " " + j );
32 }
33 }
34
35 return numMatches;
36 }
37
38 /**
39 * Performs the binary search for word search.
40 * Returns the last position examined this position
41 * either matches x, or x is a prefix of the mismatch, or there is
42 * no word for which x is a prefix.
43 */
44 private static int prefixSearch( String [ ] a, String x )
45 {
46 int idx = Arrays.binarySearch( a, x );
47
48 if( idx < 0 )
49 return -idx - 1;
50 else
51 return idx;
52

figure 10.8
Implementation of a
single search

}