import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.Map;

/**
 * A map with circular references so that all entries have a next entry and the
 * table is pre-populated with null-key and null-value entries to hold the
 * initial chain of entries. Having circular references enables quick iteration
 * of entries. This map implementation also supports multiple entries with the
 * same key value via the {@link #add(Object, Object)} method.
 * <p>
 * There are supporting methods to handle multiple keys like
 * {@link #entriesWithKey(Object)}, {@link #removeAll(Object)},
 * {@link #countOf(Object)}, {@link #removeAll(Object...)},
 * {@link #getAll(Object, Collection)}, and {@link #removeAll(Iterable)}.
 * </p>
 * <p>
 * There are also supporting methods to handle multiple values like
 * {@link #entriesWithValue(Object)}, {@link #removeAllValue(Iterable)},
 * {@link #removeAllValue(Object...)}, {@link #getAllKeys(Object, Collection)},
 * and {@link #countOfValue(Object)}.
 * </p>
 * <p>
 * This map implementation caches iterators for it's entries, values, keys,
 * entries with a specific key, and entries with a specific value. This is to
 * avoid needless allocation of iterators. The one drawback with this design
 * however is that you must avoid nested iterations over the same iterator -
 * this will not work.
 * </p>
 * <p>
 * This map implementation can also cache entries and reuse them between all
 * instances via the {@link #initPool(int)} method.
 * </p>
 * <p>
 * This map was built with speed and minimizing garbage in mind.
 * </p>
 * <p>
 * The fields of the Entry class are all public, do not modify these values.
 * </p>
 * 
 * @author Philip Diffenderfer
 * 
 * @param <K>
 *            The key type.
 * @param <V>
 *            The value type.
 */
@SuppressWarnings ({"rawtypes","unchecked"})
public class CyclicMap<K, V>
{

   public static final int SIZE_1 = 0;
   public static final int SIZE_2 = 1;
   public static final int SIZE_4 = 2;
   public static final int SIZE_8 = 3;
   public static final int SIZE_16 = 4;
   public static final int SIZE_32 = 5;
   public static final int SIZE_64 = 6;
   public static final int SIZE_128 = 7;
   public static final int SIZE_256 = 8;
   public static final int SIZE_512 = 9;
   public static final int SIZE_1024 = 10;
   public static final int SIZE_2048 = 11;
   public static final int SIZE_4096 = 12;
   
   private final int capacity;
   private final int mod;
   private final Entry<K, V>[] table;
   private int size;

   private final EntryIterable entries;
   private final ValueIterable values;
   private final KeyIterable keys;
   private final MultiKeyIterable multiKey;
   private final MultiValueIterable multiValue;
   
   /**
    * Initializes a CycleMap with a table size of 2<sup>tablePower</sup>.
    */
   public CyclicMap( int tablePower )
   {
      this.capacity = (1 << tablePower);
      this.mod = capacity - 1;
      this.table = new Entry[capacity];
      
      this.entries = new EntryIterable();
      this.values = new ValueIterable();
      this.keys = new KeyIterable();
      this.multiKey = new MultiKeyIterable();
      this.multiValue = new MultiValueIterable();
      
      for (int i = 0; i < capacity; i++) {
         table[i] = newEntry();
         table[i].hash = i;
      }
      
      this.clear( false );
   }
   
   /**
    * Adds an entry to the map with the given key and value, ignoring whether 
    * the key exists in the map already (for opposite behavior see 
    * {@link #put(Object, Object)}).
    */
   public void add(final K key, final V value)
   {
      final int hash = hash( key );
      final int tableIndex = hash & mod;
      final Entry<K, V> first = table[ tableIndex ];
      final Entry<K, V> next = newEntry();
      next.key = key;
      next.value = value;
      next.hash = hash;
      next.next = first.next;
      first.next = next;
      size++;
   }

   /**
    * Adds all entries that exist in the given map to this map.
    * @see #add(Object, Object)
    */
   public void addAll(final Map<K, V> map)
   {
      for (Map.Entry<K, V> entry : map.entrySet())
      {
         add( entry.getKey(), entry.getValue() );
      }
   }

   /**
    * Adds all entries that exist in the given map to this map.
    * @see #add(Object, Object)
    */
   public void addAll(final CyclicMap<K, V> map)
   {
      for (Entry<K, V> entry : map.entries)
      {
         add( entry.key, entry.value );
      }
   }
   
