001: package prefuse.data.util;
002:
003: import java.util.Comparator;
004:
005: import prefuse.data.Table;
006: import prefuse.data.column.Column;
007: import prefuse.data.event.ColumnListener;
008: import prefuse.data.event.EventConstants;
009: import prefuse.data.event.TableListener;
010: import prefuse.util.collections.BooleanIntSortedMap;
011: import prefuse.util.collections.DoubleIntSortedMap;
012: import prefuse.util.collections.FloatIntSortedMap;
013: import prefuse.util.collections.IncompatibleComparatorException;
014: import prefuse.util.collections.IntIntSortedMap;
015: import prefuse.util.collections.IntIterator;
016: import prefuse.util.collections.IntSortedMap;
017: import prefuse.util.collections.LongIntSortedMap;
018: import prefuse.util.collections.ObjectIntSortedMap;
019: import prefuse.util.collections.SortedMapFactory;
020:
021: /**
022: * Index instance that uses red-black trees to provide an index
023: * over a column of data.
024: *
025: * @author <a href="http://jheer.org">jeffrey heer</a>
026: */
027: public class TreeIndex implements Index, ColumnListener, TableListener {
028:
029: protected Table m_table;
030: protected RowManager m_rows;
031: protected Column m_col;
032: protected IntSortedMap m_index;
033: protected boolean m_reindex;
034: protected int m_colidx;
035:
036: /**
037: * Create a new TreeIndex.
038: * @param t the Table containing the data column to index
039: * @param rows the RowManager of the Table
040: * @param col the Column instance to index
041: * @param cmp the Comparator to use to sort data values
042: * @throws IncompatibleComparatorException if the comparator is not
043: * compatible with the column's data type
044: */
045: public TreeIndex(Table t, RowManager rows, Column col,
046: Comparator cmp) throws IncompatibleComparatorException {
047: m_table = t;
048: m_rows = rows;
049: m_col = col;
050:
051: m_index = SortedMapFactory.getMap(col.getColumnType(), cmp,
052: false);
053: index();
054:
055: m_col.addColumnListener(this );
056: m_table.addTableListener(this );
057: }
058:
059: /**
060: * @see prefuse.data.util.Index#dispose()
061: */
062: public void dispose() {
063: m_col.removeColumnListener(this );
064: m_table.removeTableListener(this );
065: }
066:
067: /**
068: * @see prefuse.data.util.Index#getComparator()
069: */
070: public Comparator getComparator() {
071: return m_index.comparator();
072: }
073:
074: /**
075: * @see prefuse.data.util.Index#size()
076: */
077: public int size() {
078: return m_index.size();
079: }
080:
081: private int getColumnIndex() {
082: if (!(m_table.getColumn(m_colidx) == m_col)) {
083: m_colidx = m_table.getColumnNumber(m_col);
084: }
085: return m_colidx;
086: }
087:
088: // ------------------------------------------------------------------------
089: // Index Update Methods
090:
091: /**
092: * @see prefuse.data.util.Index#index()
093: */
094: public void index() {
095: m_index.clear();
096:
097: // iterate over all valid values, adding them to the index
098: int idx = getColumnIndex();
099: m_colidx = idx;
100: IntIterator rows = m_rows.rows();
101:
102: if (m_index instanceof IntIntSortedMap) {
103: IntIntSortedMap map = (IntIntSortedMap) m_index;
104: while (rows.hasNext()) {
105: int r = rows.nextInt();
106: map.put(m_col.getInt(m_table.getColumnRow(r, idx)), r);
107: }
108: } else if (m_index instanceof LongIntSortedMap) {
109: LongIntSortedMap map = (LongIntSortedMap) m_index;
110: while (rows.hasNext()) {
111: int r = rows.nextInt();
112: map.put(m_col.getLong(m_table.getColumnRow(r, idx)), r);
113: }
114: } else if (m_index instanceof FloatIntSortedMap) {
115: FloatIntSortedMap map = (FloatIntSortedMap) m_index;
116: while (rows.hasNext()) {
117: int r = rows.nextInt();
118: map
119: .put(m_col.getFloat(m_table
120: .getColumnRow(r, idx)), r);
121: }
122: } else if (m_index instanceof DoubleIntSortedMap) {
123: DoubleIntSortedMap map = (DoubleIntSortedMap) m_index;
124: while (rows.hasNext()) {
125: int r = rows.nextInt();
126: map.put(m_col.getDouble(m_table.getColumnRow(r, idx)),
127: r);
128: }
129: } else if (m_index instanceof BooleanIntSortedMap) {
130: BooleanIntSortedMap map = (BooleanIntSortedMap) m_index;
131: while (rows.hasNext()) {
132: int r = rows.nextInt();
133: map.put(m_col.getBoolean(m_table.getColumnRow(r, idx)),
134: r);
135: }
136: } else if (m_index instanceof ObjectIntSortedMap) {
137: ObjectIntSortedMap map = (ObjectIntSortedMap) m_index;
138: while (rows.hasNext()) {
139: int r = rows.nextInt();
140: map.put(m_col.get(m_table.getColumnRow(r, idx)), r);
141: }
142: } else {
143: throw new IllegalStateException();
144: }
145:
146: m_reindex = false;
147: }
148:
149: // ------------------------------------------------------------------------
150: // Listener Methods
151:
152: /**
153: * @see prefuse.data.event.TableListener#tableChanged(prefuse.data.Table, int, int, int, int)
154: */
155: public void tableChanged(Table t, int start, int end, int col,
156: int type) {
157: if (type == EventConstants.UPDATE || t != m_table
158: || col != EventConstants.ALL_COLUMNS)
159: return;
160:
161: boolean insert = (type == EventConstants.INSERT);
162: for (int r = start; r <= end; ++r)
163: rowChanged(r, insert);
164: }
165:
166: private void rowChanged(int row, boolean insert) {
167: // make sure we access the right column value
168: int crow = m_rows.getColumnRow(row, getColumnIndex());
169:
170: if (m_index instanceof IntIntSortedMap) {
171: IntIntSortedMap map = (IntIntSortedMap) m_index;
172: int key = m_col.getInt(row);
173: if (insert)
174: map.put(key, row);
175: else
176: map.remove(key, row);
177: } else if (m_index instanceof LongIntSortedMap) {
178: LongIntSortedMap map = (LongIntSortedMap) m_index;
179: long key = m_col.getLong(crow);
180: if (insert)
181: map.put(key, row);
182: else
183: map.remove(key, row);
184: } else if (m_index instanceof FloatIntSortedMap) {
185: FloatIntSortedMap map = (FloatIntSortedMap) m_index;
186: float key = m_col.getFloat(crow);
187: if (insert)
188: map.put(key, row);
189: else
190: map.remove(key, row);
191: } else if (m_index instanceof DoubleIntSortedMap) {
192: DoubleIntSortedMap map = (DoubleIntSortedMap) m_index;
193: double key = m_col.getDouble(crow);
194: if (insert)
195: map.put(key, row);
196: else
197: map.remove(key, row);
198: } else if (m_index instanceof BooleanIntSortedMap) {
199: BooleanIntSortedMap map = (BooleanIntSortedMap) m_index;
200: boolean key = m_col.getBoolean(crow);
201: if (insert)
202: map.put(key, row);
203: else
204: map.remove(key, row);
205: } else if (m_index instanceof ObjectIntSortedMap) {
206: ObjectIntSortedMap map = (ObjectIntSortedMap) m_index;
207: Object key = m_col.get(crow);
208: if (insert)
209: map.put(key, row);
210: else
211: map.remove(key, row);
212: } else {
213: throw new IllegalStateException();
214: }
215: }
216:
217: /**
218: * @see prefuse.data.event.ColumnListener#columnChanged(prefuse.data.column.Column, int, int, int)
219: */
220: public void columnChanged(Column src, int type, int start, int end) {
221: m_reindex = true;
222: }
223:
224: /**
225: * @see prefuse.data.event.ColumnListener#columnChanged(prefuse.data.column.Column, int, boolean)
226: */
227: public void columnChanged(Column src, int idx, boolean prev) {
228: int row = m_rows.getTableRow(idx, getColumnIndex());
229: if (row < 0)
230: return; // invalid row value
231: ((BooleanIntSortedMap) m_index).remove(prev, row);
232: ((BooleanIntSortedMap) m_index).put(src.getBoolean(idx), row);
233: }
234:
235: /**
236: * @see prefuse.data.event.ColumnListener#columnChanged(prefuse.data.column.Column, int, int)
237: */
238: public void columnChanged(Column src, int idx, int prev) {
239: int row = m_rows.getTableRow(idx, getColumnIndex());
240: if (row < 0)
241: return; // invalid row value
242: ((IntIntSortedMap) m_index).remove(prev, row);
243: ((IntIntSortedMap) m_index).put(src.getInt(idx), row);
244: }
245:
246: /**
247: * @see prefuse.data.event.ColumnListener#columnChanged(prefuse.data.column.Column, int, long)
248: */
249: public void columnChanged(Column src, int idx, long prev) {
250: int row = m_rows.getTableRow(idx, getColumnIndex());
251: if (row < 0)
252: return; // invalid row value
253: ((LongIntSortedMap) m_index).remove(prev, row);
254: ((LongIntSortedMap) m_index).put(src.getLong(idx), row);
255: }
256:
257: /**
258: * @see prefuse.data.event.ColumnListener#columnChanged(prefuse.data.column.Column, int, float)
259: */
260: public void columnChanged(Column src, int idx, float prev) {
261: int row = m_rows.getTableRow(idx, getColumnIndex());
262: if (row < 0)
263: return; // invalid row value
264: ((FloatIntSortedMap) m_index).remove(prev, row);
265: ((FloatIntSortedMap) m_index).put(src.getFloat(idx), row);
266: }
267:
268: /**
269: * @see prefuse.data.event.ColumnListener#columnChanged(prefuse.data.column.Column, int, double)
270: */
271: public void columnChanged(Column src, int idx, double prev) {
272: int row = m_rows.getTableRow(idx, getColumnIndex());
273: if (row < 0)
274: return; // invalid row value
275: ((DoubleIntSortedMap) m_index).remove(prev, row);
276: ((DoubleIntSortedMap) m_index).put(src.getDouble(idx), row);
277: }
278:
279: /**
280: * @see prefuse.data.event.ColumnListener#columnChanged(prefuse.data.column.Column, int, java.lang.Object)
281: */
282: public void columnChanged(Column src, int idx, Object prev) {
283: int row = m_rows.getTableRow(idx, getColumnIndex());
284: if (row < 0)
285: return; // invalid row value
286: ((ObjectIntSortedMap) m_index).remove(prev, row);
287: ((ObjectIntSortedMap) m_index).put(src.get(idx), row);
288: }
289:
290: // ------------------------------------------------------------------------
291: // Retrieval Methods
292:
293: /**
294: * @see prefuse.data.util.Index#minimum()
295: */
296: public int minimum() {
297: return m_index.getMinimum();
298: }
299:
300: /**
301: * @see prefuse.data.util.Index#maximum()
302: */
303: public int maximum() {
304: return m_index.getMaximum();
305: }
306:
307: /**
308: * @see prefuse.data.util.Index#median()
309: */
310: public int median() {
311: return m_index.getMedian();
312: }
313:
314: /**
315: * @see prefuse.data.util.Index#uniqueCount()
316: */
317: public int uniqueCount() {
318: return m_index.getUniqueCount();
319: }
320:
321: // ------------------------------------------------------------------------
322:
323: /**
324: * @see prefuse.data.util.Index#allRows(int)
325: */
326: public IntIterator allRows(int type) {
327: boolean ascending = (type & Index.TYPE_ASCENDING) > 0;
328: return m_index.valueIterator(ascending);
329: }
330:
331: /**
332: * @see prefuse.data.util.Index#rows(java.lang.Object, java.lang.Object, int)
333: */
334: public IntIterator rows(Object lo, Object hi, int type) {
335: if (!(m_index instanceof ObjectIntSortedMap))
336: throw new IllegalStateException();
337:
338: boolean reverse = (type & Index.TYPE_DESCENDING) > 0;
339: boolean linc = (type & Index.TYPE_LEFT_INCLUSIVE) > 0;
340: boolean hinc = (type & Index.TYPE_RIGHT_INCLUSIVE) > 0;
341:
342: if (lo == null)
343: lo = ObjectIntSortedMap.MIN_KEY;
344: if (hi == null)
345: hi = ObjectIntSortedMap.MAX_KEY;
346:
347: ObjectIntSortedMap index = (ObjectIntSortedMap) m_index;
348: if (reverse) {
349: return index.valueRangeIterator(hi, hinc, lo, linc);
350: } else {
351: return index.valueRangeIterator(lo, linc, hi, hinc);
352: }
353: }
354:
355: /**
356: * @see prefuse.data.util.Index#rows(int, int, int)
357: */
358: public IntIterator rows(int lo, int hi, int type) {
359: if (!(m_index instanceof IntIntSortedMap))
360: throw new IllegalStateException();
361:
362: boolean reverse = (type & Index.TYPE_DESCENDING) > 0;
363: boolean linc = (type & Index.TYPE_LEFT_INCLUSIVE) > 0;
364: boolean hinc = (type & Index.TYPE_RIGHT_INCLUSIVE) > 0;
365:
366: IntIntSortedMap index = (IntIntSortedMap) m_index;
367: if (reverse) {
368: return index.valueRangeIterator(hi, hinc, lo, linc);
369: } else {
370: return index.valueRangeIterator(lo, linc, hi, hinc);
371: }
372: }
373:
374: /**
375: * @see prefuse.data.util.Index#rows(long, long, int)
376: */
377: public IntIterator rows(long lo, long hi, int type) {
378: if (!(m_index instanceof LongIntSortedMap))
379: throw new IllegalStateException();
380:
381: boolean reverse = (type & Index.TYPE_DESCENDING) > 0;
382: boolean linc = (type & Index.TYPE_LEFT_INCLUSIVE) > 0;
383: boolean hinc = (type & Index.TYPE_RIGHT_INCLUSIVE) > 0;
384:
385: LongIntSortedMap index = (LongIntSortedMap) m_index;
386: if (reverse) {
387: return index.valueRangeIterator(hi, hinc, lo, linc);
388: } else {
389: return index.valueRangeIterator(lo, linc, hi, hinc);
390: }
391: }
392:
393: /**
394: * @see prefuse.data.util.Index#rows(float, float, int)
395: */
396: public IntIterator rows(float lo, float hi, int type) {
397: if (!(m_index instanceof FloatIntSortedMap))
398: throw new IllegalStateException();
399:
400: boolean reverse = (type & Index.TYPE_DESCENDING) > 0;
401: boolean linc = (type & Index.TYPE_LEFT_INCLUSIVE) > 0;
402: boolean hinc = (type & Index.TYPE_RIGHT_INCLUSIVE) > 0;
403:
404: FloatIntSortedMap index = (FloatIntSortedMap) m_index;
405: if (reverse) {
406: return index.valueRangeIterator(hi, hinc, lo, linc);
407: } else {
408: return index.valueRangeIterator(lo, linc, hi, hinc);
409: }
410: }
411:
412: /**
413: * @see prefuse.data.util.Index#rows(double, double, int)
414: */
415: public IntIterator rows(double lo, double hi, int type) {
416: if (!(m_index instanceof DoubleIntSortedMap))
417: throw new IllegalStateException();
418:
419: boolean reverse = (type & Index.TYPE_DESCENDING) > 0;
420: boolean linc = (type & Index.TYPE_LEFT_INCLUSIVE) > 0;
421: boolean hinc = (type & Index.TYPE_RIGHT_INCLUSIVE) > 0;
422:
423: DoubleIntSortedMap index = (DoubleIntSortedMap) m_index;
424: if (reverse) {
425: return index.valueRangeIterator(hi, hinc, lo, linc);
426: } else {
427: return index.valueRangeIterator(lo, linc, hi, hinc);
428: }
429: }
430:
431: // ------------------------------------------------------------------------
432:
433: /**
434: * @see prefuse.data.util.Index#rows(int)
435: */
436: public IntIterator rows(int val) {
437: return rows(val, val, Index.TYPE_AII);
438: }
439:
440: /**
441: * @see prefuse.data.util.Index#rows(long)
442: */
443: public IntIterator rows(long val) {
444: return rows(val, val, Index.TYPE_AII);
445: }
446:
447: /**
448: * @see prefuse.data.util.Index#rows(float)
449: */
450: public IntIterator rows(float val) {
451: return rows(val, val, Index.TYPE_AII);
452: }
453:
454: /**
455: * @see prefuse.data.util.Index#rows(double)
456: */
457: public IntIterator rows(double val) {
458: return rows(val, val, Index.TYPE_AII);
459: }
460:
461: /**
462: * @see prefuse.data.util.Index#rows(boolean)
463: */
464: public IntIterator rows(boolean val) {
465: if (!(m_index instanceof BooleanIntSortedMap))
466: throw new IllegalStateException();
467:
468: BooleanIntSortedMap index = (BooleanIntSortedMap) m_index;
469: return index.valueRangeIterator(val, true, val, true);
470: }
471:
472: /**
473: * @see prefuse.data.util.Index#rows(java.lang.Object)
474: */
475: public IntIterator rows(Object val) {
476: return rows(val, val, Index.TYPE_AII);
477: }
478:
479: // ------------------------------------------------------------------------
480:
481: /**
482: * @see prefuse.data.util.Index#get(double)
483: */
484: public int get(double x) {
485: DoubleIntSortedMap index = (DoubleIntSortedMap) m_index;
486: return index.get(x);
487: }
488:
489: /**
490: * @see prefuse.data.util.Index#get(float)
491: */
492: public int get(float x) {
493: FloatIntSortedMap index = (FloatIntSortedMap) m_index;
494: return index.get(x);
495: }
496:
497: /**
498: * @see prefuse.data.util.Index#get(int)
499: */
500: public int get(int x) {
501: IntIntSortedMap index = (IntIntSortedMap) m_index;
502: return index.get(x);
503: }
504:
505: /**
506: * @see prefuse.data.util.Index#get(long)
507: */
508: public int get(long x) {
509: LongIntSortedMap index = (LongIntSortedMap) m_index;
510: return index.get(x);
511: }
512:
513: /**
514: * @see prefuse.data.util.Index#get(java.lang.Object)
515: */
516: public int get(Object x) {
517: ObjectIntSortedMap index = (ObjectIntSortedMap) m_index;
518: return index.get(x);
519: }
520:
521: } // end of class ColumnIndex
|