From aafd5dac118e52d0f0646082ab2beb6e64cb1e7e Mon Sep 17 00:00:00 2001 From: adam Date: Thu, 6 Jan 2005 23:35:56 +0000 Subject: [PATCH] added Basket.java darcs-hash:20050106233556-5007d-25d646ee7a58b3c637e23ad4e8c301a117a4af2a.gz --- src/org/ibex/util/Basket.java | 365 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 365 insertions(+) create mode 100644 src/org/ibex/util/Basket.java diff --git a/src/org/ibex/util/Basket.java b/src/org/ibex/util/Basket.java new file mode 100644 index 0000000..d7a434d --- /dev/null +++ b/src/org/ibex/util/Basket.java @@ -0,0 +1,365 @@ +// Copyright 2000-2005 the Contributors, as shown in the revision logs. +// Licensed under the Apache Public Source License 2.0 ("the License"). +// You may not use this file except in compliance with the License. + +package org.ibex.util; + +import java.io.Serializable; + +public interface Basket extends Serializable { + public boolean containsValue(Object object); + public void clear(); + public int size(); + public void remove(Object object); + + public interface List extends Basket { + public void add(Object object); + public void add(int index, Object object); + public Object set(int index, Object object); + public Object get(int index); + public Object remove(int index); + public int indexOf(Object object); + public void reverse(); + public void sort(CompareFunc c); + } + + public interface RandomAccess extends List { } + + public interface Stack extends Basket { + public Object pop(); + public Object peek(); + public void push(Object object); + } + + public interface Map extends Basket { + public boolean containsKey(Object key); + public Object get(Object key); + public Object put(Object key, Object value); + } + + public interface CompareFunc { + public int compare(Object a, Object b); + } + + + // Implementations //////////////////////////////////////////////////////// + + public class Array implements RandomAccess, Stack { + private static final long serialVersionUID = 1233428092L; + + private Object[] o; + private int size = 0; + + public Array() { this(10); } + public Array(int initialCapacity) { o = new Object[initialCapacity]; } + public Array(Object entry) { this(1); add(entry); } + + public void add(Object obj) { add(size, obj); } + public void add(int i, Object obj) { + size(size + 1); + if (size - 1 > i) System.arraycopy(o, i, o, size, size - i - 1); + o[i] = obj; size++; + } + public Object set(int i, Object obj) { + if (i >= size) throw new IndexOutOfBoundsException( + "index "+i+" is beyond list boundary "+size); + Object old = o[i]; o[i] = obj; return old; + } + public Object get(int i) { + if (i >= size) throw new IndexOutOfBoundsException( + "index "+i+" is beyond list boundary "+size); + return o[i]; + } + public Object remove(int i) { + if (i >= size || i < 0) throw new IndexOutOfBoundsException( + "index "+i+" is beyond list boundary "+size); + Object old = o[i]; o[i] = null; + if (size - 1 > i) System.arraycopy(o, i + 1, o, i, size - i - 1); + size--; return old; + } + public void remove(Object obj) { remove(indexOf(obj)); } + + public int indexOf(Object obj) { + for (int i=0; i < size; i++) + if ((obj == null && o[i] == null) || obj.equals(o[i])) return i; + return -1; + } + + public boolean containsValue(Object obj) { + for (int i=0; i < size; i++) + if ((obj == null && o[i] == null) || obj.equals(o[i])) return true; + return false; + } + public void clear() { for (int i=0; i < size; i++) o[i] = null; size = 0; } + public int size() { return size; } + public void size(int s) { + if (o.length >= s) return; + Object[] newo = new Object[s]; + System.arraycopy(o, 0, newo, 0, size); + o = newo; + } + + public void reverse() { + Object tmp; int max = (int)Math.floor((double)size / 2); + for (int i=0; i < size; i++) { tmp = o[i]; o[i] = o[size - i]; o[size - i] = tmp; } + } + + public void sort(CompareFunc c) { sort(this, null, c, 0, size); } + + private static void sort(Array a, Array b, CompareFunc c, int start, int end) { + Object tmpa, tmpb = null; + if(start >= end) return; + if(end-start <= 6) { + for(int i=start+1;i<=end;i++) { + tmpa = a.o[i]; + if (b != null) tmpb = b.o[i]; + int j; + for(j=i-1;j>=start;j--) { + if(c.compare(a.o[j],tmpa) <= 0) break; + a.o[j+1] = a.o[j]; + if (b != null) b.o[j+1] = b.o[j]; + } + a.o[j+1] = tmpa; + if (b != null) b.o[j+1] = tmpb; + } + return; + } + Object pivot = a.o[end]; + int lo = start - 1; + int hi = end; + do { + while(c.compare(a.o[++lo],pivot) < 0) { } + while((hi > lo) && c.compare(a.o[--hi],pivot) > 0) { } + swap(a, lo,hi); + if (b != null) swap(b, lo,hi); + } while(lo < hi); + + swap(a, lo,end); + if (b != null) swap(b, lo,end); + sort(a, b, c, start, lo-1); + sort(a, b, c, lo+1, end); + } + + private static final void swap(Array vec, int a, int b) { + if(a != b) { + Object tmp = vec.o[a]; + vec.o[a] = vec.o[b]; + vec.o[b] = tmp; + } + } + + public Object peek() { + if (size < 1) throw new IndexOutOfBoundsException("array is empty"); + return o[size - 1]; + } + public Object pop() { return remove(size - 1); } + 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. + * + *