   /**
    * Adds the value to the map if an entry with the given key does not exist
    * already, if it does this method has no affect. Returns true if the
    * value was added, otherwise false.
    */
   public boolean addIfAbsent(final K key, final V value)
   {
      final Entry<K, V> before = beforeKey( key );
      final boolean absent = (before == null);
      
      if (absent)
      {
         add( key, value );
      }
      
      return absent;
   }
   
   /**
    * Adds the value to the map if an entry with the key doesn't exist, 
    * otherwise the old entry with a matching key will have it's value 
    * replaced and the previous value returned. If there are multiple
    * entries in the map with the given key the last added entry will
    * have it's value overridden.
    */
   public V put(final K key, final V value)
   {
      final Entry<K, V> before = beforeKey( key );
      V previousValue = null;
      
      if ( before == null )
      {
         add( key, value );
      }
      else
      {
         Entry<K, V> entry = before.next;
         previousValue = entry.value;
         entry.value = value;
      }
      
      return previousValue;
   }
   
   /**
    * Puts all keys and values from the given map into this map overwriting 
    * any entries with the same keys. If the given map has entries with 
    * duplicate keys the value of the oldest entry will be the one taken. If
    * a destination Collection is given all non-null previous values will
    * be added to it. If the given map has duplicate keys AND a destination is
    * given there is a chance multiple values will be inserted into the 
    * destination that had the same key. Returns the destination passed in.
    */
   public <D extends Collection<V>> D putAll(final CyclicMap<K, V> map, final D destination)
   {
      for (Entry<K, V> entry : map.entries)
      {
         V previous = put( entry.key, entry.value );
         
         if ( previous != null && destination != null )
         {
            destination.add( previous );
         }
      }
      
      return destination;
   }
   
   /**
    * Puts all keys and values from the given map into this map overwriting 
    * any entries with the same keys. If the given map has entries with 
    * duplicate keys the value of the oldest entry will be the one taken. If
    * a destination Collection is given all non-null previous values will
    * be added to it. If the given map has duplicate keys AND a destination is
    * given there is a chance multiple values will be inserted into the 
    * destination that had the same key. Returns the destination passed in.
    */
   public <D extends Collection<V>> D putAll(final Map<K, V> map, final D destination)
   {
      for (Map.Entry<K, V> entry : map.entrySet())
      {
         V previous = put( entry.getKey(), entry.getValue() );
         
         if ( previous != null && destination != null )
         {
            destination.add( previous );
         }
      }
      
      return destination;
   }
   
   /**
    * Returns the value of the last added entry with the given key.
    */
   public V get(final K key)
   {
      final Entry<K, V> before = beforeKey( key );
      
      return ( before == null ? null : before.next.value );
   }
   
   /**
    * Adds all values that exist with the given key to the given destination 
    * and returns the reference to that destination.
    */
   public <D extends Collection<V>> D getAll(final K key, final D destination)
   {
      return stripValues( entriesWithKey( key ), destination );
   }
   
   /**
    * Returns the key of the first entry in the map with the given value.
    */
   public K getKey(final V value)
   {
      final Entry<K, V> before = beforeValue( value );
      
      return ( before == null ? null : before.next.key );
   }
   
   /**
    * Adds all keys that exist with the given value to the given destination
    * and returns the reference to that destination.
    */
   public <D extends Collection<K>> D getAllKeys(final V value, final D destination)
   {
      return stripKeys( entriesWithValue( value ), destination );
   }
   
   /**
    * Removes the last added entry from the map with the given key and 
    * returns the associated value.
    */
   public V remove(final K key)
   {
      final Entry<K, V> before = beforeKey( key );
      
      if ( before == null )
      {
         return null;
      }
      
      final Entry<K, V> removing = before.next;
      final V removingValue = removing.value;
      before.next = removing.next;
      free( removing );
      size--;
      
      return removingValue;
   }
   
   /**
    * Removes all entries with the given key.
    */
   public void removeAll(final K key)
   {
      removeAllFromIterator( entriesWithKey( key ) );
   }
   
   /**
    * Removes all entries with the given keys.
    */
   public void removeAll(final K ... keyArray)
   {
      for (K key : keyArray) 
      {
         removeAllFromIterator( entriesWithKey( key ) );
      }
   }
   
