18#ifndef _DECAF_UTIL_HASHMAP_H_
19#define _DECAF_UTIL_HASHMAP_H_
94 template<
typename K,
typename V,
typename HASHCODE = HashCode<K> >
101 HashMapEntry(
const HashMapEntry&);
102 HashMapEntry& operator= (
const HashMapEntry&);
113 this->origKeyHash = hash;
117 this->origKeyHash = HASHCODE()(key);
124 class AbstractMapIterator {
127 mutable int position;
128 int expectedModCount;
129 HashMapEntry* futureEntry;
130 HashMapEntry* currentEntry;
131 HashMapEntry* prevEntry;
137 AbstractMapIterator(
const AbstractMapIterator&);
138 AbstractMapIterator& operator= (
const AbstractMapIterator&);
142 AbstractMapIterator(
HashMap* parent) : position(0),
147 associatedMap(parent) {
150 virtual ~AbstractMapIterator() {}
152 virtual bool checkHasNext()
const {
153 if (futureEntry !=
NULL) {
156 while (position < associatedMap->
elementData.length()) {
157 if (associatedMap->elementData[position] ==
NULL) {
166 void checkConcurrentMod()
const {
167 if (expectedModCount != associatedMap->modCount) {
168 throw ConcurrentModificationException(
169 __FILE__, __LINE__,
"HashMap modified outside this iterator");
174 checkConcurrentMod();
176 if (!checkHasNext()) {
177 throw NoSuchElementException(__FILE__, __LINE__,
"No next element");
180 if (futureEntry ==
NULL) {
181 currentEntry = associatedMap->elementData[position++];
182 futureEntry = currentEntry->next;
185 if (currentEntry !=
NULL){
186 prevEntry = currentEntry;
188 currentEntry = futureEntry;
189 futureEntry = futureEntry->next;
193 virtual void doRemove() {
195 checkConcurrentMod();
197 if (currentEntry ==
NULL) {
198 throw decaf::lang::exceptions::IllegalStateException(
199 __FILE__, __LINE__,
"Remove called before call to next()");
202 if (prevEntry ==
NULL){
203 int index = currentEntry->origKeyHash & (associatedMap->elementData.length() - 1);
204 associatedMap->elementData[index] = associatedMap->elementData[index]->next;
206 prevEntry->next = currentEntry->next;
213 associatedMap->modCount++;
214 associatedMap->elementCount--;
218 class EntryIterator :
public Iterator< MapEntry<K,V> >,
public AbstractMapIterator {
221 EntryIterator(
const EntryIterator&);
222 EntryIterator& operator= (
const EntryIterator&);
226 EntryIterator(
HashMap* parent) : AbstractMapIterator(parent) {
229 virtual ~EntryIterator() {}
231 virtual bool hasNext()
const {
232 return this->checkHasNext();
235 virtual MapEntry<K, V> next() {
237 return *(this->currentEntry);
240 virtual void remove() {
245 class KeyIterator :
public Iterator<K>,
public AbstractMapIterator {
248 KeyIterator(
const KeyIterator&);
249 KeyIterator& operator= (
const KeyIterator&);
253 KeyIterator(
HashMap* parent) : AbstractMapIterator(parent) {
256 virtual ~KeyIterator() {}
258 virtual bool hasNext()
const {
259 return this->checkHasNext();
264 return this->currentEntry->getKey();
267 virtual void remove() {
272 class ValueIterator :
public Iterator<V>,
public AbstractMapIterator {
275 ValueIterator(
const ValueIterator&);
276 ValueIterator& operator= (
const ValueIterator&);
280 ValueIterator(
HashMap* parent) : AbstractMapIterator(parent) {
283 virtual ~ValueIterator() {}
285 virtual bool hasNext()
const {
286 return this->checkHasNext();
291 return this->currentEntry->getValue();
294 virtual void remove() {
301 class ConstAbstractMapIterator {
304 mutable int position;
305 int expectedModCount;
306 const HashMapEntry* futureEntry;
307 const HashMapEntry* currentEntry;
308 const HashMapEntry* prevEntry;
314 ConstAbstractMapIterator(
const ConstAbstractMapIterator&);
315 ConstAbstractMapIterator& operator= (
const ConstAbstractMapIterator&);
319 ConstAbstractMapIterator(
const HashMap* parent) : position(0),
324 associatedMap(parent) {
327 virtual ~ConstAbstractMapIterator() {}
329 virtual bool checkHasNext()
const {
330 if (futureEntry !=
NULL) {
333 while (position < associatedMap->
elementData.length()) {
334 if (associatedMap->elementData[position] ==
NULL) {
343 void checkConcurrentMod()
const {
344 if (expectedModCount != associatedMap->modCount) {
345 throw ConcurrentModificationException(
346 __FILE__, __LINE__,
"HashMap modified outside this iterator");
351 checkConcurrentMod();
353 if (!checkHasNext()) {
354 throw NoSuchElementException(__FILE__, __LINE__,
"No next element");
357 if (futureEntry ==
NULL) {
358 currentEntry = associatedMap->elementData[position++];
359 futureEntry = currentEntry->next;
362 if (currentEntry !=
NULL){
363 prevEntry = currentEntry;
365 currentEntry = futureEntry;
366 futureEntry = futureEntry->next;
371 class ConstEntryIterator :
public Iterator< MapEntry<K,V> >,
public ConstAbstractMapIterator {
374 ConstEntryIterator(
const ConstEntryIterator&);
375 ConstEntryIterator& operator= (
const ConstEntryIterator&);
379 ConstEntryIterator(
const HashMap* parent) : ConstAbstractMapIterator(parent) {
382 virtual ~ConstEntryIterator() {}
384 virtual bool hasNext()
const {
385 return this->checkHasNext();
388 virtual MapEntry<K, V> next() {
390 return *(this->currentEntry);
393 virtual void remove() {
394 throw lang::exceptions::UnsupportedOperationException(
395 __FILE__, __LINE__,
"Cannot write to a const Iterator.");
399 class ConstKeyIterator :
public Iterator<K>,
public ConstAbstractMapIterator {
402 ConstKeyIterator(
const ConstKeyIterator&);
403 ConstKeyIterator& operator= (
const ConstKeyIterator&);
407 ConstKeyIterator(
const HashMap* parent) : ConstAbstractMapIterator(parent) {
410 virtual ~ConstKeyIterator() {}
412 virtual bool hasNext()
const {
413 return this->checkHasNext();
418 return this->currentEntry->getKey();
421 virtual void remove() {
422 throw lang::exceptions::UnsupportedOperationException(
423 __FILE__, __LINE__,
"Cannot write to a const Iterator.");
427 class ConstValueIterator :
public Iterator<V>,
public ConstAbstractMapIterator {
430 ConstValueIterator(
const ConstValueIterator&);
431 ConstValueIterator& operator= (
const ConstValueIterator&);
435 ConstValueIterator(
const HashMap* parent) : ConstAbstractMapIterator(parent) {
438 virtual ~ConstValueIterator() {}
440 virtual bool hasNext()
const {
441 return this->checkHasNext();
446 return this->currentEntry->getValue();
449 virtual void remove() {
450 throw lang::exceptions::UnsupportedOperationException(
451 __FILE__, __LINE__,
"Cannot write to a const Iterator.");
465 HashMapEntrySet(
const HashMapEntrySet&);
466 HashMapEntrySet& operator= (
const HashMapEntrySet&);
476 return associatedMap->elementCount;
480 associatedMap->clear();
486 associatedMap->removeEntry(result);
502 return new EntryIterator(associatedMap);
506 return new ConstEntryIterator(associatedMap);
511 class ConstHashMapEntrySet :
public AbstractSet< MapEntry<K, V> > {
518 ConstHashMapEntrySet(
const ConstHashMapEntrySet&);
519 ConstHashMapEntrySet& operator= (
const ConstHashMapEntrySet&);
529 return associatedMap->elementCount;
534 __FILE__, __LINE__,
"Can't clear a const collection");
539 __FILE__, __LINE__,
"Can't remove from const collection");
552 __FILE__, __LINE__,
"Can't return a non-const iterator for a const collection");
556 return new ConstEntryIterator(associatedMap);
569 HashMapKeySet(
const HashMapKeySet&);
570 HashMapKeySet& operator= (
const HashMapKeySet&);
584 return this->associatedMap->
size();
588 this->associatedMap->
clear();
601 return new KeyIterator(this->associatedMap);
605 return new ConstKeyIterator(this->associatedMap);
616 ConstHashMapKeySet(
const ConstHashMapKeySet&);
617 ConstHashMapKeySet& operator= (
const ConstHashMapKeySet&);
631 return this->associatedMap->
size();
636 __FILE__, __LINE__,
"Can't modify a const collection");
639 virtual bool remove(
const K& key DECAF_UNUSED) {
641 __FILE__, __LINE__,
"Can't modify a const collection");
646 __FILE__, __LINE__,
"Can't return a non-const iterator for a const collection");
650 return new ConstKeyIterator(this->associatedMap);
663 HashMapValueCollection(
const HashMapValueCollection&);
664 HashMapValueCollection& operator= (
const HashMapValueCollection&);
678 return this->associatedMap->
size();
682 this->associatedMap->
clear();
686 return new ValueIterator(this->associatedMap);
690 return new ConstValueIterator(this->associatedMap);
701 ConstHashMapValueCollection(
const ConstHashMapValueCollection&);
702 ConstHashMapValueCollection& operator= (
const ConstHashMapValueCollection&);
716 return this->associatedMap->
size();
721 __FILE__, __LINE__,
"Can't modify a const collection");
726 __FILE__, __LINE__,
"Can't return a non-const iterator for a const collection");
730 return new ConstValueIterator(this->associatedMap);
779 void computeThreshold() {
783 static int calculateCapacity(
int x) {
809 int capacity = calculateCapacity(12);
828 capacity = calculateCapacity(capacity);
834 __FILE__, __LINE__,
"Invalid capacity configuration");
853 capacity = calculateCapacity(capacity);
860 __FILE__, __LINE__,
"Invalid configuration");
875 int capacity = calculateCapacity(map.
size());
893 int capacity = calculateCapacity(map.
size());
903 while (entry !=
NULL) {
924 return this->
equals(other);
928 return !this->
equals(other);
939 while (entry !=
NULL) {
959 return entry !=
NULL;
965 while (entry !=
NULL) {
975 virtual V&
get(
const K& key) {
982 __FILE__, __LINE__,
"The specified key is not present in the Map");
985 virtual const V&
get(
const K& key)
const {
992 __FILE__, __LINE__,
"The specified key is not present in the Map");
995 virtual bool put(
const K& key,
const V& value) {
996 return this->
putImpl(key, value);
999 virtual bool put(
const K& key,
const V& value, V& oldValue) {
1000 return this->
putImpl(key, value, oldValue);
1011 if (entry !=
NULL) {
1018 __FILE__, __LINE__,
"Specified key not present in the Map.");
1022 if (this->cachedEntrySet ==
NULL) {
1025 return *(this->cachedEntrySet);
1029 if (this->cachedConstEntrySet ==
NULL) {
1032 return *(this->cachedConstEntrySet);
1036 if (this->cachedKeySet ==
NULL) {
1039 return *(this->cachedKeySet);
1043 if (this->cachedConstKeySet ==
NULL) {
1046 return *(this->cachedConstKeySet);
1050 if (this->cachedValueCollection ==
NULL) {
1053 return *(this->cachedValueCollection);
1057 if (this->cachedConstValueCollection ==
NULL) {
1060 return *(this->cachedConstValueCollection);
1065 if (
this == &source) {
1075 while (iter->hasNext() ) {
1084 if (source.
get(key) != mine) {
1097 int capacity = calculateCapacity(source.
size());
1122 virtual bool putImpl(
const K& key,
const V& value) {
1124 return putImpl(key, value, oldValue);
1127 virtual bool putImpl(
const K& key,
const V& value, V& oldValue) {
1128 bool replaced =
true;
1136 if (entry ==
NULL) {
1175 while (iterator->hasNext()) {
1184 entry = entry->
next;
1190 int length = calculateCapacity((capacity == 0 ? 1 : capacity << 1));
1196 while (entry !=
NULL) {
1199 entry->
next = newData[index];
1200 newData[index] = entry;
1216 if (current == entry) {
1219 while (current->
next != entry) {
1220 current = current->
next;
1241 current = current->
next;
1244 if (current ==
NULL) {
Decaf's implementation of a Smart Pointer that is a template on a Type and is Thread Safe if the defa...
Definition ArrayPointer.h:51
virtual decaf::util::Iterator< E > * iterator()=0
Decaf's implementation of a Smart Pointer that is a template on a Type and is Thread Safe if the defa...
Definition Pointer.h:53
void reset(T *value=NULL)
Resets the Pointer to hold the new value.
Definition Pointer.h:161
Definition ClassCastException.h:31
Definition IllegalArgumentException.h:31
Definition NullPointerException.h:32
Definition UnsupportedOperationException.h:32
AbstractCollection()
Definition AbstractCollection.h:65
AbstractMap()
Definition AbstractMap.h:66
AbstractSet()
Definition AbstractSet.h:50
The root interface in the collection hierarchy.
Definition Collection.h:69
virtual ~ConstHashMapEntrySet()
Definition HashMap.h:526
ConstHashMapEntrySet(const HashMap *parent)
Definition HashMap.h:523
virtual void clear()
Removes all of the elements from this collection (optional operation).
Definition HashMap.h:532
virtual bool remove(const MapEntry< K, V > &entry DECAF_UNUSED)
Definition HashMap.h:537
virtual bool contains(const MapEntry< K, V > &entry) const
Returns true if this collection contains the specified element.
Definition HashMap.h:542
virtual Iterator< MapEntry< K, V > > * iterator()
Definition HashMap.h:550
virtual int size() const
Returns the number of elements in this collection.
Definition HashMap.h:528
virtual Iterator< MapEntry< K, V > > * iterator() const
Definition HashMap.h:555
virtual Iterator< K > * iterator()
Definition HashMap.h:644
ConstHashMapKeySet(const HashMap *parent)
Definition HashMap.h:621
virtual int size() const
Returns the number of elements in this collection.
Definition HashMap.h:630
virtual bool contains(const K &key) const
Returns true if this collection contains the specified element.
Definition HashMap.h:626
virtual void clear()
Removes all of the elements from this collection (optional operation).
Definition HashMap.h:634
virtual bool remove(const K &key DECAF_UNUSED)
Definition HashMap.h:639
virtual ~ConstHashMapKeySet()
Definition HashMap.h:624
virtual Iterator< K > * iterator() const
Definition HashMap.h:649
virtual ~ConstHashMapValueCollection()
Definition HashMap.h:709
virtual bool contains(const V &value) const
Returns true if this collection contains the specified element.More formally, returns true if and onl...
Definition HashMap.h:711
virtual Iterator< V > * iterator() const
Definition HashMap.h:729
virtual void clear()
Removes all of the elements from this collection (optional operation).
Definition HashMap.h:719
ConstHashMapValueCollection(const HashMap *parent)
Definition HashMap.h:706
virtual Iterator< V > * iterator()
Definition HashMap.h:724
virtual int size() const
Returns the number of elements in this collection.
Definition HashMap.h:715
HashMapEntry(const K &key, const V &value)
Definition HashMap.h:116
int origKeyHash
Definition HashMap.h:106
HashMapEntry(const K &key, const V &value, int hash)
Definition HashMap.h:110
HashMapEntry * next
Definition HashMap.h:108
virtual bool contains(const MapEntry< K, V > &entry) const
Returns true if this collection contains the specified element.
Definition HashMap.h:493
virtual void clear()
Removes all of the elements from this collection (optional operation).
Definition HashMap.h:479
virtual int size() const
Returns the number of elements in this collection.
Definition HashMap.h:475
virtual Iterator< MapEntry< K, V > > * iterator()
Definition HashMap.h:501
virtual ~HashMapEntrySet()
Definition HashMap.h:473
virtual bool remove(const MapEntry< K, V > &entry)
Removes a single instance of the specified element from the collection.
Definition HashMap.h:483
HashMapEntrySet(HashMap *parent)
Definition HashMap.h:470
virtual Iterator< MapEntry< K, V > > * iterator() const
Definition HashMap.h:505
virtual int size() const
Returns the number of elements in this collection.
Definition HashMap.h:583
virtual void clear()
Removes all of the elements from this collection (optional operation).
Definition HashMap.h:587
virtual bool contains(const K &key) const
Returns true if this collection contains the specified element.
Definition HashMap.h:579
virtual ~HashMapKeySet()
Definition HashMap.h:577
HashMapKeySet(HashMap *parent)
Definition HashMap.h:574
virtual Iterator< K > * iterator() const
Definition HashMap.h:604
virtual Iterator< K > * iterator()
Definition HashMap.h:600
virtual bool remove(const K &key)
Removes a single instance of the specified element from the collection.
Definition HashMap.h:591
virtual int size() const
Returns the number of elements in this collection.
Definition HashMap.h:677
HashMapValueCollection(HashMap *parent)
Definition HashMap.h:668
virtual Iterator< V > * iterator() const
Definition HashMap.h:689
virtual ~HashMapValueCollection()
Definition HashMap.h:671
virtual void clear()
Removes all of the elements from this collection (optional operation).
Definition HashMap.h:681
virtual bool contains(const V &value) const
Returns true if this collection contains the specified element.More formally, returns true if and onl...
Definition HashMap.h:673
virtual Iterator< V > * iterator()
Definition HashMap.h:685
Hash table based implementation of the Map interface.
Definition HashMap.h:95
virtual ~HashMap()
Definition HashMap.h:900
HashMap(const HashMap< K, V > &map)
Creates a new HashMap with default configuration settings and fills it with the contents of the given...
Definition HashMap.h:871
decaf::lang::ArrayPointer< HashMapEntry * > elementData
Definition HashMap.h:749
virtual bool put(const K &key, const V &value)
Associates the specified value with the specified key in this map (optional operation).
Definition HashMap.h:995
decaf::lang::Pointer< HashMapKeySet > cachedKeySet
Definition HashMap.h:769
HashMapEntry * removeEntry(const K &key)
Definition HashMap.h:1230
virtual const V & get(const K &key) const
Gets the value mapped to the specified key in the Map.
Definition HashMap.h:985
bool operator==(const Map< K, V > &other) const
Definition HashMap.h:923
void rehash(int capacity)
Definition HashMap.h:1189
int threshold
Definition HashMap.h:765
virtual bool put(const K &key, const V &value, V &oldValue)
Associates the specified value with the specified key in this map (optional operation).
Definition HashMap.h:999
virtual bool putImpl(const K &key, const V &value, V &oldValue)
Definition HashMap.h:1127
HashMap< K, V > & operator=(const Map< K, V > &other)
Definition HashMap.h:913
virtual const Set< K > & keySet() const
Definition HashMap.h:1042
virtual bool equals(const Map< K, V > &source) const
Compares the specified object with this map for equality.
Definition HashMap.h:1063
virtual const Set< MapEntry< K, V > > & entrySet() const
Definition HashMap.h:1028
decaf::lang::Pointer< HashMapEntrySet > cachedEntrySet
Definition HashMap.h:768
void putAllImpl(const Map< K, V > &map)
Definition HashMap.h:1168
HashMap(int capacity, float loadFactor)
Constructs a new HashMap instance with the specified capacity.
Definition HashMap.h:848
virtual void clear()
Removes all of the mappings from this map (optional operation).
Definition HashMap.h:933
virtual bool isEmpty() const
Definition HashMap.h:949
virtual int size() const
Definition HashMap.h:953
void rehash()
Definition HashMap.h:1208
virtual Collection< V > & values()
Returns a Collection view of the values contained in this map.
Definition HashMap.h:1049
decaf::lang::Pointer< ConstHashMapKeySet > cachedConstKeySet
Definition HashMap.h:774
HASHCODE hashFunc
The Hash Code generator for this map's keys.
Definition HashMap.h:739
virtual const Collection< V > & values() const
Definition HashMap.h:1056
HashMapEntry * findKeyEntry(const K &key, int index, int keyHash) const
Definition HashMap.h:1181
virtual HashMapEntry * getEntry(const K &key) const
Definition HashMap.h:1112
virtual V & get(const K &key)
Gets the value mapped to the specified key in the Map.
Definition HashMap.h:975
virtual bool containsValue(const V &value) const
Returns true if this map maps one or more keys to the specified value.
Definition HashMap.h:962
decaf::lang::Pointer< HashMapValueCollection > cachedValueCollection
Definition HashMap.h:770
virtual Set< MapEntry< K, V > > & entrySet()
Returns a Set view of the mappings contained in this map.
Definition HashMap.h:1021
float loadFactor
Definition HashMap.h:760
bool operator!=(const Map< K, V > &other) const
Definition HashMap.h:927
virtual V remove(const K &key)
Removes the value (key/value pair) for the specified key from the map, returns a copy of the value th...
Definition HashMap.h:1009
HashMap(const Map< K, V > &map)
Creates a new HashMap with default configuration settings and fills it with the contents of the given...
Definition HashMap.h:889
virtual HashMapEntry * createHashedEntry(const K &key, int index, int hash)
Definition HashMap.h:1159
HashMap()
Creates a new empty HashMap with default configuration settings.
Definition HashMap.h:805
virtual std::string toString() const
Definition HashMap.h:1106
HashMap(int capacity)
Constructs a new HashMap instance with the specified capacity.
Definition HashMap.h:823
int elementCount
Definition HashMap.h:744
virtual Set< K > & keySet()
Returns a Set view of the keys contained in this map.
Definition HashMap.h:1035
void removeEntry(HashMapEntry *entry)
Definition HashMap.h:1213
decaf::lang::Pointer< ConstHashMapValueCollection > cachedConstValueCollection
Definition HashMap.h:775
int modCount
Definition HashMap.h:755
decaf::lang::Pointer< ConstHashMapEntrySet > cachedConstEntrySet
Definition HashMap.h:773
virtual bool containsKey(const K &key) const
Returns true if this map contains a mapping for the specified key.
Definition HashMap.h:957
virtual void putAll(const Map< K, V > &map)
Copies all of the mappings from the specified map to this map (optional operation).
Definition HashMap.h:1003
virtual void copy(const Map< K, V > &source)
Copies the content of the source map into this map.
Definition HashMap.h:1096
virtual bool putImpl(const K &key, const V &value)
Definition HashMap.h:1122
virtual HashMapEntry * createEntry(const K &key, int index, const V &value)
Definition HashMap.h:1152
Defines an object that can be used to iterate over the elements of a collection.
Definition Iterator.h:34
virtual void setKey(K key)
Definition MapEntry.h:53
virtual void setValue(const V &value)
Definition MapEntry.h:65
MapEntry()
Definition MapEntry.h:35
virtual K & getKey()
Definition MapEntry.h:57
virtual V & getValue()
Definition MapEntry.h:69
An object that maps keys to values.
Definition Map.h:88
virtual V & get(const K &key)=0
Gets the value mapped to the specified key in the Map.
virtual bool isEmpty() const =0
virtual bool containsKey(const K &key) const =0
Returns true if this map contains a mapping for the specified key.
virtual int size() const =0
virtual Set< MapEntry< K, V > > & entrySet()=0
Returns a Set view of the mappings contained in this map.
Definition NoSuchElementException.h:31
A collection that contains no duplicate elements.
Definition Set.h:45
#define NULL
Definition Config.h:33
Definition AbstractCollection.h:33
Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements.
Definition AprPool.h:25