1/*
2 * Copyright (c) 2009-2010 jMonkeyEngine
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met:
8 *
9 * * Redistributions of source code must retain the above copyright
10 *   notice, this list of conditions and the following disclaimer.
11 *
12 * * Redistributions in binary form must reproduce the above copyright
13 *   notice, this list of conditions and the following disclaimer in the
14 *   documentation and/or other materials provided with the distribution.
15 *
16 * * Neither the name of 'jMonkeyEngine' nor the names of its contributors
17 *   may be used to endorse or promote products derived from this software
18 *   without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
22 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
23 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
24 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
25 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
26 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
27 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
28 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
29 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
30 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 */
32
33package com.jme3.util;
34
35import com.jme3.util.IntMap.Entry;
36import java.util.Iterator;
37import java.util.Map;
38
39/**
40 * Similar to a {@link Map} except that ints are used as keys.
41 *
42 * Taken from <a href="http://code.google.com/p/skorpios/">http://code.google.com/p/skorpios/</a>
43 *
44 * @author Nate
45 */
46public final class IntMap<T> implements Iterable<Entry<T>>, Cloneable {
47
48    private Entry[] table;
49    private final float loadFactor;
50    private int size, mask, capacity, threshold;
51
52    public IntMap() {
53        this(16, 0.75f);
54    }
55
56    public IntMap(int initialCapacity) {
57        this(initialCapacity, 0.75f);
58    }
59
60    public IntMap(int initialCapacity, float loadFactor) {
61        if (initialCapacity > 1 << 30){
62            throw new IllegalArgumentException("initialCapacity is too large.");
63        }
64        if (initialCapacity < 0){
65            throw new IllegalArgumentException("initialCapacity must be greater than zero.");
66        }
67        if (loadFactor <= 0){
68            throw new IllegalArgumentException("initialCapacity must be greater than zero.");
69        }
70        capacity = 1;
71        while (capacity < initialCapacity){
72            capacity <<= 1;
73        }
74        this.loadFactor = loadFactor;
75        this.threshold = (int) (capacity * loadFactor);
76        this.table = new Entry[capacity];
77        this.mask = capacity - 1;
78    }
79
80    @Override
81    public IntMap<T> clone(){
82        try{
83            IntMap<T> clone = (IntMap<T>) super.clone();
84            Entry[] newTable = new Entry[table.length];
85            for (int i = table.length - 1; i >= 0; i--){
86                if (table[i] != null)
87                    newTable[i] = table[i].clone();
88            }
89            clone.table = newTable;
90            return clone;
91        }catch (CloneNotSupportedException ex){
92        }
93        return null;
94    }
95
96    public boolean containsValue(Object value) {
97        Entry[] table = this.table;
98        for (int i = table.length; i-- > 0;){
99            for (Entry e = table[i]; e != null; e = e.next){
100                if (e.value.equals(value)){
101                    return true;
102                }
103            }
104        }
105        return false;
106    }
107
108    public boolean containsKey(int key) {
109        int index = ((int) key) & mask;
110        for (Entry e = table[index]; e != null; e = e.next){
111            if (e.key == key){
112                return true;
113            }
114        }
115        return false;
116    }
117
118    public T get(int key) {
119        int index = key & mask;
120        for (Entry e = table[index]; e != null; e = e.next){
121            if (e.key == key){
122                return (T) e.value;
123            }
124        }
125        return null;
126    }
127
128    public T put(int key, T value) {
129        int index = key & mask;
130        // Check if key already exists.
131        for (Entry e = table[index]; e != null; e = e.next){
132            if (e.key != key){
133                continue;
134            }
135            Object oldValue = e.value;
136            e.value = value;
137            return (T) oldValue;
138        }
139        table[index] = new Entry(key, value, table[index]);
140        if (size++ >= threshold){
141            // Rehash.
142            int newCapacity = 2 * capacity;
143            Entry[] newTable = new Entry[newCapacity];
144            Entry[] src = table;
145            int bucketmask = newCapacity - 1;
146            for (int j = 0; j < src.length; j++){
147                Entry e = src[j];
148                if (e != null){
149                    src[j] = null;
150                    do{
151                        Entry next = e.next;
152                        index = e.key & bucketmask;
153                        e.next = newTable[index];
154                        newTable[index] = e;
155                        e = next;
156                    }while (e != null);
157                }
158            }
159            table = newTable;
160            capacity = newCapacity;
161            threshold = (int) (newCapacity * loadFactor);
162            mask = capacity - 1;
163        }
164        return null;
165    }
166
167    public T remove(int key) {
168        int index = key & mask;
169        Entry prev = table[index];
170        Entry e = prev;
171        while (e != null){
172            Entry next = e.next;
173            if (e.key == key){
174                size--;
175                if (prev == e){
176                    table[index] = next;
177                }else{
178                    prev.next = next;
179                }
180                return (T) e.value;
181            }
182            prev = e;
183            e = next;
184        }
185        return null;
186    }
187
188    public int size() {
189        return size;
190    }
191
192    public void clear() {
193        Entry[] table = this.table;
194        for (int index = table.length; --index >= 0;){
195            table[index] = null;
196        }
197        size = 0;
198    }
199
200    public Iterator<Entry<T>> iterator() {
201        IntMapIterator it = new IntMapIterator();
202        it.beginUse();
203        return it;
204    }
205
206    final class IntMapIterator implements Iterator<Entry<T>> {
207
208        /**
209         * Current entry.
210         */
211        private Entry cur;
212
213        /**
214         * Entry in the table
215         */
216        private int idx = 0;
217
218        /**
219         * Element in the entry
220         */
221        private int el  = 0;
222
223        public IntMapIterator() {
224        }
225
226        public void beginUse(){
227            cur = table[0];
228            idx = 0;
229            el = 0;
230        }
231
232        public boolean hasNext() {
233            return el < size;
234        }
235
236        public Entry next() {
237            if (el >= size)
238                throw new IllegalStateException("No more elements!");
239
240            if (cur != null){
241                Entry e = cur;
242                cur = cur.next;
243                el++;
244                return e;
245            }
246//            if (cur != null && cur.next != null){
247                // if we have a current entry, continue to the next entry in the list
248//                cur = cur.next;
249//                el++;
250//                return cur;
251//            }
252
253            do {
254                // either we exhausted the current entry list, or
255                // the entry was null. find another non-null entry.
256                cur = table[++idx];
257            } while (cur == null);
258
259            Entry e = cur;
260            cur = cur.next;
261            el ++;
262
263            return e;
264        }
265
266        public void remove() {
267        }
268
269    }
270
271    public static final class Entry<T> implements Cloneable {
272
273        final int key;
274        T value;
275        Entry next;
276
277        Entry(int k, T v, Entry n) {
278            key = k;
279            value = v;
280            next = n;
281        }
282
283        public int getKey(){
284            return key;
285        }
286
287        public T getValue(){
288            return value;
289        }
290
291        @Override
292        public String toString(){
293            return key + " => " + value;
294        }
295
296        @Override
297        public Entry<T> clone(){
298            try{
299                Entry<T> clone = (Entry<T>) super.clone();
300                clone.next = next != null ? next.clone() : null;
301                return clone;
302            }catch (CloneNotSupportedException ex){
303            }
304            return null;
305        }
306    }
307}
308