001: /**
002: * com.mckoi.database.InsertSearch 14 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.BlockIntegerList;
027: import com.mckoi.util.IntegerListInterface;
028: import com.mckoi.util.IndexComparator;
029: import com.mckoi.util.IntegerIterator;
030: import java.util.Comparator;
031: import java.util.Arrays;
032: import java.io.*;
033:
034: /**
035: * This is a SelectableScheme similar in some ways to the binary tree. When
036: * a new row is added, it is inserted into a sorted list of rows. We can then
037: * use this list to select out the sorted list of elements.
038: * <p>
039: * This requires less memory than the BinaryTree, however it is not as fast.
040: * Even though, it should still perform fairly well on medium size data sets.
041: * On large size data sets, insert and remove performance may suffer.
042: * <p>
043: * This object retains knowledge of all set elements unlike BlindSearch which
044: * has no memory overhead.
045: * <p>
046: * Performance should be very comparable to BinaryTree for sets that aren't
047: * altered much.
048: *
049: * @author Tobias Downer
050: */
051:
052: public final class InsertSearch extends CollatedBaseSearch {
053:
054: /**
055: * The sorted list of rows in this set. This is sorted from min to max
056: * (not sorted by row number - sorted by entity row value).
057: */
058: private IntegerListInterface set_list;
059:
060: /**
061: * If this is true, then this SelectableScheme records additional rid
062: * information that can be used to very quickly identify whether a value is
063: * greater, equal or less.
064: */
065: boolean RECORD_UID;
066:
067: /**
068: * The IndexComparator that we use to refer elements in the set to actual
069: * data objects.
070: */
071: private IndexComparator set_comparator;
072:
073: // ----- DEBUGGING -----
074:
075: /**
076: * If this is immutable, this stores the number of entries in 'set_list'
077: * when this object was made.
078: */
079: private int DEBUG_immutable_set_size;
080:
081: /**
082: * The Constructor.
083: */
084: public InsertSearch(TableDataSource table, int column) {
085: super (table, column);
086: set_list = new BlockIntegerList();
087:
088: // The internal comparator that enables us to sort and lookup on the data
089: // in this column.
090: setupComparator();
091: }
092:
093: /**
094: * Constructor sets the scheme with a pre-sorted list. The Vector 'vec'
095: * should not be used again after this is called. 'vec' must be sorted from
096: * low key to high key.
097: */
098: public InsertSearch(TableDataSource table, int column,
099: IntegerVector vec) {
100: this (table, column);
101: for (int i = 0; i < vec.size(); ++i) {
102: set_list.add(vec.intAt(i));
103: }
104:
105: // NOTE: This must be removed in final, this is a post condition check to
106: // make sure 'vec' is infact sorted
107: checkSchemeSorted();
108:
109: }
110:
111: /**
112: * Constructor sets the scheme with a pre-sorted list. The list 'list'
113: * should not be used again after this is called. 'list' must be sorted from
114: * low key to high key.
115: */
116: InsertSearch(TableDataSource table, int column,
117: IntegerListInterface list) {
118: this (table, column);
119: this .set_list = list;
120:
121: // NOTE: This must be removed in final, this is a post condition check to
122: // make sure 'vec' is infact sorted
123: checkSchemeSorted();
124:
125: }
126:
127: /**
128: * Constructs this as a copy of the given, either mutable or immutable
129: * copy.
130: */
131: private InsertSearch(TableDataSource table, InsertSearch from,
132: boolean immutable) {
133: super (table, from.getColumn());
134:
135: if (immutable) {
136: setImmutable();
137: }
138:
139: if (immutable) {
140: // Immutable is a shallow copy
141: set_list = from.set_list;
142: DEBUG_immutable_set_size = set_list.size();
143: } else {
144: set_list = new BlockIntegerList(from.set_list);
145: }
146:
147: // Do we generate lookup caches?
148: RECORD_UID = from.RECORD_UID;
149:
150: // The internal comparator that enables us to sort and lookup on the data
151: // in this column.
152: setupComparator();
153:
154: }
155:
156: /**
157: * Sets the internal comparator that enables us to sort and lookup on the
158: * data in this column.
159: */
160: private void setupComparator() {
161: set_comparator = new IndexComparator() {
162:
163: private int internalCompare(int index, TObject cell2) {
164: TObject cell1 = getCellContents(index);
165: return cell1.compareTo(cell2);
166: }
167:
168: public int compare(int index, Object val) {
169: return internalCompare(index, (TObject) val);
170: }
171:
172: public int compare(int index1, int index2) {
173: TObject cell = getCellContents(index2);
174: return internalCompare(index1, cell);
175: }
176: };
177: }
178:
179: /**
180: * Inserts a row into the list. This will always be thread safe, table
181: * changes cause a write lock which prevents reads while we are writing to
182: * the table.
183: */
184: public void insert(int row) {
185: if (isImmutable()) {
186: throw new Error("Tried to change an immutable scheme.");
187: }
188:
189: final TObject cell = getCellContents(row);
190: set_list.insertSort(cell, row, set_comparator);
191:
192: }
193:
194: /**
195: * Removes a row from the list. This will always be thread safe, table
196: * changes cause a write lock which prevents reads while we are writing to
197: * the table.
198: */
199: public void remove(int row) {
200: if (isImmutable()) {
201: throw new Error("Tried to change an immutable scheme.");
202: }
203:
204: TObject cell = getCellContents(row);
205: int removed = set_list.removeSort(cell, row, set_comparator);
206:
207: if (removed != row) {
208: throw new Error(
209: "Removed value different than row asked to remove. "
210: + "To remove: " + row + " Removed: "
211: + removed);
212: }
213:
214: }
215:
216: /**
217: * This needs to be called to access 'set_comparator' in thread busy
218: * methods. Because creating a UID cache will modify set_comparator, we
219: * need to make sure we access this variable safely.
220: * <p>
221: * NOTE: This is a throwback method for an idea I had to speed up the
222: * 'select*' methods, but it proved unworkable. The reason being that
223: * the UID only contains knowledge of relations between rows, and the
224: * 'select*' methods find the relationship of a TObject in the column
225: * set.
226: */
227: private final IndexComparator safeSetComparator() {
228: // synchronized (uid_lock) {
229: return set_comparator;
230: // }
231: }
232:
233: /**
234: * Reads the entire state of the scheme from the input stream. Throws an
235: * exception if the scheme is not empty.
236: */
237: public void readFrom(InputStream in) throws IOException {
238: if (set_list.size() != 0) {
239: throw new RuntimeException(
240: "Error reading scheme, already a set in the Scheme");
241: }
242: DataInputStream din = new DataInputStream(in);
243: int vec_size = din.readInt();
244:
245: int row_count = getTable().getRowCount();
246: // Check we read in as many indices as there are rows in the table
247: if (row_count != vec_size) {
248: throw new IOException(
249: "Different table row count to indices in scheme. "
250: + "table=" + row_count + ", vec_size="
251: + vec_size);
252: }
253:
254: for (int i = 0; i < vec_size; ++i) {
255: int row = din.readInt();
256: if (row < 0) { // || row >= row_count) {
257: set_list = new BlockIntegerList();
258: throw new IOException(
259: "Scheme contains out of table bounds index.");
260: }
261: set_list.add(row);
262: }
263:
264: getSystem().stats().add(vec_size,
265: "{session} InsertSearch.read_indices");
266:
267: // NOTE: This must be removed in final, this is a post condition check to
268: // make sure 'vec' is infact sorted
269: checkSchemeSorted();
270: }
271:
272: /**
273: * Writes the entire state of the scheme to the output stream.
274: */
275: public void writeTo(OutputStream out) throws IOException {
276: DataOutputStream dout = new DataOutputStream(out);
277: int list_size = set_list.size();
278: dout.writeInt(list_size);
279:
280: IntegerIterator i = set_list.iterator(0, list_size - 1);
281: while (i.hasNext()) {
282: dout.writeInt(i.next());
283: }
284: }
285:
286: /**
287: * Returns an exact copy of this scheme including any optimization
288: * information. The copied scheme is identical to the original but does not
289: * share any parts. Modifying any part of the copied scheme will have no
290: * effect on the original and vice versa.
291: */
292: public SelectableScheme copy(TableDataSource table,
293: boolean immutable) {
294: // ASSERTION: If immutable, check the size of the current set is equal to
295: // when the scheme was created.
296: if (isImmutable()) {
297: if (DEBUG_immutable_set_size != set_list.size()) {
298: throw new Error(
299: "Assert failed: "
300: + "Immutable set size is different from when created.");
301: }
302: }
303:
304: // We must create a new InsertSearch object and copy all the state
305: // information from this object to the new one.
306: return new InsertSearch(table, this , immutable);
307: }
308:
309: /**
310: * Disposes this scheme.
311: */
312: public void dispose() {
313: // Close and invalidate.
314: set_list = null;
315: set_comparator = null;
316: }
317:
318: /**
319: * Checks that the scheme is in sorted order. This is a debug check to
320: * ensure we maintain a sorted index.
321: * NOTE: This *MUST* be removed in a release version because it uses up
322: * many cycles for each check.
323: */
324: private void checkSchemeSorted() {
325: // int list_size = set_list.size();
326: // DataCell last_cell = null;
327: // for (int i = 0; i < list_size; ++i) {
328: // int row = set_list.intAt(i);
329: // DataCell this_cell = getCellContents(row);
330: // if (last_cell != null) {
331: // if (this_cell.compareTo(last_cell) < 0) {
332: // throw new Error("checkSchemeSorted failed. Corrupt index.");
333: // }
334: // }
335: // last_cell = this_cell;
336: // }
337: // if (Debug().isInterestedIn(Lvl.WARNING)) {
338: // StringBuffer info_string = new StringBuffer();
339: // info_string.append("POST CONDITION CHECK - Checked index of size: ");
340: // info_string.append(list_size);
341: // info_string.append(". Sorted correctly (REMOVE THIS CHECK IN FINAL)");
342: // Debug().write(Lvl.WARNING, this, new String(info_string));
343: // }
344: }
345:
346: // ---------- Implemented/Overwritten from CollatedBaseSearch ----------
347:
348: protected int searchFirst(TObject val) {
349: return set_list.searchFirst(val, safeSetComparator());
350: }
351:
352: protected int searchLast(TObject val) {
353: return set_list.searchLast(val, safeSetComparator());
354: }
355:
356: protected int setSize() {
357: return set_list.size();
358: }
359:
360: protected TObject firstInCollationOrder() {
361: return getCellContents(set_list.get(0));
362: }
363:
364: protected TObject lastInCollationOrder() {
365: return getCellContents(set_list.get(setSize() - 1));
366: }
367:
368: protected IntegerVector addRangeToSet(int start, int end,
369: IntegerVector ivec) {
370: if (ivec == null) {
371: ivec = new IntegerVector((end - start) + 2);
372: }
373: IntegerIterator i = set_list.iterator(start, end);
374: while (i.hasNext()) {
375: ivec.addInt(i.next());
376: }
377: return ivec;
378: }
379:
380: /**
381: * The select operations for this scheme.
382: */
383:
384: public IntegerVector selectAll() {
385: IntegerVector ivec = new IntegerVector(set_list);
386: return ivec;
387: }
388:
389: }
|