TreeIndex


1   package prefuse.data.util;
2   
3   import java.util.Comparator  ;
4   
5   import prefuse.data.Table;
6   import prefuse.data.column.Column;
7   import prefuse.data.event.ColumnListener;
8   import prefuse.data.event.EventConstants;
9   import prefuse.data.event.TableListener;
10  import prefuse.util.collections.BooleanIntSortedMap;
11  import prefuse.util.collections.DoubleIntSortedMap;
12  import prefuse.util.collections.FloatIntSortedMap;
13  import prefuse.util.collections.IncompatibleComparatorException;
14  import prefuse.util.collections.IntIntSortedMap;
15  import prefuse.util.collections.IntIterator;
16  import prefuse.util.collections.IntSortedMap;
17  import prefuse.util.collections.LongIntSortedMap;
18  import prefuse.util.collections.ObjectIntSortedMap;
19  import prefuse.util.collections.SortedMapFactory;
20  
21  /**
22   * Index instance that uses red-black trees to provide an index
23   * over a column of data.
24   * 
25   * @author <a HREF="http://jheer.org">jeffrey heer</a>
26   */
27  public class TreeIndex implements Index, ColumnListener, TableListener {
28  
29      protected Table           m_table;
30      protected RowManager      m_rows;
31      protected Column          m_col;
32      protected IntSortedMap    m_index;
33      protected boolean         m_reindex;
34      protected int             m_colidx;
35      
36      /**
37       * Create a new TreeIndex.
38       * @param t the Table containing the data column to index
39       * @param rows the RowManager of the Table
40       * @param col the Column instance to index
41       * @param cmp the Comparator to use to sort data values
42       * @throws IncompatibleComparatorException if the comparator is not
43       * compatible with the column's data type
44       */
45      public TreeIndex(Table t, RowManager rows, Column col, Comparator   cmp)
46          throws IncompatibleComparatorException
47      {
48          m_table = t;
49          m_rows = rows;
50          m_col = col;
51          
52          m_index = SortedMapFactory.getMap(col.getColumnType(), cmp, false);
53          index();
54          
55          m_col.addColumnListener(this);
56          m_table.addTableListener(this);
57      }
58      
59      /**
60       * @see prefuse.data.util.Index#dispose()
61       */
62      public void dispose() {
63          m_col.removeColumnListener(this);
64          m_table.removeTableListener(this);
65      }
66      
67      /**
68       * @see prefuse.data.util.Index#getComparator()
69       */
70      public Comparator   getComparator() {
71          return m_index.comparator();
72      }
73      
74      /**
75       * @see prefuse.data.util.Index#size()
76       */
77      public int size() {
78          return m_index.size();
79      }
80      
81      private int getColumnIndex() {
82          if ( !(m_table.getColumn(m_colidx) == m_col) ) {
83              m_colidx = m_table.getColumnNumber(m_col);
84          }
85          return m_colidx;
86      }
87      
88      // ------------------------------------------------------------------------
89      // Index Update Methods
90  
91      /**
92       * @see prefuse.data.util.Index#index()
93       */
94      public void index() {
95          m_index.clear();
96   
97          // iterate over all valid values, adding them to the index
98          int idx = getColumnIndex();
99          m_colidx = idx;
100         IntIterator rows = m_rows.rows();
101         
102         if ( m_index instanceof IntIntSortedMap )
103         {
104             IntIntSortedMap map = (IntIntSortedMap)m_index;
105             while ( rows.hasNext() ) {
106                 int r = rows.nextInt();
107                 map.put(m_col.getInt(m_table.getColumnRow(r,idx)), r);
108             }
109         }
110         else if ( m_index instanceof LongIntSortedMap )
111         {
112             LongIntSortedMap map = (LongIntSortedMap)m_index;
113             while ( rows.hasNext() ) {
114                 int r = rows.nextInt();
115                 map.put(m_col.getLong(m_table.getColumnRow(r,idx)), r);
116             }
117         }
118         else if ( m_index instanceof FloatIntSortedMap )
119         {
120             FloatIntSortedMap map = (FloatIntSortedMap)m_index;
121             while ( rows.hasNext() ) {
122                 int r = rows.nextInt();
123                 map.put(m_col.getFloat(m_table.getColumnRow(r,idx)), r);
124             }
125         }
126         else if ( m_index instanceof DoubleIntSortedMap )
127         {
128             DoubleIntSortedMap map = (DoubleIntSortedMap)m_index;
129             while ( rows.hasNext() ) {
130                 int r = rows.nextInt();
131                 map.put(m_col.getDouble(m_table.getColumnRow(r,idx)), r);
132             }
133         }
134         else if ( m_index instanceof BooleanIntSortedMap )
135         {
136             BooleanIntSortedMap map = (BooleanIntSortedMap)m_index;
137             while ( rows.hasNext() ) {
138                 int r = rows.nextInt();
139                 map.put(m_col.getBoolean(m_table.getColumnRow(r,idx)), r);
140             }
141         }
142         else if ( m_index instanceof ObjectIntSortedMap )
143         {
144             ObjectIntSortedMap map = (ObjectIntSortedMap)m_index;
145             while ( rows.hasNext() ) {
146                 int r = rows.nextInt();
147                 map.put(m_col.get(m_table.getColumnRow(r,idx)), r);
148             }
149         }
150         else {
151             throw new IllegalStateException  ();
152         }
153         
154         m_reindex = false;
155     }
156 
157     // ------------------------------------------------------------------------
158     // Listener Methods
159     
160     /**
161      * @see prefuse.data.event.TableListener#tableChanged(prefuse.data.Table, int, int, int, int)
162      */
163     public void tableChanged(Table t, int start, int end, int col, int type) {
164         if ( type == EventConstants.UPDATE || t != m_table 
165               || col != EventConstants.ALL_COLUMNS )
166             return;
167         
168         boolean insert = (type==EventConstants.INSERT);
169         for ( int r=start; r<=end; ++r )
170             rowChanged(r, insert);
171     }
172     
173     private void rowChanged(int row, boolean insert) {
174         // make sure we access the right column value
175         int crow = m_rows.getColumnRow(row, getColumnIndex());
176         
177         if ( m_index instanceof IntIntSortedMap )
178         {
179             IntIntSortedMap map = (IntIntSortedMap)m_index;
180             int key = m_col.getInt(row);
181             if ( insert )
182                 map.put(key, row);
183             else
184                 map.remove(key, row);
185         }
186         else if ( m_index instanceof LongIntSortedMap )
187         {
188             LongIntSortedMap map = (LongIntSortedMap)m_index;
189             long key = m_col.getLong(crow);
190             if ( insert )
191                 map.put(key, row);
192             else
193                 map.remove(key, row);
194         }
195         else if ( m_index instanceof FloatIntSortedMap )
196         {
197             FloatIntSortedMap map = (FloatIntSortedMap)m_index;
198             float key = m_col.getFloat(crow);
199             if ( insert )
200                 map.put(key, row);
201             else
202                 map.remove(key, row);
203         }
204         else if ( m_index instanceof DoubleIntSortedMap )
205         {
206             DoubleIntSortedMap map = (DoubleIntSortedMap)m_index;
207             double key = m_col.getDouble(crow);
208             if ( insert )
209                 map.put(key, row);
210             else
211                 map.remove(key, row);
212         }
213         else if ( m_index instanceof BooleanIntSortedMap )
214         {
215             BooleanIntSortedMap map = (BooleanIntSortedMap)m_index;
216             boolean key = m_col.getBoolean(crow);
217             if ( insert )
218                 map.put(key, row);
219             else
220                 map.remove(key, row);
221         }
222         else if ( m_index instanceof ObjectIntSortedMap )
223         {
224             ObjectIntSortedMap map = (ObjectIntSortedMap)m_index;
225             Object   key = m_col.get(crow);
226             if ( insert )
227                 map.put(key, row);
228             else
229                 map.remove(key, row);
230         }
231         else {
232             throw new IllegalStateException  ();
233         }        
234     }
235 
236     /**
237      * @see prefuse.data.event.ColumnListener#columnChanged(prefuse.data.column.Column, int, int, int)
238      */
239     public void columnChanged(Column src, int type, int start, int end) {
240         m_reindex = true;
241     }    
242     
243     /**
244      * @see prefuse.data.event.ColumnListener#columnChanged(prefuse.data.column.Column, int, boolean)
245      */
246     public void columnChanged(Column src, int idx, boolean prev) {
247         int row = m_rows.getTableRow(idx, getColumnIndex());
248         if ( row < 0 ) return; // invalid row value
249         ((BooleanIntSortedMap)m_index).remove(prev, row);
250         ((BooleanIntSortedMap)m_index).put(src.getBoolean(idx), row);
251     }
252 
253     /**
254      * @see prefuse.data.event.ColumnListener#columnChanged(prefuse.data.column.Column, int, int)
255      */
256     public void columnChanged(Column src, int idx, int prev) {
257         int row = m_rows.getTableRow(idx, getColumnIndex());
258         if ( row < 0 ) return; // invalid row value
259         ((IntIntSortedMap)m_index).remove(prev, row);
260         ((IntIntSortedMap)m_index).put(src.getInt(idx), row);
261     }
262     
263     /**
264      * @see prefuse.data.event.ColumnListener#columnChanged(prefuse.data.column.Column, int, long)
265      */
266     public void columnChanged(Column src, int idx, long prev) {
267         int row = m_rows.getTableRow(idx, getColumnIndex());
268         if ( row < 0 ) return; // invalid row value
269         ((LongIntSortedMap)m_index).remove(prev, row);
270         ((LongIntSortedMap)m_index).put(src.getLong(idx), row);
271     }
272     
273     /**
274      * @see prefuse.data.event.ColumnListener#columnChanged(prefuse.data.column.Column, int, float)
275      */
276     public void columnChanged(Column src, int idx, float prev) {
277         int row = m_rows.getTableRow(idx, getColumnIndex());
278         if ( row < 0 ) return; // invalid row value
279         ((FloatIntSortedMap)m_index).remove(prev, row);
280         ((FloatIntSortedMap)m_index).put(src.getFloat(idx), row);
281     }
282     
283     /**
284      * @see prefuse.data.event.ColumnListener#columnChanged(prefuse.data.column.Column, int, double)
285      */
286     public void columnChanged(Column src, int idx, double prev) {
287         int row = m_rows.getTableRow(idx, getColumnIndex());
288         if ( row < 0 ) return; // invalid row value
289         ((DoubleIntSortedMap)m_index).remove(prev, row);
290         ((DoubleIntSortedMap)m_index).put(src.getDouble(idx), row);
291     }
292 
293     /**
294      * @see prefuse.data.event.ColumnListener#columnChanged(prefuse.data.column.Column, int, java.lang.Object)
295      */
296     public void columnChanged(Column src, int idx, Object   prev) {
297         int row = m_rows.getTableRow(idx, getColumnIndex());
298         if ( row < 0 ) return; // invalid row value
299         ((ObjectIntSortedMap)m_index).remove(prev, row);
300         ((ObjectIntSortedMap)m_index).put(src.get(idx), row);
301     }
302 
303     // ------------------------------------------------------------------------
304     // Retrieval Methods
305     
306     /**
307      * @see prefuse.data.util.Index#minimum()
308      */
309     public int minimum() {
310         return m_index.getMinimum();
311     }
312     
313     /**
314      * @see prefuse.data.util.Index#maximum()
315      */
316     public int maximum() {
317         return m_index.getMaximum();
318     }
319     
320     /**
321      * @see prefuse.data.util.Index#median()
322      */
323     public int median() {
324         return m_index.getMedian();
325     }
326     
327     /**
328      * @see prefuse.data.util.Index#uniqueCount()
329      */
330     public int uniqueCount() {
331         return m_index.getUniqueCount();
332     }
333     
334     // ------------------------------------------------------------------------
335     
336     /**
337      * @see prefuse.data.util.Index#allRows(int)
338      */
339     public IntIterator allRows(int type) {
340         boolean ascending = (type & Index.TYPE_ASCENDING) > 0;
341         return m_index.valueIterator(ascending);
342     }
343     
344     /**
345      * @see prefuse.data.util.Index#rows(java.lang.Object, java.lang.Object, int)
346      */
347     public IntIterator rows(Object   lo, Object   hi, int type) {
348         if ( !(m_index instanceof ObjectIntSortedMap) )
349             throw new IllegalStateException  ();
350 
351         boolean reverse = (type & Index.TYPE_DESCENDING) > 0;
352         boolean linc = (type & Index.TYPE_LEFT_INCLUSIVE) > 0;
353         boolean hinc = (type & Index.TYPE_RIGHT_INCLUSIVE) > 0;
354         
355         if ( lo == null ) lo = ObjectIntSortedMap.MIN_KEY;
356         if ( hi == null ) hi = ObjectIntSortedMap.MAX_KEY;
357         
358         ObjectIntSortedMap index = (ObjectIntSortedMap)m_index;
359         if ( reverse ) {
360             return index.valueRangeIterator(hi, hinc, lo, linc);
361         } else {
362             return index.valueRangeIterator(lo, linc, hi, hinc);
363         }
364     }
365     
366     /**
367      * @see prefuse.data.util.Index#rows(int, int, int)
368      */
369     public IntIterator rows(int lo, int hi, int type) {
370         if ( !(m_index instanceof IntIntSortedMap) )
371             throw new IllegalStateException  ();
372 
373         boolean reverse = (type & Index.TYPE_DESCENDING) > 0;
374         boolean linc = (type & Index.TYPE_LEFT_INCLUSIVE) > 0;
375         boolean hinc = (type & Index.TYPE_RIGHT_INCLUSIVE) > 0;
376         
377         IntIntSortedMap index = (IntIntSortedMap)m_index;
378         if ( reverse ) {
379             return index.valueRangeIterator(hi, hinc, lo, linc);
380         } else {
381             return index.valueRangeIterator(lo, linc, hi, hinc);
382         }
383     }
384     
385     /**
386      * @see prefuse.data.util.Index#rows(long, long, int)
387      */
388     public IntIterator rows(long lo, long hi, int type) {
389         if ( !(m_index instanceof LongIntSortedMap) )
390             throw new IllegalStateException  ();
391         
392         boolean reverse = (type & Index.TYPE_DESCENDING) > 0;
393         boolean linc = (type & Index.TYPE_LEFT_INCLUSIVE) > 0;
394         boolean hinc = (type & Index.TYPE_RIGHT_INCLUSIVE) > 0;
395         
396         LongIntSortedMap index = (LongIntSortedMap)m_index;
397         if ( reverse ) {
398             return index.valueRangeIterator(hi, hinc, lo, linc);
399         } else {
400             return index.valueRangeIterator(lo, linc, hi, hinc);
401         }
402     }
403     
404     /**
405      * @see prefuse.data.util.Index#rows(float, float, int)
406      */
407     public IntIterator rows(float lo, float hi, int type) {
408         if ( !(m_index instanceof FloatIntSortedMap) )
409             throw new IllegalStateException  ();
410         
411         boolean reverse = (type & Index.TYPE_DESCENDING) > 0;
412         boolean linc = (type & Index.TYPE_LEFT_INCLUSIVE) > 0;
413         boolean hinc = (type & Index.TYPE_RIGHT_INCLUSIVE) > 0;
414         
415         FloatIntSortedMap index = (FloatIntSortedMap)m_index;
416         if ( reverse ) {
417             return index.valueRangeIterator(hi, hinc, lo, linc);
418         } else {
419             return index.valueRangeIterator(lo, linc, hi, hinc);
420         }
421     }
422     
423     /**
424      * @see prefuse.data.util.Index#rows(double, double, int)
425      */
426     public IntIterator rows(double lo, double hi, int type) {
427         if ( !(m_index instanceof DoubleIntSortedMap) )
428             throw new IllegalStateException  ();
429         
430         boolean reverse = (type & Index.TYPE_DESCENDING) > 0;
431         boolean linc = (type & Index.TYPE_LEFT_INCLUSIVE) > 0;
432         boolean hinc = (type & Index.TYPE_RIGHT_INCLUSIVE) > 0;
433         
434         DoubleIntSortedMap index = (DoubleIntSortedMap)m_index;
435         if ( reverse ) {
436             return index.valueRangeIterator(hi, hinc, lo, linc);
437         } else {
438             return index.valueRangeIterator(lo, linc, hi, hinc);
439         }
440     }
441 
442     // ------------------------------------------------------------------------
443     
444     /**
445      * @see prefuse.data.util.Index#rows(int)
446      */
447     public IntIterator rows(int val) {
448         return rows(val, val, Index.TYPE_AII);
449     }
450     
451     /**
452      * @see prefuse.data.util.Index#rows(long)
453      */
454     public IntIterator rows(long val) {
455         return rows(val, val, Index.TYPE_AII);
456     }
457     
458     /**
459      * @see prefuse.data.util.Index#rows(float)
460      */
461     public IntIterator rows(float val) {
462         return rows(val, val, Index.TYPE_AII);
463     }
464     
465     /**
466      * @see prefuse.data.util.Index#rows(double)
467      */
468     public IntIterator rows(double val) {
469         return rows(val, val, Index.TYPE_AII);
470     }
471     
472     /**
473      * @see prefuse.data.util.Index#rows(boolean)
474      */
475     public IntIterator rows(boolean val) {
476         if ( !(m_index instanceof BooleanIntSortedMap) )
477             throw new IllegalStateException  ();
478         
479         BooleanIntSortedMap index = (BooleanIntSortedMap)m_index;
480         return index.valueRangeIterator(val, true, val, true);
481     }
482     
483     /**
484      * @see prefuse.data.util.Index#rows(java.lang.Object)
485      */
486     public IntIterator rows(Object   val) {
487         return rows(val, val, Index.TYPE_AII);
488     }
489     
490     // ------------------------------------------------------------------------
491     
492     /**
493      * @see prefuse.data.util.Index#get(double)
494      */
495     public int get(double x) {
496         DoubleIntSortedMap index = (DoubleIntSortedMap)m_index;
497         return index.get(x);
498     }
499 
500     /**
501      * @see prefuse.data.util.Index#get(float)
502      */
503     public int get(float x) {
504         FloatIntSortedMap index = (FloatIntSortedMap)m_index;
505         return index.get(x);
506     }
507 
508     /**
509      * @see prefuse.data.util.Index#get(int)
510      */
511     public int get(int x) {
512         IntIntSortedMap index = (IntIntSortedMap)m_index;
513         return index.get(x);
514     }
515 
516     /**
517      * @see prefuse.data.util.Index#get(long)
518      */
519     public int get(long x) {
520         LongIntSortedMap index = (LongIntSortedMap)m_index;
521         return index.get(x);
522     }
523 
524     /**
525      * @see prefuse.data.util.Index#get(java.lang.Object)
526      */
527     public int get(Object   x) {
528         ObjectIntSortedMap index = (ObjectIntSortedMap)m_index;
529         return index.get(x);
530     }
531 
532 } // end of class ColumnIndex
533
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags