001: /**
002: * com.mckoi.database.SelectableScheme 12 Mar 1998
003: *
004: * Mckoi SQL Database ( http://www.mckoi.com/database )
005: * Copyright (C) 2000, 2001, 2002 Diehl and Associates, Inc.
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License
009: * Version 2 as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful,
012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
014: * GNU General Public License Version 2 for more details.
015: *
016: * You should have received a copy of the GNU General Public License
017: * Version 2 along with this program; if not, write to the Free Software
018: * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
019: *
020: * Change Log:
021: *
022: *
023: */package com.mckoi.database;
024:
025: import com.mckoi.util.IntegerVector;
026: import com.mckoi.util.IndexComparator;
027: import com.mckoi.util.BlockIntegerList;
028: import com.mckoi.debug.DebugLogger;
029: import java.io.IOException;
030: import java.io.InputStream;
031: import java.io.OutputStream;
032:
033: /**
034: * Represents a base class for a mechanism to select ranges from a given set.
035: * Such schemes could include BinaryTree, Hashtable or just a blind search.
036: * <p>
037: * A given element in the set is specified through a 'row' integer whose
038: * contents can be obtained through the 'table.getCellContents(column, row)'.
039: * Every scheme is given a table and column number that the set refers to.
040: * While a given set element is refered to as a 'row', the integer is really
041: * only a pointer into the set list which can be de-referenced with a call to
042: * table.getCellContents(row). Better performance schemes will keep such
043: * calls to a minimum.
044: * <p>
045: * A scheme may choose to retain knowledge about a given element when it is
046: * added or removed from the set, such as a BinaryTree that catalogs all
047: * elements with respect to each other.
048: *
049: * @author Tobias Downer
050: */
051:
052: public abstract class SelectableScheme {
053:
054: /**
055: * Some statics.
056: */
057: protected static final BlockIntegerList EMPTY_LIST;
058: protected static final BlockIntegerList ONE_LIST;
059:
060: static {
061: EMPTY_LIST = new BlockIntegerList();
062: EMPTY_LIST.setImmutable();
063: ONE_LIST = new BlockIntegerList();
064: ONE_LIST.add(0);
065: ONE_LIST.setImmutable();
066: }
067:
068: /**
069: * The table data source with the column this scheme indexes.
070: */
071: private final TableDataSource table;
072:
073: /**
074: * The column number in the tree this tree helps.
075: */
076: private final int column;
077:
078: /**
079: * Set to true if this scheme is immutable (can't be changed).
080: */
081: private boolean immutable = false;
082:
083: /**
084: * The constructor for all schemes.
085: */
086: public SelectableScheme(TableDataSource table, int column) {
087: this .table = table;
088: this .column = column;
089: }
090:
091: /**
092: * Returns the Table.
093: */
094: protected final TableDataSource getTable() {
095: return table;
096: }
097:
098: /**
099: * Returns the global transaction system.
100: */
101: protected final TransactionSystem getSystem() {
102: return table.getSystem();
103: }
104:
105: /**
106: * Returns the DebugLogger object to log debug messages to.
107: */
108: protected final DebugLogger Debug() {
109: return getSystem().Debug();
110: }
111:
112: /**
113: * Returns the column this scheme is indexing in the table.
114: */
115: protected final int getColumn() {
116: return column;
117: }
118:
119: /**
120: * Obtains the given cell in the row from the table.
121: */
122: protected final TObject getCellContents(int row) {
123: return table.getCellContents(column, row);
124: }
125:
126: /**
127: * Sets this scheme to immutable.
128: */
129: public final void setImmutable() {
130: immutable = true;
131: }
132:
133: /**
134: * Returns true if this scheme is immutable.
135: */
136: public final boolean isImmutable() {
137: return immutable;
138: }
139:
140: /**
141: * Diagnostic information.
142: */
143: public String toString() {
144: // Name of the table
145: String table_name;
146: if (table instanceof DefaultDataTable) {
147: table_name = ((DefaultDataTable) table).getTableName()
148: .toString();
149: } else {
150: table_name = "VirtualTable";
151: }
152:
153: StringBuffer buf = new StringBuffer();
154: buf.append("[ SelectableScheme ");
155: buf.append(super .toString());
156: buf.append(" for table: ");
157: buf.append(table_name);
158: buf.append("]");
159:
160: return new String(buf);
161: }
162:
163: /**
164: * Writes the entire contents of the scheme to an OutputStream object.
165: */
166: public abstract void writeTo(OutputStream out) throws IOException;
167:
168: /**
169: * Reads the entire contents of the scheme from a InputStream object. If the
170: * scheme is full of any information it throws an exception.
171: */
172: public abstract void readFrom(InputStream in) throws IOException;
173:
174: /**
175: * Returns an exact copy of this scheme including any optimization
176: * information. The copied scheme is identical to the original but does not
177: * share any parts. Modifying any part of the copied scheme will have no
178: * effect on the original and vice versa.
179: * <p>
180: * The newly copied scheme can be given a new table source. If
181: * 'immutable' is true, then the resultant scheme is an immutable version
182: * of the parent. An immutable version may share information with the
183: * copied version so can not be changed.
184: * <p>
185: * NOTE: Even if the scheme maintains no state you should still be careful
186: * to ensure a fresh SelectableScheme object is returned here.
187: */
188: public abstract SelectableScheme copy(TableDataSource table,
189: boolean immutable);
190:
191: /**
192: * Dispose and invalidate this scheme.
193: */
194: public abstract void dispose();
195:
196: /**
197: * =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
198: * Abstract methods for selection of rows, and maintenance of rows
199: * =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
200: */
201: /**
202: * Inserts the given element into the set. This is called just after a
203: * row has been initially added to a table.
204: */
205: abstract void insert(int row);
206:
207: /**
208: * Removes the given element from the set. This is called just before the
209: * row is removed from the table.
210: */
211: abstract void remove(int row);
212:
213: /**
214: * Returns a BlockIntegerList that represents the given row_set sorted
215: * in the order of this scheme. The values in 'row_set' must be references
216: * to rows in the domain of the table this scheme represents.
217: * <p>
218: * The returned set must be stable, meaning if values are equal they keep
219: * the same ordering.
220: * <p>
221: * Note that the default implementation of this method can often be optimized.
222: * For example, InsertSearch uses a secondary RID list to sort items if the
223: * given list is over a certain size.
224: */
225: public BlockIntegerList internalOrderIndexSet(
226: final IntegerVector row_set) {
227: // The length of the set to order
228: int row_set_length = row_set.size();
229:
230: // Trivial cases where sorting is not required:
231: // NOTE: We use immutable objects to save some memory.
232: if (row_set_length == 0) {
233: return EMPTY_LIST;
234: } else if (row_set_length == 1) {
235: return ONE_LIST;
236: }
237:
238: // This will be 'row_set' sorted by its entry lookup. This must only
239: // contain indices to row_set entries.
240: BlockIntegerList new_set = new BlockIntegerList();
241:
242: if (row_set_length <= 250000) {
243: // If the subset is less than or equal to 250,000 elements, we generate
244: // an array in memory that contains all values in the set and we sort
245: // it. This requires use of memory from the heap but is faster than
246: // the no heap use method.
247: final TObject[] subset_list = new TObject[row_set_length];
248: for (int i = 0; i < row_set_length; ++i) {
249: subset_list[i] = getCellContents(row_set.intAt(i));
250: }
251:
252: // The comparator we use to sort
253: IndexComparator comparator = new IndexComparator() {
254: public int compare(int index, Object val) {
255: TObject cell = subset_list[index];
256: return cell.compareTo((TObject) val);
257: }
258:
259: public int compare(int index1, int index2) {
260: throw new Error("Shouldn't be called!");
261: }
262: };
263:
264: // Fill new_set with the set { 0, 1, 2, .... , row_set_length }
265: for (int i = 0; i < row_set_length; ++i) {
266: TObject cell = subset_list[i];
267: new_set.insertSort(cell, i, comparator);
268: }
269:
270: } else {
271: // This is the no additional heap use method to sorting the sub-set.
272:
273: // The comparator we use to sort
274: IndexComparator comparator = new IndexComparator() {
275: public int compare(int index, Object val) {
276: TObject cell = getCellContents(row_set.intAt(index));
277: return cell.compareTo((TObject) val);
278: }
279:
280: public int compare(int index1, int index2) {
281: throw new Error("Shouldn't be called!");
282: }
283: };
284:
285: // Fill new_set with the set { 0, 1, 2, .... , row_set_length }
286: for (int i = 0; i < row_set_length; ++i) {
287: TObject cell = getCellContents(row_set.intAt(i));
288: new_set.insertSort(cell, i, comparator);
289: }
290:
291: }
292:
293: return new_set;
294:
295: }
296:
297: /**
298: * Asks the Scheme for a SelectableScheme abject that describes a sub-set
299: * of the set handled by this Scheme. Since a Table stores a subset
300: * of a given DataTable, we pass this as the argument. It returns a
301: * new SelectableScheme that orders the rows in the given columns order.
302: * The 'column' variable specifies the column index of this column in the
303: * given table.
304: */
305: public SelectableScheme getSubsetScheme(Table subset_table,
306: int subset_column) {
307:
308: // Resolve table rows in this table scheme domain.
309: IntegerVector row_set = new IntegerVector(subset_table
310: .getRowCount());
311: RowEnumeration e = subset_table.rowEnumeration();
312: while (e.hasMoreRows()) {
313: row_set.addInt(e.nextRowIndex());
314: }
315: subset_table.setToRowTableDomain(subset_column, row_set,
316: 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(
325: "Internal sort error in finding sub-set.");
326: }
327:
328: // Set up a new SelectableScheme with the sorted index set.
329: // Move the sorted index set into the new scheme.
330: InsertSearch is = new InsertSearch(subset_table, subset_column,
331: new_set);
332: // Don't let subset schemes create uid caches.
333: is.RECORD_UID = false;
334: return is;
335:
336: }
337:
338: /**
339: * These are the select operations that are the main purpose of the scheme.
340: * They retrieve the given information from the set. Different schemes will
341: * have varying performance on different types of data sets.
342: * The select operations must *always* return a resultant row set that
343: * is sorted from lowest to highest.
344: */
345: public IntegerVector selectAll() {
346: return selectRange(new SelectableRange(
347: SelectableRange.FIRST_VALUE,
348: SelectableRange.FIRST_IN_SET,
349: SelectableRange.LAST_VALUE, SelectableRange.LAST_IN_SET));
350: }
351:
352: public IntegerVector selectFirst() {
353: // NOTE: This will find NULL at start which is probably wrong. The
354: // first value should be the first non null value.
355: return selectRange(new SelectableRange(
356: SelectableRange.FIRST_VALUE,
357: SelectableRange.FIRST_IN_SET,
358: SelectableRange.LAST_VALUE,
359: SelectableRange.FIRST_IN_SET));
360: }
361:
362: public IntegerVector selectNotFirst() {
363: // NOTE: This will find NULL at start which is probably wrong. The
364: // first value should be the first non null value.
365: return selectRange(new SelectableRange(
366: SelectableRange.AFTER_LAST_VALUE,
367: SelectableRange.FIRST_IN_SET,
368: SelectableRange.LAST_VALUE, SelectableRange.LAST_IN_SET));
369: }
370:
371: public IntegerVector selectLast() {
372: return selectRange(new SelectableRange(
373: SelectableRange.FIRST_VALUE,
374: SelectableRange.LAST_IN_SET,
375: SelectableRange.LAST_VALUE, SelectableRange.LAST_IN_SET));
376: }
377:
378: public IntegerVector selectNotLast() {
379: return selectRange(new SelectableRange(
380: SelectableRange.FIRST_VALUE,
381: SelectableRange.FIRST_IN_SET,
382: SelectableRange.BEFORE_FIRST_VALUE,
383: SelectableRange.LAST_IN_SET));
384: }
385:
386: /**
387: * Selects all values in the column that are not null.
388: */
389: public IntegerVector selectAllNonNull() {
390: return selectRange(new SelectableRange(
391: SelectableRange.AFTER_LAST_VALUE, TObject.nullVal(),
392: SelectableRange.LAST_VALUE, SelectableRange.LAST_IN_SET));
393: }
394:
395: public IntegerVector selectEqual(TObject ob) {
396: if (ob.isNull()) {
397: return new IntegerVector(0);
398: }
399: return selectRange(new SelectableRange(
400: SelectableRange.FIRST_VALUE, ob,
401: SelectableRange.LAST_VALUE, ob));
402: }
403:
404: public IntegerVector selectNotEqual(TObject ob) {
405: if (ob.isNull()) {
406: return new IntegerVector(0);
407: }
408: return selectRange(new SelectableRange[] {
409: new SelectableRange(SelectableRange.AFTER_LAST_VALUE,
410: TObject.nullVal(),
411: SelectableRange.BEFORE_FIRST_VALUE, ob),
412: new SelectableRange(SelectableRange.AFTER_LAST_VALUE,
413: ob, SelectableRange.LAST_VALUE,
414: SelectableRange.LAST_IN_SET) });
415: }
416:
417: public IntegerVector selectGreater(TObject ob) {
418: if (ob.isNull()) {
419: return new IntegerVector(0);
420: }
421: return selectRange(new SelectableRange(
422: SelectableRange.AFTER_LAST_VALUE, ob,
423: SelectableRange.LAST_VALUE, SelectableRange.LAST_IN_SET));
424: }
425:
426: public IntegerVector selectLess(TObject ob) {
427: if (ob.isNull()) {
428: return new IntegerVector(0);
429: }
430: return selectRange(new SelectableRange(
431: SelectableRange.AFTER_LAST_VALUE, TObject.nullVal(),
432: SelectableRange.BEFORE_FIRST_VALUE, ob));
433: }
434:
435: public IntegerVector selectGreaterOrEqual(TObject ob) {
436: if (ob.isNull()) {
437: return new IntegerVector(0);
438: }
439: return selectRange(new SelectableRange(
440: SelectableRange.FIRST_VALUE, ob,
441: SelectableRange.LAST_VALUE, SelectableRange.LAST_IN_SET));
442: }
443:
444: public IntegerVector selectLessOrEqual(TObject ob) {
445: if (ob.isNull()) {
446: return new IntegerVector(0);
447: }
448: return selectRange(new SelectableRange(
449: SelectableRange.AFTER_LAST_VALUE, TObject.nullVal(),
450: SelectableRange.LAST_VALUE, ob));
451: }
452:
453: // Inclusive of rows that are >= ob1 and < ob2
454: // NOTE: This is not compatible with SQL BETWEEN predicate which is all
455: // rows that are >= ob1 and <= ob2
456: public IntegerVector selectBetween(TObject ob1, TObject ob2) {
457: if (ob1.isNull() || ob2.isNull()) {
458: return new IntegerVector(0);
459: }
460: return selectRange(new SelectableRange(
461: SelectableRange.FIRST_VALUE, ob1,
462: SelectableRange.BEFORE_FIRST_VALUE, ob2));
463: }
464:
465: /**
466: * Selects the given range of values from this index. The SelectableRange
467: * must contain a 'start' value that compares <= to the 'end' value.
468: * <p>
469: * This must guarentee that the returned set is sorted from lowest to
470: * highest value.
471: */
472: abstract IntegerVector selectRange(SelectableRange range);
473:
474: /**
475: * Selects a set of ranges from this index. The ranges must not overlap and
476: * each range must contain a 'start' value that compares <= to the 'end'
477: * value. Every range in the array must represent a range that's lower than
478: * the preceeding range (if it exists).
479: * <p>
480: * If the above rules are enforced (as they must be) then this method will
481: * return a set that is sorted from lowest to highest value.
482: * <p>
483: * This must guarentee that the returned set is sorted from lowest to
484: * highest value.
485: */
486: abstract IntegerVector selectRange(SelectableRange[] ranges);
487:
488: }
|