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

package edu.emory.mathcs.util.collections.longs;

import java.util.*;
import java.lang.reflect.*;
import java.io.IOException;
import java.io.*;
import edu.emory.mathcs.util.collections.*;

/**
 * Hash set of long numbers. It uses open addressing with quadratic residue
 * search to avoid clustering. No additional memory per entry is needed, there
 * is therefore no memory allocation on add() unless rehashing is required.
 *
 * @author Dawid Kurzyniec
 * @version 1.0
 */
public class LongRadkeHashSet extends AbstractLongSet
                              implements Cloneable, java.io.Serializable {

    transient long[] elements;
    transient byte[] states;
    transient int size;
    transient int fill;
    int treshold;

    final long min, max;
    final float loadFactor;
    final float resizeTreshold;

    private final static byte EMPTY   = 0;
    private final static byte FULL    = 1;
    private final static byte REMOVED = -1;

    public LongRadkeHashSet() {
        this(19);
    }

    public LongRadkeHashSet(int minInitialCapacity) {
        this(minInitialCapacity, 0.75f, 0.3f);
    }

    public LongRadkeHashSet(int minInitialCapacity, long min, long max) {
        this(minInitialCapacity, min, max, 0.75f, 0.3f);
    }

    public LongRadkeHashSet(int minInitialCapacity, float loadFactor, float resizeTreshold) {
        this(minInitialCapacity, Long.MIN_VALUE, Long.MAX_VALUE,
             loadFactor, resizeTreshold);
    }

    public LongRadkeHashSet(int minInitialCapacity, long min, long max,
                            float loadFactor, float resizeTreshold) {
        int initialCapacity = RadkeHashMap.radkeAtLeast(minInitialCapacity);
        if (min > max) throw new IllegalArgumentException();
        this.min = min;
        this.max = max;
        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 long[initialCapacity];
        states = new byte[initialCapacity];
        size = 0;
        fill = 0;
        this.loadFactor = loadFactor;
        this.resizeTreshold = resizeTreshold;
        treshold = (int)(loadFactor * initialCapacity);
    }

    public LongRadkeHashSet(LongSet m) {
        this(Math.max((int) (m.size() / 0.75) + 1, 19), m.min(), m.max());
        addAll(m);
    }

    public LongRadkeHashSet(LongCollection c) {
        this(Math.max((int) (c.size() / 0.75) + 1, 19),
             (c instanceof LongSet ? ((LongSet)c).min() : Long.MIN_VALUE),
             (c instanceof LongSet ? ((LongSet)c).max() : Long.MAX_VALUE));
        addAll(c);
    }

    public long min() { return min; }
    public long max() { return max; }

    public boolean add(long elem) {
        if (elem < min || elem > max) return false;
        int hsize = elements.length;
        int p = phash(elem) % hsize;
        int j = -hsize;
        int refill = -1;
        while (true) {
            byte state = states[p];
            if (state == EMPTY) {
                // empty slot; check if we found REMOVED placeholder before
                // to use it instead of filling out this new spot
                if (refill >= 0) {
                    elements[refill] = elem;
                    states[refill] = FULL;
                    size++;
                    return true;
                }
                else {
                    elements[p] = elem;
                    states[p] = FULL;
                    size++;
                    fill++;
                    if (fill >= treshold) {
                         if (size >= fill*resizeTreshold) {
                             rehash(RadkeHashMap.radkeAtLeast(elements.length+1));
                         }
                         else {
                             // only rehash (to remove "REMOVED"), but do not
                             // resize
                             rehash(elements.length);
                         }
                    }
                    return true;
                }
            }
            else if (state == REMOVED) {
                // maybe can refill, but only if no overwrite; need to check
                // up to the end of the chain
                refill = p;
            }
            else if (elements[p] == elem) {
                // already in the set
                return false;
            }
            j += 2;
            p += (j > 0 ? j : -j);
            if (p >= hsize) p -= hsize;
        }
    }

    public boolean contains(long elem) {
        return find(elem) >= 0;
    }

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

    // find index of a given elem, or -1 if not found
    private int find(long elem) {
        if (elem < min || elem > max) return -1;
        int hsize = elements.length;
        int p = phash(elem) % hsize;
        int j = -hsize;

        while (true) {
            byte state = states[p];
            if (state == EMPTY) {
                // empty slot; not found
                return -1;
            }
            else if (elements[p] == elem) {
                return p;
            }

            j += 2;
            p += (j > 0 ? j : -j);
            if (p >= hsize) p -= hsize;
        }
    }

    private void rehash(int newcapacity) {
        long[] oldelements = this.elements;
        byte[] oldstates = this.states;
        this.elements = new long[newcapacity];
        this.states = new byte[newcapacity];
        size = 0;
        fill = 0;
        treshold = (int)(loadFactor * newcapacity);
        for (int i=0; i<oldelements.length; i++) {
            if (oldstates[i] == FULL) add(oldelements[i]);
        }
    }

    public void clear() {
        Arrays.fill(states, EMPTY);
        size = 0;
        fill = 0;
    }

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

    public long size64() {  // PREPROC: Long,Int only
        return size;        // PREPROC: Long,Int only
    }                       // PREPROC: Long,Int only
                            // PREPROC: Long,Int only
    public int size() {
        return size;
    }

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

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

        if (!(other instanceof LongSet)) return false;
        LongSet that = (LongSet)other;
        if (that.size() != size()) return false;
        for (int i=0; i<elements.length; i++) {
            if (states[i] == FULL && !that.contains(elements[i])) return false;
        }

        return true;
    }

    public int hashCode() {
        int hash = 0;
        for (int i=0; i<elements.length; i++) {
            if (states[i] == FULL) hash += hash(elements[i]);
        }
        return hash;
    }

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

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


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

    public boolean removeAll(LongCollection c) {
        boolean modified = false;
        if (elements.length*2 < c.size()) {
            for (int i=0; i<elements.length; i++) {
                if (states[i] == FULL && c.contains(elements[i])) {
                    states[i] = REMOVED;
                    size--;
                    modified = true;
                }
            }
        }
        else {
            for (LongIterator itr = c.iterator(); itr.hasNext();) {
                modified |= remove(itr.next());
            }
        }
        return modified;
    }

    public boolean retainAll(LongCollection c) {
        boolean modified = false;
        if (elements.length*4 < c.size()) {
            for (int i=0; i<elements.length; i++) {
                if (states[i] == FULL && !c.contains(elements[i])) {
                    states[i] = REMOVED;
                    size--;
                    modified = true;
                }
            }
        }
        else {
            LongRadkeHashSet tmp =
                new LongRadkeHashSet(elements.length, loadFactor, resizeTreshold);
            for (LongIterator itr = c.iterator(); itr.hasNext();) {
                long elem = itr.next();
                int p = find(elem);
                if (p < 0) continue;
                tmp.add(elem);
                modified = true;
            }
            if (modified) {
                this.elements = tmp.elements;
                this.states = tmp.states;
                this.size = tmp.size;
                this.fill = tmp.fill;
            }
        }
        return modified;
    }

    public long[] toArray(long a[]) {
        int size = (int)size();
        if (a.length < size) a = new long[size];

        int i=0;

        for (int j=0; j<elements.length; j++) {
            if (states[j] == FULL) a[i++] = elements[j];
        }

        return a;
    }

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

        int i=0;

        for (int j=0; j<elements.length; j++) {
            if (states[j] == FULL) a[i++] = elements[j];
        }

        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++) {
            if (states[i] == FULL) out.writeLong(elements[i]);
        }
    }

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

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

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

    private final static int hash(long e) {
        return (int)((e & 0xffffffff) ^ (e >>> 32)); // PREPROC: Long only
//        return e;                                  // PREPROC: except Long
    }

    private final static int phash(long e) {
        return (int)((e & 0x7fffffff) ^ (e >>> 33)); // PREPROC: Long only
//        return e & 0x7fffffff;                     // PREPROC: Int only
//        return e & 0xffff;                         // PREPROC: Short only
    }
}
