/*
 * Written by Dawid Kurzyniec and released to the public domain, as explained
 * at http://creativecommons.org/licenses/publicdomain
 */

package edu.emory.mathcs.util.collections;

import java.util.*;
import java.lang.reflect.*;
import java.io.IOException;
import java.io.*;

/**
 * @author Dawid Kurzyniec
 * @version 1.0
 */
public class RadkeHashSet implements Set, Cloneable, java.io.Serializable {

    transient Object[] elements;
    transient int size;
    transient int fill;
    int treshold;

    final float loadFactor;
    final float resizeTreshold;

    private final static Object NULL    = new Object();
    private final static Object REMOVED = new Object();

    public RadkeHashSet() {
        this(19);
    }

    public RadkeHashSet(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }

    public RadkeHashSet(int initialCapacity, float loadFactor) {
        this(initialCapacity, loadFactor, 0.3f);
    }

    public RadkeHashSet(int initialCapacity, float loadFactor, float resizeTreshold) {
        initialCapacity = RadkeHashMap.radkeAtLeast(initialCapacity);
        if (loadFactor <= 0 || loadFactor > 1) {
            throw new IllegalArgumentException("Load factor must be betweeen 0 and 1");
        }
        if (resizeTreshold <= 0 || resizeTreshold > 1) {
            throw new IllegalArgumentException("Fill treshold must be betweeen 0 and 1");
        }
        elements = new Object[initialCapacity];
        size = 0;
        fill = 0;
        this.loadFactor = loadFactor;
        this.resizeTreshold = resizeTreshold;
        treshold = (int)(loadFactor * initialCapacity);
    }

    public RadkeHashSet(Set m) {
        this(Math.max((int) (m.size() / 0.75) + 1, 19), 0.75f);
        addAll(m);
    }

    public boolean add(Object elem) {
        if (elem == null) elem = NULL;
        int hsize = elements.length;
        int start = (elem.hashCode() & 0x7fffffff) % hsize;
        int refill = -1;

        // initial guess

        Object prev = elements[start];
        if (prev == null) {
            elements[start] = elem;
            size++;
            fill++;
            if (fill >= treshold) rehash();
            return true;
        }
        else if (prev == REMOVED) {
            refill = start;
        }
        else if (eqNonNull(prev, elem)) {
            return false;
        }

        int p;

        // collision handling

        p = start+1;
        if (p >= hsize) p -= hsize;
        prev = elements[p];
        if (prev == null) {
            if (refill >= 0) {
                elements[refill] = elem;
                size++;
                return true;
            }
            else {
                elements[p] = elem;
                size++;
                fill++;
                if (fill >= treshold) rehash();
                return true;
            }
        }
        else if (prev == REMOVED) {
            if (refill < 0) refill = p;
        }
        else if (eqNonNull(prev, elem)) {
            return false;
        }

        p = start-1;
        if (p < 0) p += hsize;
        prev = elements[p];
        if (prev == null) {
            if (refill >= 0) {
                elements[refill] = elem;
                size++;
                return true;
            }
            else {
                elements[p] = elem;
                size++;
                fill++;
                if (fill >= treshold) rehash();
                return true;
            }
        }
        else if (prev == REMOVED) {
            if (refill < 0) refill = p;
        }
        else if (eqNonNull(prev, elem)) {
            return false;
        }

        // loop for the rest
        int j=5;
        int pu=start+4, pd=start-4;
        while (j<hsize) {
            if (pu >= hsize) pu -= hsize;

            prev = elements[pu];
            if (prev == null) {
                if (refill >= 0) {
                    elements[refill] = elem;
                    size++;
                    return true;
                }
                else {
                    elements[pu] = elem;
                    size++;
                    fill++;
                    if (fill >= treshold) rehash();
                    return true;
                }
            }
            else if (prev == REMOVED) {
                if (refill < 0) refill = pu;
            }
            else if (eqNonNull(prev, elem)) {
                return false;
            }

            if (pd < 0) pd += hsize;

            prev = elements[pd];
            if (prev == null) {
                if (refill >= 0) {
                    elements[refill] = elem;
                    size++;
                    return true;
                }
                else {
                    elements[pd] = elem;
                    size++;
                    fill++;
                    if (fill >= treshold) rehash();
                    return true;
                }
            }
            else if (prev == REMOVED) {
                if (refill < 0) refill = pd;
            }
            else if (eqNonNull(prev, elem)) {
                return false;
            }

            pu+=j;
            pd-=j;
            j+=2;
        }
        throw new RuntimeException("set is full");
    }

