001/*
002 * (C) Copyright 2006-2011 Nuxeo SA (http://nuxeo.com/) and others.
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 *     http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 * 
016 * Contributors:
017 *     Nuxeo - initial API and implementation
018 *
019 * $Id$
020 */
021
022package org.nuxeo.common.collections;
023
024import java.io.Serializable;
025import java.util.Map;
026
027/**
028 * A mixture of an array list and a map used to store small table of elements using both indices and keys.
029 * <p>
030 * This map accepts null values.
031 * <p>
032 * The map is implemented using an array of successive [key, value] pairs.
033 *
034 * @author <a href="mailto:bs@nuxeo.com">Bogdan Stefanescu</a>
035 * @author <a href="mailto:ja@nuxeo.com">Julien Anguenot</a>
036 */
037@SuppressWarnings({ "ClassWithoutToString" })
038public class SerializableArrayMap<K, V> implements Serializable {
039
040    private static final long serialVersionUID = 1L;
041
042    // 4 keys, 4 values
043    protected static final int DEFAULT_SIZE = 8;
044
045    protected static final int GROW_SIZE = 10;
046
047    protected int count = 0;
048
049    protected Serializable[] elements;
050
051    public SerializableArrayMap() {
052    }
053
054    public SerializableArrayMap(int initialCapacity) {
055        elements = new Serializable[initialCapacity == 0 ? DEFAULT_SIZE : initialCapacity * 2];
056    }
057
058    public SerializableArrayMap(Map map) {
059        this(map.size());
060        putAll(map);
061    }
062
063    public SerializableArrayMap(SerializableArrayMap map) {
064        count = map.count;
065        elements = new Serializable[map.elements.length];
066        System.arraycopy(map.elements, 0, elements, 0, count * 2);
067    }
068
069    public void putAll(Map<K, V> map) {
070        for (Map.Entry<K, V> entry : map.entrySet()) {
071            Serializable o = (Serializable) entry;
072            K key = entry.getKey();
073            V value = entry.getValue();
074            add(key, value);
075        }
076    }
077
078    public V remove(K key) {
079        if (elements == null || count == 0) {
080            return null;
081        }
082        for (int i = 0; i < elements.length; i += 2) {
083            if (elements[i] != null && elements[i].equals(key)) {
084                return _remove(i);
085            }
086        }
087        return null;
088    }
089
090    public V remove(int index) {
091        if (elements == null || count == 0) {
092            return null;
093        }
094        return _remove(index << 1);
095    }
096
097    protected final V _remove(int i) {
098        V result = (V) elements[i + 1];
099        int len = count * 2;
100        if (i + 2 == len) {
101            elements[i] = null;
102            elements[i + 1] = null;
103        } else {
104            int k = i + 2;
105            System.arraycopy(elements, k, elements, i, len - k);
106        }
107        count--;
108        return result;
109    }
110
111    public V get(K key) {
112        if (elements == null || count == 0) {
113            return null;
114        }
115        for (int i = 0; i < elements.length; i += 2) {
116            if (elements[i] != null && elements[i].equals(key)) {
117                return (V) elements[i + 1];
118            }
119        }
120        return null;
121    }
122
123    public V get(int i) {
124        if (elements == null || i >= count) {
125            throw new ArrayIndexOutOfBoundsException(i);
126        }
127        return (V) elements[(i << 1) + 1];
128    }
129
130    public K getKey(Serializable value) {
131        if (elements == null || count == 0) {
132            return null;
133        }
134        for (int i = 1; i < elements.length; i += 2) {
135            if (elements[i] != null && elements[i].equals(value)) {
136                return (K) elements[i - 1];
137            }
138        }
139        return null;
140    }
141
142    public K getKey(int i) {
143        if (elements == null || i >= count) {
144            throw new ArrayIndexOutOfBoundsException(i);
145        }
146        return (K) elements[i << 1];
147    }
148
149    public V put(K key, V value) {
150
151        // handle the case where we don't have any attributes yet
152        if (elements == null) {
153            elements = new Serializable[DEFAULT_SIZE];
154        }
155        if (count == 0) {
156            elements[0] = (Serializable) key;
157            elements[1] = (Serializable) value;
158            count++;
159            return null;
160        }
161
162        int insertIndex = count * 2;
163
164        // replace existing value if it exists
165        for (int i = 0; i < insertIndex; i += 2) {
166            if (elements[i].equals(key)) {
167                Serializable oldValue = elements[i + 1];
168                elements[i + 1] = (Serializable) value;
169                return (V) oldValue;
170            }
171        }
172
173        if (elements.length <= insertIndex) {
174            grow();
175        }
176        elements[insertIndex] = (Serializable) key;
177        elements[insertIndex + 1] = (Serializable) value;
178        count++;
179
180        return null;
181    }
182
183    public void add(K key, V value) {
184        // handle the case where we don't have any attributes yet
185        int insertIndex;
186        if (elements == null) {
187            elements = new Serializable[DEFAULT_SIZE];
188            insertIndex = 0;
189        } else {
190            insertIndex = count * 2;
191            if (elements.length <= insertIndex) {
192                grow();
193            }
194        }
195        elements[insertIndex] = (Serializable) key;
196        elements[insertIndex + 1] = (Serializable) value;
197        count++;
198    }
199
200    public void trimToSize() {
201        int len = count * 2;
202        if (len < elements.length) {
203            Serializable[] tmp = new Serializable[len];
204            System.arraycopy(elements, 0, tmp, 0, len);
205            elements = tmp;
206        }
207    }
208
209    public int size() {
210        return count;
211    }
212
213    public boolean isEmpty() {
214        return count == 0;
215    }
216
217    public void clear() {
218        elements = null;
219        count = 0;
220    }
221
222    protected void grow() {
223        Serializable[] expanded = new Serializable[elements.length + GROW_SIZE];
224        System.arraycopy(elements, 0, expanded, 0, elements.length);
225        elements = expanded;
226    }
227
228    public Serializable[] getArray() {
229        return elements;
230    }
231
232    @Override
233    public boolean equals(Object obj) {
234        if (obj == this) {
235            return true;
236        }
237        if (obj instanceof SerializableArrayMap) {
238            SerializableArrayMap map = (SerializableArrayMap) obj;
239            if (count != map.count) {
240                return false;
241            }
242            int len = count << 1;
243            for (int i = 0; i < len; i += 2) {
244                Serializable key1 = elements[i];
245                Serializable key2 = map.elements[i];
246                if (!key1.equals(key2)) {
247                    return false;
248                }
249                Serializable val1 = elements[i + 1];
250                Serializable val2 = map.elements[i + 1];
251                if (val1 == null) {
252                    if (val1 != val2) {
253                        return false;
254                    }
255                } else if (!val1.equals(val2)) {
256                    return false;
257                }
258            }
259            return true;
260        }
261        return false;
262    }
263
264    @Override
265    public int hashCode() {
266        int result = 17;
267        for (int i = 0; i < count * 2; i++) {
268            result = result * 37 + elements[i].hashCode();
269        }
270        return result;
271    }
272
273}