KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > gnu > kawa > util > RangeTable


1 package gnu.kawa.util;
2 import java.util.Hashtable JavaDoc;
3
4 /** Map integers to Object.
5  * Future implementaton will be optimized for ranges that map to the
6  * same value, but the current implementation is bad except for 0..127. */

7
8 public class RangeTable implements Cloneable JavaDoc // extends map
9
{
10   Object JavaDoc[] index = new Object JavaDoc[128];
11   Hashtable JavaDoc hash = new Hashtable JavaDoc(200);
12
13   public Object JavaDoc lookup(int key, Object JavaDoc defaultValue)
14   {
15     if ((key & 127) == key)
16       return index[key];
17     return hash.get(new Integer JavaDoc(key));
18   }
19
20   public void set(int lo, int hi, Object JavaDoc value)
21   {
22     if (lo > hi)
23       return;
24     for (int i = lo; ; i++)
25       {
26     if ((i & 127) == i)
27       index[i] = value;
28     else
29       hash.put(new Integer JavaDoc(i), value);
30     if (i == hi)
31       break;
32       }
33   }
34
35   public void set(int key, Object JavaDoc value)
36   {
37     set(key, key, value);
38   }
39
40   public void remove(int lo, int hi)
41   {
42     if (lo > hi)
43       return;
44     for (int i = lo; ; i++)
45       {
46     if ((i & 127) == i)
47       index[i] = null;
48     else
49       hash.remove(new Integer JavaDoc(i));
50     if (i == hi)
51       break;
52       }
53   }
54
55   public void remove(int key)
56   {
57     remove(key, key);
58   }
59
60   public RangeTable copy()
61   {
62     RangeTable copy = new RangeTable();
63     copy.index = (Object JavaDoc[]) index.clone();
64     copy.hash = (Hashtable JavaDoc) hash.clone();
65     return copy;
66   }
67
68   public Object JavaDoc clone()
69   {
70     return copy();
71   }
72
73   /*
74   Object[] index = null;
75   //int index256 = null;
76
77   Range ranges;
78   
79   private static void update(Object[] index, int lo, int hi, Object value)
80   {
81   }
82
83   private Object update(int lo, int hi, Object value, int shift, Object[] index)
84   {
85     if (index == null)
86       {
87     if (shift == 24)
88       index = new Range(lo, hi, value);
89     else
90       index = new Object[16];
91       }
92     int ilo = (lo >> shift) & 0xf;
93     int ihi = (hi >> shift) & 0xf;
94     for (int i = ilo; i < ihi; i++)
95       {
96     index[i] = update(lo, hi, shift - 4, index[i]);
97       }
98   }
99
100   public void set(int lo, int hi, Object value)
101   {
102     set(lo, ho, value, index, 24);
103   }
104
105   private void set(int lo, int hi, Object value, Object[] index, int shift)
106   {
107     Range r = findLower(lo);
108     if (r == null)
109       {
110     r = new Range(lo, hi, value, index);
111     // ???
112       }
113     // Now: r != null && r.lo <= lo && (r.next == null || r.next.lo > lo).
114     Range next = r.next;
115     if (lo <= r.hi)
116       {
117     // Overlap: lo is within r.
118
119     if (lo == r.lo || hi == r.hi)
120       {
121         r.value = value;
122         return;
123       }
124     if (hi <= r.hi)
125       {
126         // Completely within r.
127         if (r.value == value)
128           return;
129         Range s = new Range(lo, hi, value, next);
130         if (hi != r.hi)
131           s.next = t = new Range(hi + 1, r.hi, r.value, next);
132         r.hi = lo - 1;
133         r.next = s;
134         // goto fixup;
135       }
136       }
137     else if (lo == r.hi + 1 && value == r.value)
138       {
139     r.hi = hi;
140     if (next != null)
141       {
142         if (value == next.value && hi + 1 >= next.lo)
143           {
144         r.next = next.next;
145         r.hi = next.hi;
146           }
147         while (hi >= next.hi)
148           {
149         r.hi = hi = next.hi;
150         next = next.next;
151         r.next = next;
152           }
153         if (hi >= next.lo)
154           {
155         next.lo ...
156           }
157       }
158       }
159   }
160
161   private static Range getLast(Object[] index, int key)
162   {
163     for (;;)
164       {
165     Object cur = index[key];
166     if (cur == null)
167       {
168         if (key == 0)
169           return null;
170         key--;
171         continue;
172       }
173     if (cur instanceof Range)
174       return (Range) cur;
175     key = 15;
176     index = (Object[]) cur;
177       }
178   }
179   */

180
181   /* Find last range r such that r.hi <= key. */
182   /*
183   public Range findLower(int key)
184   {
185     Object cur;
186     int shift;
187     //if ((key & 0xFF) == key)
188     // {
189     // // Optimize for key in range [0 .. 256].
190     // cur = index256;
191     // shift = 4;
192     // }
193     // else
194       {
195     cur = index;
196     shift = 24;
197     // FIXME - handle negative values in proper order?
198     // key ^= 0x8000000;
199       }
200     for (;;)
201       {
202     int key15 = (key >> shift) & 0xF;
203     cur = index[key15];
204     if (cur == null)
205       return getLast(index, key15);
206     if (cur instanceof Range)
207       return (Range) cur;
208     shift -= 24;
209       }
210
211   }
212
213   public Object lookup(int key, Object defaultValue)
214   {
215     Object cur;
216     int shift;
217     if ((key & 0xFF) == key)
218       {
219     // Optimize for key in range [0 .. 256].
220     cur = index256;
221     shift = 4;
222       }
223     else
224       {
225     cur = index;
226     shift = 24;
227     // FIXME - handle negative values in proper order?
228     // key ^= 0x8000000;
229       }
230     for (;;)
231       {
232     cur = index[(key >> shift) & 0xF];
233     if (cur == null)
234       return defaultValue;
235     if (cur instanceof Range)
236       {
237         Range range = (Range) cur;
238         if (key <= range.lo && key >= range.hi)
239           return range.value;
240         else
241           return defaultValue;
242       }
243     shift -= 24;
244       }
245
246
247   }
248
249   public Object enumerate (RangeHandler handler)
250   {
251     for (Range range; range != null; range = range.chain)
252       {
253     handel.handle(range.lo, range.hi, range.value);
254       }
255   }
256   */

257 }
258
259 /*
260 interface RangeHandler
261 {
262   public Object handle(int lo, int hi, Object value);
263 }
264
265 class Range
266 {
267   int lo;
268   int hi;
269   Object value;
270   Range next;
271
272   public Range(int lo, int hi, Object value, Range next)
273   {
274     this.lo = lo;
275     this.hi = hi;
276     this.value = value;
277     this.next = next;
278   }
279 }
280 */

281
Popular Tags