001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017: package org.apache.wicket.util.collections;
018:
019: import java.io.Serializable;
020: import java.util.AbstractList;
021: import java.util.AbstractSet;
022: import java.util.Collection;
023: import java.util.Iterator;
024: import java.util.Map;
025: import java.util.NoSuchElementException;
026: import java.util.Set;
027:
028: /**
029: * A fixed size map implementation. Holds an array of keys and array of values
030: * which correspond by index. Null key entries are available for use. This means
031: * that null is not a valid key.
032: *
033: * @author Jonathan Locke
034: */
035: public final class MiniMap implements Map, Serializable {
036: private static final long serialVersionUID = 1L;
037:
038: /** The array of keys. Keys that are null are not used. */
039: private final Object[] keys;
040:
041: /** The array of values which correspond by index with the keys array. */
042: private final Object[] values;
043:
044: /** The number of valid entries */
045: private int size;
046:
047: /** The last search index. This makes putting and getting more efficient. */
048: private int lastSearchIndex;
049:
050: /**
051: * Constructor
052: *
053: * @param maxEntries
054: * The maximum number of entries this map can hold
055: */
056: public MiniMap(final int maxEntries) {
057: this .keys = new Object[maxEntries];
058: this .values = new Object[maxEntries];
059: }
060:
061: /**
062: * Constructor
063: *
064: * @param map
065: * The map
066: * @param maxEntries
067: * The maximum number of entries this map can hold
068: */
069: public MiniMap(final Map map, final int maxEntries) {
070: this (maxEntries);
071: putAll(map);
072: }
073:
074: /**
075: * @return True if this MicroMap is full
076: */
077: public boolean isFull() {
078: return size == keys.length;
079: }
080:
081: /**
082: * @see java.util.Map#size()
083: */
084: public int size() {
085: return size;
086: }
087:
088: /**
089: * @see java.util.Map#isEmpty()
090: */
091: public boolean isEmpty() {
092: return size == 0;
093: }
094:
095: /**
096: * @see java.util.Map#containsKey(java.lang.Object)
097: */
098: public boolean containsKey(final Object key) {
099: return findKey(0, key) != -1;
100: }
101:
102: /**
103: * @see java.util.Map#containsValue(java.lang.Object)
104: */
105: public boolean containsValue(final Object value) {
106: return findValue(0, value) != -1;
107: }
108:
109: /**
110: * @see java.util.Map#get(java.lang.Object)
111: */
112: public Object get(final Object key) {
113: // Search for key
114: final int index = findKey(key);
115:
116: if (index != -1) {
117: // Return value
118: return values[index];
119: }
120:
121: // Failed to find key
122: return null;
123: }
124:
125: /**
126: * @see java.util.Map#put(java.lang.Object, java.lang.Object)
127: */
128: public Object put(final Object key, final Object value) {
129: // Search for key
130: final int index = findKey(key);
131:
132: if (index != -1) {
133: // Replace existing value
134: final Object oldValue = values[index];
135: this .values[index] = value;
136: return oldValue;
137: }
138:
139: // Is there room for a new entry?
140: if (size < keys.length) {
141: // Store at first null index and continue searching after null index
142: // next time
143: final int nullIndex = nextNullKey(lastSearchIndex);
144: lastSearchIndex = nextIndex(nullIndex);
145: keys[nullIndex] = key;
146: values[nullIndex] = value;
147: size++;
148:
149: return null;
150: } else {
151: throw new IllegalStateException("Map full");
152: }
153: }
154:
155: /**
156: * @see java.util.Map#remove(java.lang.Object)
157: */
158: public Object remove(final Object key) {
159: // Search for key
160: final int index = findKey(key);
161:
162: if (index != -1) {
163: // Store value
164: final Object oldValue = values[index];
165:
166: keys[index] = null;
167: values[index] = null;
168: size--;
169:
170: return oldValue;
171: }
172:
173: return null;
174: }
175:
176: /**
177: * @see java.util.Map#putAll(java.util.Map)
178: */
179: public void putAll(final Map map) {
180: for (final Iterator iterator = map.entrySet().iterator(); iterator
181: .hasNext();) {
182: final Map.Entry e = (Map.Entry) iterator.next();
183: put(e.getKey(), e.getValue());
184: }
185: }
186:
187: /**
188: * @see java.util.Map#clear()
189: */
190: public void clear() {
191: for (int i = 0; i < keys.length; i++) {
192: keys[i] = null;
193: values[i] = null;
194: }
195:
196: size = 0;
197: }
198:
199: /**
200: * @see java.util.Map#keySet()
201: */
202: public Set keySet() {
203: return new AbstractSet() {
204: public Iterator iterator() {
205: return new Iterator() {
206: public boolean hasNext() {
207: return i < size - 1;
208: }
209:
210: public Object next() {
211: // Just in case... (WICKET-428)
212: if (!hasNext()) {
213: throw new NoSuchElementException();
214: }
215:
216: // Find next key
217: i = nextKey(nextIndex(i));
218:
219: // Get key
220: return keys[i];
221: }
222:
223: public void remove() {
224: keys[i] = null;
225: values[i] = null;
226: size--;
227: }
228:
229: int i = -1;
230: };
231: }
232:
233: public int size() {
234: return size;
235: }
236: };
237: }
238:
239: /**
240: * @see java.util.Map#values()
241: */
242: public Collection values() {
243: return new AbstractList() {
244: public Object get(final int index) {
245: if (index > size - 1) {
246: throw new IndexOutOfBoundsException();
247: }
248: int keyIndex = nextKey(0);
249:
250: for (int i = 0; i < index; i++) {
251: keyIndex = nextKey(keyIndex + 1);
252: }
253:
254: return values[keyIndex];
255: }
256:
257: public int size() {
258: return size;
259: }
260: };
261: }
262:
263: /**
264: * @see java.util.Map#entrySet()
265: */
266: public Set entrySet() {
267: return new AbstractSet() {
268: public Iterator iterator() {
269: return new Iterator() {
270: public boolean hasNext() {
271: return index < size;
272: }
273:
274: public Object next() {
275: if (!hasNext()) {
276: throw new NoSuchElementException();
277: }
278:
279: keyIndex = nextKey(nextIndex(keyIndex));
280:
281: index++;
282:
283: return new Map.Entry() {
284: public Object getKey() {
285: return keys[keyIndex];
286: }
287:
288: public Object getValue() {
289: return values[keyIndex];
290: }
291:
292: public Object setValue(final Object value) {
293: final Object oldValue = values[keyIndex];
294:
295: values[keyIndex] = value;
296:
297: return oldValue;
298: }
299: };
300: }
301:
302: public void remove() {
303: keys[keyIndex] = null;
304: values[keyIndex] = null;
305: }
306:
307: int keyIndex = -1;
308:
309: int index = 0;
310: };
311: }
312:
313: public int size() {
314: return size;
315: }
316: };
317: }
318:
319: /**
320: * Computes the next index in the key or value array (both are the same
321: * length)
322: *
323: * @param index
324: * The index
325: * @return The next index, taking into account wraparound
326: */
327: private int nextIndex(final int index) {
328: return (index + 1) % keys.length;
329: }
330:
331: /**
332: * Finds the index of the next non-null key. If the map is empty, -1 will be
333: * returned.
334: *
335: * @param start
336: * Index to start at
337: * @return Index of next non-null key
338: */
339: private int nextKey(final int start) {
340: int i = start;
341:
342: do {
343: if (keys[i] != null) {
344: return i;
345: }
346:
347: i = nextIndex(i);
348: } while (i != start);
349:
350: return -1;
351: }
352:
353: /**
354: * Finds the index of the next null key. If no null key can be found, the
355: * map is full and -1 will be returned.
356: *
357: * @param start
358: * Index to start at
359: * @return Index of next null key
360: */
361: private int nextNullKey(final int start) {
362: int i = start;
363:
364: do {
365: if (keys[i] == null) {
366: return i;
367: }
368:
369: i = nextIndex(i);
370: } while (i != start);
371:
372: return -1;
373: }
374:
375: /**
376: * Finds a key by starting at lastSearchIndex and searching from there. If
377: * the key is found, lastSearchIndex is advanced so the next key search can
378: * find the next key in the array, which is the most likely to be retrieved.
379: *
380: * @param key
381: * Key to find in map
382: * @return Index of matching key or -1 if not found
383: */
384: private int findKey(final Object key) {
385: // Find key starting at search index
386: final int index = findKey(lastSearchIndex, key);
387:
388: // Found match?
389: if (index != -1) {
390: // Start search at the next index next time
391: lastSearchIndex = nextIndex(index);
392:
393: // Return index of key
394: return index;
395: }
396:
397: return -1;
398: }
399:
400: /**
401: * Searches for a key from a given starting index.
402: *
403: * @param key
404: * The key to find in this map
405: * @param start
406: * Index to start at
407: * @return Index of matching key or -1 if not found
408: */
409: private int findKey(final int start, final Object key) {
410: int i = start;
411:
412: do {
413: if (key.equals(keys[i])) {
414: return i;
415: }
416:
417: i = nextIndex(i);
418: } while (i != start);
419:
420: return -1;
421: }
422:
423: /**
424: * Searches for a value from a given starting index.
425: *
426: * @param start
427: * Index to start at
428: * @param value
429: * The value to find in this map
430: * @return Index of matching value or -1 if not found
431: */
432: private int findValue(final int start, final Object value) {
433: int i = start;
434:
435: do {
436: if (value.equals(values[i])) {
437: return i;
438: }
439:
440: i = nextIndex(i);
441: } while (i != start);
442:
443: return -1;
444: }
445: }
|