SelectableScheme


1   /**
2    * com.mckoi.database.SelectableScheme  12 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 com.mckoi.util.IntegerVector;
28  import com.mckoi.util.IndexComparator;
29  import com.mckoi.util.BlockIntegerList;
30  import com.mckoi.debug.DebugLogger;
31  import java.io.IOException  ;
32  import java.io.InputStream  ;
33  import java.io.OutputStream  ;
34  
35  /**
36   * Represents a base class for a mechanism to select ranges from a given set.
37   * Such schemes could include BinaryTree, Hashtable or just a blind search.
38   * <p>
39   * A given element in the set is specified through a 'row' integer whose
40   * contents can be obtained through the 'table.getCellContents(column, row)'.
41   * Every scheme is given a table and column number that the set refers to.
42   * While a given set element is refered to as a 'row', the integer is really
43   * only a pointer into the set list which can be de-referenced with a call to
44   * table.getCellContents(row).  Better performance schemes will keep such
45   * calls to a minimum.
46   * <p>
47   * A scheme may choose to retain knowledge about a given element when it is
48   * added or removed from the set, such as a BinaryTree that catalogs all
49   * elements with respect to each other.
50   *
51   * @author Tobias Downer
52   */
53  
54  public abstract class SelectableScheme {
55  
56    /**
57     * Some statics.
58     */
59    protected static final BlockIntegerList EMPTY_LIST;
60    protected static final BlockIntegerList ONE_LIST;
61  
62    static {
63      EMPTY_LIST = new BlockIntegerList();
64      EMPTY_LIST.setImmutable();
65      ONE_LIST = new BlockIntegerList();
66      ONE_LIST.add(0);
67      ONE_LIST.setImmutable();
68    }
69    
70    /**
71     * The table data source with the column this scheme indexes.
72     */
73    private final TableDataSource table;
74  
75    /**
76     * The column number in the tree this tree helps.
77     */
78    private final int column;
79  
80    /**
81     * Set to true if this scheme is immutable (can't be changed).
82     */
83    private boolean immutable = false;
84  
85    /**
86     * The constructor for all schemes.
87     */
88    public SelectableScheme(TableDataSource table, int column) {
89      this.table = table;
90      this.column = column;
91    }
92  
93    /**
94     * Returns the Table.
95     */
96    protected final TableDataSource getTable() {
97      return table;
98    }
99  
100   /**
101    * Returns the global transaction system.
102    */
103   protected final TransactionSystem getSystem() {
104     return table.getSystem();
105   }
106 
107   /**
108    * Returns the DebugLogger object to log debug messages to.
109    */
110   protected final DebugLogger Debug() {
111     return getSystem().Debug();
112   }
113 
114   /**
115    * Returns the column this scheme is indexing in the table.
116    */
117   protected final int getColumn() {
118     return column;
119   }
120 
121   /**
122    * Obtains the given cell in the row from the table.
123    */
124   protected final TObject getCellContents(int row) {
125     return table.getCellContents(column, row);
126   }
127 
128   /**
129    * Sets this scheme to immutable.
130    */
131   public final void setImmutable() {
132     immutable = true;
133   }
134 
135   /**
136    * Returns true if this scheme is immutable.
137    */
138   public final boolean isImmutable() {
139     return immutable;
140   }
141 
142   /**
143    * Diagnostic information.
144    */
145   public String   toString() {
146     // Name of the table
147     String   table_name;
148     if (table instanceof DefaultDataTable) {
149       table_name = ((DefaultDataTable) table).getTableName().toString();
150     }
151     else {
152       table_name = "VirtualTable";
153     }
154 
155     StringBuffer   buf = new StringBuffer  ();
156     buf.append("[ SelectableScheme ");
157     buf.append(super.toString());
158     buf.append(" for table: ");
159     buf.append(table_name);
160     buf.append("]");
161 
162     return new String  (buf);
163   }
164 
165   /**
166    * Writes the entire contents of the scheme to an OutputStream object.
167    */
168   public abstract void writeTo(OutputStream   out) throws IOException  ;
169 
170   /**
171    * Reads the entire contents of the scheme from a InputStream object.  If the
172    * scheme is full of any information it throws an exception.
173    */
174   public abstract void readFrom(InputStream   in) throws IOException  ;
175 
176   /**
177    * Returns an exact copy of this scheme including any optimization
178    * information.  The copied scheme is identical to the original but does not
179    * share any parts.  Modifying any part of the copied scheme will have no
180    * effect on the original and vice versa.
181    * <p>
182    * The newly copied scheme can be given a new table source.  If
183    * 'immutable' is true, then the resultant scheme is an immutable version
184    * of the parent.  An immutable version may share information with the
185    * copied version so can not be changed.
186    * <p>
187    * NOTE: Even if the scheme maintains no state you should still be careful
188    *   to ensure a fresh SelectableScheme object is returned here.
189    */
190   public abstract SelectableScheme copy(TableDataSource table,
191                                         boolean immutable);
192 
193   /**
194    * Dispose and invalidate this scheme.
195    */
196   public abstract void dispose();
197 
198 
199   /**
200    * =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
201    * Abstract methods for selection of rows, and maintenance of rows
202    * =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
203    */
204   /**
205    * Inserts the given element into the set.  This is called just after a
206    * row has been initially added to a table.
207    */
208   abstract void insert(int row);
209 
210   /**
211    * Removes the given element from the set.  This is called just before the
212    * row is removed from the table.
213    */
214   abstract void remove(int row);
215 
216   /**
217    * Returns a BlockIntegerList that represents the given row_set sorted
218    * in the order of this scheme.  The values in 'row_set' must be references
219    * to rows in the domain of the table this scheme represents.
220    * <p>
221    * The returned set must be stable, meaning if values are equal they keep
222    * the same ordering.
223    * <p>
224    * Note that the default implementation of this method can often be optimized.
225    * For example, InsertSearch uses a secondary RID list to sort items if the
226    * given list is over a certain size.
227    */
228   public BlockIntegerList internalOrderIndexSet(final IntegerVector row_set) {
229     // The length of the set to order
230     int row_set_length = row_set.size();
231 
232     // Trivial cases where sorting is not required:
233     // NOTE: We use immutable objects to save some memory.
234     if (row_set_length == 0) {
235       return EMPTY_LIST;
236     }
237     else if (row_set_length == 1) {
238       return ONE_LIST;
239     }
240 
241     // This will be 'row_set' sorted by its entry lookup.  This must only
242     // contain indices to row_set entries.
243     BlockIntegerList new_set = new BlockIntegerList();
244 
245     if (row_set_length <= 250000) {
246       // If the subset is less than or equal to 250,000 elements, we generate
247       // an array in memory that contains all values in the set and we sort
248       // it.  This requires use of memory from the heap but is faster than
249       // the no heap use method.
250       final TObject[] subset_list = new TObject[row_set_length];
251       for (int i = 0; i < row_set_length; ++i) {
252         subset_list[i] = getCellContents(row_set.intAt(i));
253       }
254     
255       // The comparator we use to sort
256       IndexComparator comparator = new IndexComparator() {
257         public int compare(int index, Object   val) {
258           TObject cell = subset_list[index];
259           return cell.compareTo((TObject) val);
260         }
261         public int compare(int index1, int index2) {
262           throw new Error  ("Shouldn't be called!");
263         }
264       };
265 
266       // Fill new_set with the set { 0, 1, 2, .... , row_set_length }
267       for (int i = 0; i < row_set_length; ++i) {
268         TObject cell = subset_list[i];
269         new_set.insertSort(cell, i, comparator);
270       }
271 
272     }
273     else {
274       // This is the no additional heap use method to sorting the sub-set.
275       
276       // The comparator we use to sort
277       IndexComparator comparator = new IndexComparator() {
278         public int compare(int index, Object   val) {
279           TObject cell = getCellContents(row_set.intAt(index));
280           return cell.compareTo((TObject) val);
281         }
282         public int compare(int index1, int index2) {
283           throw new Error  ("Shouldn't be called!");
284         }
285       };
286 
287       // Fill new_set with the set { 0, 1, 2, .... , row_set_length }
288       for (int i = 0; i < row_set_length; ++i) {
289         TObject cell = getCellContents(row_set.intAt(i));
290         new_set.insertSort(cell, i, comparator);
291       }
292 
293     }
294 
295     return new_set;
296 
297   }
298 
299   /**
300    * Asks the Scheme for a SelectableScheme abject that describes a sub-set
301    * of the set handled by this Scheme.  Since a Table stores a subset
302    * of a given DataTable, we pass this as the argument.  It returns a
303    * new SelectableScheme that orders the rows in the given columns order.
304    * The 'column' variable specifies the column index of this column in the
305    * given table.
306    */
307   public SelectableScheme getSubsetScheme(Table subset_table,
308                                           int subset_column) {
309 
310     // Resolve table rows in this table scheme domain.
311     IntegerVector row_set = new IntegerVector(subset_table.getRowCount());
312     RowEnumeration e = subset_table.rowEnumeration();
313     while (e.hasMoreRows()) {
314       row_set.addInt(e.nextRowIndex());
315     }
316     subset_table.setToRowTableDomain(subset_column, row_set, getTable());
317 
318     // Generates an IntegerVector which contains indices into 'row_set' in
319     // sorted order.
320     BlockIntegerList new_set = internalOrderIndexSet(row_set);
321 
322     // Our 'new_set' should be the same size as 'row_set'
323     if (new_set.size() != row_set.size()) {
324       throw new RuntimeException  ("Internal sort error in finding sub-set.");
325     }
326 
327     // Set up a new SelectableScheme with the sorted index set.
328     // Move the sorted index set into the new scheme.
329     InsertSearch is = new InsertSearch(subset_table, subset_column, new_set);
330     // Don't let subset schemes create uid caches.
331     is.RECORD_UID = false;
332     return is;
333 
334   }
335 
336   /**
337    * These are the select operations that are the main purpose of the scheme.
338    * They retrieve the given information from the set.  Different schemes will
339    * have varying performance on different types of data sets.
340    * The select operations must *always* return a resultant row set that
341    * is sorted from lowest to highest.
342    */
343   public IntegerVector selectAll() {
344     return selectRange(new SelectableRange(
345              SelectableRange.FIRST_VALUE, SelectableRange.FIRST_IN_SET,
346              SelectableRange.LAST_VALUE, SelectableRange.LAST_IN_SET));
347   }
348 
349   public IntegerVector selectFirst() {
350     // NOTE: This will find NULL at start which is probably wrong.  The
351     //   first value should be the first non null value.
352     return selectRange(new SelectableRange(
353              SelectableRange.FIRST_VALUE, SelectableRange.FIRST_IN_SET,
354              SelectableRange.LAST_VALUE, SelectableRange.FIRST_IN_SET));
355   }
356 
357   public IntegerVector selectNotFirst() {
358     // NOTE: This will find NULL at start which is probably wrong.  The
359     //   first value should be the first non null value.
360     return selectRange(new SelectableRange(
361              SelectableRange.AFTER_LAST_VALUE, SelectableRange.FIRST_IN_SET,
362              SelectableRange.LAST_VALUE, SelectableRange.LAST_IN_SET));
363   }
364 
365   public IntegerVector selectLast() {
366     return selectRange(new SelectableRange(
367              SelectableRange.FIRST_VALUE, SelectableRange.LAST_IN_SET,
368              SelectableRange.LAST_VALUE, SelectableRange.LAST_IN_SET));
369   }
370 
371   public IntegerVector selectNotLast() {
372     return selectRange(new SelectableRange(
373              SelectableRange.FIRST_VALUE, SelectableRange.FIRST_IN_SET,
374              SelectableRange.BEFORE_FIRST_VALUE, SelectableRange.LAST_IN_SET));
375   }
376 
377   /**
378    * Selects all values in the column that are not null.
379    */
380   public IntegerVector selectAllNonNull() {
381     return selectRange(new SelectableRange(
382                  SelectableRange.AFTER_LAST_VALUE, TObject.nullVal(),
383                  SelectableRange.LAST_VALUE, SelectableRange.LAST_IN_SET));
384   }
385 
386   public IntegerVector selectEqual(TObject ob) {
387     if (ob.isNull()) {
388       return new IntegerVector(0);
389     }
390     return selectRange(new SelectableRange(
391                          SelectableRange.FIRST_VALUE, ob,
392                          SelectableRange.LAST_VALUE, ob));
393   }
394 
395   public IntegerVector selectNotEqual(TObject ob) {
396     if (ob.isNull()) {
397       return new IntegerVector(0);
398     }
399     return selectRange(new SelectableRange[] {
400           new SelectableRange(
401                   SelectableRange.AFTER_LAST_VALUE, TObject.nullVal(),
402                   SelectableRange.BEFORE_FIRST_VALUE, ob)
403           , new SelectableRange(
404                   SelectableRange.AFTER_LAST_VALUE, ob,
405                   SelectableRange.LAST_VALUE, SelectableRange.LAST_IN_SET)
406           });
407   }
408 
409   public IntegerVector selectGreater(TObject ob) {
410     if (ob.isNull()) {
411       return new IntegerVector(0);
412     }
413     return selectRange(new SelectableRange(
414                SelectableRange.AFTER_LAST_VALUE, ob,
415                SelectableRange.LAST_VALUE, SelectableRange.LAST_IN_SET));
416   }
417 
418   public IntegerVector selectLess(TObject ob) {
419     if (ob.isNull()) {
420       return new IntegerVector(0);
421     }
422     return selectRange(new SelectableRange(
423                SelectableRange.AFTER_LAST_VALUE, TObject.nullVal(),
424                SelectableRange.BEFORE_FIRST_VALUE, ob));
425   }
426 
427   public IntegerVector selectGreaterOrEqual(TObject ob) {
428     if (ob.isNull()) {
429       return new IntegerVector(0);
430     }
431     return selectRange(new SelectableRange(
432                SelectableRange.FIRST_VALUE, ob,
433                SelectableRange.LAST_VALUE, SelectableRange.LAST_IN_SET));
434   }
435 
436   public IntegerVector selectLessOrEqual(TObject ob) {
437     if (ob.isNull()) {
438       return new IntegerVector(0);
439     }
440     return selectRange(new SelectableRange(
441                SelectableRange.AFTER_LAST_VALUE, TObject.nullVal(),
442                SelectableRange.LAST_VALUE, ob));
443   }
444 
445   // Inclusive of rows that are >= ob1 and < ob2
446   // NOTE: This is not compatible with SQL BETWEEN predicate which is all
447   //   rows that are >= ob1 and <= ob2
448   public IntegerVector selectBetween(TObject ob1, TObject ob2) {
449     if (ob1.isNull() || ob2.isNull()) {
450       return new IntegerVector(0);
451     }
452     return selectRange(new SelectableRange(
453                SelectableRange.FIRST_VALUE, ob1,
454                SelectableRange.BEFORE_FIRST_VALUE, ob2));
455   }
456 
457   /**
458    * Selects the given range of values from this index.  The SelectableRange
459    * must contain a 'start' value that compares <= to the 'end' value.
460    * <p>
461    * This must guarentee that the returned set is sorted from lowest to
462    * highest value.
463    */
464   abstract IntegerVector selectRange(SelectableRange range);
465 
466   /**
467    * Selects a set of ranges from this index.  The ranges must not overlap and
468    * each range must contain a 'start' value that compares <= to the 'end'
469    * value.  Every range in the array must represent a range that's lower than
470    * the preceeding range (if it exists).
471    * <p>
472    * If the above rules are enforced (as they must be) then this method will
473    * return a set that is sorted from lowest to highest value.
474    * <p>
475    * This must guarentee that the returned set is sorted from lowest to
476    * highest value.
477    */
478   abstract IntegerVector selectRange(SelectableRange[] ranges);
479 
480 }
481
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags