src/org/ibex/util/Basket.java

   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.
   4
   5 package org.ibex.util;
   6
   7 import java.io.Serializable;
   8
   9 public interface Basket extends Serializable {
  10     public boolean containsValue(Object object);
  11     public void clear();
  12     public int size();
  13     public void remove(Object object);
  14
  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);
  24     }
  25
  26     public interface RandomAccess extends List { }
  27
  28     public interface Queue extends Basket {
  29         // FIXME
  30         //public void   enqueue(Object o);
  31         //public Object dequeue();
  32     }
  33
  34     public interface Stack extends Basket {
  35         public Object pop();
  36         public Object peek();
  37         public void push(Object object);
  38     }
  39
  40     public interface Map extends Basket {
  41         public boolean containsKey(Object key);
  42         public Object get(Object key);
  43         public Object put(Object key, Object value);
  44     }
  45
  46     public interface CompareFunc {
  47         public int compare(Object a, Object b);
  48     }
  49
  50
  51     // Implementations ////////////////////////////////////////////////////////
  52
  53     public class Array implements RandomAccess, Stack, Queue {
  54         private static final long serialVersionUID = 1233428092L;
  55
  56         private Object[] o;
  57         private int size = 0;
  58
  59         public Array() { this(10); }
  60         public Array(int initialCapacity) { o = new Object[initialCapacity]; }
  61         public Array(Object entry) { this(1); add(entry); }
  62
  63         public void add(Object obj) { add(size, obj); }
  64         public void add(int i, Object obj) {
  65             size(size + 1);
  66             if (size - 1 > i) System.arraycopy(o, i, o, size, size - i - 1);
  67             o[i] = obj; size++;
  68         }
  69         public Object set(int i, Object obj) {
  70             if (i >= size) throw new IndexOutOfBoundsException(
  71                 "index "+i+" is beyond list boundary "+size);
  72             Object old = o[i]; o[i] = obj; return old;
  73         }
  74         public Object get(int i) {
  75             if (i >= size) throw new IndexOutOfBoundsException(
  76                 "index "+i+" is beyond list boundary "+size);
  77             return o[i];
  78         }
  79         public Object remove(int i) {
  80             if (i >= size || i < 0) throw new IndexOutOfBoundsException(
  81                 "index "+i+" is beyond list boundary "+size);
  82             Object old = o[i]; o[i] = null;
  83             if (size - 1 > i) System.arraycopy(o, i + 1, o, i, size - i - 1);
  84             size--; return old;
  85         }
  86         public void remove(Object obj) { remove(indexOf(obj)); }
  87
  88         public int indexOf(Object obj) {
  89             for (int i=0; i < size; i++)
  90                 if ((obj == null && o[i] == null) || obj.equals(o[i])) return i;
  91             return -1;
  92         }
  93
  94         public boolean containsValue(Object obj) {
  95             for (int i=0; i < size; i++)
  96                 if ((obj == null && o[i] == null) || obj.equals(o[i])) return true;
  97             return false;
  98         }
  99         public void clear() { for (int i=0; i < size; i++) o[i] = null; size = 0; }
 100         public int size() { return size; }
 101         public void size(int s) {
 102             if (o.length >= s) return;
 103             Object[] newo = new Object[s];
 104             System.arraycopy(o, 0, newo, 0, size);
 105             o = newo;
 106         }
 107
 108         public void reverse() {
 109             Object tmp; int max = (int)Math.floor((double)size / 2);
 110             for (int i=0; i < size; i++) { tmp = o[i]; o[i] = o[size - i]; o[size - i] = tmp; }
 111         }
 112
 113         public void sort(CompareFunc c) { sort(this, null, c, 0, size); }
 114
 115         private static void sort(Array a, Array b, CompareFunc c, int start, int end) {
 116             Object tmpa, tmpb = null;
 117             if(start >= end) return;
 118             if(end-start <= 6) {
 119                 for(int i=start+1;i<=end;i++) {
 120                     tmpa = a.o[i];
 121                     if (b != null) tmpb = b.o[i];
 122                     int j;
 123                     for(j=i-1;j>=start;j--) {
 124                         if(c.compare(a.o[j],tmpa) <= 0) break;
 125                         a.o[j+1] = a.o[j];
 126                         if (b != null) b.o[j+1] = b.o[j];
 127                     }
 128                     a.o[j+1] = tmpa;
 129                     if (b != null) b.o[j+1] = tmpb;
 130                 }
 131                 return;
 132             }
 133             Object pivot = a.o[end];
 134             int lo = start - 1;
 135             int hi = end;
 136             do {
 137                 while(c.compare(a.o[++lo],pivot) < 0) { }
 138                 while((hi > lo) && c.compare(a.o[--hi],pivot) > 0) { }
 139                 swap(a, lo,hi);
 140                 if (b != null) swap(b, lo,hi);
 141             } while(lo < hi);
 142
 143             swap(a, lo,end);
 144             if (b != null) swap(b, lo,end);
 145             sort(a, b, c, start, lo-1);
 146             sort(a, b, c, lo+1, end);
 147         }
 148
 149         private static final void swap(Array vec, int a, int b) {
 150             if(a != b) {
 151                 Object tmp = vec.o[a];
 152                 vec.o[a] = vec.o[b];
 153                 vec.o[b] = tmp;
 154             }
 155         }
 156
 157         public Object peek() {
 158             if (size < 1) throw new IndexOutOfBoundsException("array is empty");
 159             return o[size - 1];
 160         }
 161         public Object pop() { return remove(size - 1); }
 162         public void push(Object o) { add(o); }
 163     }
 164
 165     //public class Tree implements RandomAccess { } FIXME
 166
 167     //public class IndexedTree extends Tree { } FIXME
 168
 169     /** Implementation of a hash table using Radke's quadratic residue
 170      *  linear probing. Uses a single array to store all entries.
 171      *
 172      * <p>See C. Radke, Communications of the ACM, 1970, 103-105</p>
 173      *
 174      * @author adam@ibex.org, crawshaw@ibex.org
 175      */
 176     public abstract class Hash implements Basket {
 177         private static final long serialVersionUID = 3948384093L;
 178
 179         /** Used internally to record used slots. */
 180         protected final Object placeholder = new java.io.Serializable() {
 181             private static final long serialVersionUID = 1331L;
 182         };
 183
 184         /** When <tt>loadFactor * usedslots > num_slots</tt>, call
 185          *  <tt>rehash()</tt>. */
 186         protected final float loadFactor;
 187
 188         /** Used to determine the number of array slots required by each
 189          *  mapping entry. */
 190         protected final int indexmultiple = 1;
 191
 192         /** Number of entries with non-null key (includes placeholder slots). */
 193         protected int usedslots = 0;
 194
 195         /** Number of currently available entry slots. */
 196         protected int numslots = 0;
 197
 198         /** Number of currently active entries. */
 199         protected int size = 0;
 200
 201         /** Array of mappings.
 202          *
 203          *  <p>Each map requires multiple slots in the array, and subclasses
 204          *  can vary the number of required slots without reimplementing all
 205          *  the functions of this class by changing the value of
 206          *  <tt>indexmultiple</tt>.</p>
 207          *
 208          *  Default implementation uses <tt>indexmultiple == 1</tt>, and
 209          *  stores only the keys in <tt>entries</tt>.
 210          */
 211         protected Object[] entries = null;
 212
 213         public Hash(int initialCapacity, float loadFactor) {
 214             // using a pseudoprime in the form 4x+3 ensures full coverage
 215             initialCapacity = initialCapacity / 4;
 216             initialCapacity = 4 * initialCapacity + 3;
 217             entries = new Object[initialCapacity * indexmultiple];
 218             this.numslots = initialCapacity;
 219             this.loadFactor = loadFactor;
 220         }
 221
 222         public int size() { return size; }
 223         public void clear() {
 224             for (int i = usedslots * indexmultiple; i >= 0; i--) entries[i] = null;
 225             size = usedslots = 0;
 226         }
 227
 228         public boolean containsKey(Object k) { return indexOf(k) >= 0; }
 229
 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); }
 233
 234         public void remove(Object k) { remove(indexOf(k)); }
 235
 236         public void remove(int dest) {
 237             if (dest < 0) return;
 238             entryRemoved(dest);
 239
 240             // instead of removing, insert a placeholder
 241             entries[dest] = placeholder;
 242             for (int inc=1; inc < indexmultiple; inc++) entries[dest + inc] = null;
 243             size--;
 244         }
 245
 246         /** Insert new entry or replace existing at given index. */
 247         public int put(int dest, Object k) {
 248             if (usedslots + 1 > numslots * loadFactor) rehash();
 249             if (dest >= 0) { // update existing entry
 250                 entryUpdated(dest);
 251             } else {         // new entry
 252                 dest = -1 * dest - 1;
 253                 entries[dest] = k;
 254                 for (int inc = 1; inc < indexmultiple; inc++)
 255                     entries[dest + inc] = null;
 256                 entryAdded(dest);
 257             }
 258             return dest;
 259         }
 260
 261         /** Called immediately after the addition of a new entry. */
 262         protected abstract void entryAdded(int dest);
 263
 264         /** Called immediately after the update of a current entry. */
 265         protected abstract void entryUpdated(int dest);
 266
 267         /** Called immediately before the removal of an entry. */
 268         protected abstract void entryRemoved(int dest);
 269
 270         /** Compares two keys for equality. <tt>userKey</tt> is the key
 271          *  passed to the map, <tt>storedKey</tt> is from the map.
 272          *
 273          * <p>Default implementation provides standard Java equality
 274          * testing, <tt>k1 == null ? k2 == null : k1.equals(k2)</tt>.</p>
 275          */
 276         protected boolean equals(Object userKey, Object storedKey) {
 277             return userKey == null ? storedKey == null : userKey.equals(storedKey);
 278         }
 279
 280         /** Returns the array position in <tt>entries</tt>, adjusted for
 281          *  <tt>indexmultiple</tt>, where <tt>k</tt> is/should be stored
 282          *  using Radke's quadratic residue linear probing.
 283          *
 284          *  <p><tt>entries[0]</tt> is a hard coded exception for the null
 285          *  key.</p>
 286          *
 287          * <p>If the key is not found, this function returns
 288          * <tt>(-1 * indexPosition) - 1</tt>, where <tt>indexPosition</tt>
 289          * is the array position where the mapping should be stored.</p>
 290          *
 291          * <p>Uses <tt>placeholder</tt> as a placeholder object, and
 292          * compares keys using <tt>equals(Object, Object)</tt>.</p>
 293          */
 294         protected int indexOf(Object k) {
 295             // special case null key
 296             if (k == null) return equals(placeholder, entries[0]) ? -1 : 0;
 297
 298             int hash = k == null ? 0 : k.hashCode();
 299             final int orig = Math.abs(hash) % numslots;
 300             int dest = orig * indexmultiple;
 301             int tries = 1;
 302             boolean plus = true;
 303
 304             while (entries[dest] != null) {
 305                 if (equals(k, entries[dest])) return dest;
 306                 dest = Math.abs((orig + (plus ? 1 : -1) * tries * tries) % numslots) * indexmultiple;
 307                 if (plus) tries++;
 308                 plus = !plus;
 309             }
 310             return -1 * dest - 1;
 311         }
 312
 313         /** Doubles the available entry space, first by packing the data
 314          *  set (removes <tt>placeholder</tt> references) and if necessary
 315          *  by increasing the size of the <tt>entries</tt> array.
 316          */
 317         protected void rehash() {
 318             int oldnumslots = numslots;
 319             Object[] oldentries = entries;
 320
 321             if (size * 2 > usedslots) numslots *= 2;
 322             entries = new Object[numslots * indexmultiple];
 323
 324             for (int i=0; i < oldnumslots; i++) {
 325                 int pos = i * indexmultiple;
 326                 if (pos > 0 && oldentries[pos] == null) continue;
 327                 if (oldentries[pos] == placeholder) continue;
 328
 329                 // dont adjust any of the support entries
 330                 int dest = indexOf(oldentries[pos]);
 331                 dest = -1 * dest - 1; size++; usedslots++; // always new entry
 332                 for (int inc=0; inc < indexmultiple; inc++)
 333                     entries[dest + inc] = oldentries[pos + inc];
 334             }
 335         }
 336     }
 337
 338     public class HashMap extends Hash implements Map {
 339         private static final long serialVersionUID = 2348905755L;
 340
 341         protected final int indexmultiple = 2;
 342
 343         public HashMap() { this(16, 0.75F); }
 344         public HashMap(int cap, float load) { super(cap, load); }
 345
 346         public Object get(Object key) { int i = indexOf(key);  return i >= 0 ? entries[i + 1] : null; }
 347         public Object put(Object key, Object value) {
 348             Object old = null;
 349             int dest = indexOf(key);
 350             if (dest >= 0) old = entries[(-1 * dest - 1) + 1];
 351             dest = put(dest, key);
 352             entries[dest + 1] = value;
 353             return old;
 354         }
 355
 356         protected void entryAdded(int dest) {}
 357         protected void entryUpdated(int dest) {}
 358         protected void entryRemoved(int dest) {}
 359
 360         public boolean containsKey(Object k) { return super.containsValue(k); }
 361
 362         public boolean containsValue(Object v) {
 363             for (int i=0; i < numslots; i++)
 364                 if ((i == 0 || entries[i * indexmultiple] != null) && // exception for null key
 365                     !equals(placeholder, entries[i * indexmultiple]) &&
 366                     v == null ? entries[i + 1] == null : v.equals(entries[i + 1]))
 367                         return true;
 368             return false;
 369         }
 370     }
 371 }