InsertSearch


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