activemq-cpp-3.9.5
LinkedList.h
Go to the documentation of this file.
1/*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18#ifndef _DECAF_UTIL_LINKEDLIST_H_
19#define _DECAF_UTIL_LINKEDLIST_H_
20
21#include <list>
22#include <memory>
26#include <decaf/lang/System.h>
27#include <decaf/lang/Integer.h>
28#include <decaf/util/Config.h>
29#include <decaf/util/Deque.h>
31#include <decaf/util/Iterator.h>
34
35namespace decaf {
36namespace util {
37
38 using decaf::lang::System;
39
54 template< typename E >
55 class LinkedList : public AbstractSequentialList<E>, public Deque<E> {
56 private:
57
58 template< typename U >
59 class ListNode {
60 public:
61
62 U value;
63 ListNode<U>* prev;
64 ListNode<U>* next;
65
66 private:
67
68 ListNode(const ListNode&);
69 ListNode& operator=(const ListNode&);
70
71 public:
72
73 ListNode() : value(), prev(NULL), next(NULL) {}
74
75 ListNode(const U& value) : value(value), prev(NULL), next(NULL) {}
76
77 ListNode(ListNode<U>* prev, ListNode<U>* next, const U& value) :
78 value(value), prev(prev), next(next) {
79 }
80
81 };
82
83 private:
84
85 int listSize;
86 ListNode<E> head;
87 ListNode<E> tail;
88
89 public:
90
91 LinkedList() : AbstractSequentialList<E>(), listSize(0), head(), tail() {
92
93 this->head.next = &this->tail;
94 this->tail.prev = &this->head;
95 }
96
97 LinkedList(const LinkedList<E>& list) : AbstractSequentialList<E>(), listSize(0), head(), tail() {
98
99 this->head.next = &this->tail;
100 this->tail.prev = &this->head;
101
102 this->addAllAtLocation(0, list);
103 }
104
105 LinkedList(const Collection<E>& collection) : AbstractSequentialList<E>(), listSize(0), head(), tail() {
106
107 this->head.next = &this->tail;
108 this->tail.prev = &this->head;
109
110 this->addAllAtLocation(0, collection);
111 }
112
113 virtual ~LinkedList() {
114 try{
115 this->purgeList();
116 } catch(...) {}
117 }
118
119 public:
120
122 this->clear();
123 this->addAllAtLocation(0, list);
124 return *this;
125 }
126
128 this->clear();
129 this->addAllAtLocation(0, collection);
130 return *this;
131 }
132
133 bool operator==(const LinkedList<E>& other) const {
134 return this->equals(other);
135 }
136
137 bool operator!=(const LinkedList<E>& other) const {
138 return !this->equals(other);
139 }
140
141 public:
142
143 virtual E get(int index) const {
144
145 if (index < 0 || index >= this->listSize) {
147 __FILE__, __LINE__, "Index given is outside bounds of this list {%d}", index );
148 }
149
150 const ListNode<E>* location = NULL;
151
152 if (index < this->listSize / 2) {
153 location = &this->head;
154 for (int i = 0; i <= index; ++i) {
155 location = location->next;
156 }
157 } else {
158 location = &this->tail;
159 for (int i = this->listSize; i > index; --i) {
160 location = location->prev;
161 }
162 }
163
164 return location->value;
165 }
166
167 virtual E set(int index, const E& element) {
168
169 if (index < 0 || index >= this->listSize) {
171 __FILE__, __LINE__, "Index given is outside bounds of this list {%d}", index );
172 }
173
174 ListNode<E>* location = NULL;
175
176 if (index < this->listSize / 2) {
177 location = &this->head;
178 for (int i = 0; i <= index; ++i) {
179 location = location->next;
180 }
181 } else {
182 location = &this->tail;
183 for (int i = this->listSize; i > index; --i) {
184 location = location->prev;
185 }
186 }
187
188 E oldValue = location->value;
189 location->value = element;
190
191 return oldValue;
192 }
193
194 virtual bool add(const E& value) {
195 this->addToEnd(value);
196 return true;
197 }
198
199 virtual void add(int index, const E& value) {
200
201 if (index < 0 || index > this->listSize) {
203 __FILE__, __LINE__, "Index given is outside bounds of this list {%d}", index );
204 }
205
206 this->addAtLocation(index, value);
207 }
208
209 virtual bool addAll(const Collection<E>& collection) {
210 return this->addAllAtLocation(this->listSize, collection);
211 }
212
213 virtual bool addAll(int index, const Collection<E>& collection) {
214 return this->addAllAtLocation(index, collection);
215 }
216
217 virtual void copy(const Collection<E>& collection) {
218 this->clear();
219 this->addAllAtLocation(0, collection);
220 }
221
222 virtual bool remove(const E& value) {
223 return this->removeFirstOccurrence(value);
224 }
225
226 virtual bool isEmpty() const {
227 return this->listSize == 0;
228 }
229
230 virtual int size() const {
231 return this->listSize;
232 }
233
234 virtual void clear() {
235 this->purgeList();
236 this->head.next = &this->tail;
237 this->tail.prev = &this->head;
238 this->listSize = 0;
240 }
241
242 virtual bool contains(const E& value) const {
243 return this->indexOf(value) != -1;
244 }
245
246 virtual int indexOf(const E& value) const {
247
248 if (this->listSize == 0) {
249 return -1;
250 }
251
252 const ListNode<E>* location = this->head.next;
253
254 for (int i = 0; location != &this->tail; ++i, location = location->next) {
255 if (location->value == value) {
256 return i;
257 }
258 }
259
260 return -1;
261 }
262
263 virtual int lastIndexOf(const E& value) const {
264
265 if (this->listSize == 0) {
266 return -1;
267 }
268
269 const ListNode<E>* location = this->tail.prev;
270
271 for (int i = this->listSize - 1; location != &this->head; --i, location = location->prev) {
272 if (location->value == value) {
273 return i;
274 }
275 }
276
277 return -1;
278 }
279
280 virtual std::vector<E> toArray() const {
281
282 std::vector<E> result;
283 result.reserve(this->listSize);
284
285 const ListNode<E>* current = this->head.next;
286
287 while (current != &this->tail) {
288 result.push_back(current->value);
289 current = current->next;
290 }
291
292 return result;
293 }
294
295 public: // Deque interface implementation.
296
297 virtual bool offer(const E& value) {
298 this->addLast(value);
299 return true;
300 }
301
302 virtual bool poll(E& result) {
303
304 if (this->listSize == 0) {
305 return false;
306 }
307
308 result = this->head.next->value;
309 this->removeAtFront();
310 return true;
311 }
312
313 virtual E remove() {
314 return this->removeAtFront();
315 }
316
317 virtual bool peek(E& result) const {
318
319 if (this->listSize == 0) {
320 return false;
321 }
322
323 result = this->head.next->value;
324 return true;
325 }
326
327 virtual E element() const {
328 if (this->listSize == 0) {
329 throw decaf::util::NoSuchElementException(__FILE__, __LINE__, "The list is Empty");
330 }
331
332 return this->head.next->value;
333 }
334
335 virtual void addFirst(const E& value) {
336 this->addToFront(value);
337 }
338
339 virtual void addLast(const E& value) {
340 this->addToEnd(value);
341 }
342
343 virtual E& getFirst() {
344 if (this->listSize == 0) {
345 throw decaf::util::NoSuchElementException(__FILE__, __LINE__, "The list is Empty");
346 }
347
348 return this->head.next->value;
349 }
350
351 virtual const E& getFirst() const {
352 if (this->listSize == 0) {
353 throw decaf::util::NoSuchElementException(__FILE__, __LINE__, "The list is Empty");
354 }
355
356 return this->head.next->value;
357 }
358
359 virtual E& getLast() {
360 if (this->listSize == 0) {
361 throw decaf::util::NoSuchElementException(__FILE__, __LINE__, "The list is Empty");
362 }
363
364 return this->tail.prev->value;
365 }
366
367 virtual const E& getLast() const {
368 if (this->listSize == 0) {
369 throw decaf::util::NoSuchElementException(__FILE__, __LINE__, "The list is Empty");
370 }
371
372 return this->tail.prev->value;
373 }
374
375 virtual bool offerFirst(const E& element) {
376 this->addToFront(element);
377 return true;
378 }
379
380 virtual bool offerLast(const E& element) {
381 this->addToEnd(element);
382 return true;
383 }
384
385 virtual E removeFirst() {
386 return this->removeAtFront();
387 }
388
389 virtual E removeLast() {
390 return this->removeAtEnd();
391 }
392
393 virtual bool pollFirst(E& result) {
394 if (this->listSize == 0) {
395 return false;
396 }
397
398 result = this->head.next->value;
399 this->removeAtFront();
400 return true;
401 }
402
403 virtual bool pollLast(E& result) {
404 if (this->listSize == 0) {
405 return false;
406 }
407
408 result = this->tail.prev->value;
409 this->removeAtEnd();
410 return true;
411 }
412
413 virtual bool peekFirst(E& result) const {
414 if (this->listSize == 0) {
415 return false;
416 }
417
418 result = this->head.next->value;
419 return true;
420 }
421
422 virtual bool peekLast(E& result) const {
423 if (this->listSize == 0) {
424 return false;
425 }
426
427 result = this->tail.prev->value;
428 return true;
429 }
430
431 virtual E pop() {
432 return this->removeAtFront();
433 }
434
435 virtual void push(const E& element) {
436 this->addToFront(element);
437 }
438
439 virtual bool removeFirstOccurrence(const E& value) {
440 std::auto_ptr<Iterator<E> > iter(this->iterator());
441 while (iter->hasNext()) {
442 if (iter->next() == value) {
443 iter->remove();
444 return true;
445 }
446 }
447
448 return false;
449 }
450
451 virtual bool removeLastOccurrence(const E& value) {
452 std::auto_ptr<Iterator<E> > iter(this->descendingIterator());
453 while (iter->hasNext()) {
454 if (iter->next() == value) {
455 iter->remove();
456 return true;
457 }
458 }
459
460 return false;
461 }
462
463 private:
464
465 class LinkedListIterator : public ListIterator<E> {
466 private:
467
468 mutable LinkedList<E>* list;
469 ListNode<E>* current;
470 ListNode<E>* lastReturned;
471 int index;
472 int expectedModCount;
473
474 private:
475
476 LinkedListIterator(const LinkedListIterator&);
477 LinkedListIterator operator=(const LinkedListIterator&);
478
479 public:
480
481 LinkedListIterator(LinkedList<E>* list, int index) :
482 ListIterator<E>(), list(list), current(NULL), lastReturned(NULL), index(-1), expectedModCount(0) {
483
484 if (list == NULL) {
486 __FILE__, __LINE__, "Parent LinkedList pointer was Null." );
487 }
488
489 if (index < 0 || index > list->listSize) {
490 throw decaf::lang::exceptions::IndexOutOfBoundsException(
491 __FILE__, __LINE__, "Given index {%d} is out of range.", index );
492 }
493
494 this->expectedModCount = list->modCount;
495
496 // index starts at -1 to indicate that we are before begin or that the
497 // list is empty. We always want to start out one before so that the call
498 // to next moves us onto the element in question;
499
500 if (index < this->list->listSize / 2) {
501 this->current = &this->list->head;
502 for (this->index = -1; this->index + 1 < index; ++this->index) {
503 this->current = this->current->next;
504 }
505 } else {
506 this->current = &this->list->tail;
507 for (this->index = this->list->listSize; this->index >= index; --this->index) {
508 this->current = this->current->prev;
509 }
510 }
511 }
512
513 virtual ~LinkedListIterator() {}
514
515 virtual E next() {
516
517 if (this->expectedModCount != this->list->modCount) {
518 throw ConcurrentModificationException(
519 __FILE__, __LINE__, "List modified outside of this Iterator." );
520 }
521
522 if (this->current->next == &(this->list->tail)) {
523 throw NoSuchElementException(
524 __FILE__, __LINE__, "No more elements to return from next()" );
525 }
526
527 this->current = this->current->next;
528 this->lastReturned = this->current;
529 this->index++;
530
531 return this->current->value;
532 }
533
534 virtual bool hasNext() const {
535 return (this->current->next != &this->list->tail);
536 }
537
538
539 virtual E previous() {
540 if (this->expectedModCount != this->list->modCount) {
541 throw ConcurrentModificationException(
542 __FILE__, __LINE__, "List modified outside of this Iterator." );
543 }
544
545 if (this->current == &(this->list->head)) {
546 throw decaf::lang::exceptions::IllegalStateException(
547 __FILE__, __LINE__,
548 "No previous element, must call next() before calling previous()." );
549 }
550
551 this->lastReturned = this->current;
552 this->current = this->current->prev;
553 this->index--;
554
555 return this->lastReturned->value;
556 }
557
558 virtual bool hasPrevious() const {
559 return (this->current != &this->list->head);
560 }
561
562 virtual void remove() {
563 if (this->expectedModCount != this->list->modCount) {
564 throw ConcurrentModificationException(
565 __FILE__, __LINE__, "List modified outside of this Iterator." );
566 }
567
568 if (this->lastReturned == NULL) {
569 throw lang::exceptions::IllegalStateException(
570 __FILE__, __LINE__,
571 "Invalid State to call remove, must call next() before remove()" );
572 }
573
574 ListNode<E>* next = this->lastReturned->next;
575 ListNode<E>* previous = this->lastReturned->prev;
576
577 next->prev = previous;
578 previous->next = next;
579
580 // When iterating in reverse this would not be true
581 if (this->current == this->lastReturned) {
582 this->index--;
583 }
584 this->current = previous;
585
586 delete this->lastReturned;
587 this->lastReturned = NULL;
588
589 this->list->listSize--;
590 this->list->modCount++;
591
592 this->expectedModCount++;
593 }
594
595 virtual void add(const E& e) {
596 if (this->expectedModCount != this->list->modCount) {
597 throw ConcurrentModificationException(
598 __FILE__, __LINE__, "List modified outside of this Iterator." );
599 }
600
601 ListNode<E>* newNode = new ListNode<E>( this->current, this->current->next, e );
602
603 this->current->next->prev = newNode;
604 this->current->next = newNode;
605
606 this->current = newNode;
607 this->lastReturned = NULL;
608
609 this->index++;
610 this->expectedModCount++;
611 this->list->modCount++;
612 this->list->listSize++;
613 }
614
615 virtual void set(const E& e) {
616
617 if (this->expectedModCount != this->list->modCount) {
618 throw ConcurrentModificationException(
619 __FILE__, __LINE__, "List modified outside of this Iterator." );
620 }
621
622 if (this->lastReturned != NULL) {
623 this->lastReturned->value = e;
624 } else {
625 throw decaf::lang::exceptions::IllegalStateException(
626 __FILE__, __LINE__, "Iterator next has not been called." );
627 }
628 }
629
630 virtual int nextIndex() const {
631 return this->index + 1;
632 }
633
634 virtual int previousIndex() const {
635 return this->index;
636 }
637 };
638
639 class ConstLinkedListIterator : public ListIterator<E> {
640 private:
641
642 const LinkedList<E>* list;
643 const ListNode<E>* current;
644 const ListNode<E>* lastReturned;
645 int index;
646
647 private:
648
649 ConstLinkedListIterator(const ConstLinkedListIterator&);
650 ConstLinkedListIterator operator=(const ConstLinkedListIterator&);
651
652 public:
653
654 ConstLinkedListIterator(const LinkedList<E>* list, int index) :
655 ListIterator<E>(), list(list), current(NULL), lastReturned(NULL), index(-1) {
656
657 if (list == NULL) {
658 throw decaf::lang::exceptions::NullPointerException(
659 __FILE__, __LINE__, "Parent LinkedList pointer was Null." );
660 }
661
662 if (index < 0 || index > list->listSize) {
663 throw decaf::lang::exceptions::IndexOutOfBoundsException(
664 __FILE__, __LINE__, "Given index {%d} is out of range.", index );
665 }
666
667 // index starts at -1 to indicate that we are before begin or that the
668 // list is empty. We always want to start out one before so that the call
669 // to next moves us onto the element in question;
670
671 if (index < this->list->listSize / 2) {
672 this->current = &this->list->head;
673 for (this->index = -1; this->index + 1 < index; ++this->index) {
674 this->current = this->current->next;
675 }
676 } else {
677 this->current = &this->list->tail;
678 for (this->index = this->list->listSize; this->index >= index; --this->index) {
679 this->current = this->current->prev;
680 }
681 }
682 }
683
684 virtual ~ConstLinkedListIterator() {}
685
686 virtual E next() {
687
688 if (this->current->next == &(this->list->tail)) {
690 __FILE__, __LINE__, "No more elements to return from this ListIterator" );
691 }
692
693 this->current = this->current->next;
694 this->lastReturned = this->current;
695 this->index++;
696
697 return this->current->value;
698 }
699
700 virtual bool hasNext() const {
701 return (this->current->next != &(this->list->tail));
702 }
703
704 virtual E previous() {
705
706 if (this->current == &(this->list->head)) {
707 throw decaf::lang::exceptions::IllegalStateException(
708 __FILE__, __LINE__,
709 "No previous element, must call next() before calling previous()." );
710 }
711
712 this->lastReturned = this->current;
713 this->current = this->current->prev;
714 this->index--;
715
716 return this->lastReturned->value;
717 }
718
719 virtual bool hasPrevious() const {
720 return (this->current != &(this->list->head));
721 }
722
723 virtual void remove() {
724 throw lang::exceptions::UnsupportedOperationException(
725 __FILE__, __LINE__, "Cannot write to a const ListIterator." );
726 }
727
728 virtual void add( const E& e DECAF_UNUSED ) {
729 throw lang::exceptions::UnsupportedOperationException(
730 __FILE__, __LINE__, "Cannot write to a const ListIterator." );
731 }
732
733 virtual void set( const E& e DECAF_UNUSED ) {
734 throw lang::exceptions::UnsupportedOperationException(
735 __FILE__, __LINE__, "Cannot write to a const ListIterator." );
736 }
737
738 virtual int nextIndex() const {
739 return this->index + 1;
740 }
741
742 virtual int previousIndex() const {
743 return this->index;
744 }
745 };
746
747 class ReverseIterator : public Iterator<E> {
748 private:
749
750 LinkedList<E>* list;
751 ListNode<E>* current;
752 int expectedModCount;
753 bool canRemove;
754
755 private:
756
757 ReverseIterator(const ReverseIterator&);
758 ReverseIterator operator=(const ReverseIterator&);
759
760 public:
761
762 ReverseIterator(LinkedList<E>* list) :
763 Iterator<E>(), list(list), current(NULL), expectedModCount(0), canRemove(false) {
764
765 if (list == NULL) {
766 throw decaf::lang::exceptions::NullPointerException(
767 __FILE__, __LINE__, "Parent LinkedList pointer was Null." );
768 }
769
770 this->expectedModCount = this->list->modCount;
771 this->current = &list->tail;
772 }
773
774 virtual ~ReverseIterator() {}
775
776 virtual bool hasNext() const {
777 return this->current->prev != &(this->list->head);
778 }
779
780 virtual E next() {
781
782 if (this->expectedModCount != this->list->modCount) {
783 throw ConcurrentModificationException(
784 __FILE__, __LINE__, "List modified outside of this Iterator." );
785 }
786
787 if (this->current->prev == &(this->list->head)) {
788 throw NoSuchElementException(
789 __FILE__, __LINE__, "No more elements to return from next()" );
790 }
791
792 this->current = this->current->prev;
793 this->canRemove = true;
794
795 return this->current->value;
796 }
797
798 virtual void remove() {
799 if (this->expectedModCount != this->list->modCount) {
800 throw ConcurrentModificationException(
801 __FILE__, __LINE__, "List modified outside of this Iterator." );
802 }
803
804 if (!this->canRemove) {
805 throw lang::exceptions::IllegalStateException(
806 __FILE__, __LINE__,
807 "Invalid State to call remove, must call next() before remove()" );
808 }
809
810 ListNode<E>* next = this->current->prev;
811 ListNode<E>* prev = this->current->next;
812
813 next->next = prev;
814 prev->prev = next;
815
816 delete this->current;
817
818 this->current = prev;
819
820 this->list->listSize--;
821 this->list->modCount++;
822 this->expectedModCount++;
823 this->canRemove = false;
824 }
825 };
826
827 class ConstReverseIterator : public Iterator<E> {
828 private:
829
830 const LinkedList<E>* list;
831 const ListNode<E>* current;
832
833 private:
834
835 ConstReverseIterator(const ConstReverseIterator&);
836 ConstReverseIterator operator=(const ConstReverseIterator&);
837
838 public:
839
840 ConstReverseIterator(const LinkedList<E>* list) : Iterator<E>(), list(list), current(NULL) {
841
842 if (list == NULL) {
843 throw decaf::lang::exceptions::NullPointerException(
844 __FILE__, __LINE__, "Parent LinkedList pointer was Null." );
845 }
846
847 this->current = &list->tail;
848 }
849
850 virtual ~ConstReverseIterator() {}
851
852 virtual bool hasNext() const {
853 return this->current->prev != &(this->list->head);
854 }
855
856 virtual E next() {
857
858 if (this->current->prev == &(this->list->head)) {
859 throw NoSuchElementException(
860 __FILE__, __LINE__, "No more elements to return from next()" );
861 }
862
863 this->current = this->current->prev;
864
865 return this->current->value;
866 }
867
868 virtual void remove() {
869 throw lang::exceptions::UnsupportedOperationException(
870 __FILE__, __LINE__, "Cannot write to a const Iterator." );
871 }
872 };
873
874 public:
875
876 using AbstractSequentialList<E>::listIterator;
877
878 virtual ListIterator<E>* listIterator(int index) {
879 return new LinkedListIterator(this, index);
880 }
881 virtual ListIterator<E>* listIterator(int index) const {
882 return new ConstLinkedListIterator(this, index);
883 }
884
886 return new ReverseIterator(this);
887 }
889 return new ConstReverseIterator(this);
890 }
891
892 private:
893
894 E removeAtFront() {
895
896 if (this->head.next == &this->tail) {
898 __FILE__, __LINE__, "The Collection is empty." );
899 }
900
901 ListNode<E>* oldNode = this->head.next;
902 E result = oldNode->value;
903
904 this->head.next = oldNode->next;
905 this->head.next->prev = &this->head;
906
907 delete oldNode;
908
909 this->listSize--;
910 AbstractList<E>::modCount++;
911
912 return result;
913 }
914
915 E removeAtEnd() {
916
917 if (this->head.next == &this->tail) {
918 throw NoSuchElementException(
919 __FILE__, __LINE__, "The Collection is empty." );
920 }
921
922 ListNode<E>* oldNode = this->tail.prev;
923 E result = oldNode->value;
924
925 this->tail.prev = oldNode->prev;
926 this->tail.prev->next = &this->tail;
927
928 delete oldNode;
929
930 this->listSize--;
931 AbstractList<E>::modCount++;
932
933 return result;
934 }
935
936 void addToFront(const E& value) {
937
938 ListNode<E>* newHead = new ListNode<E> (&this->head, this->head.next, value);
939
940 (this->head.next)->prev = newHead;
941 this->head.next = newHead;
942
943 this->listSize++;
944 AbstractList<E>::modCount++;
945 }
946
947 void addToEnd(const E& value) {
948
949 ListNode<E>* newTail = new ListNode<E> (this->tail.prev, &this->tail, value);
950
951 (this->tail.prev)->next = newTail;
952 this->tail.prev = newTail;
953
954 this->listSize++;
955 AbstractList<E>::modCount++;
956 }
957
958 void addAtLocation(int index, const E& value) {
959
960 ListNode<E>* location = NULL;
961
962 if (index <= this->listSize / 2) {
963 location = this->head.next;
964 for (int i = 0; i < index; ++i) {
965 location = location->next;
966 }
967 } else {
968 location = &this->tail;
969 for (int i = this->listSize; i > index; --i) {
970 location = location->prev;
971 }
972 }
973
974 ListNode<E>* newNode = new ListNode<E> (location->prev, location, value);
975
976 (location->prev)->next = newNode;
977 location->prev = newNode;
978
979 this->listSize++;
980 AbstractList<E>::modCount++;
981 }
982
983 bool addAllAtLocation(int index, const Collection<E>& collection) {
984
985 if (index < 0 || index > this->listSize) {
986 throw decaf::lang::exceptions::IndexOutOfBoundsException(
987 __FILE__, __LINE__, "Index for add is outside bounds of this LinkedList." );
988 }
989
990 int csize = collection.size();
991 if (csize == 0) {
992 return false;
993 }
994
995 std::auto_ptr<ArrayList<E> > copy;
996 std::auto_ptr<Iterator<E> > iter;
997
998 if (this == &collection) {
999 copy.reset(new ArrayList<E> (collection));
1000 iter.reset(copy->iterator());
1001 } else {
1002 iter.reset(collection.iterator());
1003 }
1004
1005 ListNode<E>* newNode = NULL;
1006 ListNode<E>* previous = NULL;
1007
1008 if (index < this->listSize / 2) {
1009 previous = &this->head;
1010 for (int i = 0; i < index; ++i) {
1011 previous = previous->next;
1012 }
1013 } else {
1014 previous = &this->tail;
1015 for (int i = this->listSize; i >= index; --i) {
1016 previous = previous->prev;
1017 }
1018 }
1019
1020 while (iter->hasNext()) {
1021 newNode = new ListNode<E> (previous, previous->next, iter->next());
1022 previous->next->prev = newNode;
1023 previous->next = newNode;
1024 previous = newNode;
1025 }
1026
1027 this->listSize += csize;
1028 AbstractList<E>::modCount++;
1029
1030 return true;
1031 }
1032
1033 void purgeList() {
1034 ListNode<E>* current = this->head.next;
1035 ListNode<E>* temp = NULL;
1036 while (current != &this->tail) {
1037 temp = current;
1038 current = current->next;
1039 delete temp;
1040 }
1041 }
1042 };
1043
1044}}
1045
1046#endif /* _DECAF_UTIL_LINKEDLIST_H_ */
LinkedList< E > & operator=(const LinkedList< E > &list)
Definition LinkedList.h:121
LinkedList()
Definition LinkedList.h:91
Definition IndexOutOfBoundsException.h:31
Definition NullPointerException.h:32
virtual bool equals(const Collection< E > &collection) const
Answers true if this Collection and the one given are the same size and if each element contained in ...
Definition AbstractCollection.h:172
int modCount
Definition AbstractList.h:69
This class provides a skeletal implementation of the List interface to minimize the effort required t...
Definition AbstractSequentialList.h:59
virtual Iterator< E > * iterator()
Definition AbstractSequentialList.h:69
The root interface in the collection hierarchy.
Definition Collection.h:69
Defines a 'Double ended Queue' interface that allows for insertion and removal of elements from both ...
Definition Deque.h:42
Defines an object that can be used to iterate over the elements of a collection.
Definition Iterator.h:34
A complete implementation of the List interface using a doubly linked list data structure.
Definition LinkedList.h:55
virtual bool addAll(int index, const Collection< E > &collection)
Inserts all of the elements in the specified collection into this list at the specified position (opt...
Definition LinkedList.h:213
virtual ListIterator< E > * listIterator(int index)
Definition LinkedList.h:878
bool operator==(const LinkedList< E > &other) const
Definition LinkedList.h:133
virtual const E & getLast() const
Definition LinkedList.h:367
virtual E removeLast()
Removes the last element from the Deque and returns it.
Definition LinkedList.h:389
virtual bool removeLastOccurrence(const E &value)
Removes the last occurrence of the specified element from this Deque.
Definition LinkedList.h:451
virtual void clear()
Removes all of the elements from this collection (optional operation).
Definition LinkedList.h:234
LinkedList< E > & operator=(const LinkedList< E > &list)
Definition LinkedList.h:121
virtual Iterator< E > * descendingIterator() const
Definition LinkedList.h:888
virtual int size() const
Returns the number of elements in this collection.
Definition LinkedList.h:230
virtual bool add(const E &value)
Returns true if this collection changed as a result of the call.
Definition LinkedList.h:194
virtual bool peekFirst(E &result) const
Retrieves the first element contained in this Deque and assigns its value to the reference value pass...
Definition LinkedList.h:413
virtual void copy(const Collection< E > &collection)
Renders this Collection as a Copy of the given Collection.
Definition LinkedList.h:217
virtual bool addAll(const Collection< E > &collection)
Adds all of the elements in the specified collection to this collection.
Definition LinkedList.h:209
virtual E pop()
Treats this Deque as a stack and attempts to pop an element off the top.
Definition LinkedList.h:431
virtual const E & getFirst() const
Definition LinkedList.h:351
virtual cms::Connection * element() const
Definition LinkedList.h:327
virtual bool offer(const E &value)
Inserts the specified element into the queue provided that the condition allows such an operation.
Definition LinkedList.h:297
virtual E & getFirst()
Attempts to fetch a reference to the first element in the Deque.
Definition LinkedList.h:343
virtual void push(const E &element)
Pushes an element onto the stack represented by this deque (in other words, at the head of this deque...
Definition LinkedList.h:435
virtual bool poll(E &result)
Gets and removes the element in the head of the queue.
Definition LinkedList.h:302
virtual bool peekLast(E &result) const
Retrieves the last element contained in this Deque and assigns its value to the reference value passe...
Definition LinkedList.h:422
virtual bool removeFirstOccurrence(const E &value)
Removes the first occurrence of the specified element from this Deque.
Definition LinkedList.h:439
virtual E & getLast()
Attempts to fetch a reference to the last element in the Deque.
Definition LinkedList.h:359
virtual bool pollLast(E &result)
Removes the last element from the Deque assigns it to the element reference passed.
Definition LinkedList.h:403
virtual int indexOf(const E &value) const
Returns the index of the first occurrence of the specified element in this list, or -1 if this list d...
Definition LinkedList.h:246
LinkedList(const LinkedList< E > &list)
Definition LinkedList.h:97
virtual Iterator< E > * descendingIterator()
Provides an Iterator over this Collection that traverses the element in reverse order.
Definition LinkedList.h:885
virtual void addLast(const E &value)
Inserts an element onto the end of the Deque if possible without violating the implementations capaci...
Definition LinkedList.h:339
virtual bool offerLast(const E &element)
This method attempts to insert the given element into the Deque at the end.
Definition LinkedList.h:380
virtual bool isEmpty() const
Definition LinkedList.h:226
virtual E get(int index) const
Gets the element contained at position passed.value at index specified.This implementation first gets...
Definition LinkedList.h:143
virtual int lastIndexOf(const E &value) const
Returns the index of the last occurrence of the specified element in this list, or -1 if this list do...
Definition LinkedList.h:263
virtual void addFirst(const E &value)
Inserts an element onto the front of the Deque if possible without violating the implementations capa...
Definition LinkedList.h:335
bool operator!=(const LinkedList< E > &other) const
Definition LinkedList.h:137
virtual bool offerFirst(const E &element)
This method attempts to insert the given element into the Deque at the front end.
Definition LinkedList.h:375
virtual E remove()
Gets and removes the element in the head of the queue.
Definition LinkedList.h:313
virtual E set(int index, const E &element)
Replaces the element at the specified position in this list with the specified element....
Definition LinkedList.h:167
virtual bool peek(E &result) const
Gets but not removes the element in the head of the queue.
Definition LinkedList.h:317
virtual E removeFirst()
Removes the topmost element from the Deque and returns it.
Definition LinkedList.h:385
virtual std::vector< E > toArray() const
Returns an array containing all of the elements in this collection.
Definition LinkedList.h:280
virtual bool contains(const E &value) const
Returns true if this collection contains the specified element.
Definition LinkedList.h:242
virtual ListIterator< E > * listIterator(int index) const
Definition LinkedList.h:881
virtual bool pollFirst(E &result)
Removes the first element from the Deque assigns it to the element reference passed.
Definition LinkedList.h:393
LinkedList()
Definition LinkedList.h:91
virtual ~LinkedList()
Definition LinkedList.h:113
virtual void add(int index, const E &value)
Inserts the specified element at the specified position in this list.Shifts the element currently at ...
Definition LinkedList.h:199
LinkedList(const Collection< E > &collection)
Definition LinkedList.h:105
LinkedList< E > & operator=(const Collection< E > &collection)
Definition LinkedList.h:127
virtual bool remove(const E &value)
Removes a single instance of the specified element from the collection.
Definition LinkedList.h:222
An iterator for lists that allows the programmer to traverse the list in either direction,...
Definition ListIterator.h:38
Definition NoSuchElementException.h:31
#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