template class DoublyLinkedList { // The forward declarations of these classes allows us to establish // that they exist, but delay displaying all of the details until // later in the file. // // (This is generally a good style, with the most important details // appearing earlier in the class declaration. That's the same // reason why we're implementing the bodies of the member functions // outside of the class declaration.) public: class Iterator; class ConstIterator;

private: struct Node;

public: // Initializes this list to be empty. DoublyLinkedList() noexcept;

// Initializes this list as a copy of an existing one. DoublyLinkedList(const DoublyLinkedList &list);

// Initializes this list from an expiring one. DoublyLinkedList(DoublyLinkedList &&list) noexcept;

// Destroys the contents of this list. virtual ~DoublyLinkedList() noexcept;

// Replaces the contents of this list with a copy of the contents // of an existing one. DoublyLinkedList &operator=(const DoublyLinkedList &list);

// Replaces the contents of this list with the contents of an // expiring one. DoublyLinkedList &operator=(DoublyLinkedList &&list) noexcept;

// addToStart() adds a value to the start of the list, meaning that // it will now be the first value, with all subsequent elements still // being in the list (after the new value) in the same order. void addToStart(const ValueType &value);

// addToEnd() adds a value to the end of the list, meaning that // it will now be the last value, with all subsequent elements still // being in the list (before the new value) in the same order. void addToEnd(const ValueType &value);

// removeFromStart() removes a value from the start of the list, meaning // that the list will now contain all of the values *in the same order* // that it did before, *except* that the first one will be gone. // In the event that the list is empty, an EmptyException will be thrown. void removeFromStart();

// removeFromEnd() removes a value from the end of the list, meaning // that the list will now contain all of the values *in the same order* // that it did before, *except* that the last one will be gone. // In the event that the list is empty, an EmptyException will be thrown. void removeFromEnd();

// first() returns the value at the start of the list. In the event that // the list is empty, an EmptyException will be thrown. There are two // variants of this member function: one for a const DoublyLinkedList and // another for a non-const one. const ValueType &first() const; ValueType &first();

// last() returns the value at the end of the list. In the event that // the list is empty, an EmptyException will be thrown. There are two // variants of this member function: one for a const DoublyLinkedList and // another for a non-const one. const ValueType &last() const; ValueType &last();

// isEmpty() returns true if the list has no values in it, false // otherwise. bool isEmpty() const noexcept;

// size() returns the number of values in the list. unsigned int size() const noexcept;

// There are two kinds of iterators supported: Iterators and // ConstIterators. They have similar characteristics; they both // allow you to see what values are in the list and move back and // forth between them. The difference is that ConstIterators allow // you to see the elements but not modify them, while Iterators also // support modification of the list (both by modifying the elements // directly, and also by inserting or removing values at arbitrary // locations). // // At any given time, an iterator refers to a value in the list. // There are also two additional places it can refer: "past start" // and "past end", which are the positions directly before the // first value and directly after the last one, respectively. // Except with respect to those boundaries, they can be moved // both forward and backward. // // Note, too, that the reason we have a ConstIterator class instead // of just saying "const Iterator" is because a "const Iterator" // is something different: It's an Iterator object that you can't // modify (i.e., you can't move it around). What a ConstIterator // holds constant isn't the iterator; it's the list that's protected // by it.

// iterator() creates a new Iterator over this list. It will // initially be referring to the first value in the list, unless the // list is empty, in which case it will be considered both "past start" // and "past end". Iterator iterator();

// constIterator() creates a new ConstIterator over this list. It will // initially be referring to the first value in the list, unless the // list is empty, in which case it will be considered both "past start" // and "past end". ConstIterator constIterator() const;

public: // The IteratorBase class is the base class for our two kinds of // iterators. Because there are so many similarities between them, // we write those similarities in a base class, then inherit from // that base class to specify only the differences. class IteratorBase { public: // Initializes a newly-constructed IteratorBase to operate on // the given list. It will initially be referring to the first // value in the list, unless the list is empty, in which case // it will be considered to be both "past start" and "past end". IteratorBase(const DoublyLinkedList &list) noexcept;

// moveToNext() moves this iterator forward to the next value in // the list. If the iterator is refrering to the last value, it // moves to the "past end" position. If it is already at the // "past end" position, an IteratorException will be thrown. void moveToNext();

// moveToPrevious() moves this iterator backward to the previous // value in the list. If the iterator is refrering to the first // value, it moves to the "past start" position. If it is already // at the "past start" position, an IteratorException will be thrown. void moveToPrevious();

// isPastStart() returns true if this iterator is in the "past // start" position, false otherwise. bool isPastStart() const noexcept;

// isPastEnd() returns true if this iterator is in the "past end" // position, false otherwise. bool isPastEnd() const noexcept;

protected: // You may want protected member variables and member functions, // which will be accessible to the derived classes. Node *current; };

class ConstIterator : public IteratorBase { public: // Initializes a newly-constructed ConstIterator to operate on // the given list. It will initially be referring to the first // value in the list, unless the list is empty, in which case // it will be considered to be both "past start" and "past end". ConstIterator(const DoublyLinkedList &list) noexcept;

// value() returns the value that the iterator is currently // referring to. If the iterator is in the "past start" or // "past end" positions, an IteratorException will be thrown. const ValueType &value() const;

private: // You may want private member variables and member functions. Node *current_node; };

class Iterator : public IteratorBase { public: // Initializes a newly-constructed Iterator to operate on the // given list. It will initially be referring to the first // value in the list, unless the list is empty, in which case // it will be considered to be both "past start" and "past end". Iterator(DoublyLinkedList &list) noexcept;

// value() returns the value that the iterator is currently // referring to. If the iterator is in the "past start" or // "past end" positions, an IteratorException will be thrown. ValueType &value() const;

// insertBefore() inserts a new value into the list before // the one to which the iterator currently refers. If the // iterator is in the "past start" position, an IteratorException // is thrown. void insertBefore(const ValueType &value);

// insertAfter() inserts a new value into the list after // the one to which the iterator currently refers. If the // iterator is in the "past end" position, an IteratorException // is thrown. void insertAfter(const ValueType &value);

// remove() removes the value to which this iterator refers, // moving the iterator to refer to either the value after it // (if moveToNextAfterward is true) or before it (if // moveToNextAfterward is false). If the iterator is in the // "past start" or "past end" position, an IteratorException // is thrown. void remove(bool moveToNextAfterward = true);

private: // You may want private member variables and member functions. Node *current_node; };

void clear();

private: // A structure that contains the vital parts of a Node in a // doubly-linked list, the value and two pointers: one pointing // to the previous node (or nullptr if there isn't one) and // one pointing to the next node (or nullptr if there isn't // one). struct Node { ValueType value; Node *prev; Node *next; };

Node *head; Node *tail; };

need implementation: template typename DoublyLinkedList::Iterator DoublyLinkedList::iterator() { }

template typename DoublyLinkedList::ConstIterator DoublyLinkedList::constIterator() const { }

template DoublyLinkedList::IteratorBase::IteratorBase(const DoublyLinkedList &list) noexcept {

}