1 package prefuse.util.collections; 2 3 import java.util.Collections ; 4 import java.util.Comparator ; 5 import java.util.Iterator ; 6 7 13 public class ObjectIntTreeMap extends AbstractTreeMap 14 implements ObjectIntSortedMap 15 { 16 17 private ObjectEntry dummy = new ObjectEntry(null, Integer.MIN_VALUE, NIL, 0); 19 private Comparator cmp = null; 20 21 24 public ObjectIntTreeMap() { 25 this(null, false); 26 } 27 28 public ObjectIntTreeMap(boolean allowDuplicates) { 29 this(null, allowDuplicates); 30 } 31 32 public ObjectIntTreeMap(Comparator comparator) { 33 this(comparator, false); 34 } 35 36 public ObjectIntTreeMap(Comparator comparator, boolean allowDuplicates) { 37 super(null, allowDuplicates); 38 this.cmp = (comparator == null ? super.comparator() : comparator); 39 } 40 41 44 public Comparator comparator() { 45 return cmp; 46 } 47 48 51 54 public boolean containsKey(Object key) { 55 return find(key, 0) != NIL; 56 } 57 58 61 public int get(Object key) { 62 Entry ret = find(key, 0); 63 return ( ret == NIL ? Integer.MIN_VALUE : ret.val ); 64 } 65 66 69 public int put(Object 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 { 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 111 public int remove(Object key) { 112 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 key, int val) { 128 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 147 public Object firstKey() { 148 return minimum(root).getKey(); 149 } 150 151 154 public Object lastKey() { 155 return maximum(root).getKey(); 156 } 157 158 160 public Iterator keyIterator() { 161 return new KeyIterator(); 162 } 163 164 public Iterator keyRangeIterator(Object fromKey, boolean fromInc, 165 Object 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 fromKey, boolean fromInc, 188 Object toKey, boolean toInc) 189 { 190 return new ValueIterator( 191 (EntryIterator)keyRangeIterator(fromKey,fromInc,toKey,toInc)); 192 } 193 194 198 protected int compare(Entry e1, Entry e2) { 199 Object 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 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 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 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 246 249 static class ObjectEntry extends AbstractTreeMap.Entry { 250 Object key; 251 252 public ObjectEntry(Object key, int val) { 253 super(val); 254 this.key = key; 255 } 256 257 public ObjectEntry(Object key, int val, Entry parent, int order) { 258 super(val, parent, order); 259 this.key = key; 260 } 261 262 public Object 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 } | Popular Tags |