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         public void   enqueue(Object o);
  30         public Object dequeue();
  31     }
  32
  33     public interface Stack extends Basket {
  34         public Object pop();
  35         public Object peek();
  36         public void push(Object object);
  37     }
  38
  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);
  43     }
  44
  45     public interface CompareFunc {
  46         public int compare(Object a, Object b);
  47     }
  48
  49
  50     // Implementations ////////////////////////////////////////////////////////
  51
  52     public class Array implements RandomAccess, Stack, Queue {
  53         private static final long serialVersionUID = 1233428092L;
  54
  55         private Object[] o;
  56         private int size = 0;
  57
  58         public Array() { this(10); }
  59         public Array(int initialCapacity) { o = new Object[initialCapacity]; }
  60         public Array(Object entry) { this(1); add(entry); }
  61
  62         public void   enqueue(Object o) { add(o); }
  63
  64         // FEATURE: make this more efficient with general wraparound
  65         public Object dequeue() {
  66             if (size==0) return null;
  67             Object ret = o[0];
  68             for(int i=1; i<size; i++) o[i-1]=o[i];
  69             return ret;
  70         }
  71
  72         public void add(Object obj) { add(size, obj); }
  73         public void add(int i, Object obj) {
  74             size(size + 1);
  75             if (size - 1 > i) System.arraycopy(o, i, o, size, size - i - 1);
  76             o[i] = obj; size++;
  77         }
  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);
  83             return old;
  84         }
  85         public Object get(int i) {
  86             if (i >= size) throw new IndexOutOfBoundsException(
  87                 "index "+i+" is beyond list boundary "+size);
  88             return o[i];
  89         }
  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);
  95             size--; return old;
  96         }
  97         public void remove(Object obj) { remove(indexOf(obj)); }
  98
  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;
 102             return -1;
 103         }
 104
 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;
 108             return false;
 109         }
 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);
 116             o = newo;
 117         }
 118
 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; }
 122         }
 123
 124         public void sort(CompareFunc c) { sort(this, null, c, 0, size); }
 125
 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;
 129             if(end-start <= 6) {
 130                 for(int i=start+1;i<=end;i++) {
 131                     tmpa = a.o[i];
 132                     if (b != null) tmpb = b.o[i];
 133                     int j;
 134                     for(j=i-1;j>=start;j--) {
 135                         if(c.compare(a.o[j],tmpa) <= 0) break;
 136                         a.o[j+1] = a.o[j];
 137                         if (b != null) b.o[j+1] = b.o[j];
 138                     }
 139                     a.o[j+1] = tmpa;
 140                     if (b != null) b.o[j+1] = tmpb;
 141                 }
 142                 return;
 143             }
 144             Object pivot = a.o[end];
 145             int lo = start - 1;
 146             int hi = end;
 147             do {
 148                 while(c.compare(a.o[++lo],pivot) < 0) { }
 149                 while((hi > lo) && c.compare(a.o[--hi],pivot) > 0) { }
 150                 swap(a, lo,hi);
 151                 if (b != null) swap(b, lo,hi);
 152             } while(lo < hi);
 153
 154             swap(a, lo,end);
 155             if (b != null) swap(b, lo,end);
 156             sort(a, b, c, start, lo-1);
 157             sort(a, b, c, lo+1, end);
 158         }
 159
 160         private static final void swap(Array vec, int a, int b) {
 161             if(a != b) {
 162                 Object tmp = vec.o[a];
 163                 vec.o[a] = vec.o[b];
 164                 vec.o[b] = tmp;
 165             }
 166         }
 167
 168         public Object peek() {
 169             if (size < 1) throw new IndexOutOfBoundsException("array is empty");
 170             return o[size - 1];
 171         }
 172         public Object pop() { return remove(size - 1); }
 173         public void push(Object o) { add(o); }
 174     }
 175
 176     /** Implementation of a hash table using Radke's quadratic residue
 177      *  linear probing. Uses a single array to store all entries.
 178      *
 179      * <p>See C. Radke, Communications of the ACM, 1970, 103-105</p>
 180      *
 181      * @author adam@ibex.org, crawshaw@ibex.org
 182      */
 183     public class Hash implements Basket, Map {
 184         static final long serialVersionUID = 3948384093L;
 185
 186         /** Used internally to record used slots. */
 187         final Object placeholder = new java.io.Serializable() { private static final long serialVersionUID = 1331L; };
 188
 189         /** When <tt>loadFactor * usedslots > num_slots</tt>, call
 190          *  <tt>rehash()</tt>. */
 191         final float loadFactor;
 192
 193         /** Used to determine the number of array slots required by each
 194          *  mapping entry. */
 195         final int indexmultiple;
 196
 197         /** Number of currently active entries. */
 198         private int size = 0;
 199
 200         /** Number of placeholders in entries[]. */
 201         private int placeholders = 0;
 202
 203         /** Array of mappings.
 204          *
 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>
 209          *
 210          *  Default implementation uses <tt>indexmultiple == 1</tt>, and
 211          *  stores only the keys in <tt>entries</tt>.
 212          */
 213         private Object[] entries = null;
 214
 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];
 223         }
 224
 225         public int size() { return size; }
 226         public void clear() { for (int i = 0; i<entries.length; i++) entries[i] = null; size = 0; }
 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
 235         // UGLY
 236         public Object[] dumpkeys() {
 237             Object[] ret = new Object[size];
 238             int pos = 0;
 239             for(int i=0; i<entries.length; i+=indexmultiple)
 240                 if (placeholder!=entries[i] && entries[i]!=null) {
 241                     ret[pos++] = entries[i];
 242                 }
 243             return ret;
 244         }
 245
 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;
 252             size--;
 253             placeholders++;
 254         }
 255
 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;
 260         }
 261
 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);
 266             Object old = null;
 267             if (dest < 0) {
 268                 dest = -1 * (dest + 1);
 269                 if (entries[dest] != placeholder) size++;
 270                 entries[dest] = key;
 271                 for(int i=1; i<indexmultiple; i++) entries[dest+i] = null;
 272             } else {
 273                 old = entries[dest + 1 + whichval];
 274             }
 275             entries[dest + 1 + whichval] = value;
 276             return old;
 277         }
 278
 279         /*
 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]))
 286                         return true;
 287             return false;
 288         }
 289         */
 290
 291         /** Compares two keys for equality. <tt>userKey</tt> is the key
 292          *  passed to the map, <tt>storedKey</tt> is from the map.
 293          *
 294          * <p>Default implementation provides standard Java equality
 295          * testing, <tt>k1 == null ? k2 == null : k1.equals(k2)</tt>.</p>
 296          */
 297         protected boolean equals(Object userKey, Object storedKey) {
 298             return userKey == null ? storedKey == null : userKey.equals(storedKey);
 299         }
 300
 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.
 304          *
 305          *  <p><tt>entries[0]</tt> is a hard coded exception for the null
 306          *  key.</p>
 307          *
 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>
 311          *
 312          * <p>Uses <tt>placeholder</tt> as a placeholder object, and
 313          * compares keys using <tt>equals(Object, Object)</tt>.</p>
 314          */
 315         private int indexOf(Object k) {
 316             // special case null key
 317             if (k == null) return equals(placeholder, entries[0]) ? -1 : 0;
 318
 319             int hash = k == null ? 0 : k.hashCode();
 320             final int orig = Math.abs(hash) % (entries.length / indexmultiple);
 321             int dest = orig * indexmultiple;
 322             int tries = 1;
 323             boolean plus = true;
 324
 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;
 328                 if (plus) tries++;
 329                 plus = !plus;
 330             }
 331             return -1 * dest - 1;
 332         }
 333
 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.
 337          */
 338         private void rehash() {
 339             Object[] oldentries = entries;
 340             entries = new Object[oldentries.length * indexmultiple];
 341
 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;
 346
 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];
 352             }
 353             placeholders = 0;
 354         }
 355     }
 356
 357     // FIXME, BalancedTree goes here
 358
 359 }