KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > mckoi > database > BlindSearch


1 /**
2  * com.mckoi.database.BlindSearch 14 Mar 1998
3  *
4  * Mckoi SQL Database ( http://www.mckoi.com/database )
5  * Copyright (C) 2000, 2001, 2002 Diehl and Associates, Inc.
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * Version 2 as published by the Free Software Foundation.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License Version 2 for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * Version 2 along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
19  *
20  * Change Log:
21  *
22  *
23  */
24
25 package com.mckoi.database;
26
27 import java.io.*;
28 import java.util.Arrays JavaDoc;
29 import java.util.Comparator JavaDoc;
30 import com.mckoi.util.IntegerVector;
31 import com.mckoi.util.BlockIntegerList;
32
33 /**
34  * This is a scheme that performs a blind search of a given set. It records
35  * no information about how a set element relates to the rest. It blindly
36  * searches through the set to find elements that match the given criteria.
37  * <p>
38  * This scheme performs badly on large sets because it requires that the
39  * database is queried often for information. However since it records no
40  * information about the set, memory requirements are non-existant.
41  * <p>
42  * This scheme should not be used for anything other than small domain sets
43  * because the performance suffers very badly with larger sets. It is ideal
44  * for small domain sets because of its no memory overhead. For any select
45  * operation this algorithm must check every element in the set.
46  *
47  * @author Tobias Downer
48  */
49
50 public final class BlindSearch extends SelectableScheme {
51
52   /**
53    * The Constructor.
54    */
55   public BlindSearch(TableDataSource table, int column) {
56     super(table, column);
57   }
58
59   /**
60    * This scheme doesn't take any notice of insertions or removals.
61    */
62   public void insert(int row) {
63     if (isImmutable()) {
64       throw new Error JavaDoc("Tried to change an immutable scheme.");
65     }
66   }
67
68   /**
69    * This scheme doesn't take any notice of insertions or removals.
70    */
71   public void remove(int row) {
72     if (isImmutable()) {
73       throw new Error JavaDoc("Tried to change an immutable scheme.");
74     }
75   }
76
77   /**
78    * Reads the entire state of the scheme from the input stream.
79    * This is a trivial case for BlindSearch which doesn't require any
80    * data to be stored.
81    */
82   public void readFrom(InputStream in) throws IOException {
83   }
84
85   /**
86    * Writes the entire state of the scheme to the output stream.
87    * This is a trivial case for BlindSearch which doesn't require any
88    * data to be stored.
89    */
90   public void writeTo(OutputStream out) throws IOException {
91   }
92
93   /**
94    * Returns an exact copy of this scheme including any optimization
95    * information. The copied scheme is identical to the original but does not
96    * share any parts. Modifying any part of the copied scheme will have no
97    * effect on the original and vice versa.
98    */
99   public SelectableScheme copy(TableDataSource table, boolean immutable) {
100     // Return a fresh object. This implementation has no state so we can
101 // ignore the 'immutable' flag.
102 return new BlindSearch(table, getColumn());
103   }
104
105   /**
106    * Disposes and invalidates the BlindSearch.
107    */
108   public void dispose() {
109     // Nothing to do!
110 }
111
112   /**
113    * Selection methods for obtaining various sub-sets of information from the
114    * set.
115    */
116
117   /**
118    * We implement an insert sort algorithm here. Each new row is inserted
119    * into our row vector at the sorted corrent position.
120    * The algorithm assumes the given vector is already sorted. We then just
121    * subdivide the set until we can insert at the required position.
122    */
123   private int search(TObject ob, IntegerVector vec, int lower, int higher) {
124     if (lower >= higher) {
125       if (ob.compareTo(getCellContents(vec.intAt(lower))) > 0) {
126         return lower + 1;
127       }
128       else {
129         return lower;
130       }
131     }
132
133     int mid = lower + ((higher - lower) / 2);
134     int comp_result = ob.compareTo(getCellContents(vec.intAt(mid)));
135
136     if (comp_result == 0) {
137       return mid;
138     }
139     else if (comp_result < 0) {
140       return search(ob, vec, lower, mid - 1);
141     }
142     else {
143       return search(ob, vec, mid + 1, higher);
144     }
145
146   }
147
148   /**
149    * Searches for a given TObject (ob) in the row list between the two
150    * bounds. This will return the highest row of the set of values that are
151    * equal to 'ob'.
152    * <p>
153    * This returns the place to insert ob into the vector, it should not be
154    * used to determine if ob is in the list or not.
155    */
156   private int highestSearch(TObject ob, IntegerVector vec,
157                             int lower, int higher) {
158
159     if ((higher - lower) <= 5) {
160       // Start from the bottom up until we find the highest val
161 for (int i = higher; i >= lower; --i) {
162         int res = ob.compareTo(getCellContents(vec.intAt(i)));
163         if (res >= 0) {
164           return i + 1;
165         }
166       }
167       // Didn't find return lowest
168 return lower;
169     }
170
171     int mid = (lower + higher) / 2;
172     int comp_result = ob.compareTo(getCellContents(vec.intAt(mid)));
173
174     if (comp_result == 0) {
175       // We know the bottom is between 'mid' and 'higher'
176 return highestSearch(ob, vec, mid, higher);
177     }
178     else if (comp_result < 0) {
179       return highestSearch(ob, vec, lower, mid - 1);
180     }
181     else {
182       return highestSearch(ob, vec, mid + 1, higher);
183     }
184   }
185
186
187   private void doInsertSort(IntegerVector vec, int row) {
188     int list_size = vec.size();
189     if (list_size == 0) {
190       vec.addInt(row);
191     }
192     else {
193       int point = highestSearch(getCellContents(row), vec, 0, list_size - 1);
194       if (point == list_size) {
195         vec.addInt(row);
196       }
197       else {
198         vec.insertIntAt(row, point);
199       }
200     }
201   }
202
203   public IntegerVector selectAll() {
204     IntegerVector row_list = new IntegerVector(getTable().getRowCount());
205     RowEnumeration e = getTable().rowEnumeration();
206     while (e.hasMoreRows()) {
207       doInsertSort(row_list, e.nextRowIndex());
208     }
209     return row_list;
210   }
211
212   
213   
214   public IntegerVector selectRange(SelectableRange range) {
215     int set_size = getTable().getRowCount();
216     // If no items in the set return an empty set
217 if (set_size == 0) {
218       return new IntegerVector(0);
219     }
220
221     return selectRange(new SelectableRange[] { range } );
222   }
223
224   public IntegerVector selectRange(SelectableRange[] ranges) {
225     int set_size = getTable().getRowCount();
226     // If no items in the set return an empty set
227 if (set_size == 0) {
228       return new IntegerVector(0);
229     }
230
231     RangeChecker checker = new RangeChecker(ranges);
232     return checker.resolve();
233   }
234
235
236   // ---------- Inner classes ----------
237
238   /**
239    * Object used to during range check loop.
240    */
241   final class RangeChecker {
242
243     /**
244      * The sorted list of all items in the set created as a cache for finding
245      * the first and last values.
246      */
247     private IntegerVector sorted_set = null;
248
249     /**
250      * The list of flags for each check in the range.
251      * Either 0 for no check, 1 for < or >, 2 for <= or >=.
252      */
253     private byte[] lower_flags;
254     private byte[] upper_flags;
255
256     /**
257      * The TObject objects to check against.
258      */
259     private TObject[] lower_cells;
260     private TObject[] upper_cells;
261
262     /**
263      * Constructs the checker.
264      */
265     public RangeChecker(SelectableRange[] ranges) {
266       int size = ranges.length;
267       lower_flags = new byte[size];
268       upper_flags = new byte[size];
269       lower_cells = new TObject[size];
270       upper_cells = new TObject[size];
271       for (int i = 0; i < ranges.length; ++i) {
272         setupRange(i, ranges[i]);
273       }
274     }
275
276     private void resolveSortedSet() {
277       if (sorted_set == null) {
278 // System.out.println("SLOW RESOLVE SORTED SET ON BLIND SEARCH.");
279 sorted_set = selectAll();
280       }
281     }
282
283     /**
284      * Resolves a cell.
285      */
286     private TObject resolveCell(TObject ob) {
287       if (ob == SelectableRange.FIRST_IN_SET) {
288         resolveSortedSet();
289         return getCellContents(sorted_set.intAt(0));
290
291       }
292       else if (ob == SelectableRange.LAST_IN_SET) {
293         resolveSortedSet();
294         return getCellContents(sorted_set.intAt(sorted_set.size() - 1));
295       }
296       else {
297         return ob;
298       }
299     }
300
301     /**
302      * Set up a range.
303      */
304     public void setupRange(int i, SelectableRange range) {
305       TObject l = range.getStart();
306       byte lf = range.getStartFlag();
307       TObject u = range.getEnd();
308       byte uf = range.getEndFlag();
309
310       // Handle lower first
311 if (l == SelectableRange.FIRST_IN_SET &&
312           lf == SelectableRange.FIRST_VALUE) {
313         // Special case no lower check
314 lower_flags[i] = 0;
315       }
316       else {
317         if (lf == SelectableRange.FIRST_VALUE) {
318           lower_flags[i] = 2; // >=
319 }
320         else if (lf == SelectableRange.AFTER_LAST_VALUE) {
321           lower_flags[i] = 1; // >
322 }
323         else {
324           throw new Error JavaDoc("Incorrect lower flag.");
325         }
326         lower_cells[i] = resolveCell(l);
327       }
328
329       // Now handle upper
330 if (u == SelectableRange.LAST_IN_SET &&
331           uf == SelectableRange.LAST_VALUE) {
332         // Special case no upper check
333 upper_flags[i] = 0;
334       }
335       else {
336         if (uf == SelectableRange.LAST_VALUE) {
337           upper_flags[i] = 2; // <=
338 }
339         else if (uf == SelectableRange.BEFORE_FIRST_VALUE) {
340           upper_flags[i] = 1; // <
341 }
342         else {
343           throw new Error JavaDoc("Incorrect upper flag.");
344         }
345         upper_cells[i] = resolveCell(u);
346       }
347
348     }
349
350     /**
351      * Resolves the ranges.
352      */
353     public IntegerVector resolve() {
354       // The idea here is to only need to scan the column once to find all
355 // the cells that meet our criteria.
356 IntegerVector ivec = new IntegerVector();
357       RowEnumeration e = getTable().rowEnumeration();
358
359       int compare_tally = 0;
360
361       int size = lower_flags.length;
362       while (e.hasMoreRows()) {
363         int row = e.nextRowIndex();
364         // For each range
365 range_set:
366         for (int i = 0; i < size; ++i) {
367           boolean result = true;
368           byte lf = lower_flags[i];
369           if (lf != 0) {
370             ++compare_tally;
371             TObject v = getCellContents(row);
372             int compare = lower_cells[i].compareTo(v);
373             if (lf == 1) { // >
374 result = (compare < 0);
375             }
376             else if (lf == 2) { // >=
377 result = (compare <= 0);
378             }
379             else {
380               throw new Error JavaDoc("Incorrect flag.");
381             }
382           }
383           if (result) {
384             byte uf = upper_flags[i];
385             if (uf != 0) {
386               ++compare_tally;
387               TObject v = getCellContents(row);
388               int compare = upper_cells[i].compareTo(v);
389               if (uf == 1) { // <
390 result = (compare > 0);
391               }
392               else if (uf == 2) { // >=
393 result = (compare >= 0);
394               }
395               else {
396                 throw new Error JavaDoc("Incorrect flag.");
397               }
398             }
399             // Pick this row
400 if (result) {
401               doInsertSort(ivec, row);
402               break range_set;
403             }
404           }
405         }
406       }
407
408 // System.out.println("Blind Search compare tally: " + compare_tally);
409
410       return ivec;
411     }
412
413   }
414
415 }
416
417
Popular Tags