    public boolean contains(Object elem) {
        //return find(elem) >= 0; // the following is equivalent (optimization)

        if (elem == null) elem = NULL;
        int hsize = elements.length;
        int start = (elem.hashCode() & 0x7fffffff) % hsize;

        Object prev;
        prev = elements[start];
        if (prev == null) return false;
        else if (eqNonNull(prev, elem)) return true;

        int p;
        p = start+1; if (p >= hsize) p -= hsize;
        prev = elements[p];
        if (prev == null) return false;
        else if (eqNonNull(prev, elem)) return true;

        p = start-1; if (p < 0) p += hsize;
        prev = elements[p];
        if (prev == null) return false;
        else if (eqNonNull(prev, elem)) return true;

        int j=5;
        int pu= start+4;
        int pd = start-4;
        while (j<hsize) {
            if (pu >= hsize) pu -= hsize;
            prev = elements[pu];
            if (prev == null) return false;
            else if (eqNonNull(prev, elem)) return true;

            if (pd < 0) pd += hsize;
            prev = elements[pd];
            if (prev == null) return false;
            else if (eqNonNull(prev, elem)) return true;

            pu += j;
            pd -= j;
            j+=2;
        }
        return false;
    }

    public boolean remove(Object elem) {
        int p = find(elem);
        if (p < 0) return false;
        elements[p] = REMOVED;
        size--;
        return true;
    }

    // find index of a given elem, or -1 if not found
    private int find(Object elem) {
        if (elem == null) elem = NULL;
        int hsize = elements.length;
        int start = (elem.hashCode() & 0x7fffffff) % hsize;

        Object prev;
        prev = elements[start];
        if (prev == null) return -1;
        else if (eqNonNull(prev, elem)) return start;

        int p;
        p = start+1; if (p >= hsize) p -= hsize;
        prev = elements[p];
        if (prev == null) return -1;
        else if (eqNonNull(prev, elem)) return p;

        p = start-1; if (p < 0) p += hsize;
        prev = elements[p];
        if (prev == null) return -1;
        else if (eqNonNull(prev, elem)) return p;

        int j=5;
        int pu= start+4;
        int pd = start-4;
        while (j<hsize) {
            if (pu >= hsize) pu -= hsize;
            prev = elements[pu];
            if (prev == null) return -1;
            else if (eqNonNull(prev, elem)) return pu;

            if (pd < 0) pd += hsize;
            prev = elements[pd];
            if (prev == null) return -1;
            else if (eqNonNull(prev, elem)) return pd;

            pu += j;
            pd -= j;
            j+=2;
        }
        return -1;
    }

    private void rehash() {
        if (size >= fill*resizeTreshold) {
            rehash(RadkeHashMap.radkeAtLeast(elements.length+1));
        }
        else {
            // only rehash (to remove "REMOVED"), but do not
            // resize
            rehash(elements.length);
        }
    }

    private void rehash(int newcapacity) {
//        System.out.println("Rehashing to " + newcapacity + "; size is " + size + "; fill is " + fill);
        Object[] oldelements = this.elements;
        this.elements = new Object[newcapacity];
        size = 0;
        fill = 0;
        treshold = (int)(loadFactor * newcapacity);
        for (int i=0; i<oldelements.length; i++) {
            if (oldelements[i] == null || oldelements[i] == REMOVED) continue;
            add(oldelements[i]);
        }
    }

