/*
 *                    BioJava development code
 *
 * This code may be freely distributed and modified under the
 * terms of the GNU Lesser General Public Licence.  This should
 * be distributed with the code.  If you do not have a copy,
 * see:
 *
 *      http://www.gnu.org/copyleft/lesser.html
 *
 * Copyright for this code is held jointly by the individual
 * authors.  These should be listed in @author doc comments.
 *
 * For more information on the BioJava project and its aims,
 * or to join the biojava-l mailing list, visit the home page
 * at:
 *
 *      http://www.biojava.org/
 *
 */
package org.biojava.utils;

import java.io.Serializable;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;

/**
 * Lightweight implementation of Map which uses little memory to store a
 * small number of mappings, at the expense of scalability.  Not recommended
 * for more than 20-30 mappings.
 *
 * <p>
 * This implementation has the useful property that the iteration order is
 * the same as the order in which mappings are added.
 * </p>
 *
 * @author Thomas Down
 * @author Len Trigg
 */

public class SmallMap extends AbstractMap implements Serializable {
    private Object[] mappings = null;
    private int numMappings = 0;

    public SmallMap() {
        super();
    }

    public SmallMap(int size) {
        super();
        mappings = new Object[size * 2];
    }

    public SmallMap(Map m) {
        this(m.size());
        for (Iterator i = m.entrySet().iterator(); i.hasNext(); ) {
            Map.Entry me = (Map.Entry) i.next();
            put(me.getKey(), me.getValue());
        }
    }

    /**
     * @throws NullPointerException if key is null
     */
    public Object get(Object key) {
        // Doesn't actually need to check if mappings is null, since numMappings
        // will necessarily be zero.
        
        int keyHash = key.hashCode();
        for (int i = 0; i < numMappings * 2; i += 2) {
            if (keyHash == mappings[i].hashCode() && key.equals(mappings[i])) {
                return mappings[i + 1];
            }
        }
        return null;
    }

    /**
     * @throws NullPointerException if key is null
     */
    public Object put(Object key, Object value) {
        int keyHash = key.hashCode();
        
        for (int i = 0; i < numMappings * 2; i += 2) {
            if (keyHash == mappings[i].hashCode() && key.equals(mappings[i])) {
                Object oldValue = mappings[i+1];
                mappings[i+1] = value;
                return oldValue;
            }
        }
        
        int newPos = numMappings * 2;
        int oldLength = 0;
        if (mappings != null) {
            oldLength = mappings.length;
        }
        if (newPos + 1 >= oldLength) {
            Object[] newMappings = new Object[oldLength + 6];
            if (oldLength > 0) {
                System.arraycopy(mappings, 0, newMappings, 0, mappings.length);
            }
            mappings = newMappings;
        }
        
        mappings[newPos] = key;
        mappings[newPos + 1] = value;
        numMappings++;
        
        return null;
    }

    public Set keySet() {
        return new KeySet();
    }

    public Set entrySet() {
        return new EntrySet();
    }

    public int size() {
        return numMappings;
    }

    public boolean containsKey(Object key) {
        int keyHash = key.hashCode();
        for (int i = 0; i < numMappings * 2; i += 2) {
            if (keyHash == mappings[i].hashCode() && key.equals(mappings[i])) {
                return true;
            }
        }
        return false;
    }


    // num ranges from 1 to numMappings
    private void removeMapping(int num) {
        if (num < numMappings) {
            System.arraycopy(mappings, num * 2, mappings, (num - 1) * 2, (numMappings - num) * 2);
        }
        mappings[numMappings * 2 - 1] = null;
        mappings[numMappings * 2 - 2] = null;
        numMappings--;
    }

    private class KeySet extends AbstractSet {
        public Iterator iterator() {
            return new KeyIterator();
        }

        public int size() {
            return numMappings;
        }
    }

    private class KeyIterator implements Iterator {
        int pos = 0;
        
        public boolean hasNext() {
            return pos < numMappings;
        }
        
        public Object next() {
            if (pos >= numMappings) {
                throw new NoSuchElementException();
            }
            int offset = pos * 2;
            ++pos;
            return mappings[offset];
        }
        
        public void remove() {
            removeMapping(pos);
            pos -= 1;
        }
    }

    private class EntrySet extends AbstractSet {
        public Iterator iterator() {
            return new EntryIterator();
        }

        public int size() {
            return numMappings;
        }
    }

    private class EntryIterator implements Iterator {
        int pos = 0;
        
        public boolean hasNext() {
            return pos < numMappings;
        }
        
        public Object next() {
            if (pos >= numMappings) {
                throw new NoSuchElementException();
            }
            int offset = pos * 2;
            ++pos;
            return new MapEntry(offset);
        }
        
        public void remove() {
            removeMapping(pos);
            pos -= 1;
        }
    }

    private class MapEntry implements Map.Entry {
        private int offset;
        
        private MapEntry(int offset) {
            this.offset = offset;
        }
        
        public Object getKey() {
            return mappings[offset];
        }
        
        public Object getValue() {
            return mappings[offset + 1];
        }
        
        public Object setValue(Object v) {
            Object oldValue = mappings[offset + 1];
            mappings[offset + 1] = v;
            return oldValue;
        }
        
        public boolean equals(Object o) {
            if (! (o instanceof Map.Entry)) {
                return false;
            }
            
            Map.Entry mo = (Map.Entry) o;
            return ((getKey() == null ? mo.getKey() == null : getKey().equals(mo.getKey())) &&
		    (getValue() == null ? mo.getValue() == null : getValue().equals(mo.getValue())));
        }
        
        public int hashCode() {
            return (getKey() == null ? 0 : getKey().hashCode()) ^ (getValue() == null ? 0 : getValue().hashCode());
        }
    }
}