001: package gnu.kawa.util;
002:
003: import java.util.Hashtable;
004:
005: /** Map integers to Object.
006: * Future implementaton will be optimized for ranges that map to the
007: * same value, but the current implementation is bad except for 0..127. */
008:
009: public class RangeTable implements Cloneable // extends map
010: {
011: Object[] index = new Object[128];
012: Hashtable hash = new Hashtable(200);
013:
014: public Object lookup(int key, Object defaultValue) {
015: if ((key & 127) == key)
016: return index[key];
017: return hash.get(new Integer(key));
018: }
019:
020: public void set(int lo, int hi, Object value) {
021: if (lo > hi)
022: return;
023: for (int i = lo;; i++) {
024: if ((i & 127) == i)
025: index[i] = value;
026: else
027: hash.put(new Integer(i), value);
028: if (i == hi)
029: break;
030: }
031: }
032:
033: public void set(int key, Object value) {
034: set(key, key, value);
035: }
036:
037: public void remove(int lo, int hi) {
038: if (lo > hi)
039: return;
040: for (int i = lo;; i++) {
041: if ((i & 127) == i)
042: index[i] = null;
043: else
044: hash.remove(new Integer(i));
045: if (i == hi)
046: break;
047: }
048: }
049:
050: public void remove(int key) {
051: remove(key, key);
052: }
053:
054: public RangeTable copy() {
055: RangeTable copy = new RangeTable();
056: copy.index = (Object[]) index.clone();
057: copy.hash = (Hashtable) hash.clone();
058: return copy;
059: }
060:
061: public Object clone() {
062: return copy();
063: }
064:
065: /*
066: Object[] index = null;
067: //int index256 = null;
068:
069: Range ranges;
070:
071: private static void update(Object[] index, int lo, int hi, Object value)
072: {
073: }
074:
075: private Object update(int lo, int hi, Object value, int shift, Object[] index)
076: {
077: if (index == null)
078: {
079: if (shift == 24)
080: index = new Range(lo, hi, value);
081: else
082: index = new Object[16];
083: }
084: int ilo = (lo >> shift) & 0xf;
085: int ihi = (hi >> shift) & 0xf;
086: for (int i = ilo; i < ihi; i++)
087: {
088: index[i] = update(lo, hi, shift - 4, index[i]);
089: }
090: }
091:
092: public void set(int lo, int hi, Object value)
093: {
094: set(lo, ho, value, index, 24);
095: }
096:
097: private void set(int lo, int hi, Object value, Object[] index, int shift)
098: {
099: Range r = findLower(lo);
100: if (r == null)
101: {
102: r = new Range(lo, hi, value, index);
103: // ???
104: }
105: // Now: r != null && r.lo <= lo && (r.next == null || r.next.lo > lo).
106: Range next = r.next;
107: if (lo <= r.hi)
108: {
109: // Overlap: lo is within r.
110:
111: if (lo == r.lo || hi == r.hi)
112: {
113: r.value = value;
114: return;
115: }
116: if (hi <= r.hi)
117: {
118: // Completely within r.
119: if (r.value == value)
120: return;
121: Range s = new Range(lo, hi, value, next);
122: if (hi != r.hi)
123: s.next = t = new Range(hi + 1, r.hi, r.value, next);
124: r.hi = lo - 1;
125: r.next = s;
126: // goto fixup;
127: }
128: }
129: else if (lo == r.hi + 1 && value == r.value)
130: {
131: r.hi = hi;
132: if (next != null)
133: {
134: if (value == next.value && hi + 1 >= next.lo)
135: {
136: r.next = next.next;
137: r.hi = next.hi;
138: }
139: while (hi >= next.hi)
140: {
141: r.hi = hi = next.hi;
142: next = next.next;
143: r.next = next;
144: }
145: if (hi >= next.lo)
146: {
147: next.lo ...
148: }
149: }
150: }
151: }
152:
153: private static Range getLast(Object[] index, int key)
154: {
155: for (;;)
156: {
157: Object cur = index[key];
158: if (cur == null)
159: {
160: if (key == 0)
161: return null;
162: key--;
163: continue;
164: }
165: if (cur instanceof Range)
166: return (Range) cur;
167: key = 15;
168: index = (Object[]) cur;
169: }
170: }
171: */
172:
173: /* Find last range r such that r.hi <= key. */
174: /*
175: public Range findLower(int key)
176: {
177: Object cur;
178: int shift;
179: //if ((key & 0xFF) == key)
180: // {
181: // // Optimize for key in range [0 .. 256].
182: // cur = index256;
183: // shift = 4;
184: // }
185: // else
186: {
187: cur = index;
188: shift = 24;
189: // FIXME - handle negative values in proper order?
190: // key ^= 0x8000000;
191: }
192: for (;;)
193: {
194: int key15 = (key >> shift) & 0xF;
195: cur = index[key15];
196: if (cur == null)
197: return getLast(index, key15);
198: if (cur instanceof Range)
199: return (Range) cur;
200: shift -= 24;
201: }
202:
203: }
204:
205: public Object lookup(int key, Object defaultValue)
206: {
207: Object cur;
208: int shift;
209: if ((key & 0xFF) == key)
210: {
211: // Optimize for key in range [0 .. 256].
212: cur = index256;
213: shift = 4;
214: }
215: else
216: {
217: cur = index;
218: shift = 24;
219: // FIXME - handle negative values in proper order?
220: // key ^= 0x8000000;
221: }
222: for (;;)
223: {
224: cur = index[(key >> shift) & 0xF];
225: if (cur == null)
226: return defaultValue;
227: if (cur instanceof Range)
228: {
229: Range range = (Range) cur;
230: if (key <= range.lo && key >= range.hi)
231: return range.value;
232: else
233: return defaultValue;
234: }
235: shift -= 24;
236: }
237:
238:
239: }
240:
241: public Object enumerate (RangeHandler handler)
242: {
243: for (Range range; range != null; range = range.chain)
244: {
245: handel.handle(range.lo, range.hi, range.value);
246: }
247: }
248: */
249: }
250:
251: /*
252: interface RangeHandler
253: {
254: public Object handle(int lo, int hi, Object value);
255: }
256:
257: class Range
258: {
259: int lo;
260: int hi;
261: Object value;
262: Range next;
263:
264: public Range(int lo, int hi, Object value, Range next)
265: {
266: this.lo = lo;
267: this.hi = hi;
268: this.value = value;
269: this.next = next;
270: }
271: }
272: */
|