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