////////////////////////////////////////////////////////////////////////////////
   // MillScript-Util: an Open Spice interpreter and batch website creation tool
   // Copyright (C) 2005 Kevin Rogers
   //
   // This file is part of MillScript-Util.
   //
   // MillScript-Util is free software; you can redistribute it and/or modify it under
   // the terms of the GNU General Public License as published by the Free
   // Software Foundation; either version 2 of the License, or (at your option)
  // any later version.
  //
  // MillScript-Util is distributed in the hope that it will be useful, but WITHOUT
  // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  // FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  // more details.
  //
  // You should have received a copy of the GNU General Public License along with
  // MillScript-Util; if not, write to the Free Software Foundation, Inc., 59 Temple
  // Place, Suite 330, Boston, MA  02111-1307  USA
  ////////////////////////////////////////////////////////////////////////////////
  package org.millscript.commons.util.map;
  
  import java.io.IOException;
  import java.io.ObjectInputStream;
  import java.io.ObjectOutputStream;
  import java.io.Serializable;
  
  import org.millscript.commons.alert.alerts.IllegalArgumentAlert;
  import org.millscript.commons.util.IList;
  import org.millscript.commons.util.IMap;
  import org.millscript.commons.util.MapIterator;
  import org.millscript.commons.util.Maplet;
  import org.millscript.commons.util.alerts.NoSuchKeyInMapAlert;
  import org.millscript.commons.util.iterator.AbstractMapIterator;
  
  /**
   * This class provides a mutable <code>Map</code> implementation which is
   * backed by an Object array containing alternate name-value objects.
   */
  public class EArrayMap< K, V > extends AbstractEMap< K, V > implements Cloneable, Serializable {
  
      // TODO - Complete the concurrency work, i.e. get the synchroised bits in
  
      /**
       * This is the ID from the release 0.1.0 for future compatibility.
       */
      private static final long serialVersionUID = -4589591352463632844L;
  
      /**
       * This class implements a map iterator which iterates over an array
       * containing alternating key-value objects, sharing the backing store with
       * it's enclosing mutable map.
       * <p>
       * As expected, the iterator uses a copy-on-write contract with its
       * enclosing class during the iteration. Simple updates will not cause a
       * copy, but structural(i.e. inserts/removes) will cause a copy for the
       * duration of the iteration.
       * </p>
       */
      public static class ArrayMapMapIterator< K, V > extends AbstractMapIterator< K, V > {
  
          /**
           * The next free element in the backing store at the time the iterator
           * was created. We have to copy the value into this iterator to avoid
           * problems with updates to the map during an interation.
           */
          private final int nextFree;
  
          /**
           * The current position within the backing store array.
           */
          private int pos = -2;
  
          /**
           * The backing store containing a variable array of alternate name-value
           * objects. We copy the reference into this iterator to avoid problems
           * with updated to the map during an iteration.
           */
          private final Object[] store;
  
          /**
           * Contructs a new array map iterator for the specified mutable array
           * map.
           *
           * @param map   the mutable array map to iterate over
           */
          public ArrayMapMapIterator( final EArrayMap< K, V > map ) {
              this.nextFree = map.nextFree;
              this.store = map.store;
          }
  
          /**
           * @see org.millscript.commons.util.iterator.AbstractMapIterator#advance()
           */
          @Override
          protected void advance() {
              this.pos += 2;
          }
  
         /**
          * @see org.millscript.commons.util.iterator.AbstractMapIterator#getKey()
          */
         @Override
         @SuppressWarnings("unchecked")
         protected K getKey() {
             return (K) store[ this.pos ];
         }
 
         /**
          * @see org.millscript.commons.util.iterator.AbstractMapIterator#getValue()
          */
         @Override
         @SuppressWarnings("unchecked")
         protected V getValue() {
             return (V) this.store[ this.pos + 1 ];
         }
 
         /**
          * @see org.millscript.commons.util.MapIterator#hasNext()
          */
         public boolean hasNext() {
             return this.pos + 2 < this.nextFree;
         }
 
         /**
          * @see org.millscript.commons.util.iterator.AbstractMapIterator#outOfBounds()
          */
         @Override
         protected boolean outOfBounds() {
             return this.pos < 0 || this.pos >= this.nextFree;
         }
 
     }
 
     /**
      * The default amount of free space available in the map is enough for 16
      * name-value pairs. This value must be a multiple of two otherwise array
      * index out of bounds errors may occur.
      */
     static final byte DEFAULT_FREE_SPACE = 32;
 
     // FIXME - The should ideally be private
     /**
      * The position of the next free element in the backing store and also the
      * twice the number of name-value pairs in this map.
      */
     transient int nextFree = 0;
 
     // FIXME - The store should ideally be private
     /**
      * The backing store containing a variable array of alternate name-value
      * objects.
      */
     transient Object[] store;
 
     /**
      * Constructs a new, emtpy mutable array map.
      */
     public EArrayMap() {
         this.store = new Object[ DEFAULT_FREE_SPACE ];
     }
 
     /**
      * Constructs a new mutable array map with a copy of the specified backing
      * array containing alternate name-value objects.
      *
      * @param objects   the backing array of alternate name-value objects to
      * copy
      */
     public EArrayMap( final Object[] objects ) {
         if ( objects.length % 2 == 1 ) {
             throw new IllegalArgumentAlert(
                 "Backing store must be a name, value sequence"
             ).culprit(
                 "object array",
                 objects
             ).culprit(
                 "object array length",
                 objects.length
             ).mishap();
         }
         this.nextFree = objects.length;
         this.store = new Object[ objects.length + DEFAULT_FREE_SPACE ];
         System.arraycopy( objects, 0, this.store, 0, objects.length );
     }
 
     /**
      * @see java.lang.Object#clone()
      */
     @Override
     @SuppressWarnings( "unchecked" )
     public Object clone() throws CloneNotSupportedException {
         final EArrayMap< K, V > map = (EArrayMap< K, V >) super.clone();
         map.store = (V[]) new Object[ this.store.length ];
         System.arraycopy( this.store, 0, map.store, 0, this.store.length );
         return map;
     }
 
     /**
      * @see org.millscript.commons.util.IMap#contains(java.lang.Object, java.lang.Object)
      */
     public boolean contains( final K key, final V value ) {
         int i = 0;
         while ( i < this.nextFree - 1 ) {
             final Object sKey = this.store[ i++ ];
             final Object sValue = this.store[ i++ ];
             if ( sKey == null ? key == null : sKey.equals( key ) ) {
                 // The keys are equal, so return true if the values are both
                 // null or equal and false otherwise
                 return sValue == null ? value == null
                                       : sValue.equals( value );
             }
         }
         return false;
     }
 
     /**
      * @see org.millscript.commons.util.IMap#containsKey(java.lang.Object)
      */
     public boolean containsKey( final K key ) {
         for ( int i = 0; i < this.nextFree; i += 2 ) {
             if ( key == null ? this.store[ i ] == null : key.equals( this.store[ i ] ) ) {
                 return true;
             }
         }
         return false;
     }
 
     /**
      * @see org.millscript.commons.util.IMap#containsValue(java.lang.Object)
      */
     public boolean containsValue( final V value ) {
         for ( int i = 1; i < this.nextFree; i += 2 ) {
             final Object sValue = this.store[ i ];
             if ( sValue == null ? value == null : sValue.equals( value ) ) {
                 return true;
             }
         }
         return false;
     }
 
     /**
      * @see org.millscript.commons.util.IMap#get(java.lang.Object)
      */
     @SuppressWarnings( "unchecked" )
     public V get( final K key ) {
         for ( int i = 0; i < this.nextFree - 1; i += 2 ) {
             if ( key == null ? this.store[ i ] == null : key.equals( this.store[ i ] ) ) {
                 return (V) this.store[ ++i ];
             }
         }
         return this.getDefault().get( this, key );
     }
 
     /**
      * @see org.millscript.commons.util.EMap#insert(java.lang.Object, java.lang.Object)
      */
     public void insert( final K key, final V value ) {
         // Look to see if the key is already present
         for ( int i = 0; i < this.nextFree - 1; i += 2 ) {
             if ( key == null ? this.store[ i ] == null : key.equals( this.store[ i ] ) ) {
                 this.store[ ++i ] = value;
                 return;
             }
         }
         // Nope, the key isn't already here, we have to add it
         // Is there enough space in the backing store?
         if ( this.nextFree == this.store.length ) {
             // No space left, we need to resize
             final Object[] newStore = new Object[ this.store.length + DEFAULT_FREE_SPACE ];
             System.arraycopy( this.store, 0, newStore, 0, this.store.length );
             this.store = newStore;
         }
         // Now append the new mapping
         this.store[ this.nextFree++ ] = key;
         this.store[ this.nextFree++ ] = value;
     }
 
     /**
      * @see org.millscript.commons.util.EMap#insertAll(org.millscript.commons.util.IMap)
      */
     @Override
     public void insertAll( final IMap< ? extends K, ? extends V > map ) {
         // For speed, check if there is enough free space for all the mappings.
         // NOTE - we perform a cursory check on the number of mappings in the
         // supplied map and no more. We can't be sure how many keys in the
         // supplied map are already present in this one and hence if we are
         // going to start wasting space.
         if ( map.size() > this.store.length ) {
             // Not enough space left, we need to resize. Make the new store a
             // little bit bigger than the supplied map.
             final Object[] newStore = new Object[ map.size() + DEFAULT_FREE_SPACE ];
             System.arraycopy( this.store, 0, newStore, 0, this.nextFree );
             this.store = newStore;
         }
         // Now insert all the mappings.
         super.insertAll( map );
     }
 
     /**
      * @see org.millscript.commons.util.IMap#iterator(boolean)
      */
     public MapIterator< K, V > iterator( final boolean share ) {
         if ( share ) {
             return new ArrayMapMapIterator< K, V >( this );
         } else {
             // FIXME - This bit probably needs to be synchronised to avoid
             // structural updates during the array creation and copy, not the
             // iterator construction though
             final Object[] objects = new Object[ this.nextFree ];
             System.arraycopy( this.store, 0, objects, 0, objects.length );
             return new IArrayMap.ArrayMapMapIterator< K, V >( objects, true );
         }
     }
 
     /**
      * Reads this object from the specified {@link ObjectInputStream}.
      *
      * @param stream    the {@link ObjectInputStream} to read the objects data
      * from
      * @serialData      Reads the default object, followed by the integer
      * number of mappings and then an alternating sequence of key-value pairs
      * @throws ClassNotFoundException   if a required class cannot be found
      * @throws IOException      if something goes wrong during the
      * deserialization process
      */
     private void readObject( final ObjectInputStream stream ) throws ClassNotFoundException, IOException {
         // Write the default stuff
         stream.defaultReadObject();
         // Retrieve the number of mappings in the array.
         final int size = stream.readInt();
         // Allocate the required amount of storage.
         this.store = new Object[ ( size * 2 ) + DEFAULT_FREE_SPACE ];
         // Retrieve the mappings
         for ( this.nextFree = 0; this.nextFree < size * 2; this.nextFree++ ) {
             this.store[ this.nextFree ] = stream.readObject();
         }
     }
 
     /**
      * @see org.millscript.commons.util.EMap#remove(java.lang.Object, java.lang.Object)
      */
     public void remove( final K key, final V value ) {
         // Find the key-value pair
         for ( int i = 0; i < this.nextFree - 1; i += 2 ) {
             if ( key == null ? this.store[ i ] == null : key.equals( this.store[ i ] ) ) {
                 // The keys are equal, are the values?
                 if ( value == null ? this.store[ i + 1 ] == null : value.equals( this.store[ i + 1 ] ) ) {
                     // The keys are equal and so are the values. We should
                     // remove this pair
                     // Whatever we do, we have to reduce the used portion of
                     // the backing store by two.
                     this.nextFree -= 2;
                     // Now, if the new used size is the same as the counter we
                     // don't have to do anything else, otherwise we have to
                     // shift the end of the backing store by two places.
                     if ( i != this.nextFree ) {
                         System.arraycopy( this.store, i + 2, this.store, i, this.nextFree - i );
                     }
                 }
             }
         }
     }
 
     /**
      * @see org.millscript.commons.util.EMap#removeAll()
      */
     public void removeAll() {
         this.nextFree = 0;
         this.store = new Object[ DEFAULT_FREE_SPACE ];
     }
 
     /**
      * @see org.millscript.commons.util.EMap#removeKey(java.lang.Object)
      */
     public void removeKey( final K key ) {
         // Find the key
         for ( int i = 0; i < this.nextFree - 1; i += 2 ) {
             if ( key == null ? this.store[ i ] == null : key.equals( this.store[ i ] ) ) {
                 // The keys are equal, we should remove this pair
                 // Whatever we do, we have to reduce the used portion of
                 // the backing store by two.
                 this.nextFree -= 2;
                 // Now, if the new used size is the same as the counter we
                 // don't have to do anything else, otherwise we have to
                 // shift the end of the backing store by two places.
                 if ( i != this.nextFree ) {
                     System.arraycopy( this.store, i + 2, this.store, i, this.nextFree - i );
                     // Nothing more to do now as there are duplicate keys are
                     // not allowed
                     return;
                 }
             }
         }
     }
 
     /**
      * @see org.millscript.commons.util.EMap#removeValue(java.lang.Object)
      */
     public void removeValue( final V value ) {
         // Find the value
         int i = 1;
         while ( i < this.nextFree ) {
             if ( value == null ? this.store[ i ] == null : value.equals( this.store[ i ] ) ) {
                 // The keys are equal, we should remove this pair
                 // Now, if the new used size is the same as the key position we
                 // don't have to do anything else, otherwise we have to
                 // shift the end of the backing store by two places.
                 if ( i + 1 != this.nextFree ) {
                     System.arraycopy( this.store, i + 1, this.store, i - 1, this.nextFree - i - 1 );
                 }
                 // Reduce the used portion of the backing store by two.
                 this.nextFree -= 2;
             } else {
                 // We only increment the position if we didn't match values,
                 // otherwise we will have shifted the array values left two
                 // places which achieves the same result as incrementing the
                 // position
                 i += 2;
             }
         }
     }
 
     /**
      * @see org.millscript.commons.util.map.AbstractIMap#sharedKeyList()
      */
     @Override
     protected IList< K > sharedKeyList() {
         // NOTE - We use the same type of list as for the shared value list but
         // ofset it by one in the array, so we get a list of the keys!
         return new IArrayMap.ImmutableXList< K >( this.store, 1, this.size() );
     }
 
     /**
      * @see org.millscript.commons.util.map.AbstractIMap#sharedMapletList()
      */
     @Override
     protected IList< Maplet< K, V > > sharedMapletList() {
         return new IArrayMap.ImmutableSharedMapletList< K, V >( this.store, 1, this.size() );
     }
 
     /**
      * @see org.millscript.commons.util.map.AbstractIMap#sharedValueList()
      */
     @Override
     protected IList< V > sharedValueList() {
         // NOTE - We use the same type of list as for the shared key list but
         // ofset it by one in the array, so we get a list of the values!
         return new IArrayMap.ImmutableXList< V >( this.store, 2, this.size() );
     }
 
     /**
      * @see org.millscript.commons.util.IMap#size()
      */
     public int size() {
         return this.nextFree / 2;
     }
 
     /**
      * @see org.millscript.commons.util.UMap#update(java.lang.Object, java.lang.Object)
      */
     public void update( final K key, final V value ) {
         // Look to see if the key is already present
         for ( int i = 0; i < this.nextFree - 1; i += 2 ) {
             if ( key == null ? this.store[ i ] == null : key.equals( this.store[ i ] ) ) {
                 this.store[ ++i ] = value;
                 return;
             }
         }
         // Error
         throw new NoSuchKeyInMapAlert(
             "Only pre-existing keys can have their values updated"
         ).culpritKey( key ).decorate( this ).mishap();
     }
 
     /**
      * Writes this object to the specified {@link ObjectOutputStream}.
      *
      * @param stream    the {@link ObjectOutputStream} to write this object to
      * @serialData      Writes the default object, followed by the integer
      * number of mappings and then an alternating sequence of key-value pairs
      * @throws IOException      if something goes wrong during the
      * serialization process
      */
     private void writeObject( final ObjectOutputStream stream ) throws IOException {
         // Write the default stuff
         stream.defaultWriteObject();
         // Save the number of mappings in the array.
         stream.writeInt( this.size() );
         // Save the mappings in the array
         for ( int i = 0; i < this.nextFree; i++ ) {
             stream.writeObject( this.store[ i ] );
         }
     }
 
 }