1 // Copyright 2000-2005 the Contributors, as shown in the revision logs.
2 // Licensed under the Apache Public Source License 2.0 ("the License").
3 // You may not use this file except in compliance with the License.
7 import java.io.Serializable;
9 public interface Basket extends Serializable {
10 public boolean containsValue(Object object);
13 public void remove(Object object);
15 public interface List extends Basket {
16 public void add(Object object);
17 public void add(int index, Object object);
18 public Object set(int index, Object object);
19 public Object get(int index);
20 public Object remove(int index);
21 public int indexOf(Object object);
22 public void reverse();
23 public void sort(CompareFunc c);
26 public interface RandomAccess extends List { }
28 public interface Queue extends Basket {
29 public void enqueue(Object o);
30 public Object dequeue();
33 public interface Stack extends Basket {
36 public void push(Object object);
39 public interface Map extends Basket {
40 public boolean containsKey(Object key);
41 public Object get(Object key);
42 public Object put(Object key, Object value);
45 public interface CompareFunc {
46 public int compare(Object a, Object b);
50 // Implementations ////////////////////////////////////////////////////////
52 public class Array implements RandomAccess, Stack, Queue {
53 private static final long serialVersionUID = 1233428092L;
58 public Array() { this(10); }
59 public Array(int initialCapacity) { o = new Object[initialCapacity]; }
60 public Array(Object entry) { this(1); add(entry); }
62 public void enqueue(Object o) { add(o); }
64 // FEATURE: make this more efficient with general wraparound
65 public Object dequeue() {
66 if (size==0) return null;
68 for(int i=1; i<size; i++) o[i-1]=o[i];
72 public void add(Object obj) { add(size, obj); }
73 public void add(int i, Object obj) {
75 if (size - 1 > i) System.arraycopy(o, i, o, size, size - i - 1);
78 public Object set(int i, Object obj) {
79 if (i >= o.length) throw new IndexOutOfBoundsException(
80 "index "+i+" is beyond list boundary "+size);
81 Object old = o[i]; o[i] = obj;
82 size = Math.max(i+1, size);
85 public Object get(int i) {
86 if (i >= size) throw new IndexOutOfBoundsException(
87 "index "+i+" is beyond list boundary "+size);
90 public Object remove(int i) {
91 if (i >= size || i < 0) throw new IndexOutOfBoundsException(
92 "index "+i+" is beyond list boundary "+size);
93 Object old = o[i]; o[i] = null;
94 if (size - 1 > i) System.arraycopy(o, i + 1, o, i, size - i - 1);
97 public void remove(Object obj) { remove(indexOf(obj)); }
99 public int indexOf(Object obj) {
100 for (int i=0; i < size; i++)
101 if ((obj == null && o[i] == null) || obj.equals(o[i])) return i;
105 public boolean containsValue(Object obj) {
106 for (int i=0; i < size; i++)
107 if ((obj == null && o[i] == null) || obj.equals(o[i])) return true;
110 public void clear() { for (int i=0; i < size; i++) o[i] = null; size = 0; }
111 public int size() { return size; }
112 public void size(int s) {
113 if (o.length >= s) return;
114 Object[] newo = new Object[s];
115 System.arraycopy(o, 0, newo, 0, size);
119 public void reverse() {
120 Object tmp; int max = (int)Math.floor((double)size / 2);
121 for (int i=0; i < size; i++) { tmp = o[i]; o[i] = o[size - i]; o[size - i] = tmp; }
124 public void sort(CompareFunc c) { sort(this, null, c, 0, size); }
126 public static void sort(Array a, Array b, CompareFunc c, int start, int end) {
127 Object tmpa, tmpb = null;
128 if(start >= end) return;
130 for(int i=start+1;i<=end;i++) {
132 if (b != null) tmpb = b.o[i];
134 for(j=i-1;j>=start;j--) {
135 if(c.compare(a.o[j],tmpa) <= 0) break;
137 if (b != null) b.o[j+1] = b.o[j];
140 if (b != null) b.o[j+1] = tmpb;
144 Object pivot = a.o[end];
148 while(c.compare(a.o[++lo],pivot) < 0) { }
149 while((hi > lo) && c.compare(a.o[--hi],pivot) > 0) { }
151 if (b != null) swap(b, lo,hi);
155 if (b != null) swap(b, lo,end);
156 sort(a, b, c, start, lo-1);
157 sort(a, b, c, lo+1, end);
160 private static final void swap(Array vec, int a, int b) {
162 Object tmp = vec.o[a];
168 public Object peek() {
169 if (size < 1) throw new IndexOutOfBoundsException("array is empty");
172 public Object pop() { return remove(size - 1); }
173 public void push(Object o) { add(o); }
176 /** Implementation of a hash table using Radke's quadratic residue
177 * linear probing. Uses a single array to store all entries.
179 * <p>See C. Radke, Communications of the ACM, 1970, 103-105</p>
181 * @author adam@ibex.org, crawshaw@ibex.org
183 public class Hash implements Basket, Map {
184 static final long serialVersionUID = 3948384093L;
186 /** Used internally to record used slots. */
187 final Object placeholder = new java.io.Serializable() { private static final long serialVersionUID = 1331L; };
189 /** When <tt>loadFactor * usedslots > num_slots</tt>, call
190 * <tt>rehash()</tt>. */
191 final float loadFactor;
193 /** Used to determine the number of array slots required by each
195 final int indexmultiple;
197 /** Number of currently active entries. */
198 private int size = 0;
200 /** Number of placeholders in entries[]. */
201 private int placeholders = 0;
203 /** Array of mappings.
205 * <p>Each map requires multiple slots in the array, and subclasses
206 * can vary the number of required slots without reimplementing all
207 * the functions of this class by changing the value of
208 * <tt>indexmultiple</tt>.</p>
210 * Default implementation uses <tt>indexmultiple == 1</tt>, and
211 * stores only the keys in <tt>entries</tt>.
213 private Object[] entries = null;
215 public Hash() { this(16, 0.75F); }
216 public Hash(int cap, float load) { this(2, cap, load); }
217 public Hash(int indexmultiple, int initialCapacity, float loadFactor) {
218 // using a pseudoprime in the form 4x+3 ensures full coverage
219 initialCapacity = (initialCapacity / 4) * 4 + 3;
220 this.loadFactor = loadFactor;
221 this.indexmultiple = indexmultiple;
222 this.entries = new Object[initialCapacity * indexmultiple];
225 public int size() { return size; }
226 public void clear() { for (int i = 0; i<entries.length; i++) entries[i] = null; size = 0; }
228 public boolean containsKey(Object k) { return indexOf(k) >= 0; }
230 /** <b>Warning:</b> This function is equivalent here to
231 * <tt>containsKey()</tt>. For a value map, use Basket.HashMap. */
232 public boolean containsValue(Object k) { return containsKey(k); }
236 public Object[] dumpkeys() {
237 Object[] ret = new Object[size];
239 for(int i=0; i<entries.length; i+=indexmultiple)
240 if (placeholder!=entries[i] && entries[i]!=null) {
241 ret[pos++] = entries[i];
246 public void remove(Object k) { remove(indexOf(k)); }
247 public void remove(int dest) {
248 if (dest < 0) return;
249 // instead of removing, insert a placeholder
250 entries[dest] = placeholder;
251 for (int inc=1; inc < indexmultiple; inc++) entries[dest + inc] = null;
256 public Object get(Object key) { return get(key, 0); }
257 public Object get(Object key, int whichval) {
258 int i = indexOf(key);
259 return i >= 0 ? entries[i + 1 + whichval] : null;
262 public Object put(Object key, Object value) { return put(key, value, 0); }
263 public Object put(Object key, Object value, int whichval) {
264 if (loadFactor * (size + placeholders) > entries.length) rehash();
265 int dest = indexOf(key);
268 dest = -1 * (dest + 1);
269 if (entries[dest] != placeholder) size++;
271 for(int i=1; i<indexmultiple; i++) entries[dest+i] = null;
273 old = entries[dest + 1 + whichval];
275 entries[dest + 1 + whichval] = value;
280 public boolean containsKey(Object k) { return super.containsValue(k); }
281 public boolean containsValue(Object v) {
282 for (int i=0; i < entries.length/indexmultiple; i++)
283 if ((i == 0 || entries[i * indexmultiple] != null) && // exception for null key
284 !equals(placeholder, entries[i * indexmultiple]) &&
285 v == null ? entries[i + 1] == null : v.equals(entries[i + 1]))
291 /** Compares two keys for equality. <tt>userKey</tt> is the key
292 * passed to the map, <tt>storedKey</tt> is from the map.
294 * <p>Default implementation provides standard Java equality
295 * testing, <tt>k1 == null ? k2 == null : k1.equals(k2)</tt>.</p>
297 protected boolean equals(Object userKey, Object storedKey) {
298 return userKey == null ? storedKey == null : userKey.equals(storedKey);
301 /** Returns the array position in <tt>entries</tt>, adjusted for
302 * <tt>indexmultiple</tt>, where <tt>k</tt> is/should be stored
303 * using Radke's quadratic residue linear probing.
305 * <p><tt>entries[0]</tt> is a hard coded exception for the null
308 * <p>If the key is not found, this function returns
309 * <tt>(-1 * indexPosition) - 1</tt>, where <tt>indexPosition</tt>
310 * is the array position where the mapping should be stored.</p>
312 * <p>Uses <tt>placeholder</tt> as a placeholder object, and
313 * compares keys using <tt>equals(Object, Object)</tt>.</p>
315 private int indexOf(Object k) {
316 // special case null key
317 if (k == null) return equals(placeholder, entries[0]) ? -1 : 0;
319 int hash = k == null ? 0 : k.hashCode();
320 final int orig = Math.abs(hash) % (entries.length / indexmultiple);
321 int dest = orig * indexmultiple;
325 while (entries[dest] != null) {
326 if (equals(k, entries[dest])) return dest;
327 dest = Math.abs((orig + (plus ? 1 : -1) * tries * tries) % (entries.length / indexmultiple)) * indexmultiple;
331 return -1 * dest - 1;
334 /** Doubles the available entry space, first by packing the data
335 * set (removes <tt>placeholder</tt> references) and if necessary
336 * by increasing the size of the <tt>entries</tt> array.
338 private void rehash() {
339 Object[] oldentries = entries;
340 entries = new Object[oldentries.length * indexmultiple];
342 for (int i=0; i < (oldentries.length/indexmultiple); i++) {
343 int pos = i * indexmultiple;
344 if (pos > 0 && oldentries[pos] == null) continue;
345 if (oldentries[pos] == placeholder) continue;
347 // dont adjust any of the support entries
348 int dest = indexOf(oldentries[pos]);
349 dest = -1 * dest - 1; size++; // always new entry
350 for (int inc=0; inc < indexmultiple; inc++)
351 entries[dest + inc] = oldentries[pos + inc];
357 // FIXME, BalancedTree goes here