    public void clear() {
        Arrays.fill(elements, null);
        size = 0;
        fill = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public boolean addAll(Collection c) {
        boolean modified = false;
        for (Iterator itr = c.iterator(); itr.hasNext();) {
            modified |= add(itr.next());
        }
        return modified;
    }

    public Iterator iterator() {
        return new HashIterator();
    }

    public boolean equals(Object other) {
        if (other == this) return true;

        if (!(other instanceof Set)) return false;
        Set that = (Set)other;
        if (that.size() != size()) return false;
        for (int i=0; i<elements.length; i++) {
            Object elem = elements[i];
            if (elem == null || elem == REMOVED) continue;
            if (elem == NULL) elem = null;
            if (!that.contains(elem)) return false;
        }

        return true;
    }

    public int hashCode() {
        int hash = 0;
        for (int i=0; i<elements.length; i++) {
            Object elem = elements[i];
            if (elem == null || elem == REMOVED) continue;
            if (elem == NULL) elem = null;
            hash += (elem == null ? 0 : elem.hashCode());
        }
        return hash;
    }

    public Object clone() {
        RadkeHashSet result;
        try {
            result = (RadkeHashSet)super.clone();
        } catch (CloneNotSupportedException e) {
            throw new RuntimeException(e);
        }

        result.elements = new Object[elements.length];
        result.fill = 0;
        result.size = 0;
        result.addAll(this);
        return result;
    }


    private class HashIterator implements Iterator {
        int curr;
        int next;
        HashIterator() {
            this.curr = 0;
            this.next = 0;
            findNext();
        }
        public boolean hasNext() {
            return next < elements.length;
        }
        public Object next() {
            if (next >= elements.length) {
                throw new NoSuchElementException();
            }
            curr = next++;
            findNext();
            return elements[curr];
        }
        private void findNext() {
            while (next < elements.length &&
                   (elements[next] == null || elements[next] == REMOVED)) {
                next++;
            }
        }
        public void remove() {
            if (elements[curr] != REMOVED) {
                elements[curr] = REMOVED;
                size--;
            }
        }
    }

    public boolean containsAll(Collection c) {
        for (Iterator itr = c.iterator(); itr.hasNext();) {
            if (!contains(itr.next())) return false;
        }
        return true;
    }

    public boolean removeAll(Collection c) {
        boolean modified = false;
        if (elements.length*2 < c.size()) {
            for (int i=0; i<elements.length; i++) {
                Object key = elements[i];
                if (key == null || key == REMOVED) continue;
                if (key == NULL) key = null;
                if (c.contains(key)) {
                    elements[i] = REMOVED;
                    size--;
                    modified = true;
                }
            }
        }
        else {
            for (Iterator itr = c.iterator(); itr.hasNext();) {
                modified |= remove(itr.next());
            }
        }
        return modified;
    }

    public boolean retainAll(Collection c) {
        boolean modified = false;
        if (elements.length*4 < c.size()) {
            for (int i=0; i<elements.length; i++) {
                Object key = elements[i];
                if (key == null || key == REMOVED) continue;
                if (key == NULL) key = null;
                if (!c.contains(key)) {
                    elements[i] = REMOVED;
                    size--;
                    modified = true;
                }
            }
        }
        else {
            RadkeHashSet tmp = new RadkeHashSet(elements.length, loadFactor, resizeTreshold);
            for (Iterator itr = c.iterator(); itr.hasNext();) {
                Object elem = itr.next();
                int p = find(elem);
                if (p < 0) continue;
                tmp.add(elem);
                modified = true;
            }
            if (modified) {
                this.elements = tmp.elements;
                this.size = tmp.size;
                this.fill = tmp.fill;
            }
        }
        return modified;
    }

    public Object[] toArray(Object a[]) {
        int size = size();
        if (a.length < size) {
            a = (Object[])Array.newInstance(a.getClass().getComponentType(), size);
        }

        int i=0;

        for (int j=0; j<elements.length; j++) {
            Object key = elements[j];
            if (key == null || key == REMOVED) continue;
            if (key == NULL) key = null;
            a[i++] = key;
        }

        return a;
    }

    public Object[] toArray() {
        Object[] a = new Object[size()];

        int i=0;

        for (int j=0; j<elements.length; j++) {
            Object key = elements[j];
            if (key == null || key == REMOVED) continue;
            if (key == NULL) key = null;
            a[i++] = key;
        }

        return a;
    }


    private void writeObject(ObjectOutputStream out) throws IOException {
        out.defaultWriteObject();
        out.writeInt(elements.length); // the capacity
        out.writeInt(size);        // number of entries

        for (int i=0; i<elements.length; i++) {
            Object elem = elements[i];
            if (elem == null || elem == REMOVED) continue;
            if (elem == NULL) elem = null;
            out.writeObject(elem);
        }
    }

    private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
        in.defaultReadObject();
        int capacity = in.readInt();
        this.elements = new Object[capacity];

        // number of entries
        int size = in.readInt();

        for (int i=0; i<size; i++) {
            Object elem = in.readObject();
            add(elem);
        }
    }

