001/*
002 *                    BioJava development code
003 *
004 * This code may be freely distributed and modified under the
005 * terms of the GNU Lesser General Public Licence.  This should
006 * be distributed with the code.  If you do not have a copy,
007 * see:
008 *
009 *      http://www.gnu.org/copyleft/lesser.html
010 *
011 * Copyright for this code is held jointly by the individual
012 * authors.  These should be listed in @author doc comments.
013 *
014 * For more information on the BioJava project and its aims,
015 * or to join the biojava-l mailing list, visit the home page
016 * at:
017 *
018 *      http://www.biojava.org/
019 *
020 */
021package org.biojava.utils;
022
023import java.io.Serializable;
024import java.util.AbstractMap;
025import java.util.AbstractSet;
026import java.util.Iterator;
027import java.util.Map;
028import java.util.NoSuchElementException;
029import java.util.Set;
030
031/**
032 * Lightweight implementation of Map which uses little memory to store a
033 * small number of mappings, at the expense of scalability.  Not recommended
034 * for more than 20-30 mappings.
035 *
036 * <p>
037 * This implementation has the useful property that the iteration order is
038 * the same as the order in which mappings are added.
039 * </p>
040 *
041 * @author Thomas Down
042 * @author Len Trigg
043 */
044
045public class SmallMap extends AbstractMap implements Serializable {
046    private Object[] mappings = null;
047    private int numMappings = 0;
048
049    public SmallMap() {
050        super();
051    }
052
053    public SmallMap(int size) {
054        super();
055        mappings = new Object[size * 2];
056    }
057
058    public SmallMap(Map m) {
059        this(m.size());
060        for (Iterator i = m.entrySet().iterator(); i.hasNext(); ) {
061            Map.Entry me = (Map.Entry) i.next();
062            put(me.getKey(), me.getValue());
063        }
064    }
065
066    /**
067     * @throws NullPointerException if key is null
068     */
069    public Object get(Object key) {
070        // Doesn't actually need to check if mappings is null, since numMappings
071        // will necessarily be zero.
072        
073        int keyHash = key.hashCode();
074        for (int i = 0; i < numMappings * 2; i += 2) {
075            if (keyHash == mappings[i].hashCode() && key.equals(mappings[i])) {
076                return mappings[i + 1];
077            }
078        }
079        return null;
080    }
081
082    /**
083     * @throws NullPointerException if key is null
084     */
085    public Object put(Object key, Object value) {
086        int keyHash = key.hashCode();
087        
088        for (int i = 0; i < numMappings * 2; i += 2) {
089            if (keyHash == mappings[i].hashCode() && key.equals(mappings[i])) {
090                Object oldValue = mappings[i+1];
091                mappings[i+1] = value;
092                return oldValue;
093            }
094        }
095        
096        int newPos = numMappings * 2;
097        int oldLength = 0;
098        if (mappings != null) {
099            oldLength = mappings.length;
100        }
101        if (newPos + 1 >= oldLength) {
102            Object[] newMappings = new Object[oldLength + 6];
103            if (oldLength > 0) {
104                System.arraycopy(mappings, 0, newMappings, 0, mappings.length);
105            }
106            mappings = newMappings;
107        }
108        
109        mappings[newPos] = key;
110        mappings[newPos + 1] = value;
111        numMappings++;
112        
113        return null;
114    }
115
116    public Set keySet() {
117        return new KeySet();
118    }
119
120    public Set entrySet() {
121        return new EntrySet();
122    }
123
124    public int size() {
125        return numMappings;
126    }
127
128    public boolean containsKey(Object key) {
129        int keyHash = key.hashCode();
130        for (int i = 0; i < numMappings * 2; i += 2) {
131            if (keyHash == mappings[i].hashCode() && key.equals(mappings[i])) {
132                return true;
133            }
134        }
135        return false;
136    }
137
138
139    // num ranges from 1 to numMappings
140    private void removeMapping(int num) {
141        if (num < numMappings) {
142            System.arraycopy(mappings, num * 2, mappings, (num - 1) * 2, (numMappings - num) * 2);
143        }
144        mappings[numMappings * 2 - 1] = null;
145        mappings[numMappings * 2 - 2] = null;
146        numMappings--;
147    }
148
149    private class KeySet extends AbstractSet {
150        public Iterator iterator() {
151            return new KeyIterator();
152        }
153
154        public int size() {
155            return numMappings;
156        }
157    }
158
159    private class KeyIterator implements Iterator {
160        int pos = 0;
161        
162        public boolean hasNext() {
163            return pos < numMappings;
164        }
165        
166        public Object next() {
167            if (pos >= numMappings) {
168                throw new NoSuchElementException();
169            }
170            int offset = pos * 2;
171            ++pos;
172            return mappings[offset];
173        }
174        
175        public void remove() {
176            removeMapping(pos);
177            pos -= 1;
178        }
179    }
180
181    private class EntrySet extends AbstractSet {
182        public Iterator iterator() {
183            return new EntryIterator();
184        }
185
186        public int size() {
187            return numMappings;
188        }
189    }
190
191    private class EntryIterator implements Iterator {
192        int pos = 0;
193        
194        public boolean hasNext() {
195            return pos < numMappings;
196        }
197        
198        public Object next() {
199            if (pos >= numMappings) {
200                throw new NoSuchElementException();
201            }
202            int offset = pos * 2;
203            ++pos;
204            return new MapEntry(offset);
205        }
206        
207        public void remove() {
208            removeMapping(pos);
209            pos -= 1;
210        }
211    }
212
213    private class MapEntry implements Map.Entry {
214        private int offset;
215        
216        private MapEntry(int offset) {
217            this.offset = offset;
218        }
219        
220        public Object getKey() {
221            return mappings[offset];
222        }
223        
224        public Object getValue() {
225            return mappings[offset + 1];
226        }
227        
228        public Object setValue(Object v) {
229            Object oldValue = mappings[offset + 1];
230            mappings[offset + 1] = v;
231            return oldValue;
232        }
233        
234        public boolean equals(Object o) {
235            if (! (o instanceof Map.Entry)) {
236                return false;
237            }
238            
239            Map.Entry mo = (Map.Entry) o;
240            return ((getKey() == null ? mo.getKey() == null : getKey().equals(mo.getKey())) &&
241                    (getValue() == null ? mo.getValue() == null : getValue().equals(mo.getValue())));
242        }
243        
244        public int hashCode() {
245            return (getKey() == null ? 0 : getKey().hashCode()) ^ (getValue() == null ? 0 : getValue().hashCode());
246        }
247    }
248}