/*******************************************************************************
 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
 * in Industry THTH ry.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     VTT Technical Research Centre of Finland - initial API and implementation
 *******************************************************************************/
package org.simantics.db.impl.query;

import java.util.Arrays;
import java.util.Iterator;


/**
 * An implementation of the <tt>Set</tt> interface that uses an
 * open-addressed hash table to store its contents.
 *
 * Created: Sat Nov  3 10:38:17 2001
 *
 * @author Eric D. Friedman
 * @version $Id: QueryIdentityHashSet.java,v 1.1 2008/03/14 11:32:01 tuoksk Exp $
 */

final public class QueryIdentityHashSet extends QueryIdentityHash implements Iterable<CacheEntry> {
    
    /**
     * Creates a new <code>THashSet</code> instance with a prime
     * capacity equal to or greater than <tt>initialCapacity</tt> and
     * with the default load factor.
     *
     * @param initialCapacity an <code>int</code> value
     */
    public QueryIdentityHashSet(int initialCapacity) {
        super(initialCapacity);
    }

    /**
     * Inserts a value into the set.
     *
     * @param obj an <code>Object</code> value
     * @return true if the set was modified by the add operation
     */
    final public boolean add(final CacheEntry obj) {
    	
        final int index = insertionIndex(obj);

        if (index < 0) {
            return false;       // already present in set, nothing to add
        }

        final CacheEntry old = _set[index];
        _set[index] = obj;

        postInsertHook(old == null);
        return true;            // yes, we added something
        
    }

    /**
     * Expands the set to accomodate new values.
     *
     * @param newCapacity an <code>int</code> value
     */
    final protected void rehash(int newCapacity) {
        
        final int oldCapacity = _set.length;
        final CacheEntry oldSet[] = _set;

        _set = new CacheEntry[newCapacity];

        for (int i = oldCapacity; i-- > 0;) {
            if(oldSet[i] != null && oldSet[i] != REMOVED) {
                final CacheEntry o = oldSet[i];
                //if(o.isDiscarded()) continue;
                final int index = insertionIndex(o);
                if(index < 0) {
                    new Exception().printStackTrace();
                    System.out.println("rehash " + i + " " + o);
                    for (int j = oldCapacity; j-- > 0;) {
                        System.out.println("rehash " + j+ " " + oldSet[j] + " " + System.identityHashCode(oldSet[j]));
                    }
                }
                else _set[index] = o;
            }
        }
        
    }

    /**
     * Removes <tt>obj</tt> from the set.
     *
     * @param obj an <code>Object</code> value
     * @return true if the set was modified by the remove operation.
     */
    final public boolean remove(Object obj) {
        int index = index(obj);
        if (index >= 0) {
            removeAt(index);
            return true;
        }
        return false;
    }
    
    private int knownBound = 10;
    
    final public void purge() {
    	
    	if(size() > (knownBound<<1)) {
    		
    		knownBound=10;
	        for(int i=0;i<_set.length;i++) {
	            CacheEntry entry = _set[i];
	            if(entry != null && REMOVED != entry) {
	                if(entry.isDiscarded()) {
	                	removeAt(i); 
	                } else {
	                	knownBound++;
	                }
	            }
	        }
	        
    	}
    	
    }

    final public CacheEntry removeDiscarded() {
        
        tempDisableAutoCompaction();
        try {
        	
	        for(int i=0;i<_set.length;i++) {
	            CacheEntry entry = _set[i];
	            if(entry != null && REMOVED != entry) {
	            	removeAt(i);
	                if(!entry.isDiscarded()) return entry; 
	            }
	        }
	        
	        return null;
	        
        } finally {
        	reenableAutoCompaction(false);
        }
        
    }
    
    /**
     * Creates an iterator over the values of the set.  The iterator
     * supports element deletion.
     *
     * @return an <code>Iterator</code> value
     */
    final public Iterator<CacheEntry> iterator() {
        
        class Iter implements Iterator<CacheEntry> {

            private int index = capacity();
            
            public Iter() {
                advance();
            }

            private void advance() {
                while (index-- > 0 && (_set[index] == null || _set[index] == QueryIdentityHash.REMOVED)) ;
            }
            
            @Override
            public boolean hasNext() {
                return index >= 0;
            }

            @Override
            public CacheEntry next() {
                if(index >= 0) {
                    CacheEntry result = (CacheEntry)_set[index];
                    advance();
                    return result;
                }
                return null;
            }

            @Override
            public void remove() {
                throw new Error("Not supported.");
            }
            
        };
        
        return new Iter();
        
    }

    public void clear() {
        super.clear();

        Arrays.fill(_set, 0, _set.length, null);
    }
    
} // THashSet