    private final static boolean eqNonNull(Object o1, Object o2) {
        return o1 == o2 || o1.equals(o2);
    }

//
//    private static class Test {
//        public static void permutationTest(int hsize, int iters) {
//            boolean[] hits = new boolean[hsize];
//            Random r = new Random();
//            for (int i=0; i<iters; i++) {
//                Arrays.fill(hits, false);
//                int hash = r.nextInt();
//
//                int p = (hash & 0x7fffffff) % hsize;
//                int j = -hsize;
//
//                System.out.print(".");
//                for (int k=0; k<hsize; k++) {
//                    if (hits[p]) throw new IllegalStateException();
//                    hits[p] = true;
//
//                    j += 2;
//                    p += (j > 0 ? j : -j);
//                    if (p >= hsize) p -= hsize;
//                }
//
//            }
//        }
//
//        public static void hashSetTest(int iters, int floor, int ceil, int gets) {
//            Random r = new Random();
//            RadkeHashSet rset = new RadkeHashSet(ceil / 2, 0.75f, 0.3f);
//            HashSet hset = new HashSet(ceil / 2);
//
//            long total = 0;
//            for (int i=0; i<iters; i++) {
//                System.out.println("total: " + total);
//                while (rset.size() < ceil) {
//                    Object elem = new Integer(r.nextInt(ceil*5));
//
//                    boolean b1 = rset.add(elem);
//                    boolean b2 = hset.add(elem);
//                    if (b1 != b2) throw new IllegalStateException();
//                    if (b1) total++;
//                }
//                if (!rset.equals(hset) || !hset.equals(rset)) {
//                    throw new IllegalStateException();
//                }
//
//                for (int j=0; j<gets; j++) {
//                    Object elem = new Integer(r.nextInt(ceil*5));
//                    boolean b1 = hset.contains(elem);
//                    boolean b2 = rset.contains(elem);
//                    if (b1 != b2) throw new IllegalStateException();
//                }
//
//                while (rset.size() > floor) {
//                    Object elem = new Integer(r.nextInt(ceil*5));
//                    boolean b1 = rset.remove(elem);
//                    boolean b2 = hset.remove(elem);
//                    if (b1 != b2) throw new IllegalStateException();
//                }
//
//                if (!rset.equals(hset) || !hset.equals(rset)) {
//                    throw new IllegalStateException();
//                }
//            }
//        }
//    }
//
//    public static void main(String[] args) {
// //        Test.permutationTest(0x0080000B, 10);
//        Test.hashSetTest(100, 1, 21880, 1000);
//    }
}
