117 LinkedHashMapEntry(
const LinkedHashMapEntry&);
118 LinkedHashMapEntry& operator= (
const LinkedHashMapEntry&);
122 LinkedHashMapEntry* chainForward;
123 LinkedHashMapEntry* chainBackward;
127 LinkedHashMapEntry(
const K& key,
const V& value,
int hash) :
131 LinkedHashMapEntry(
const K& key,
const V& value) :
139 mutable LinkedHashMapEntry* head;
140 mutable LinkedHashMapEntry* tail;
144 class AbstractMapIterator {
147 int expectedModCount;
148 LinkedHashMapEntry* futureEntry;
149 LinkedHashMapEntry* currentEntry;
154 AbstractMapIterator(
const AbstractMapIterator&);
155 AbstractMapIterator& operator= (
const AbstractMapIterator&);
160 futureEntry(parent->head),
162 associatedMap(parent) {
165 virtual ~AbstractMapIterator() {}
167 void checkConcurrentMod()
const {
168 if (expectedModCount != associatedMap->
modCount) {
170 __FILE__, __LINE__,
"LinkedHashMap modified outside this iterator");
174 virtual bool checkHasNext()
const {
175 return (futureEntry !=
NULL);
179 checkConcurrentMod();
180 if (!checkHasNext()) {
182 __FILE__, __LINE__,
"No next element");
184 currentEntry = futureEntry;
185 futureEntry = futureEntry->chainForward;
188 virtual void doRemove() {
189 checkConcurrentMod();
190 if (currentEntry ==
NULL) {
192 __FILE__, __LINE__,
"Remove called before call to next()");
195 LinkedHashMapEntry* entry = currentEntry;
196 LinkedHashMapEntry* prev = entry->chainBackward;
197 LinkedHashMapEntry* next = entry->chainForward;
205 prev->chainForward = next;
207 next->chainBackward = prev;
214 next->chainBackward =
NULL;
224 class EntryIterator :
public Iterator< MapEntry<K,V> >,
public AbstractMapIterator {
227 EntryIterator(
const EntryIterator&);
228 EntryIterator& operator= (
const EntryIterator&);
232 EntryIterator(
LinkedHashMap* parent) : AbstractMapIterator(parent) {
235 virtual ~EntryIterator() {}
237 virtual bool hasNext()
const {
238 return this->checkHasNext();
243 return *(this->currentEntry);
251 class KeyIterator :
public Iterator<K>,
public AbstractMapIterator {
254 KeyIterator(
const KeyIterator&);
255 KeyIterator& operator= (
const KeyIterator&);
259 KeyIterator(
LinkedHashMap* parent) : AbstractMapIterator(parent) {
262 virtual ~KeyIterator() {}
264 virtual bool hasNext()
const {
265 return this->checkHasNext();
270 return this->currentEntry->
getKey();
278 class ValueIterator :
public Iterator<V>,
public AbstractMapIterator {
281 ValueIterator(
const ValueIterator&);
282 ValueIterator& operator= (
const ValueIterator&);
286 ValueIterator(
LinkedHashMap* parent) : AbstractMapIterator(parent) {
289 virtual ~ValueIterator() {}
291 virtual bool hasNext()
const {
292 return this->checkHasNext();
297 return this->currentEntry->
getValue();
307 class ConstAbstractMapIterator {
310 int expectedModCount;
311 const LinkedHashMapEntry* futureEntry;
312 const LinkedHashMapEntry* currentEntry;
317 ConstAbstractMapIterator(
const ConstAbstractMapIterator&);
318 ConstAbstractMapIterator& operator= (
const ConstAbstractMapIterator&);
323 futureEntry(parent->head),
325 associatedMap(parent) {
328 virtual ~ConstAbstractMapIterator() {}
330 virtual bool checkHasNext()
const {
331 return (futureEntry !=
NULL);
334 void checkConcurrentMod()
const {
335 if (expectedModCount != associatedMap->
modCount) {
337 __FILE__, __LINE__,
"LinkedHashMap modified outside this iterator");
342 checkConcurrentMod();
343 if (!checkHasNext()) {
345 __FILE__, __LINE__,
"No next element");
347 currentEntry = futureEntry;
348 futureEntry = futureEntry->chainForward;
352 class ConstEntryIterator :
public Iterator< MapEntry<K,V> >,
public ConstAbstractMapIterator {
355 ConstEntryIterator(
const ConstEntryIterator&);
356 ConstEntryIterator& operator= (
const ConstEntryIterator&);
360 ConstEntryIterator(
const LinkedHashMap* parent) : ConstAbstractMapIterator(parent) {
363 virtual ~ConstEntryIterator() {}
365 virtual bool hasNext()
const {
366 return this->checkHasNext();
371 return *(this->currentEntry);
376 __FILE__, __LINE__,
"Cannot write to a const Iterator." );
380 class ConstKeyIterator :
public Iterator<K>,
public ConstAbstractMapIterator {
383 ConstKeyIterator(
const ConstKeyIterator&);
384 ConstKeyIterator& operator= (
const ConstKeyIterator&);
388 ConstKeyIterator(
const LinkedHashMap* parent) : ConstAbstractMapIterator(parent) {
391 virtual ~ConstKeyIterator() {}
393 virtual bool hasNext()
const {
394 return this->checkHasNext();
399 return this->currentEntry->
getKey();
404 __FILE__, __LINE__,
"Cannot write to a const Iterator." );
408 class ConstValueIterator :
public Iterator<V>,
public ConstAbstractMapIterator {
411 ConstValueIterator(
const ConstValueIterator&);
412 ConstValueIterator& operator= (
const ConstValueIterator&);
416 ConstValueIterator(
const LinkedHashMap* parent) : ConstAbstractMapIterator(parent) {
419 virtual ~ConstValueIterator() {}
421 virtual bool hasNext()
const {
422 return this->checkHasNext();
427 return this->currentEntry->
getValue();
432 __FILE__, __LINE__,
"Cannot write to a const Iterator." );
446 LinkedHashMapEntrySet(
const LinkedHashMapEntrySet&);
447 LinkedHashMapEntrySet& operator= (
const LinkedHashMapEntrySet&);
455 virtual ~LinkedHashMapEntrySet() {}
458 return new EntryIterator(associatedMap);
462 return new ConstEntryIterator(associatedMap);
474 ConstLinkedHashMapEntrySet(
const ConstLinkedHashMapEntrySet&);
475 ConstLinkedHashMapEntrySet& operator= (
const ConstLinkedHashMapEntrySet&);
483 virtual ~ConstLinkedHashMapEntrySet() {}
487 __FILE__, __LINE__,
"Can't return a non-const iterator for a const collection");
491 return new ConstEntryIterator(associatedMap);
504 LinkedHashMapKeySet(
const LinkedHashMapKeySet&);
505 LinkedHashMapKeySet& operator= (
const LinkedHashMapKeySet&);
513 virtual ~LinkedHashMapKeySet() {}
516 return new KeyIterator(this->associatedMap);
520 return new ConstKeyIterator(this->associatedMap);
531 ConstLinkedHashMapKeySet(
const ConstLinkedHashMapKeySet&);
532 ConstLinkedHashMapKeySet& operator= (
const ConstLinkedHashMapKeySet&);
540 virtual ~ConstLinkedHashMapKeySet() {}
542 using HashMap<K, V, HASHCODE>::ConstHashMapKeySet::iterator;
545 return new ConstKeyIterator(this->associatedMap);
558 LinkedHashMapValueCollection(
const LinkedHashMapValueCollection&);
559 LinkedHashMapValueCollection& operator= (
const LinkedHashMapValueCollection&);
567 virtual ~LinkedHashMapValueCollection() {}
570 return new ValueIterator(this->associatedMap);
574 return new ConstValueIterator(this->associatedMap);
585 ConstLinkedHashMapValueCollection(
const ConstLinkedHashMapValueCollection&);
586 ConstLinkedHashMapValueCollection& operator= (
const ConstLinkedHashMapValueCollection&);
590 ConstLinkedHashMapValueCollection(
const LinkedHashMap* parent) :
594 virtual ~ConstLinkedHashMapValueCollection() {}
597 return new ConstValueIterator(this->associatedMap);
600 using HashMap<K, V, HASHCODE>::ConstHashMapValueCollection::iterator;
636 HashMap<K, V, HASHCODE>(capacity, load), accessOrder(false), head(), tail() {
657 HashMap<K, V, HASHCODE>(capacity, load), accessOrder(order), head(), tail() {
703 LinkedHashMapEntry* entry = head;
704 while (entry !=
NULL) {
708 entry = entry->chainForward;
719 virtual bool put(
const K& key,
const V& value) {
720 bool result = this->
putImpl(key, value);
730 virtual bool put(
const K& key,
const V& value, V& oldValue) {
731 bool result = this->
putImpl(key, value, oldValue);
743 LinkedHashMapEntry* toRemove = (LinkedHashMapEntry*) this->
removeEntry(key);
744 if (toRemove !=
NULL) {
745 LinkedHashMapEntry* prev = toRemove->chainBackward;
746 LinkedHashMapEntry* next = toRemove->chainForward;
748 prev->chainForward = next;
753 next->chainBackward = prev;
764 __FILE__, __LINE__,
"Specified key not present in the Map.");
783 this->
cachedKeySet.reset(
new LinkedHashMapKeySet(
this));
810 return "LinkedHashMap";
815 virtual LinkedHashMapEntry*
getEntry(
const K& key)
const {
816 LinkedHashMapEntry* result =
NULL;
819 int index = hash & (this->
elementData.length() - 1);
820 result = (LinkedHashMapEntry*) this->
findKeyEntry(key, index, hash);
822 if (result !=
NULL && accessOrder && tail != result) {
823 LinkedHashMapEntry* prev = result->chainBackward;
824 LinkedHashMapEntry* next = result->chainForward;
825 next->chainBackward = prev;
827 prev->chainForward = next;
831 result->chainForward =
NULL;
832 result->chainBackward = tail;
833 tail->chainForward = result;
841 LinkedHashMapEntry* entry =
new LinkedHashMapEntry(key, value);
849 LinkedHashMapEntry* entry =
new LinkedHashMapEntry(key, V(), hash);
869 LinkedHashMapEntry* prev = entry->chainBackward;
870 LinkedHashMapEntry* next = entry->chainForward;
876 next->chainBackward =
NULL;
877 entry->chainBackward = tail;
878 entry->chainForward =
NULL;
879 tail->chainForward = entry;
884 entry->chainBackward = tail;
885 entry->chainForward =
NULL;
886 tail->chainForward = entry;
899 prev->chainForward = next;
900 next->chainBackward = prev;
901 entry->chainForward =
NULL;
902 entry->chainBackward = tail;
903 tail->chainForward = entry;
908 virtual bool putImpl(
const K& key,
const V& value) {
910 return putImpl(key, value, oldValue);
913 virtual bool putImpl(
const K& key,
const V& value, V& oldValue) {
915 LinkedHashMapEntry* entry;
920 bool replaced =
true;
922 int index = hash & (this->
elementData.length() - 1);
924 entry = (LinkedHashMapEntry*) this->
findKeyEntry(key, index, hash);