   /**
    * Removes all entries with the given keys.
    */
   public void removeAll(final Iterable<K> keyIterable)
   {
      for (K key : keyIterable) 
      {
         removeAllFromIterator( entriesWithKey( key ) );
      }
   }
   
   /**
    * Returns the number of entries with the given key.
    */
   public int countOf(final K key)
   {
      return countIterator( entriesWithKey( key ) );
   }
   
   /**
    * Removes the first entry found in the table with the given value and 
    * returns it's key.
    */
   public K removeValue(final V value)
   {
      final Entry<K, V> before = beforeValue( value );
      
      if ( before == null )
      {
         return null;
      }
      
      final Entry<K, V> removing = before.next;
      final K removingKey = removing.key;
      before.next = removing.next;
      free( removing );
      size--;
      
      return removingKey;
   }

   /**
    * Removes all entries with the given value.
    */
   public void removeAllValue(final V value)
   {
      removeAllFromIterator( entriesWithValue( value ) );
   }
   
   /**
    * Removes all entries with the given values.
    */
   public void removeAllValue(final V ... valueyArray)
   {
      for (V value : valueyArray) 
      {
         removeAllFromIterator( entriesWithValue( value ) );
      }
   }
   
   /**
    * Removes all entries with the given values.
    */
   public void removeAllValue(final Iterable<V> valueIterable)
   {
      for (V value : valueIterable) 
      {
         removeAllFromIterator( entriesWithValue( value ) );
      }
   }
   
   /**
    * Returns the number of entries with the given key.
    */
   public int countOfValue(final V value)
   {
      return countIterator( entriesWithValue( value ) );
   }
   
   /**
    * Returns whether the given key exists in the map at least once.
    */
   public boolean has(final K key)
   {
      return beforeKey( key ) != null;
   }
   
   /**
    * Returns whether the given value exists in the map at least once.
    */
   public boolean hasValue(final V value)
   {
      return beforeValue( value ) != null;
   }
   
   /**
    * Returns the entry directly before the key or null if the key doesn't 
    * exist in the map.
    */
   public Entry<K, V> beforeKey(final K key)
   {
      final int hash = hash( key );
      final int tableIndex = hash & mod;
      final Entry<K, V> ending = table[ (tableIndex + 1) & mod ];
      Entry<K, V> before = table[ tableIndex ];
      Entry<K, V> current = before.next;
      
      while ( current != ending )
      {
         if ( current.hash == hash && (current.key == key || (key.equals( current.key ) ) ) )
         {
            return before;
         }

         before = current;
         current = current.next;
      }
      
      return null;
   }
   
   /**
    * Returns the entry directly before the value or null if the value doesn't
    * exist in the map.
    */
   public Entry<K, V> beforeValue(final V value)
   {
      final Entry<K, V> ending = table[0];
      Entry<K, V> before = ending;
      Entry<K, V> current = before.next;
      
      while (current != ending)
      {
         if ( current.value == value || value.equals( current.value ) )
         {
            return before;
         }
         
         before = current;
         current = current.next;
      }
      
      return null;
   }
   
   /**
    * Hashes the given key. This can he overridden by subclasses to provide
    * better hashes based on Key type.
    */
   public int hash(final K key)
   {
      return key.hashCode();
   }
   
   /**
    * Removes the first key from the map. If no entries exists then null is returned.
    */
   public K removeFirstKey()
   {
      final Entry<K, V> removed = removeFirstEntry();
      K first = null;
      
      if ( removed != null )
      {
         first = removed.key;
         
         free( removed );
      }
      
      return first;
   }
   
   /**
    * Removes the first value from the map. If no entries exists then null is returned.
    */
   public V removeFirstValue()
   {
      final Entry<K, V> removed = removeFirstEntry();
      V first = null;
      
      if ( removed != null )
      {
         first = removed.value;
         
         free( removed );
      }
      
      return first;
   }
   
