--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/com/go/trove/util/FlyweightSet.java	Sat Mar 21 11:00:06 2009 +0000
@@ -0,0 +1,270 @@
+/*
+ * FlyweightSet.java
+ * 
+ * Copyright (c) 2000 Starwave Corporation.  All Rights Reserved.
+ * 
+ * Original author: Brian S O'Neill
+ * 
+ * $Workfile:: FlyweightSet.java                                              $
+ *   $Author: dan $
+ * $Revision: 1.1 $
+ *     $Date: Mon, 13 Oct 2003 12:20:39 +0100 $
+ */
+
+package com.go.trove.util;
+
+import java.lang.ref.*;
+import java.util.*;
+
+/******************************************************************************
+ * A thread-safe Set that manages flyweights: sharable objects that are usually
+ * immutable. Call the {@link #get get} method for supplying the FlyweightSet
+ * with candidate flyweight instances.
+ * <p>
+ * Objects that do not customize the hashCode and equals methods don't make
+ * sense to use as flyweights because each instance will be considered unique.
+ * The object returned from the {@link #get get} method will always be the same
+ * as the one passed in.
+ *
+ * @author Brian S O'Neill
+ * @version
+ * <!--$$Revision: 1.1 $-->, <!--$$JustDate:--> 00/12/18 <!-- $-->
+ * @see Utils#intern
+ */
+public class FlyweightSet extends AbstractSet {
+    // This implementation is basically a stripped down version of
+    // IdentityMap in which the entries contain only a referenced key and
+    // no value.
+    
+    private Entry mTable[];
+    private int mCount;
+    private int mThreshold;
+    private float mLoadFactor;
+    
+    public FlyweightSet() {
+        final int initialCapacity = 101;
+        final float loadFactor = 0.75f;
+        mLoadFactor = loadFactor;
+        mTable = new Entry[initialCapacity];
+        mThreshold = (int)(initialCapacity * loadFactor);
+    }
+
+    /**
+     * Pass in a candidate flyweight object and get a unique instance from this
+     * set. The returned object will always be of the same type as that passed
+     * in. If the object passed in does not equal any object currently in the
+     * set, it will be added to the set, becoming a flyweight.
+     *
+     * @param obj candidate flyweight; null is also accepted
+     */    
+    public synchronized Object put(Object obj) {
+        // This implementation is based on the IdentityMap.put method.
+        
+        if (obj == null) {
+            return null;
+        }
+        
+        Entry tab[] = mTable;
+        int hash = hashCode(obj);
+        int index = (hash & 0x7FFFFFFF) % tab.length;
+        
+        for (Entry e = tab[index], prev = null; e != null; e = e.mNext) {
+            Object iobj = e.get();
+            if (iobj == null) {
+                // Clean up after a cleared Reference.
+                if (prev != null) {
+                    prev.mNext = e.mNext;
+                }
+                else {
+                    tab[index] = e.mNext;
+                }
+                mCount--;
+            }
+            else if (e.mHash == hash &&
+                     obj.getClass() == iobj.getClass() &&
+                     equals(obj, iobj)) {
+                // Found flyweight instance.
+                return iobj;
+            }
+            else {
+                prev = e;
+            }
+        }
+        
+        if (mCount >= mThreshold) {
+            // Cleanup the table if the threshold is exceeded.
+            cleanup();
+        }
+        
+        if (mCount >= mThreshold) {
+            // Rehash the table if the threshold is still exceeded.
+            rehash();
+            tab = mTable;
+            index = (hash & 0x7FFFFFFF) % tab.length;
+        }
+        
+        // Create a new entry.
+        tab[index] = new Entry(obj, hash, tab[index]);
+        mCount++;
+        return obj;
+    }
+    
+    public Iterator iterator() {
+        return new SetIterator();
+    }
+
+    public int size() {
+        return mCount;
+    }
+
+    public boolean contains(Object obj) {
+        if (obj == null) {
+            return false;
+        }
+        
+        Entry tab[] = mTable;
+        int hash = hashCode(obj);
+        int index = (hash & 0x7FFFFFFF) % tab.length;
+        
+        for (Entry e = tab[index], prev = null; e != null; e = e.mNext) {
+            Object iobj = e.get();
+            if (iobj == null) {
+                // Clean up after a cleared Reference.
+                if (prev != null) {
+                    prev.mNext = e.mNext;
+                }
+                else {
+                    tab[index] = e.mNext;
+                }
+                mCount--;
+            }
+            else if (e.mHash == hash &&
+                     obj.getClass() == iobj.getClass() &&
+                     equals(obj, iobj)) {
+                // Found flyweight instance.
+                return true;
+            }
+            else {
+                prev = e;
+            }
+        }
+
+        return false;
+    }
+
+    public String toString() {
+        return IdentityMap.toString(this);
+    }
+
+    protected int hashCode(Object obj) {
+        return obj.hashCode();
+    }
+
+    protected boolean equals(Object a, Object b) {
+        return a.equals(b);
+    }
+
+    private void cleanup() {
+        Entry tab[] = mTable;
+        for (int i = tab.length; i-- > 0; ) {
+            for (Entry e = tab[i], prev = null; e != null; e = e.mNext) {
+                if (e.get() == null) {
+                    // Clean up after a cleared Reference.
+                    if (prev != null) {
+                        prev.mNext = e.mNext;
+                    }
+                    else {
+                        tab[i] = e.mNext;
+                    }
+                    mCount--;
+                }
+                else {
+                    prev = e;
+                }
+            }
+        }
+    }
+    
+    private void rehash() {
+        int oldCapacity = mTable.length;
+        Entry[] tab = mTable;
+        
+        int newCapacity = oldCapacity * 2 + 1;
+        Entry[] newTab = new Entry[newCapacity];
+        
+        mThreshold = (int)(newCapacity * mLoadFactor);
+        mTable = newTab;
+        
+        for (int i = oldCapacity; i-- > 0; ) {
+            for (Entry old = tab[i]; old != null; ) {
+                Entry e = old;
+                old = old.mNext;
+                
+                // Only copy entry if it hasn't been cleared.
+                if (e.get() == null) {
+                    mCount--;
+                }
+                else {
+                    int index = (e.mHash & 0x7FFFFFFF) % newCapacity;
+                    e.mNext = newTab[index];
+                    newTab[index] = e;
+                }
+            }
+        }
+    }
+    
+    private static class Entry extends WeakReference {
+        int mHash;
+        Entry mNext;
+        
+        Entry(Object flyweight, int hash, Entry next) {
+            super(flyweight);
+            mHash = hash;
+            mNext = next;
+        }
+    }
+
+    private class SetIterator implements Iterator {
+        private Entry[] mTable = FlyweightSet.this.mTable;
+        private int mIndex = mTable.length;
+        private Entry mEntry;
+        // To ensure that the iterator doesn't return cleared entries, keep a
+        // hard reference to the flyweight. Its existence will prevent the weak
+        // reference from being cleared.
+        private Object mEntryFlyweight;
+        private Entry mLastReturned;
+        
+        public boolean hasNext() {
+            while (mEntry == null ||
+                   (mEntryFlyweight = mEntry.get()) == null) {
+                if (mEntry != null) {
+                    // Skip past a cleared Reference.
+                    mEntry = mEntry.mNext;
+                }
+                else {
+                    if (mIndex <= 0) {
+                        return false;
+                    }
+                    else {
+                        mEntry = mTable[--mIndex];
+                    }
+                }
+            }
+
+            return true;
+        }
+        
+        public Object next() {
+            if (!hasNext()) {
+                throw new NoSuchElementException();
+            }
+
+            mEntry = mEntry.mNext;
+            return mEntryFlyweight;
+        }
+        
+        public void remove() {
+            throw new UnsupportedOperationException();
+        }
+    }
+}