See C. Radke, Communications of the ACM, 1970, 103-105

+ * + * @author adam@ibex.org, crawshaw@ibex.org + */ + public abstract class Hash implements Basket { + private 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; + }; + + /** When loadFactor * usedslots > num_slots, call + * rehash(). */ + protected 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; + + /** Number of currently active entries. */ + protected int size = 0; + + /** Array of mappings. + * + *

Each map requires multiple slots in the array, and subclasses + * can vary the number of required slots without reimplementing all + * the functions of this class by changing the value of + * indexmultiple.

+ * + * Default implementation uses indexmultiple == 1, and + * stores only the keys in entries. + */ + protected Object[] entries = null; + + public Hash(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; + this.loadFactor = loadFactor; + } + + public int size() { return size; } + public void clear() { + for (int i = usedslots * indexmultiple; i >= 0; i--) entries[i] = null; + size = usedslots = 0; + } + + public boolean containsKey(Object k) { return indexOf(k) >= 0; } + + /** Warning: This function is equivalent here to + * containsKey(). For a value map, use Basket.HashMap. */ + public boolean containsValue(Object k) { return containsKey(k); } + + 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--; + } + + /** 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; + } + + /** 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); + + /** Called immediately before the removal of an entry. */ + protected abstract void entryRemoved(int dest); + + /** Compares two keys for equality. userKey is the key + * passed to the map, storedKey is from the map. + * + *

Default implementation provides standard Java equality + * testing, k1 == null ? k2 == null : k1.equals(k2).

+ */ + protected boolean equals(Object userKey, Object storedKey) { + return userKey == null ? storedKey == null : userKey.equals(storedKey); + } + + /** Returns the array position in entries, adjusted for + * indexmultiple, where k is/should be stored + * using Radke's quadratic residue linear probing. + * + *

entries[0] is a hard coded exception for the null + * key.

+ * + *

If the key is not found, this function returns + * (-1 * indexPosition) - 1, where indexPosition + * is the array position where the mapping should be stored.

+ * + *

Uses placeholder as a placeholder object, and + * compares keys using equals(Object, Object).

+ */ + protected 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; + 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; + if (plus) tries++; + plus = !plus; + } + return -1 * dest - 1; + } + + /** Doubles the available entry space, first by packing the data + * set (removes placeholder references) and if necessary + * by increasing the size of the entries array. + */ + protected void rehash() { + int oldnumslots = numslots; + Object[] oldentries = entries; + + if (size * 2 > usedslots) numslots *= 2; + entries = new Object[numslots * indexmultiple]; + + for (int i=0; i < oldnumslots; 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 + for (int inc=0; inc < indexmultiple; inc++) + entries[dest + inc] = oldentries[pos + inc]; + } + } + } + + 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); } + + 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; + } + } +} -- 1.7.10.4