KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > prefuse > util > collections > ObjectIntTreeMap


1 package prefuse.util.collections;
2
3 import java.util.Collections JavaDoc;
4 import java.util.Comparator JavaDoc;
5 import java.util.Iterator JavaDoc;
6
7 /**
8  * Sorted map implementation using a red-black tree to map from Object keys to
9  * int values.
10  *
11  * @author <a HREF="http://jheer.org">jeffrey heer</a>
12  */

13 public class ObjectIntTreeMap extends AbstractTreeMap
14     implements ObjectIntSortedMap
15 {
16     
17     // dummy entry used as wrapper for queries
18
private ObjectEntry dummy = new ObjectEntry(null, Integer.MIN_VALUE, NIL, 0);
19     private Comparator JavaDoc cmp = null;
20     
21     // ------------------------------------------------------------------------
22
// Constructors
23

24     public ObjectIntTreeMap() {
25         this(null, false);
26     }
27     
28     public ObjectIntTreeMap(boolean allowDuplicates) {
29         this(null, allowDuplicates);
30     }
31     
32     public ObjectIntTreeMap(Comparator JavaDoc comparator) {
33         this(comparator, false);
34     }
35     
36     public ObjectIntTreeMap(Comparator JavaDoc comparator, boolean allowDuplicates) {
37         super(null, allowDuplicates);
38         this.cmp = (comparator == null ? super.comparator() : comparator);
39     }
40     
41     /**
42      * @see java.util.SortedMap#comparator()
43      */

44     public Comparator JavaDoc comparator() {
45         return cmp;
46     }
47     
48     // ------------------------------------------------------------------------
49
// SortedMap Methods
50

51     /**
52      * @see java.util.Map#containsKey(java.lang.Object)
53      */

54     public boolean containsKey(Object JavaDoc key) {
55         return find(key, 0) != NIL;
56     }
57
58     /**
59      * @see java.util.Map#get(java.lang.Object)
60      */

61     public int get(Object JavaDoc key) {
62         Entry ret = find(key, 0);
63         return ( ret == NIL ? Integer.MIN_VALUE : ret.val );
64     }
65
66     /**
67      * @see java.util.Map#put(java.lang.Object, java.lang.Object)
68      */

69     public int put(Object JavaDoc key, int value) {
70         Entry t = root;
71         lastOrder = 0;
72         
73         if (t == NIL) {
74             incrementSize(true);
75             root = new ObjectEntry(key, value, NIL, lastOrder);
76             return Integer.MIN_VALUE;
77         }
78
79         dummy.key = key;
80         dummy.order = Integer.MAX_VALUE;
81         
82         while (true) {
83             int cmp = compare(dummy, t);
84             if (cmp == 0) {
85                 return t.setValue(value);
86             } else if (cmp < 0) {
87                 if (t.left != NIL) {
88                     t = t.left;
89                 } else {
90                     incrementSize(lastOrder==0);
91                     t.left = new ObjectEntry(key, value, t, lastOrder);
92                     fixUpInsert(t.left);
93                     return Integer.MIN_VALUE;
94                 }
95             } else { // cmp > 0
96
if (t.right != NIL) {
97                     t = t.right;
98                 } else {
99                     incrementSize(lastOrder==0);
100                     t.right = new ObjectEntry(key, value, t, lastOrder);
101                     fixUpInsert(t.right);
102                     return Integer.MIN_VALUE;
103                 }
104             }
105         }
106     }
107
108     /**
109      * @see java.util.Map#remove(java.lang.Object)
110      */

111     public int remove(Object JavaDoc key) {
112         // remove the last instance with the given key
113
Entry x;
114         if ( allowDuplicates )
115             x = findPredecessor(key, Integer.MAX_VALUE);
116         else
117             x = find(key, 0);
118         
119         if (x == NIL)
120             return Integer.MIN_VALUE;
121
122         int val = x.val;
123         remove(x);
124         return val;
125     }
126
127     public int remove(Object JavaDoc key, int val) {
128         // remove the last instance with the given key
129
Entry x = findCeiling(key, 0);
130         if ( x!=NIL && ((key==null && x.getKey()!=null) ||
131                         (key!=null && !x.getKey().equals(key))) )
132             x = successor(x);
133         if (x==NIL || ((key==null && x.getKey()!=null)
134                    || (key!=null && !x.getKey().equals(key))) )
135             return Integer.MIN_VALUE;
136
137         for ( ; x.val != val && x != NIL; x = successor(x) );
138         if (x == NIL) return Integer.MIN_VALUE;
139         
140         remove(x);
141         return val;
142     }
143     
144     /**
145      * @see java.util.SortedMap#firstKey()
146      */

147     public Object JavaDoc firstKey() {
148         return minimum(root).getKey();
149     }
150     
151     /**
152      * @see java.util.SortedMap#lastKey()
153      */

154     public Object JavaDoc lastKey() {
155         return maximum(root).getKey();
156     }
157     
158     // -- Collection view methods ---------------------------------------------
159

160     public Iterator JavaDoc keyIterator() {
161         return new KeyIterator();
162     }
163     
164     public Iterator JavaDoc keyRangeIterator(Object JavaDoc fromKey, boolean fromInc,
165                                      Object JavaDoc toKey, boolean toInc)
166     {
167         Entry start, end;
168         
169         if ( fromKey == toKey && (fromKey == MIN_KEY || fromKey == MAX_KEY) )
170             return Collections.EMPTY_LIST.iterator();
171         
172         boolean bmin = (fromKey == MIN_KEY || toKey == MAX_KEY);
173         boolean bmax = (fromKey == MAX_KEY || toKey == MIN_KEY);
174         
175         if ( !bmax && (bmin || cmp.compare(fromKey, toKey) <= 0) ) {
176             start = findCeiling(fromKey, (fromInc ? 0 : Integer.MAX_VALUE));
177             end = findCeiling(toKey, (toInc? Integer.MAX_VALUE : 0));
178         } else {
179             start = findCeiling(fromKey, (fromInc ? Integer.MAX_VALUE : 0));
180             start = predecessor(start);
181             end = findCeiling(toKey, (toInc ? 0 : Integer.MAX_VALUE));
182             end = predecessor(end);
183         }
184         return new KeyIterator(start, end);
185     }
186     
187     public IntIterator valueRangeIterator(Object JavaDoc fromKey, boolean fromInc,
188                                           Object JavaDoc toKey, boolean toInc)
189     {
190         return new ValueIterator(
191            (EntryIterator)keyRangeIterator(fromKey,fromInc,toKey,toInc));
192     }
193     
194     // ------------------------------------------------------------------------
195
// Internal Binary Search Tree / Red-Black Tree methods
196
// Adapted from Cormen, Leiserson, and Rivest's Introduction to Algorithms
197

198     protected int compare(Entry e1, Entry e2) {
199         Object JavaDoc k1 = e1.getKey(), k2 = e2.getKey();
200         
201         if ( k1 == k2 && (k1 == MIN_KEY || k1 == MAX_KEY) ) {
202             return 0;
203         } else if ( k1 == MIN_KEY || k2 == MAX_KEY ) {
204             return -1;
205         } else if ( k1 == MAX_KEY || k2 == MIN_KEY ) {
206             return 1;
207         }
208         
209         int c = cmp.compare(e1.getKey(), e2.getKey());
210         if ( allowDuplicates ) {
211             if ( c == 0 ) {
212                 c = (e1.order < e2.order ? -1 : (e1.order > e2.order ? 1 : 0));
213                 lastOrder = 1 + (c < 0 ? e1.order : e2.order);
214             }
215         }
216         return c;
217     }
218     
219     private Entry find(Object JavaDoc key, int order) {
220         dummy.key = key;
221         dummy.order = order;
222         Entry e = find(dummy);
223         dummy.key = null;
224         return e;
225     }
226     
227     private Entry findPredecessor(Object JavaDoc key, int order) {
228         dummy.key = key;
229         dummy.order = order;
230         Entry e = findPredecessor(dummy);
231         dummy.key = null;
232         return e;
233     }
234     
235     private Entry findCeiling(Object JavaDoc key, int order) {
236         dummy.key = key;
237         dummy.order = order;
238         Entry e = findCeiling(dummy);
239         dummy.key = null;
240         return e;
241     }
242     
243     // ========================================================================
244
// Inner classes
245

246     // ------------------------------------------------------------------------
247
// Entry class - represents a Red-Black Tree Node
248

249     static class ObjectEntry extends AbstractTreeMap.Entry {
250         Object JavaDoc key;
251         
252         public ObjectEntry(Object JavaDoc key, int val) {
253             super(val);
254             this.key = key;
255         }
256         
257         public ObjectEntry(Object JavaDoc key, int val, Entry parent, int order) {
258             super(val, parent, order);
259             this.key = key;
260         }
261         
262         public Object JavaDoc getKey() {
263             return key;
264         }
265         
266         public void copyFields(Entry x) {
267             super.copyFields(x);
268             this.key = x.getKey();
269         }
270         
271     }
272     
273 } // end of class DuplicateTreeMap
274
Popular Tags