58 template<
typename U >
68 ListNode(
const ListNode&);
73 ListNode() : value(), prev(
NULL), next(
NULL) {}
75 ListNode(
const U& value) : value(value), prev(
NULL), next(
NULL) {}
77 ListNode(ListNode<U>* prev, ListNode<U>* next,
const U& value) :
78 value(value), prev(prev), next(next) {
93 this->head.next = &this->tail;
94 this->tail.prev = &this->head;
99 this->head.next = &this->tail;
100 this->tail.prev = &this->head;
102 this->addAllAtLocation(0, list);
107 this->head.next = &this->tail;
108 this->tail.prev = &this->head;
110 this->addAllAtLocation(0, collection);
123 this->addAllAtLocation(0, list);
129 this->addAllAtLocation(0, collection);
134 return this->
equals(other);
138 return !this->
equals(other);
143 virtual E
get(
int index)
const {
145 if (index < 0 || index >= this->listSize) {
147 __FILE__, __LINE__,
"Index given is outside bounds of this list {%d}", index );
150 const ListNode<E>* location =
NULL;
152 if (index < this->listSize / 2) {
153 location = &this->head;
154 for (
int i = 0; i <= index; ++i) {
155 location = location->next;
158 location = &this->tail;
159 for (
int i = this->listSize; i > index; --i) {
160 location = location->prev;
164 return location->value;
169 if (index < 0 || index >= this->listSize) {
171 __FILE__, __LINE__,
"Index given is outside bounds of this list {%d}", index );
174 ListNode<E>* location =
NULL;
176 if (index < this->listSize / 2) {
177 location = &this->head;
178 for (
int i = 0; i <= index; ++i) {
179 location = location->next;
182 location = &this->tail;
183 for (
int i = this->listSize; i > index; --i) {
184 location = location->prev;
188 E oldValue = location->value;
194 virtual bool add(
const E& value) {
195 this->addToEnd(value);
199 virtual void add(
int index,
const E& value) {
201 if (index < 0 || index > this->listSize) {
203 __FILE__, __LINE__,
"Index given is outside bounds of this list {%d}", index );
206 this->addAtLocation(index, value);
210 return this->addAllAtLocation(this->listSize, collection);
214 return this->addAllAtLocation(index, collection);
219 this->addAllAtLocation(0, collection);
227 return this->listSize == 0;
231 return this->listSize;
236 this->head.next = &this->tail;
237 this->tail.prev = &this->head;
243 return this->
indexOf(value) != -1;
248 if (this->listSize == 0) {
252 const ListNode<E>* location = this->head.next;
254 for (
int i = 0; location != &this->tail; ++i, location = location->next) {
255 if (location->value == value) {
265 if (this->listSize == 0) {
269 const ListNode<E>* location = this->tail.prev;
271 for (
int i = this->listSize - 1; location != &this->head; --i, location = location->prev) {
272 if (location->value == value) {
282 std::vector<E> result;
283 result.reserve(this->listSize);
285 const ListNode<E>* current = this->head.next;
287 while (current != &this->tail) {
288 result.push_back(current->value);
289 current = current->next;
297 virtual bool offer(
const E& value) {
304 if (this->listSize == 0) {
308 result = this->head.next->value;
309 this->removeAtFront();
314 return this->removeAtFront();
317 virtual bool peek(E& result)
const {
319 if (this->listSize == 0) {
323 result = this->head.next->value;
328 if (this->listSize == 0) {
332 return this->head.next->value;
336 this->addToFront(value);
340 this->addToEnd(value);
344 if (this->listSize == 0) {
348 return this->head.next->value;
352 if (this->listSize == 0) {
356 return this->head.next->value;
360 if (this->listSize == 0) {
364 return this->tail.prev->value;
368 if (this->listSize == 0) {
372 return this->tail.prev->value;
386 return this->removeAtFront();
390 return this->removeAtEnd();
394 if (this->listSize == 0) {
398 result = this->head.next->value;
399 this->removeAtFront();
404 if (this->listSize == 0) {
408 result = this->tail.prev->value;
414 if (this->listSize == 0) {
418 result = this->head.next->value;
423 if (this->listSize == 0) {
427 result = this->tail.prev->value;
432 return this->removeAtFront();
440 std::auto_ptr<Iterator<E> > iter(this->
iterator());
441 while (iter->hasNext()) {
442 if (iter->next() == value) {
453 while (iter->hasNext()) {
454 if (iter->next() == value) {
469 ListNode<E>* current;
470 ListNode<E>* lastReturned;
472 int expectedModCount;
476 LinkedListIterator(
const LinkedListIterator&);
477 LinkedListIterator operator=(
const LinkedListIterator&);
482 ListIterator<E>(), list(list), current(
NULL), lastReturned(
NULL), index(-1), expectedModCount(0) {
486 __FILE__, __LINE__,
"Parent LinkedList pointer was Null." );
489 if (index < 0 || index > list->listSize) {
490 throw decaf::lang::exceptions::IndexOutOfBoundsException(
491 __FILE__, __LINE__,
"Given index {%d} is out of range.", index );
494 this->expectedModCount = list->
modCount;
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;
506 this->current = &this->list->tail;
507 for (this->index = this->list->listSize; this->index >= index; --this->index) {
508 this->current = this->current->prev;
513 virtual ~LinkedListIterator() {}
517 if (this->expectedModCount != this->list->
modCount) {
518 throw ConcurrentModificationException(
519 __FILE__, __LINE__,
"List modified outside of this Iterator." );
522 if (this->current->next == &(this->list->tail)) {
523 throw NoSuchElementException(
524 __FILE__, __LINE__,
"No more elements to return from next()" );
527 this->current = this->current->next;
528 this->lastReturned = this->current;
531 return this->current->value;
534 virtual bool hasNext()
const {
535 return (this->current->next != &this->list->tail);
539 virtual E previous() {
540 if (this->expectedModCount != this->list->
modCount) {
541 throw ConcurrentModificationException(
542 __FILE__, __LINE__,
"List modified outside of this Iterator." );
545 if (this->current == &(this->list->head)) {
546 throw decaf::lang::exceptions::IllegalStateException(
548 "No previous element, must call next() before calling previous()." );
551 this->lastReturned = this->current;
552 this->current = this->current->prev;
555 return this->lastReturned->value;
558 virtual bool hasPrevious()
const {
559 return (this->current != &this->list->head);
563 if (this->expectedModCount != this->list->
modCount) {
564 throw ConcurrentModificationException(
565 __FILE__, __LINE__,
"List modified outside of this Iterator." );
568 if (this->lastReturned ==
NULL) {
569 throw lang::exceptions::IllegalStateException(
571 "Invalid State to call remove, must call next() before remove()" );
574 ListNode<E>* next = this->lastReturned->next;
575 ListNode<E>* previous = this->lastReturned->prev;
577 next->prev = previous;
578 previous->next = next;
581 if (this->current == this->lastReturned) {
584 this->current = previous;
586 delete this->lastReturned;
587 this->lastReturned =
NULL;
589 this->list->listSize--;
592 this->expectedModCount++;
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." );
601 ListNode<E>* newNode =
new ListNode<E>( this->current, this->current->next, e );
603 this->current->next->prev = newNode;
604 this->current->next = newNode;
606 this->current = newNode;
607 this->lastReturned =
NULL;
610 this->expectedModCount++;
612 this->list->listSize++;
615 virtual void set(
const E& e) {
617 if (this->expectedModCount != this->list->
modCount) {
618 throw ConcurrentModificationException(
619 __FILE__, __LINE__,
"List modified outside of this Iterator." );
622 if (this->lastReturned !=
NULL) {
623 this->lastReturned->value = e;
625 throw decaf::lang::exceptions::IllegalStateException(
626 __FILE__, __LINE__,
"Iterator next has not been called." );
630 virtual int nextIndex()
const {
631 return this->index + 1;
634 virtual int previousIndex()
const {
639 class ConstLinkedListIterator :
public ListIterator<E> {
642 const LinkedList<E>* list;
643 const ListNode<E>* current;
644 const ListNode<E>* lastReturned;
649 ConstLinkedListIterator(
const ConstLinkedListIterator&);
650 ConstLinkedListIterator operator=(
const ConstLinkedListIterator&);
654 ConstLinkedListIterator(
const LinkedList<E>* list,
int index) :
655 ListIterator<E>(), list(list), current(
NULL), lastReturned(
NULL), index(-1) {
658 throw decaf::lang::exceptions::NullPointerException(
659 __FILE__, __LINE__,
"Parent LinkedList pointer was Null." );
662 if (index < 0 || index > list->listSize) {
663 throw decaf::lang::exceptions::IndexOutOfBoundsException(
664 __FILE__, __LINE__,
"Given index {%d} is out of range.", index );
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;
677 this->current = &this->list->tail;
678 for (this->index = this->list->listSize; this->index >= index; --this->index) {
679 this->current = this->current->prev;
684 virtual ~ConstLinkedListIterator() {}
688 if (this->current->next == &(this->list->tail)) {
690 __FILE__, __LINE__,
"No more elements to return from this ListIterator" );
693 this->current = this->current->next;
694 this->lastReturned = this->current;
697 return this->current->value;
700 virtual bool hasNext()
const {
701 return (this->current->next != &(this->list->tail));
704 virtual E previous() {
706 if (this->current == &(this->list->head)) {
707 throw decaf::lang::exceptions::IllegalStateException(
709 "No previous element, must call next() before calling previous()." );
712 this->lastReturned = this->current;
713 this->current = this->current->prev;
716 return this->lastReturned->value;
719 virtual bool hasPrevious()
const {
720 return (this->current != &(this->list->head));
723 virtual void remove() {
724 throw lang::exceptions::UnsupportedOperationException(
725 __FILE__, __LINE__,
"Cannot write to a const ListIterator." );
728 virtual void add(
const E& e DECAF_UNUSED ) {
729 throw lang::exceptions::UnsupportedOperationException(
730 __FILE__, __LINE__,
"Cannot write to a const ListIterator." );
733 virtual void set(
const E& e DECAF_UNUSED ) {
734 throw lang::exceptions::UnsupportedOperationException(
735 __FILE__, __LINE__,
"Cannot write to a const ListIterator." );
738 virtual int nextIndex()
const {
739 return this->index + 1;
742 virtual int previousIndex()
const {
747 class ReverseIterator :
public Iterator<E> {
751 ListNode<E>* current;
752 int expectedModCount;
757 ReverseIterator(
const ReverseIterator&);
758 ReverseIterator operator=(
const ReverseIterator&);
762 ReverseIterator(LinkedList<E>* list) :
763 Iterator<E>(), list(list), current(
NULL), expectedModCount(0), canRemove(false) {
766 throw decaf::lang::exceptions::NullPointerException(
767 __FILE__, __LINE__,
"Parent LinkedList pointer was Null." );
770 this->expectedModCount = this->list->modCount;
771 this->current = &list->tail;
774 virtual ~ReverseIterator() {}
776 virtual bool hasNext()
const {
777 return this->current->prev != &(this->list->head);
782 if (this->expectedModCount != this->list->modCount) {
783 throw ConcurrentModificationException(
784 __FILE__, __LINE__,
"List modified outside of this Iterator." );
787 if (this->current->prev == &(this->list->head)) {
788 throw NoSuchElementException(
789 __FILE__, __LINE__,
"No more elements to return from next()" );
792 this->current = this->current->prev;
793 this->canRemove =
true;
795 return this->current->value;
798 virtual void remove() {
799 if (this->expectedModCount != this->list->modCount) {
800 throw ConcurrentModificationException(
801 __FILE__, __LINE__,
"List modified outside of this Iterator." );
804 if (!this->canRemove) {
805 throw lang::exceptions::IllegalStateException(
807 "Invalid State to call remove, must call next() before remove()" );
810 ListNode<E>* next = this->current->prev;
811 ListNode<E>* prev = this->current->next;
816 delete this->current;
818 this->current = prev;
820 this->list->listSize--;
821 this->list->modCount++;
822 this->expectedModCount++;
823 this->canRemove =
false;
827 class ConstReverseIterator :
public Iterator<E> {
830 const LinkedList<E>* list;
831 const ListNode<E>* current;
835 ConstReverseIterator(
const ConstReverseIterator&);
836 ConstReverseIterator operator=(
const ConstReverseIterator&);
840 ConstReverseIterator(
const LinkedList<E>* list) : Iterator<E>(), list(list), current(
NULL) {
843 throw decaf::lang::exceptions::NullPointerException(
844 __FILE__, __LINE__,
"Parent LinkedList pointer was Null." );
847 this->current = &list->tail;
850 virtual ~ConstReverseIterator() {}
852 virtual bool hasNext()
const {
853 return this->current->prev != &(this->list->head);
858 if (this->current->prev == &(this->list->head)) {
859 throw NoSuchElementException(
860 __FILE__, __LINE__,
"No more elements to return from next()" );
863 this->current = this->current->prev;
865 return this->current->value;
868 virtual void remove() {
869 throw lang::exceptions::UnsupportedOperationException(
870 __FILE__, __LINE__,
"Cannot write to a const Iterator." );
876 using AbstractSequentialList<E>::listIterator;
879 return new LinkedListIterator(
this, index);
882 return new ConstLinkedListIterator(
this, index);
886 return new ReverseIterator(
this);
889 return new ConstReverseIterator(
this);
896 if (this->head.next == &this->tail) {
898 __FILE__, __LINE__,
"The Collection is empty." );
901 ListNode<E>* oldNode = this->head.next;
902 E result = oldNode->value;
904 this->head.next = oldNode->next;
905 this->head.next->prev = &this->head;
910 AbstractList<E>::modCount++;
917 if (this->head.next == &this->tail) {
918 throw NoSuchElementException(
919 __FILE__, __LINE__,
"The Collection is empty." );
922 ListNode<E>* oldNode = this->tail.prev;
923 E result = oldNode->value;
925 this->tail.prev = oldNode->prev;
926 this->tail.prev->next = &this->tail;
931 AbstractList<E>::modCount++;
936 void addToFront(
const E& value) {
938 ListNode<E>* newHead =
new ListNode<E> (&this->head, this->head.next, value);
940 (this->head.next)->prev = newHead;
941 this->head.next = newHead;
944 AbstractList<E>::modCount++;
947 void addToEnd(
const E& value) {
949 ListNode<E>* newTail =
new ListNode<E> (this->tail.prev, &this->tail, value);
951 (this->tail.prev)->next = newTail;
952 this->tail.prev = newTail;
955 AbstractList<E>::modCount++;
958 void addAtLocation(
int index,
const E& value) {
960 ListNode<E>* location =
NULL;
962 if (index <= this->listSize / 2) {
963 location = this->head.next;
964 for (
int i = 0; i < index; ++i) {
965 location = location->next;
968 location = &this->tail;
969 for (
int i = this->listSize; i > index; --i) {
970 location = location->prev;
974 ListNode<E>* newNode =
new ListNode<E> (location->prev, location, value);
976 (location->prev)->next = newNode;
977 location->prev = newNode;
980 AbstractList<E>::modCount++;
983 bool addAllAtLocation(
int index,
const Collection<E>& collection) {
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." );
990 int csize = collection.size();
995 std::auto_ptr<ArrayList<E> > copy;
996 std::auto_ptr<Iterator<E> > iter;
998 if (
this == &collection) {
999 copy.reset(
new ArrayList<E> (collection));
1000 iter.reset(copy->iterator());
1002 iter.reset(collection.iterator());
1005 ListNode<E>* newNode =
NULL;
1006 ListNode<E>* previous =
NULL;
1008 if (index < this->listSize / 2) {
1009 previous = &this->head;
1010 for (
int i = 0; i < index; ++i) {
1011 previous = previous->next;
1014 previous = &this->tail;
1015 for (
int i = this->listSize; i >= index; --i) {
1016 previous = previous->prev;
1020 while (iter->hasNext()) {
1021 newNode =
new ListNode<E> (previous, previous->next, iter->next());
1022 previous->next->prev = newNode;
1023 previous->next = newNode;
1027 this->listSize += csize;
1028 AbstractList<E>::modCount++;
1034 ListNode<E>* current = this->head.next;
1035 ListNode<E>* temp =
NULL;
1036 while (current != &this->tail) {
1038 current = current->next;