   /**
    * Removes the first entry from the map. This entry must be freed if you
    * have pooling initialized an expect it to perform properly. If no entries
    * exist then null is returned.
    * @see #free(Entry)
    */
   public Entry<K, V> removeFirstEntry()
   {
      final Entry<K, V> ending = table[0];
      Entry<K, V> before = ending;
      Entry<K, V> current = before.next;
      
      while ( current != ending )
      {
         Entry<K, V> next = current.next;
         
         if ( current.key != null )
         {
            before.next = next;
            size--;
            
            return current;
         }

         before = current;
         current = next;
      }
      
      return null;
   }
   
   /**
    * An Iterable of all entries in the map.
    */
   public Iterable<Entry<K, V>> entries()
   {
      return entries;
   }

   /**
    * An Iterable of all entries in the map with the given key. 
    */
   public Iterable<Entry<K, V>> entriesWithKey(final K key)
   {
      multiKey.reset( key );
      
      return multiKey;
   }
   
   /**
    * An Iterable of all entries in the map with the given value.
    */
   public Iterable<Entry<K, V>> entriesWithValue(final V value)
   {
      multiValue.reset( value );
      
      return multiValue;
   }
   
   /**
    * An Iterable of all values in the map.
    */
   public Iterable<V> values()
   {
      return values;
   }
   
   /**
    * An Iterable of all keys in the map. Keys may be repeated if there are
    * multiple entries in the map with the same key.
    */
   public Iterable<K> keys()
   {
      return keys;
   }

   /**
    * Clears the map of all entries.
    * 
    * @param freeEntries
    *       Whether the entries should be returned to the pool, or ignored.
    */
   public void clear( final boolean freeEntries )
   {
      if ( freeEntries )
      {
         Entry<K, V> entry = table[0].next;
         
         while (entry != table[0])
         {
            Entry<K, V> next = entry.next;
            
            if ( entry.key != null )
            {
               free( entry );
            }
            
            entry = next;
         }         
      }

      for ( int i = 0; i < capacity; i++ )
      {
         table[i].next = table[(i + 1) & mod];
      }
      
      size = 0;
   }
   
   /**
    * The number of entries in the map.
    */
   public int size()
   {
      return size;
   }
   
   /**
    * Whether the map is empty or not.
    */
   public boolean isEmpty()
   {
      return (size == 0);
   }
   
   /**
    * Frees a removed Entry.
    * 
    * @param entry
    *       The removed Entry to free.
    */
   public void free( final Entry<K, V> entry )
   {
      entry.value = null;
      entry.next = null;
      entry.key = null;
      freeEntry( entry );
   }
   
   /*
    * UTILITY METHODS
    */
   
   /**
    * Removes all elements in the given Iterable.
    */
   public static void removeAllFromIterator( final Iterable<?> iterable )
   {
      final Iterator<?> iterator = iterable.iterator();
      
      while (iterator.hasNext())
      {
         iterator.next();
         iterator.remove();
      }
   }
   
   /**
    * Removes all elements in the given Iterable and adds them to the destination.
    */
   public static <E, C extends Collection<E>> C removeAllFromIterator( final Iterable<E> iterable, final C destination )
   {
      final Iterator<E> iterator = iterable.iterator();
      
      while (iterator.hasNext())
      {
         destination.add( iterator.next() );
         
         iterator.remove();
      }
      
      return destination;
   }
   
   /**
    * Returns the number of elements in the Iterable.
    */
   public static int countIterator( final Iterable<?> iterable ) 
   {
      final Iterator<?> iterator = iterable.iterator();
      int count = 0;

      while (iterator.hasNext())
      {
         iterator.next();
         count++;
      }
      
      return count;
   }
   
   /**
    * Adds all values from the entries in the Iterable to the given 
    * destination collection.
    */
   public static <K, V, D extends Collection<V>> D stripValues( final Iterable<Entry<K, V>> entries, final D destination )
   {
      for ( Entry<K, V> entry : entries )
      {
         destination.add( entry.value );
      }
      
      return destination;
   }
   
   /**
    * Adds all keys from the entries in the Iterable to the given 
    * destination collection.
    */
   public static <K, V, D extends Collection<K>> D stripKeys( final Iterable<Entry<K, V>> entries, final D destination )
   {
      for ( Entry<K, V> entry : entries )
      {
         destination.add( entry.key );
      }
      
      return destination;
   }
   
   /*
    * ENTRY POOLING (optional)
    */
   
   private static Entry[] pool = {};
   
   private static int poolSize;
   
