KickJava   Java API By Example, From Geeks To Geeks.

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


1 /**
2  * com.mckoi.database.CollatedBaseSearch 26 Aug 2002
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 com.mckoi.util.IntegerVector;
29 import com.mckoi.util.BlockIntegerList;
30
31 /**
32  * An implementation of SelectableScheme that is based on some collated set of
33  * data. This can be used to implement more advanced types of selectable
34  * schemes based on presistant indexes (see InsertSearch).
35  * <p>
36  * The default implementation maintains no state,
37  * <p>
38  * Derived classes are required to implement 'copy', 'searchFirst' and
39  * 'searchLast' methods. With these basic methods, a selectable scheme can
40  * be generated provided the column is sorted in ascending order (value of row i
41  * is <= value of row i+1). Overwrite 'firstInCollationOrder',
42  * 'lastInCollationOrder' and 'addRangeToSet' methods for non sorted underlying
43  * sets.
44  * <p>
45  * Assumptions - the underlying column is sorted low to high (value of row i
46  * is <= value of row i+1).
47  *
48  * @author Tobias Downer
49  */
50
51 public abstract class CollatedBaseSearch extends SelectableScheme {
52
53   /**
54    * The Constructor.
55    */
56   public CollatedBaseSearch(TableDataSource table, int column) {
57     super(table, column);
58   }
59
60   /**
61    * This scheme doesn't take any notice of insertions or removals.
62    */
63   public void insert(int row) {
64     // Ignore insert (no state to maintain)
65 if (isImmutable()) {
66       throw new Error JavaDoc("Tried to change an immutable scheme.");
67     }
68   }
69
70   /**
71    * This scheme doesn't take any notice of insertions or removals.
72    */
73   public void remove(int row) {
74     // Ignore remove (no state to maintain)
75 if (isImmutable()) {
76       throw new Error JavaDoc("Tried to change an immutable scheme.");
77     }
78   }
79
80   /**
81    * Reads the entire state of the scheme from the input stream.
82    * This is a trivial case for BlindSearch which doesn't require any
83    * data to be stored.
84    */
85   public void readFrom(InputStream in) throws IOException {
86   }
87
88   /**
89    * Writes the entire state of the scheme to the output stream.
90    * This is a trivial case for BlindSearch which doesn't require any
91    * data to be stored.
92    */
93   public void writeTo(OutputStream out) throws IOException {
94   }
95
96   /**
97    * Disposes and invalidates the BlindSearch.
98    */
99   public void dispose() {
100     // Nothing to do!
101 }
102
103   
104   // -------- Abstract or overwrittable methods ----------
105
106   /**
107    * Finds the position in the collated set of the first value in the column
108    * equal to the given value. If the value is not to be found in the column,
109    * it returns -(insert_position + 1).
110    */
111   protected abstract int searchFirst(TObject val);
112
113   /**
114    * Finds the position in the collated set of the last value in the column
115    * equal to the given value. If the value is not to be found in the column,
116    * it returns -(insert_position + 1).
117    */
118   protected abstract int searchLast(TObject val);
119   
120   /**
121    * The size of the set (the number of rows in this column).
122    */
123   protected int setSize() {
124     return getTable().getRowCount();
125   }
126   
127   /**
128    * Returns the first value of this column (in collated order). For
129    * example, if the column contains (1, 4, 8} then '1' is returned.
130    */
131   protected TObject firstInCollationOrder() {
132     return getCellContents(0);
133   }
134
135   /**
136    * Returns the last value of this column (in collated order). For
137    * example, if the column contains (1, 4, 8} then '8' is returned.
138    */
139   protected TObject lastInCollationOrder() {
140     return getCellContents(setSize() - 1);
141   }
142
143   /**
144    * Adds the set indexes to the list that represent the range of values
145    * between the start (inclusive) and end offset (inclusive) given.
146    */
147   protected IntegerVector addRangeToSet(int start, int end,
148                                         IntegerVector ivec) {
149     if (ivec == null) {
150       ivec = new IntegerVector((end - start) + 2);
151     }
152     for (int i = start; i <= end; ++i) {
153       ivec.addInt(i);
154     }
155     return ivec;
156   }
157   
158   // ---------- Range search methods ----------
159
160   public IntegerVector selectAll() {
161     return addRangeToSet(0, setSize() - 1, null);
162   }
163
164   /**
165    * Given a flag (FIRST_VALUE, LAST_VALUE, BEFORE_FIRST_VALUE or
166    * AFTER_LAST_VALUE) and a value which is either a place marker (first, last
167    * in set) or a TObject object, this will determine the position in this
168    * set of the range point. For example, we may want to know the index of
169    * the last instance of a particular number in a set of numbers which
170    * would be 'positionOfRangePoint(SelectableRange.LAST_VALUE,
171    * [number TObject])'.
172    * <p>
173    * Note how the position is determined if the value is not found in the set.
174    */
175   private int positionOfRangePoint(byte flag, TObject val) {
176     int p;
177     TObject cell;
178
179     switch(flag) {
180
181       case(SelectableRange.FIRST_VALUE):
182         if (val == SelectableRange.FIRST_IN_SET) {
183           return 0;
184         }
185         if (val == SelectableRange.LAST_IN_SET) {
186           // Get the last value and search for the first instance of it.
187 cell = lastInCollationOrder();
188         }
189         else {
190           cell = val;
191         }
192         p = searchFirst(cell);
193         // (If value not found)
194 if (p < 0) {
195           return -(p + 1);
196         }
197         return p;
198
199       case(SelectableRange.LAST_VALUE):
200         if (val == SelectableRange.LAST_IN_SET) {
201           return setSize() - 1;
202         }
203         if (val == SelectableRange.FIRST_IN_SET) {
204           // Get the first value.
205 cell = firstInCollationOrder();
206         }
207         else {
208           cell = val;
209         }
210         p = searchLast(cell);
211         // (If value not found)
212 if (p < 0) {
213           return -(p + 1) - 1;
214         }
215         return p;
216
217       case(SelectableRange.BEFORE_FIRST_VALUE):
218         if (val == SelectableRange.FIRST_IN_SET) {
219           return -1;
220         }
221         if (val == SelectableRange.LAST_IN_SET) {
222           // Get the last value and search for the first instance of it.
223 cell = lastInCollationOrder();
224         }
225         else {
226           cell = val;
227         }
228         p = searchFirst(cell);
229         // (If value not found)
230 if (p < 0) {
231           return -(p + 1) - 1;
232         }
233         return p - 1;
234
235       case(SelectableRange.AFTER_LAST_VALUE):
236         if (val == SelectableRange.LAST_IN_SET) {
237           return setSize();
238         }
239         if (val == SelectableRange.FIRST_IN_SET) {
240           // Get the first value.
241 cell = firstInCollationOrder();
242         }
243         else {
244           cell = val;
245         }
246         p = searchLast(cell);
247         // (If value not found)
248 if (p < 0) {
249           return -(p + 1);
250         }
251         return p + 1;
252
253       default:
254         throw new Error JavaDoc("Unrecognised flag.");
255     }
256
257   }
258
259   /**
260    * Adds a range from this set to the given IntegerVector. IntegerVector may
261    * be null if a list has not yet been allocated for the range.
262    */
263   private IntegerVector addRange(SelectableRange range, IntegerVector ivec) {
264     int r1, r2;
265
266     // Select the range specified.
267 byte start_flag = range.getStartFlag();
268     TObject start = range.getStart();
269     byte end_flag = range.getEndFlag();
270     TObject end = range.getEnd();
271
272     r1 = positionOfRangePoint(start_flag, start);
273     r2 = positionOfRangePoint(end_flag, end);
274
275     if (r2 < r1) {
276       return ivec;
277     }
278
279     // Add the range to the set
280 return addRangeToSet(r1, r2, ivec);
281
282   }
283
284   public IntegerVector selectRange(SelectableRange range) {
285     // If no items in the set return an empty set
286 if (setSize() == 0) {
287       return new IntegerVector(0);
288     }
289
290     IntegerVector ivec = addRange(range, null);
291     if (ivec == null) {
292       return new IntegerVector(0);
293     }
294
295     return ivec;
296   }
297
298   public IntegerVector selectRange(SelectableRange[] ranges) {
299     // If no items in the set return an empty set
300 if (setSize() == 0) {
301       return new IntegerVector(0);
302     }
303
304     IntegerVector ivec = null;
305     for (int i = 0; i < ranges.length; ++i) {
306       SelectableRange range = ranges[i];
307       ivec = addRange(range, ivec);
308     }
309
310     if (ivec == null) {
311       return new IntegerVector(0);
312     }
313     return ivec;
314
315   }
316
317 }
318
319
Popular Tags