/*
 *  @author Ranides Atterwim <ranides@gmail.com>
 *  @copyright Ranides Atterwim
 *  @license WTFPL
 *  @url http://ranides.net/projects/assira
 */

package net.ranides.assira.collection.set;

import java.util.AbstractSet;
import java.util.Arrays;
import java.util.IdentityHashMap;
import java.util.Iterator;
import net.ranides.assira.collection.ArrayUtils;


/**
 * <p>
 * Zbiór, który nie używa metody {@code equals} do porównywania elementów, lecz
 * sprawdza identyczność referencji. Wersja znacznie wydajniejsza od naiwnej 
 * implementacji opierającej się na {@link IdentityHashMap} wzorowana na kodzie 
 * udostępnianym na 
 * <a href="http://www.koders.com/java/fid611A1053D4CDF966C74549F3B92EE935B298D424.aspx">www.koders.com</a>
 * będącym częścią projektu <a href="https://wikis.oracle.com/display/MaxineVM/Assembler">Maxwell Assembler</a>. 
 * </p><p>
 * Porównać z cięższą wersją używającą linkowanych węzłów z:
 * <a href="http://www.castor.org/1.2/javadoc/org/castor/util/IdentitySet.html">castor.org</a>
 * </p>
 * @param <T> 
 * @author ranides
 */
@SuppressWarnings("PMD.CompareObjectsWithEquals")
public final class IdentitySet<T> extends AbstractSet<T> {

    private int size;
    private int threshold;
    private final float loadFactor;
    private Object[] table;
    
    /**
     * Tworzy nowy zbiór o początkowej {@code capacity = 16}.
     */
    public IdentitySet() {
        this(16);
    }
    
    /**
     * Tworzy nowy zbiór o określonej pojemności oraz {@code loadFactor = 75%}.
     * @param initialCapacity
     */
    public IdentitySet(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }

    /**
     * Tworzy nowy zbiór o określonej początkowej {@code capacity} oraz {@code loadFactor}
     * @param initialCapacity
     * @param loadFactor
     */
    public IdentitySet(int initialCapacity, float loadFactor) {
        this.loadFactor = loadFactor;
        initTable(initialCapacity);
    }
    
    private void initTable(int size) {
        table = new Object[size];
        threshold = (int)Math.ceil(size * loadFactor);
    }

    @Override
    public boolean add(T element) {
        iadd(element);
        return true;
    }
    
    private boolean iadd(Object element) {
        if (element == null) {
            return false;
        }
        if (size > threshold) {
            grow();
        }
        final int start = System.identityHashCode(element) % table.length;
        int i = start;
        do {
            final Object entry = table[i];            
            if (entry == null) {
                table[i] = element;
                size++;
                return true;
            }
            if (entry == element) {
                return false;
            }
            if (++i == table.length) {
                i = 0;
            }
        } while (i != start);

        return false;
    }
    
    @Override
    public boolean contains(Object element) {
        final int start = System.identityHashCode(element) % table.length;
        int i = start;
        while (true) {
            final Object entry = table[i];            
            if (entry == element) {
                return true;
            }
            if (entry == null) {
                return false;
            }
            if (++i == table.length) {
                i = 0;
            }
            assert i != start;
        }        
    }
    
    @Override
    public boolean remove(Object element) {
        final int start = System.identityHashCode(element) % table.length;
        int i = start;
        while (true) {
            final Object entry = table[i];            
            if (entry == element) {
                table[i] = null;
                return true;
            }
            if (entry == null) {
                return false;
            }
            if (++i == table.length) {
                i = 0;
            }
            assert i != start;
        }  
    }
    
    private void grow() {
        final Object[] prev = table;
        initTable(table.length * 2);
        size = 0;
        for (Object item : prev) {
            iadd(item);
        }
    }

    @Override
    public int size() {
        return size;
    }
    
    @Override
    @SuppressWarnings("unchecked")
    public Iterator<T> iterator() {
        final Object[] array = new Object[size()];
        int j = 0;
        for (int i = 0; i < table.length; i++) {
            final Object element = table[i];
            if (element != null) {
                array[j++] = element;
            }
        }
        return (Iterator<T>)ArrayUtils.iterator(array, j, 0);
    }

    @Override
    public void clear() {
        size = 0;
        Arrays.fill(table, 0);
    }

    @Override
    public Object[] toArray() {
        return Arrays.copyOf(table, size);
    }

    @Override
    public <T> T[] toArray(T[] target) {
        return ArrayUtils.arraycopy(target, table);
    }

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

}