   private static <K, V> Entry<K, V> newEntry()
   {
      return (poolSize == 0 ? new Entry<K, V>() : pool[--poolSize] );
   }
   
   private static void freeEntry( final Entry entry )
   {
      if (poolSize < pool.length)
      {
         pool[poolSize++] = entry;
      }
   }
   
   /**
    * Initializes the pool of entries to some maximum size. By default the
    * pool has a size of zero so no entries are cached.
    */
   public static void initPool(final int size)
   {
      pool = Arrays.copyOf( pool, size );
   }
   
   /*
    * ENTRY
    */
   
   public static class Entry<K, V> 
   {
      public int hash;
      public K key;
      public V value;
      public Entry<K, V> next;
   }
   
   /*
    * ITERABLES
    */
   
   private abstract class AbstractIterable<E> implements Iterable<E>, Iterator<E>
   {
      protected Entry<K, V> prev0;
      protected Entry<K, V> curr0;
      protected Entry<K, V> prev1;
      protected Entry<K, V> curr1;
      protected Entry<K, V> end;
      
      @Override
      public final Iterator<E> iterator() 
      {
         end = end();
         curr1 = (prev1 = findPrev( start() )).next;
         
         return this;
      }
      
      @Override
      public final boolean hasNext()
      {
         return (curr1 != end);
      }
      
      @Override
      public final void remove()
      {
         prev0.next = curr0.next;
         
         free( curr0 );
      }
      
      public final Entry<K, V> nextEntry()
      {
         prev0 = prev1;
         curr0 = curr1;
         curr1 = (prev1 = findPrev( curr1 )).next;
         
         return curr0;
      }
      
      protected abstract Entry<K, V> findPrev( Entry<K, V> prev );
      protected abstract Entry<K, V> start();
      protected abstract Entry<K, V> end();
   }
   
   private class MultiKeyIterable extends AbstractIterable<Entry<K, V>>
   {
      private K key;
      private int hash;
      
      public void reset(final K key)
      {
         this.key = key;
         this.hash = hash( key );
      }
      
      @Override
      public Entry<K, V> next()
      {
         return nextEntry();
      }

      @Override
      protected Entry<K, V> findPrev(Entry<K, V> start)
      {
         Entry<K, V> next;
         
         while (((next = start.next).hash != hash || !key.equals(next.key)) && next != end)
         {
            start = next;
         }
         
         return start;
      }

      @Override
      protected Entry<K, V> start()
      {
         return table[ (hash & mod) ];
      }

      @Override
      protected Entry<K, V> end()
      {
         return table[ ((hash & mod) + 1) & mod ];
      }
   }
   
   private class MultiValueIterable extends AbstractIterable<Entry<K, V>>
   {
      private V value;
      
      public void reset(final V value)
      {
         this.value = value;
      }
      
      @Override
      public Entry<K, V> next()
      {
         return nextEntry();
      }

      @Override
      protected Entry<K, V> findPrev(Entry<K, V> prev)
      {
         Entry<K, V> next;
         
         while ( ((next = prev.next).value == null || !value.equals( next.value )) && next != end )
         {
            prev = next;
         }
         
         return prev;
      }

      @Override
      protected Entry<K, V> start()
      {
         return table[0];
      }

      @Override
      protected Entry<K, V> end()
      {
         return table[0];
      }
   }
   
   private abstract class CyclicIterable<E> extends AbstractIterable<E>
   {
      @Override
      protected Entry<K, V> findPrev(Entry<K, V> prev)
      {
         Entry<K, V> next;
         
         while ((next = prev.next).key == null && next != end )
         {
            prev = next;
         }
         
         return prev;
      }

      @Override
      protected Entry<K, V> start()
      {
         return table[0];
      }

      @Override
      protected Entry<K, V> end()
      {
         return table[0];
      }
   }
   
   private class EntryIterable extends CyclicIterable<Entry<K, V>> 
   {
      @Override
      public Entry<K, V> next() 
      {
         return nextEntry();
      }
   }
   
   private class ValueIterable extends CyclicIterable<V> 
   {
      @Override
      public V next() 
      {
         return nextEntry().value;
      }
   }
   
   private class KeyIterable extends CyclicIterable<K> 
   {
      @Override
      public K next() 
      {
         return nextEntry().key;
      }
   }
   
}