/*
 *  Copyright 2004-2010 Brian S O'Neill
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

package org.cojen.util;

import java.lang.ref.Reference;
import java.lang.ref.ReferenceQueue;
import java.lang.ref.WeakReference;
import java.util.AbstractSet;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * A thread-safe Set that manages canonical objects: sharable objects that are
 * typically immutable. Call the {@link #put put} method for supplying the
 * WeakCanonicalSet with candidate canonical instances.
 * <p>
 * Objects that do not customize the hashCode and equals methods don't make
 * sense to be canonicalized because each instance will be considered unique.
 * The object returned from the {@link #put put} method will always be the same
 * as the one passed in.
 *
 * @author Brian S O'Neill
 */
@SuppressWarnings({ "unchecked", "rawtypes" })
public class WeakCanonicalSet<T> extends AbstractSet<T> {
    private Entry<T>[] table;
    private int count;
    private int threshold;
    private final float loadFactor;
    private final ReferenceQueue<T> queue;

    public WeakCanonicalSet() {
        final int initialCapacity = 101;
        final float loadFactor = 0.75f;
        this.loadFactor = loadFactor;
        this.table = new Entry[initialCapacity];
        this.threshold = (int)(initialCapacity * loadFactor);
        this.queue = new ReferenceQueue<T>();
    }

    /**
     * Pass in a candidate canonical 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 canonical.
     *
     * @param obj candidate canonical object; null is also accepted
     */
    public synchronized <U extends T> U put(U obj) {
        // This implementation is based on the WeakIdentityMap.put method.

        if (obj == null) {
            return null;
        }

        Entry<T>[] tab = this.table;

        // Cleanup after cleared References.
        {
            ReferenceQueue queue = this.queue;
            Reference ref;
            while ((ref = queue.poll()) != null) {
                // Since buckets are single-linked, traverse entire list and
                // cleanup all cleared references in it.
                int index = (((Entry) ref).hash & 0x7fffffff) % tab.length;
                for (Entry<T> e = tab[index], prev = null; e != null; e = e.next) {
                    if (e.get() == null) {
                        if (prev != null) {
                            prev.next = e.next;
                        } else {
                            tab[index] = e.next;
                        }
                        this.count--;
                    } else {
                        prev = e;
                    }
                }
            }
        }

        int hash = hashCode(obj);
        int index = (hash & 0x7fffffff) % tab.length;

        for (Entry<T> e = tab[index], prev = null; e != null; e = e.next) {
            T iobj = e.get();
            if (iobj == null) {
                // Clean up after a cleared Reference.
                if (prev != null) {
                    prev.next = e.next;
                } else {
                    tab[index] = e.next;
                }
                this.count--;
            } else if (e.hash == hash &&
                       obj.getClass() == iobj.getClass() &&
                       equals(obj, iobj)) {
                // Found canonical instance.
                return (U) iobj;
            } else {
                prev = e;
            }
        }

        if (this.count >= this.threshold) {
            // Rehash the table if the threshold is exceeded.
            rehash();
            tab = this.table;
            index = (hash & 0x7fffffff) % tab.length;
        }

        // Create a new entry.
        tab[index] = new Entry<T>(obj, this.queue, hash, tab[index]);
        this.count++;
        return obj;
    }

    public Iterator<T> iterator() {
        return new SetIterator();
    }

    public int size() {
        return this.count;
    }

    public synchronized boolean contains(Object obj) {
        if (obj == null) {
            return false;
        }

        Entry<T>[] tab = this.table;
        int hash = hashCode(obj);
        int index = (hash & 0x7fffffff) % tab.length;

        for (Entry<T> e = tab[index], prev = null; e != null; e = e.next) {
            Object iobj = e.get();
            if (iobj == null) {
                // Clean up after a cleared Reference.
                if (prev != null) {
                    prev.next = e.next;
                } else {
                    tab[index] = e.next;
                }
                this.count--;
            } else if (e.hash == hash &&
                     obj.getClass() == iobj.getClass() &&
                     equals(obj, iobj)) {
                // Found canonical instance.
                return true;
            } else {
                prev = e;
            }
        }

        return false;
    }

    public synchronized String toString() {
        return WeakIdentityMap.toString(this);
    }

    protected int hashCode(Object obj) {
        return obj.hashCode();
    }

    protected boolean equals(Object a, Object b) {
        return a.equals(b);
    }

    private void rehash() {
        int oldCapacity = this.table.length;
        Entry<T>[] tab = this.table;

        int newCapacity = oldCapacity * 2 + 1;
        Entry<T>[] newTab = new Entry[newCapacity];

        this.threshold = (int)(newCapacity * this.loadFactor);
        this.table = newTab;

        for (int i = oldCapacity; i-- > 0; ) {
            for (Entry<T> old = tab[i]; old != null; ) {
                Entry<T> e = old;
                old = old.next;

                // Only copy entry if it hasn't been cleared.
                if (e.get() == null) {
                    this.count--;
                } else {
                    int index = (e.hash & 0x7fffffff) % newCapacity;
                    e.next = newTab[index];
                    newTab[index] = e;
                }
            }
        }
    }

    private static class Entry<T> extends WeakReference<T> {
        int hash;
        Entry<T> next;

        Entry(T canonical, ReferenceQueue<T> queue, int hash, Entry<T> next) {
            super(canonical, queue);
            this.hash = hash;
            this.next = next;
        }
    }

    private class SetIterator implements Iterator<T> {
        private final Entry<T>[] table;

        private int index;

        // To ensure that the iterator doesn't return cleared entries, keep a
        // hard reference to the canonical object. Its existence will prevent
        // the weak reference from being cleared.
        private T entryCanonical;
        private Entry<T> entry;

        SetIterator() {
            this.table = WeakCanonicalSet.this.table;
            this.index = table.length;
        }

        public boolean hasNext() {
            while (this.entry == null || (this.entryCanonical = this.entry.get()) == null) {
                if (this.entry != null) {
                    // Skip past a cleared Reference.
                    this.entry = this.entry.next;
                } else {
                    if (this.index <= 0) {
                        return false;
                    } else {
                        this.entry = this.table[--this.index];
                    }
                }
            }

            return true;
        }

        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }

            this.entry = this.entry.next;
            return this.entryCanonical;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}