X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Forg%2Fibex%2Futil%2FBasket.java;h=d4348ce677baced38e9727666d734403aaaeef31;hb=7692163af9dabe885650e977d5844f38d404d8b3;hp=04d7d97cc038c192b2c48687621081960c4da128;hpb=3de2ebed27489dbd5d874bc2290c2605c9cdc9d2;p=org.ibex.util.git

diff --git a/src/org/ibex/util/Basket.java b/src/org/ibex/util/Basket.java
index 04d7d97..d4348ce 100644
--- a/src/org/ibex/util/Basket.java
+++ b/src/org/ibex/util/Basket.java
@@ -26,9 +26,8 @@ public interface Basket extends Serializable {
     public interface RandomAccess extends List { }
 
     public interface Queue extends Basket {
-        // FIXME
-        //public void   enqueue(Object o);
-        //public Object dequeue();
+        public void   enqueue(Object o);
+        public Object dequeue();
     }
 
     public interface Stack extends Basket {
@@ -60,6 +59,16 @@ public interface Basket extends Serializable {
         public Array(int initialCapacity) { o = new Object[initialCapacity]; }
         public Array(Object entry) { this(1); add(entry); }
 
+        public void   enqueue(Object o) { add(o); }
+
+        // FEATURE: make this more efficient with general wraparound
+        public Object dequeue() {
+            if (size==0) return null;
+            Object ret = o[0];
+            for(int i=1; i<size; i++) o[i-1]=o[i];
+            return ret;
+        }
+
         public void add(Object obj) { add(size, obj); }
         public void add(int i, Object obj) {
             size(size + 1);
@@ -67,9 +76,11 @@ public interface Basket extends Serializable {
             o[i] = obj; size++;
         }
         public Object set(int i, Object obj) {
-            if (i >= size) throw new IndexOutOfBoundsException(
+            if (i >= o.length) throw new IndexOutOfBoundsException(
                 "index "+i+" is beyond list boundary "+size);
-            Object old = o[i]; o[i] = obj; return old;
+            Object old = o[i]; o[i] = obj;
+	    size = Math.max(i+1, size);
+	    return old;
         }
         public Object get(int i) {
             if (i >= size) throw new IndexOutOfBoundsException(
@@ -162,10 +173,6 @@ public interface Basket extends Serializable {
         public void push(Object o) { add(o); }
     }
 
-    //public class Tree implements RandomAccess { } FIXME
-
-    //public class IndexedTree extends Tree { } FIXME
-
     /** Implementation of a hash table using Radke's quadratic residue
      *  linear probing. Uses a single array to store all entries.
      *
@@ -173,30 +180,25 @@ public interface Basket extends Serializable {
      *
      * @author adam@ibex.org, crawshaw@ibex.org
      */
-    public abstract class Hash implements Basket {
-        private static final long serialVersionUID = 3948384093L;
+    public class Hash implements Basket, Map {
+        static final long serialVersionUID = 3948384093L;
 
         /** Used internally to record used slots. */
-        protected final Object placeholder = new java.io.Serializable() {
-            private static final long serialVersionUID = 1331L;
-        };
+        final Object placeholder = new java.io.Serializable() { private static final long serialVersionUID = 1331L; };
 
         /** When <tt>loadFactor * usedslots > num_slots</tt>, call
          *  <tt>rehash()</tt>. */
-        protected final float loadFactor;
+        final float loadFactor;
 
         /** Used to determine the number of array slots required by each
          *  mapping entry. */
-        protected final int indexmultiple = 1;
-
-        /** Number of entries with non-null key (includes placeholder slots). */
-        protected int usedslots = 0;
-
-        /** Number of currently available entry slots. */
-        protected int numslots = 0;
+        final int indexmultiple;
 
         /** Number of currently active entries. */
-        protected int size = 0;
+        private int size = 0;
+
+        /** Number of placeholders in entries[]. */
+        private int placeholders = 0;
 
         /** Array of mappings.
          *
@@ -208,22 +210,20 @@ public interface Basket extends Serializable {
          *  Default implementation uses <tt>indexmultiple == 1</tt>, and
          *  stores only the keys in <tt>entries</tt>.
          */
-        protected Object[] entries = null;
+        private Object[] entries = null;
 
-        public Hash(int initialCapacity, float loadFactor) {
+        public Hash() { this(16, 0.75F); }
+        public Hash(int cap, float load) { this(2, cap, load); }
+        public Hash(int indexmultiple, int initialCapacity, float loadFactor) {
             // using a pseudoprime in the form 4x+3 ensures full coverage
-            initialCapacity = initialCapacity / 4;
-            initialCapacity = 4 * initialCapacity + 3;
-            entries = new Object[initialCapacity * indexmultiple];
-            this.numslots = initialCapacity;
+            initialCapacity = (initialCapacity / 4) * 4 + 3;
             this.loadFactor = loadFactor;
+            this.indexmultiple = indexmultiple;
+            this.entries = new Object[initialCapacity * indexmultiple];
         }
 
         public int size() { return size; }
-        public void clear() {
-            for (int i = usedslots * indexmultiple; i >= 0; i--) entries[i] = null;
-            size = usedslots = 0;
-        }
+        public void clear() { for (int i = 0; i<entries.length; i++) entries[i] = null; size = 0; }
 
         public boolean containsKey(Object k) { return indexOf(k) >= 0; }
 
@@ -231,41 +231,62 @@ public interface Basket extends Serializable {
          *  <tt>containsKey()</tt>. For a value map, use Basket.HashMap. */
         public boolean containsValue(Object k) { return containsKey(k); }
 
-        public void remove(Object k) { remove(indexOf(k)); }
 
+        // UGLY
+        public Object[] dumpkeys() {
+            Object[] ret = new Object[size];
+            int pos = 0;
+            for(int i=0; i<entries.length; i+=indexmultiple)
+                if (placeholder!=entries[i] && entries[i]!=null) {
+                    ret[pos++] = entries[i];
+                }
+            return ret;
+        }
+
+        public void remove(Object k) { remove(indexOf(k)); }
         public void remove(int dest) {
             if (dest < 0) return;
-            entryRemoved(dest);
-
             // instead of removing, insert a placeholder
             entries[dest] = placeholder;
             for (int inc=1; inc < indexmultiple; inc++) entries[dest + inc] = null;
             size--;
+            placeholders++;
         }
 
-        /** Insert new entry or replace existing at given index. */
-        public int put(int dest, Object k) {
-            if (usedslots + 1 > numslots * loadFactor) rehash();
-            if (dest >= 0) { // update existing entry
-                entryUpdated(dest);
-            } else {         // new entry
-                dest = -1 * dest - 1;
-                entries[dest] = k;
-                for (int inc = 1; inc < indexmultiple; inc++)
-                    entries[dest + inc] = null;
-                entryAdded(dest);
-            }
-            return dest;
+        public Object get(Object key) { return get(key, 0); }
+        public Object get(Object key, int whichval) {
+            int i = indexOf(key);
+            return i >= 0 ? entries[i + 1 + whichval] : null;
         }
 
-        /** Called immediately after the addition of a new entry. */
-        protected abstract void entryAdded(int dest);
-
-        /** Called immediately after the update of a current entry. */
-        protected abstract void entryUpdated(int dest);
+        public Object put(Object key, Object value) { return put(key, value, 0); }
+        public Object put(Object key, Object value, int whichval) {
+            if (loadFactor * (size + placeholders) > entries.length) rehash();
+            int dest = indexOf(key);
+            Object old = null;
+            if (dest < 0) {
+                dest = -1 * (dest + 1);
+                if (entries[dest] != placeholder) size++;
+                entries[dest] = key;
+                for(int i=1; i<indexmultiple; i++) entries[dest+i] = null;
+            } else {
+                old = entries[dest + 1 + whichval];
+            }
+            entries[dest + 1 + whichval] = value;
+            return old;
+        }
 
-        /** Called immediately before the removal of an entry. */
-        protected abstract void entryRemoved(int dest);
+        /*
+        public boolean containsKey(Object k) { return super.containsValue(k); }
+        public boolean containsValue(Object v) {
+            for (int i=0; i < entries.length/indexmultiple; i++)
+                if ((i == 0 || entries[i * indexmultiple] != null) && // exception for null key
+                    !equals(placeholder, entries[i * indexmultiple]) &&
+                    v == null ? entries[i + 1] == null : v.equals(entries[i + 1]))
+                        return true;
+            return false;
+        }
+        */
 
         /** Compares two keys for equality. <tt>userKey</tt> is the key
          *  passed to the map, <tt>storedKey</tt> is from the map.
@@ -291,19 +312,18 @@ public interface Basket extends Serializable {
          * <p>Uses <tt>placeholder</tt> as a placeholder object, and
          * compares keys using <tt>equals(Object, Object)</tt>.</p>
          */
-        protected int indexOf(Object k) {
+        private int indexOf(Object k) {
             // special case null key
             if (k == null) return equals(placeholder, entries[0]) ? -1 : 0;
 
             int hash = k == null ? 0 : k.hashCode();
-            final int orig = Math.abs(hash) % numslots;
+            final int orig = Math.abs(hash) % (entries.length / indexmultiple);
             int dest = orig * indexmultiple;
             int tries = 1;
             boolean plus = true;
-
             while (entries[dest] != null) {
                 if (equals(k, entries[dest])) return dest;
-                dest = Math.abs((orig + (plus ? 1 : -1) * tries * tries) % numslots) * indexmultiple;
+                dest = Math.abs((orig + (plus ? 1 : -1) * tries * tries) % (entries.length / indexmultiple)) * indexmultiple;
                 if (plus) tries++;
                 plus = !plus;
             }
@@ -314,58 +334,25 @@ public interface Basket extends Serializable {
          *  set (removes <tt>placeholder</tt> references) and if necessary
          *  by increasing the size of the <tt>entries</tt> array.
          */
-        protected void rehash() {
-            int oldnumslots = numslots;
+        private void rehash() {
             Object[] oldentries = entries;
+            entries = new Object[oldentries.length * indexmultiple];
 
-            if (size * 2 > usedslots) numslots *= 2;
-            entries = new Object[numslots * indexmultiple];
-
-            for (int i=0; i < oldnumslots; i++) {
+            for (int i=0; i < (oldentries.length/indexmultiple); i++) {
                 int pos = i * indexmultiple;
                 if (pos > 0 && oldentries[pos] == null) continue;
                 if (oldentries[pos] == placeholder) continue;
 
                 // dont adjust any of the support entries
                 int dest = indexOf(oldentries[pos]);
-                dest = -1 * dest - 1; size++; usedslots++; // always new entry
+                dest = -1 * dest - 1; size++;  // always new entry
                 for (int inc=0; inc < indexmultiple; inc++)
                     entries[dest + inc] = oldentries[pos + inc];
             }
+            placeholders = 0;
         }
     }
 
-    public class HashMap extends Hash implements Map {
-        private static final long serialVersionUID = 2348905755L;
-
-        protected final int indexmultiple = 2;
-
-        public HashMap() { this(16, 0.75F); }
-        public HashMap(int cap, float load) { super(cap, load); }
+    // FIXME, BalancedTree goes here
 
-        public Object get(Object key) { int i = indexOf(key);  return i >= 0 ? entries[i + 1] : null; }
-        public Object put(Object key, Object value) {
-            Object old = null;
-            int dest = indexOf(key);
-            if (dest >= 0) old = entries[(-1 * dest - 1) + 1];
-            dest = put(dest, key);
-            entries[dest + 1] = value;
-            return old;
-        }
-
-        protected void entryAdded(int dest) {}
-        protected void entryUpdated(int dest) {}
-        protected void entryRemoved(int dest) {}
-
-        public boolean containsKey(Object k) { return super.containsValue(k); }
-    
-        public boolean containsValue(Object v) {
-            for (int i=0; i < numslots; i++)
-                if ((i == 0 || entries[i * indexmultiple] != null) && // exception for null key
-                    !equals(placeholder, entries[i * indexmultiple]) &&
-                    v == null ? entries[i + 1] == null : v.equals(entries[i + 1]))
-                        return true;
-            return false;
-        }
-    }
 }