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:
018: package org.apache.harmony.luni.util;
019:
020: import java.util.AbstractCollection;
021: import java.util.AbstractMap;
022: import java.util.AbstractSet;
023: import java.util.Arrays;
024: import java.util.Collection;
025: import java.util.ConcurrentModificationException;
026: import java.util.Iterator;
027: import java.util.Map;
028: import java.util.NoSuchElementException;
029: import java.util.Set;
030:
031: /**
032: *
033: * Reductive hash with two keys
034: *
035: */
036: public class TwoKeyHashMap<E, K, V> extends AbstractMap<String, V> {
037:
038: static final float DEFAULT_LOAD_FACTOR = 0.75f;
039: static final int DEFAULT_INITIAL_SIZE = 16;
040:
041: private Set<Map.Entry<String, V>> entrySet;
042: private Collection<V> values;
043: private int size;
044: private int arrSize;
045: private int modCount;
046:
047: private Entry<E, K, V>[] arr;
048:
049: private float loadFactor;
050: int threshold = 0;
051:
052: /**
053: * Constructs an empty HashMap
054: */
055: public TwoKeyHashMap() {
056: this (DEFAULT_INITIAL_SIZE, DEFAULT_LOAD_FACTOR);
057: }
058:
059: /**
060: * Constructs an empty HashMap
061: *
062: * @param initialCapacity
063: */
064: public TwoKeyHashMap(int initialCapacity) {
065: this (initialCapacity, DEFAULT_LOAD_FACTOR);
066: }
067:
068: /**
069: * Constructs an empty HashMap
070: *
071: * @param initialCapacity
072: * @param initialLoadFactor
073: */
074: @SuppressWarnings("unchecked")
075: public TwoKeyHashMap(int initialCapacity, float initialLoadFactor) {
076: if (initialCapacity < 0) {
077: throw new IllegalArgumentException(
078: "initialCapacity should be >= 0");
079: }
080: if (initialLoadFactor <= 0) {
081: throw new IllegalArgumentException(
082: "initialLoadFactor should be > 0");
083: }
084: loadFactor = initialLoadFactor;
085: if (initialCapacity == Integer.MAX_VALUE) {
086: initialCapacity--;
087: }
088: arrSize = initialCapacity > 0 ? initialCapacity : 1;
089: threshold = (int) (arrSize * loadFactor);
090: arr = new Entry[arrSize + 1];
091: }
092:
093: /**
094: * Returns a collection view of the values
095: */
096: public Collection<V> values() {
097: if (values == null) {
098: values = new ValuesCollectionImpl();
099: }
100: return values;
101: }
102:
103: /**
104: * Returns a collection view of the mappings
105: */
106: public Set<Map.Entry<String, V>> entrySet() {
107: if (entrySet == null) {
108: entrySet = new EntrySetImpl();
109: }
110: return entrySet;
111: }
112:
113: /**
114: * Clears the map
115: */
116: public void clear() {
117: modCount++;
118: size = 0;
119: Arrays.fill(arr, 0, arr.length, null);
120: }
121:
122: /**
123: * Removes the mapping for the keys
124: *
125: * @param key1
126: * @param key2
127: * @return
128: */
129: public V remove(Object key1, Object key2) {
130: Entry<E, K, V> e = removeEntry(key1, key2);
131: return null != e ? e.value : null;
132: }
133:
134: /**
135: * Associates the specified value with the specified keys in this map
136: *
137: * @param key1
138: * @param key2
139: * @param value
140: * @return
141: */
142: public V put(E key1, K key2, V value) {
143: if (key1 == null && key2 == null) {
144: int index = arrSize;
145: if (arr[index] == null) {
146: arr[index] = createEntry(0, null, null, value, null);
147: size++;
148: modCount++;
149: return null;
150: } else {
151: V oldValue = arr[index].value;
152: arr[index].value = value;
153: return oldValue;
154: }
155: }
156:
157: int hash = key1.hashCode() + key2.hashCode();
158: int index = (hash & 0x7fffffff) % arrSize;
159: Entry<E, K, V> e = arr[index];
160:
161: while (e != null) {
162: if (hash == e.hash && key1.equals(e.getKey1())
163: && key2.equals(e.getKey2())) {
164: V oldValue = e.value;
165: e.value = value;
166: return oldValue;
167: }
168: e = e.next;
169: }
170:
171: arr[index] = createEntry(hash, key1, key2, value, arr[index]);
172: size++;
173: modCount++;
174:
175: if (size > threshold) {
176: rehash();
177: }
178: return null;
179: }
180:
181: /**
182: * Rehash the map
183: *
184: */
185: @SuppressWarnings("unchecked")
186: void rehash() {
187: int newArrSize = (arrSize + 1) * 2 + 1;
188: if (newArrSize < 0) {
189: newArrSize = Integer.MAX_VALUE - 1;
190: }
191: Entry<E, K, V>[] newArr = new Entry[newArrSize + 1];
192:
193: for (int i = 0; i < arr.length - 1; i++) {
194: Entry<E, K, V> entry = arr[i];
195: while (entry != null) {
196: Entry<E, K, V> next = entry.next;
197:
198: int newIndex = (entry.hash & 0x7fffffff) % newArrSize;
199: entry.next = newArr[newIndex];
200: newArr[newIndex] = entry;
201:
202: entry = next;
203: }
204: }
205: newArr[newArrSize] = arr[arrSize]; // move null entry
206: arrSize = newArrSize;
207:
208: // The maximum array size is reached, increased loadFactor
209: // will keep array from further growing
210: if (arrSize == Integer.MAX_VALUE) {
211: loadFactor *= 10;
212: }
213: threshold = (int) (arrSize * loadFactor);
214: arr = newArr;
215: }
216:
217: /**
218: * Answers whether this map contains a mapping for the specified keys.
219: *
220: * @param key1 first key
221: * @param key2 second key
222: * @return true if this map contains a mapping for the specified keys, and
223: * false otherwise.
224: */
225: public boolean containsKey(Object key1, Object key2) {
226: return findEntry(key1, key2) != null;
227: }
228:
229: /**
230: * Return the value by keys
231: *
232: * @param key1
233: * @param key2
234: * @return
235: */
236: public V get(Object key1, Object key2) {
237: Entry<E, K, V> e = findEntry(key1, key2);
238: if (e != null) {
239: return e.value;
240: }
241: return null;
242: }
243:
244: /**
245: * Returns true if this map contains no key-value mappings
246: */
247: public boolean isEmpty() {
248: return size == 0;
249: }
250:
251: /**
252: * Returns the number of mappings
253: */
254: public int size() {
255: return size;
256: }
257:
258: /**
259: * Creates new entry
260: *
261: * @param hashCode
262: * @param key1
263: * @param key2
264: * @param value
265: * @param next
266: * @return
267: */
268: Entry<E, K, V> createEntry(int hashCode, E key1, K key2, V value,
269: Entry<E, K, V> next) {
270: return new Entry<E, K, V>(hashCode, key1, key2, value, next);
271: }
272:
273: /**
274: * Creates entries iterator
275: *
276: * @return
277: */
278: Iterator<Map.Entry<String, V>> createEntrySetIterator() {
279: return new EntryIteratorImpl();
280: }
281:
282: /**
283: * Creates values iterator
284: *
285: * @return
286: */
287: Iterator<V> createValueCollectionIterator() {
288: return new ValueIteratorImpl();
289: }
290:
291: /**
292: * Entry implementation for the TwoKeyHashMap class
293: *
294: */
295: public static class Entry<E, K, V> implements Map.Entry<String, V> {
296: int hash;
297: E key1;
298: K key2;
299: V value;
300: Entry<E, K, V> next;
301:
302: public Entry(int hash, E key1, K key2, V value,
303: Entry<E, K, V> next) {
304: this .hash = hash;
305: this .key1 = key1;
306: this .key2 = key2;
307: this .value = value;
308: this .next = next;
309: }
310:
311: public String getKey() {
312: return key1.toString() + key2.toString();
313: }
314:
315: public E getKey1() {
316: return key1;
317: }
318:
319: public K getKey2() {
320: return key2;
321: }
322:
323: public V getValue() {
324: return value;
325: }
326:
327: public V setValue(V value) {
328: V oldValue = this .value;
329: this .value = value;
330: return oldValue;
331: }
332:
333: public boolean equals(Object obj) {
334: if (!(obj instanceof Entry)) {
335: return false;
336: }
337:
338: Entry<?, ?, ?> e = (Entry<?, ?, ?>) obj;
339: Object getKey1 = e.getKey1();
340: Object getKey2 = e.getKey2();
341: Object getValue = e.getValue();
342: if ((key1 == null && getKey1 != null)
343: || (key2 == null && getKey2 != null)
344: || (value == null && getValue != null)
345: || !key1.equals(e.getKey1())
346: || !key2.equals(e.getKey2())
347: || !value.equals(getValue)) {
348: return false;
349: }
350: return true;
351: }
352:
353: public int hashCode() {
354: int hash1 = (key1 == null ? 0 : key1.hashCode());
355: int hash2 = (key2 == null ? 0 : key2.hashCode());
356: return (hash1 + hash2)
357: ^ (value == null ? 0 : value.hashCode());
358: }
359:
360: }
361:
362: class EntrySetImpl extends AbstractSet<Map.Entry<String, V>> {
363: public int size() {
364: return size;
365: }
366:
367: public void clear() {
368: TwoKeyHashMap.this .clear();
369: }
370:
371: public boolean isEmpty() {
372: return size == 0;
373: }
374:
375: public boolean contains(Object obj) {
376: if (!(obj instanceof Entry)) {
377: return false;
378: }
379:
380: Entry<?, ?, ?> entry = (Entry<?, ?, ?>) obj;
381: Entry<E, K, V> entry2 = findEntry(entry.getKey1(), entry
382: .getKey2());
383: if (entry2 == null) {
384: return false;
385: }
386: Object value = entry.getValue();
387: Object value2 = entry2.getValue();
388: return value == null ? value2 == null : value
389: .equals(value2);
390: }
391:
392: public boolean remove(Object obj) {
393: if (!(obj instanceof Entry)) {
394: return false;
395: }
396: return removeEntry(((Entry) obj).getKey1(), ((Entry) obj)
397: .getKey2()) != null;
398: }
399:
400: public Iterator<Map.Entry<String, V>> iterator() {
401: return createEntrySetIterator();
402: }
403: }
404:
405: // Iterates Entries inside the Map
406: class EntryIteratorImpl implements Iterator<Map.Entry<String, V>> {
407: private int startModCount;
408: private boolean found;
409: private int curr = -1;
410: private int returned_index = -1;
411: private Entry<E, K, V> curr_entry;
412: private Entry<E, K, V> returned_entry;
413:
414: EntryIteratorImpl() {
415: startModCount = modCount;
416: }
417:
418: public boolean hasNext() {
419: if (found) {
420: return true;
421: }
422: if (curr_entry != null) {
423: curr_entry = curr_entry.next;
424: }
425: if (curr_entry == null) {
426: for (curr++; curr < arr.length && arr[curr] == null; curr++) {
427: }
428:
429: if (curr < arr.length) {
430: curr_entry = arr[curr];
431: }
432: }
433: return found = (curr_entry != null);
434: }
435:
436: public Map.Entry<String, V> next() {
437: if (modCount != startModCount) {
438: throw new ConcurrentModificationException();
439: }
440: if (!hasNext()) {
441: throw new NoSuchElementException();
442: }
443:
444: found = false;
445: returned_index = curr;
446: returned_entry = curr_entry;
447: return (Map.Entry<String, V>) curr_entry;
448: }
449:
450: public void remove() {
451: if (returned_index == -1) {
452: throw new IllegalStateException();
453: }
454:
455: if (modCount != startModCount) {
456: throw new ConcurrentModificationException();
457: }
458:
459: Entry<E, K, V> p = null;
460: Entry<E, K, V> e = arr[returned_index];
461: while (e != returned_entry) {
462: p = e;
463: e = e.next;
464: }
465: if (p != null) {
466: p.next = returned_entry.next;
467: } else {
468: arr[returned_index] = returned_entry.next;
469: }
470: size--;
471: modCount++;
472: startModCount++;
473: returned_index = -1;
474: }
475: }
476:
477: private final Entry<E, K, V> findEntry(Object key1, Object key2) {
478: if (key1 == null && key2 == null) {
479: return arr[arrSize];
480: }
481:
482: int hash = key1.hashCode() + key2.hashCode();
483: int index = (hash & 0x7fffffff) % arrSize;
484: Entry<E, K, V> e = arr[index];
485:
486: while (e != null) {
487: if (hash == e.hash && key1.equals(e.getKey1())
488: && key2.equals(e.getKey2())) {
489: return e;
490: }
491: e = e.next;
492: }
493: return null;
494: }
495:
496: // Removes entry
497: private final Entry<E, K, V> removeEntry(Object key1, Object key2) {
498: if (key1 == null && key2 == null) {
499: int index = arrSize;
500: if (arr[index] != null) {
501: Entry<E, K, V> ret = arr[index];
502: arr[index] = null;
503: size--;
504: modCount++;
505: return ret;
506: }
507: return null;
508: }
509:
510: int hash = key1.hashCode() + key2.hashCode();
511: int index = (hash & 0x7fffffff) % arrSize;
512:
513: Entry<E, K, V> e = arr[index];
514: Entry<E, K, V> prev = e;
515: while (e != null) {
516: if (hash == e.hash && key1.equals(e.getKey1())
517: && key2.equals(e.getKey2())) {
518: if (prev == e) {
519: arr[index] = e.next;
520: } else {
521: prev.next = e.next;
522: }
523: size--;
524: modCount++;
525: return e;
526: }
527:
528: prev = e;
529: e = e.next;
530: }
531: return null;
532: }
533:
534: /**
535: * An instance is returned by the values() call.
536: */
537: class ValuesCollectionImpl extends AbstractCollection<V> {
538: public int size() {
539: return size;
540: }
541:
542: public void clear() {
543: TwoKeyHashMap.this .clear();
544: }
545:
546: public boolean isEmpty() {
547: return size == 0;
548: }
549:
550: public Iterator<V> iterator() {
551: return createValueCollectionIterator();
552: }
553:
554: public boolean contains(Object obj) {
555: return containsValue(obj);
556: }
557: }
558:
559: class ValueIteratorImpl implements Iterator<V> {
560: private EntryIteratorImpl itr;
561:
562: ValueIteratorImpl() {
563: super ();
564: this .itr = new EntryIteratorImpl();
565: }
566:
567: public V next() {
568: return itr.next().getValue();
569: }
570:
571: public void remove() {
572: itr.remove();
573: }
574:
575: public boolean hasNext() {
576: return itr.hasNext();
577: }
578: }
579: }
|