Map Example

import java.util.Map;

import java.util.Map.Entry;

import java.util.HashMap; /** It doesn't implement java.util.Map because that's not the important part for what

    this examples intends to show. To keep it simple, it's quite an inefficient map

    - no hashing.

*/

public class MapExample

{

    /**    This is set and populated only by MapExample( Map original ) - otherwise it's null.

        It is not modified once MapExample( Map original ) returns - then it's accessed read-only.

        It's used only while mutableArray is null. Once mutableArray is set it's used instead of initialArray.

        It's protected by Direct Component Guarantee. To be 100% JMM-compliant, the actual Map.Entry

        items must be final objects - because Direct Component Guarantee doesn't apply recursively deep.

        If used then it contains all initial entries of the map, and only those entries. I.e. map's size is same

        as initialArray.length.

    */

    private final Map.Entry initialArray[];

    /** It contains all entries of the map

        - once the instance was modified after it was constructed by MapExample( Map original ).

        - if the instance was initialized by constructor other than MapExample( Map original ).

        In both cases all threads must synchronize when using the instance - both read and write.

        If non-null it contains all current entries of the map starting from index 0 up to mutableSize-1. The rest of the array is ignored

        - that's where new entries are added, unless the array needs to be resized.

    */

    private Map.Entry mutableArray[];

    /** If mutableArray is non-null then mutableSize is the number of valid entries that are

        currently stored in mutableArray. mutableSize is always equal or lower than mutableArray.lenght.

    */

    private int mutableSize;

    public MapExample() { this(16); }

    public MapExample( int initialCapacity ) {

        initialArray= null;

        mutableArray= new Map.Entry[initialCapacity];

        mutableSize= 0;

    }

    /** To be 100% JMM-compliant, both the key and *value* must be final fields when used for initial

        unsynchronized entries in initialArray[]. Otherwise other threads could see key/value as null  

        Since there's no public Java 6 for Mac OS X, I can't use java.util.AbstractMap.SimpleImmutableEntry

    */

    private static final class Entry implements Map.Entry {

        private final KT key;

        private final VT value;

        public KT getKey() { return key; }

        public VT getValue() { return value; }

        public VT setValue(VT newValue) { throw new Error( "Never to be used." ); }

        public boolean equals( Object o ) { throw new Error("TODO"); }

        public int hashCode() { throw new Error("TODO"); }

        Entry( KT givenKey, VT givenValue ) {

            key= givenKey;

            value= givenValue;

        }

    }

    public MapExample( Map original ) {

        initialArray= new Map.Entry[ original.size() ];

        int index= 0;

        for( Map.Entry entry:original.entrySet() ) {

            initialArray[ index ]= new Entry( (K)entry.getKey(), (V)entry.getValue() );

            index++;

        }

    }

private boolean usingMutableArray() { return mutableArray!=null; }

private Map.Entry[] currentActiveArray() { return usingMutableArray() ? mutableArray : initialArray; }

public int size() { return usingMutableArray() ? mutableSize : initialArray.length; }

private static boolean keysEqual( Object first, Object second ) {

        return first!=null && first.equals( second ) || first==second;

}

public V get( K key ) {

        // Efficiency is not important in this example

        for( int i=0; i< size(); i++ ) {

            Map.Entry entry= currentActiveArray()[ i ];

            if( keysEqual( key, entry.getKey() ) ) {

                return (V)entry.getValue();

            }

        }

        return null;

    }

    /** This doesn't return the previous value as Map.put(K,V) does.

    */

    public void put( K givenKey, V givenValue ) {

        // Efficiency is a foreign word here  

        if( !usingMutableArray() || size()==mutableArray.length ) {

            /** Following should only resize if we need a new slot - not when replacing an existing value.

                And if !usingMutableArray() and changing the instance for the first time

                and if there's no need for a new slot, then it could just assign mutableArray= initialArray

                rather than creating a new array.

                It could also round the new size of mutableArray

                to the nearest higher power of 2. But it doesn't matter in this example.

            */

            Map.Entry newArray[]= new Map.Entry[ size()+1 ];

            /** Since we use immutable instances of class Entry in both initialArray[] and mutableArray[],

                we don't need to clone the actual entries here. It would be nice to type initialArray and mutableArray

                as arrays of MapExample.Entry rather than Map.Entry, but it doesn't matter.

            */

            System.arraycopy( currentActiveArray(), 0, newArray, 0, size() );

            if( !usingMutableArray() ) {

                // Here we initialize mutableSize to non-zero value for the first time

                assert mutableSize==0;

                mutableSize= size(); // We didn't put (newKey, newValue) yet

            }

            mutableArray= newArray;

        }

        assert usingMutableArray();

        for( int i=0; i< size(); i++ ) {

            Map.Entry entry= currentActiveArray()[ i ];

            if( keysEqual( givenKey, entry.getKey() ) ) {

                entry.setValue( givenValue );

                return; // replaced an existing value, done

            }

        }

        mutableArray[ mutableSize ]= new Entry( givenKey, givenValue );

        mutableSize++;

        assert mutableSize<=mutableArray.length;

    }

public static void main( String... argv ) {

        HashMap map= new HashMap();

        map.put( "1", "One" );

        map.put( "2", "Two" );

        MapExample initialized= new MapExample( map );

        assert initialized.size()==2;

        assert initialized.get( "1" ).equals( "One" );

        assert initialized.get( "2" ).equals( "Two" );

        /** If the code guaranteed that initialized doesn't ever get modified after it

            was constructed, it could be used in other threads without any synchronization action.

            Otherwise it must be synchronized if used by several threads.

        */

        initialized.put( "3", "Three" );

        assert initialized.size()==3;

        assert initialized.get( "3" ).equals( "Three" );

        MapExample modified= new MapExample( 2 ); // 2 is so that we can test resize easily

        modified.put( "1", "One" );

        modified.put( "2", "Two" );

        modified.put( "3", "Three" );

        modified.put( "4", "Four" );

        modified.put( "5", "Five" );

        assert modified.size()==5;

        assert modified.get( "1" ).equals( "One" );

        assert modified.get( "2" ).equals( "Two" );

        assert modified.get( "3" ).equals( "Three" );

        assert modified.get( "4" ).equals( "Four" );

        assert modified.get( "5" ).equals( "Five" );

}

}