AVLTree.hh

/****************************************************************************
 * File: AVLTree.hh
 * Author: Keith Schwarz (htiek@cs.stanford.edu)
 *
 * An implementation of a sorted dictionary backed by an AVL tree.  AVL trees
 * are a type of self-balancing binary tree and were the first such structure
 * to be described that guaranteed that the tree height was no greater than
 * O(lg n).
 *
 * The idea behind the AVL tree is to ensure that for every node in the tree,
 * the height of the node's left and right subtrees differ by at most one.  To
 * see that this ensures that the tree remains balanced, we can show that the
 * minimum number of nodes n required to create a tree of height h is governed
 * by the relationship n = O(lg h).  Once we have this, we know that any AVL
 * tree containing n nodes must have height no greater than O(lg n), and all
 * the standard BST operations on such a tree will complete in time O(lg n).
 * We can show this inductively.  Let N(h) be the minimum number of nodes that
 * could be present in a tree of height h.  Clearly, N(0) = 0, since the empty
 * tree can't have any nodes in it.  We also have that N(1) = 1, since a tree
 * of height one must have at least one node.  Now, let's suppose that we are
 * considering a tree of height h + 2.  This means that the root of the tree
 * must have some subtree that has height h + 1.  Because we enforce the
 * invariant that the heights of the subtrees of each node differ by at most
 * one, this means that the minimum height of the other subtree of the root is
 * h.  This gives us that the minimum number of nodes in the tree is
 * N(h + 2) = N(h) + N(h + 1) + 1, with the +1 coming from the root element.
 * We claim that N(h) = F(h + 2) - 1, where F(h) is the hth Fibonacci 
 * number.  This proof is by induction:
 *
 *   Base cases: N(0) = 0 = 1 - 1 = F(2) - 1
 *               N(1) = 1 = 2 - 1 = F(3) - 1
 *   Inductive step: N(h + 2)  = N(h) + N(h + 1) + 1
 *                             = F(h + 2) - 1 + F(h + 3) - 1 + 1
 *                             = F(h + 2) + F(h + 3) - 1
 *                             = F(h + 4) - 1
 *                             = F((h + 2) + 2) - 1
 *
 * It's well-known that F(h) = (1 / sqrt(5)) (P^h - p^h), where
 *
 *                             P = (1 + sqrt(5)) / 2 ~= 1.6
 *                             p = (1 - sqrt(5)) / 2 ~= 0.6
 *
 * For h > 1, F(h) >= (P^h / sqrt(5)) - 1, and so we have that
 *
 *                       N(h)      >= P^h / sqrt(5) - 1
 *                       N(h) + 1  >= P^h / sqrt(5)
 *              sqrt(5) (N(h) + 1) >= P^h
 *        lg_P(sqrt(5) (N(h) + 1)) >= h
 *
 * And so we have that h = O(lg N(h)); that is, the height of the tree is
 * O(lg n) as required.
 *
 * Given that a tree with this structure will have O(lg n) height, the
 * question now is how we can maintain this property in the tree as we begin
 * adding and removing nodes.  To do this, we'll have each node keep track of
 * its height in the tree.  Whenever we insert a node, we can propagate the
 * new height information from the newly-inserted node up to the root.  If in
 * the course of doing so we detect that a node has two subtrees whose heights
 * differ by more than 1, we can use a series of tree rotations to fix up the
 * balancing.  In particular, there are two cases to consider, plus two
 * symmetric cases:
 *
 * Case 1: We have two nodes in this configuration:
 *
 *                                  a (+2)
 *                                 / \
 *                     (+0 or +1) b   Z
 *                               / \
 *                              X   Y
 *
 *                           
 *
 * Here, the values in parentheses are the "balance term" for each node, which
 * is defined as the difference between the height of its left and right
 * subtrees.  If we are in this case, then suppose that subtree Z has height
 * h.  Since a has a balance factor of +2, this means that the height of b
 * must be h + 2, so at least one of X or Y has height h + 1, and since the
 * balance term of b is not -1, either X and Y both have height h + 1, or X
 * has height h + 1 and Y has height h.  To fix up the balance terms here, we
 * rotate along the edge from a to b to give this setup:
 *
 *                               b (+0 or -1)
 *                              / \
 *                             X   a  (+0 or +1)
 *                                / \
 *                               Y   Z
 *
 * The values of these balance terms can be seen quite easily.  We know that 
 * Z has height h, and Y either has height h + 1 or h.  This means that node
 * a is either at height h + 1 or h + 2, and its balance term is either +0 or
 * +1.  Tree X has height h + 1 as well, and so the balance term of b is
 * either +0 or -1.  Notice that when we started the root of this tree was at
 * height h + 3, and after this operation the height is still h + 3, and so
 * none of the node heights above this tree are affected.
 *
 * Case 2: We have three nodes in this configuration:
 *
 *                                  a (+2)
 *                                 / \
 *                           (-1) b   Z
 *                               / \
 *                              W   c (?)
 *                                 / \
 *                                X   Y
 *
 * Because the balance terms are the way they are, we know that if tree Z has
 * height h, tree b has height h + 2.  Moreover, since the balance term on the
 * node is -1, we know that tree W has height h and the tree rooted at c has
 * height h + 1.  Consequently, at least one of X and Y have height h, and at
 * most one of them has height h - 1.   In this case, we do two rotations.  
 * First, we rotate c and b to get
 *
 *                               (+2) a
 *                                   / \
 *                       (+1 or +2) c   Z
 *                                 / \
 *                     (+0 or +1) b   Y
 *                               / \
 *                              W   X
 *
 * The balance terms here are as follows.  Since W has height h and X has
 * height either h or h - 1, the balance term on b is either 0 or 1, and the
 * height of the tree rooted at b is h + 1.  Y has height either h or h - 1,
 * and so the balance term on c is either +1 or +2, and it has height h + 2.
 * Finally, the height of Z is defined as h, and so a has balance term +2.  To
 * fix up all of these imbalances, we do one more rotation to pull c above a:
 *
 *                             (+0) c
 *                                /   \
 *                    (+0 or +1) b     a (+0 or -1)
 *                              / \   / \
 *                             W   X Y   Z
 *
 * The term on b is unchanged from the previous step and it is still at height
 * h + 1.  Since Z has height h and Y has height either h - 1 or h, a has
 * balance either +0 or -1, and is at height h + 1.  This means that node c
 * is at height h + 2 and has balance term 0.  However, notice that the height
 * of the root of this tree is now h + 2 instead of h + 3, meaning that the
 * balance terms of nodes above this one may need to be updated in response.
 *
 * The logic for removing a node from an AVL tree is similar.  We use standard
 * techniques to remove the node in question from the BST, then run a fixup
 * step like this one to fix all the imbalances in the tree.  This is tricky,
 * and the approach I've opted
 * to use is based on the discussion from the libavl discussion at
 * http://www.stanford.edu/~blp/avl/libavl.html/Deleting-from-a-BST.html.
 * However, I've opted to ignore their Case 2/Case 3 distinction, since I
 * don't see it as necessary.
 *
 * Case 1: If the node has no left child or no right child, we can just
 *         replace it with the child it does have (if any).
 *
 *                          a                a
 *                         / \              / \
 *                        Z   x     ->     Z   Y
 *                             \
 *                              Y
 *
 *         In this case, we need to begin a fixup pass from a, since the
 *         balance factors may have changed.
 *
 * Case 2: If the node has both children and its left child has a right child,
 *         then replace the node with its successor.  This works by
 *         identifying the node's successor in its left subtree, which is the
 *         leftmost node of the tree.  If it's not a leaf, then it's a node 
 *         missing a left child and we can easily delete it using the logic 
 *         in Case 1.  This raises the successor's subtree (if any) by one
 *         level in the tree.
 *
 * In both cases, there is some point in the tree in which some subtree's
 * height decreases by one, and we need to do apply the rebalance step to fix
 * it up.
 */
#ifndef AVLTree_Included
#define AVLTree_Included

#include <algorithm>   // For lexicographical_compare, equal, max
#include <functional>  // For less
#include <utility>     // For pair
#include <iterator>    // For iterator, reverse_iterator
#include <stdexcept>   // For out_of_range
#include <cassert>

/**
 * A map-like class backed by a AVL tree.
 */
template <typename Key, typename Value, typename Comparator = std::less<Key> >
class AVLTree {
public:
  /**
   * Constructor: AVLTree(Comparator comp = Comparator());
   * Usage: AVLTree<string, int> myAVLTree;
   * Usage: AVLTree<string, int> myAVLTree(MyComparisonFunction);
   * -------------------------------------------------------------------------
   * Constructs a new, empty AVL tree that uses the indicated comparator to
   * compare keys.
   */
  AVLTree(Comparator comp = Comparator());

  /**
   * Destructor: ~AVLTree();
   * Usage: (implicit)
   * -------------------------------------------------------------------------
   * Destroys the AVL tree, deallocating all memory allocated internally.
   */
  ~AVLTree();

  /**
   * Copy functions: AVLTree(const AVLTree& other);
   *                 AVLTree& operator= (const AVLTree& other);
   * Usage: AVLTree<string, int> one = two;
   *        one = two;
   * -------------------------------------------------------------------------
   * Makes this AVL tree equal to a deep-copy of some other AVL tree.
   */
  AVLTree(const AVLTree& other);
  AVLTree& operator= (const AVLTree& other);

  /**
   * Type: iterator
   * Type: const_iterator
   * -------------------------------------------------------------------------
   * A pair of types that can traverse the elements of an AVL tree in 
   * ascending order.
   */
  class iterator;
  class const_iterator;

  /**
   * Type: reverse_iterator
   * Type: const_reverse_iterator
   * -------------------------------------------------------------------------
   * A pair of types that can traverse the elements of an AVL tree in 
   * descending order.
   */
  typedef std::reverse_iterator<iterator> reverse_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

  /**
   * std::pair<iterator, bool> insert(const Key& key, const Value& value);
   * Usage: myAVLTree.insert("Skiplist", 137);
   * -------------------------------------------------------------------------
   * Inserts the specified key/value pair into the AVL tree.  If an entry with
   * the specified key already existed, this function returns false paired
   * with an iterator to the extant value.  If the entry was inserted
   * successfully, returns true paired with an iterator to the new element.
   */
  std::pair<iterator, bool> insert(const Key& key, const Value& value);

  /**
   * bool erase(const Key& key);
   * Usage: myAVLTree.erase("AVL Tree");
   * -------------------------------------------------------------------------
   * Removes the entry from the AVL tree with the specified key, if it exists.
   * Returns whether or not an element was erased.  All outstanding iterators
   * remain valid, except for those referencing the deleted element.
   */
  bool erase(const Key& key);

  /**
   * iterator erase(iterator where);
   * Usage: myAVLTree.erase(myAVLTree.begin());
   * -------------------------------------------------------------------------
   * Removes the entry referenced by the specified iterator from the tree,
   * returning an iterator to the next element in the sequence.
   */
  iterator erase(iterator where);

  /**
   * iterator find(const Key& key);
   * const_iterator find(const Key& key);
   * Usage: if (myAVLTree.find("Skiplist") != myAVLTree.end()) { ... }
   * -------------------------------------------------------------------------
   * Returns an iterator to the entry in the AVL tree with the specified key,
   * or end() as as sentinel if it does not exist.
   */
  iterator find(const Key& key);
  const_iterator find(const Key& key) const;

  /**
   * Value& operator[] (const Key& key);
   * Usage: myAVLTree["skiplist"] = 137;
   * -------------------------------------------------------------------------
   * Returns a reference to the value associated with the specified key in the
   * AVL tree.  If the key is not contained in the AVL tree, it will be 
   * inserted into the AVL tree with a default-constructed Entry as its value.
   */
  Value& operator[] (const Key& key);

  /**
   * Value& at(const Key& key);
   * const Value& at(const Key& key) const;
   * Usage: myAVLTree.at("skiplist") = 137;
   * -------------------------------------------------------------------------
   * Returns a reference to the value associated with the specified key,
   * throwing a std::out_of_range exception if the key does not exist in the
   * AVL tree.
   */
  Value& at(const Key& key);
  const Value& at(const Key& key) const;

  /**
   * (const_)iterator begin() (const);
   * (const_)iterator end() (const);
   * Usage: for (AVLTree<string, int>::iterator itr = t.begin(); 
   *             itr != t.end(); ++itr) { ... }
   * -------------------------------------------------------------------------
   * Returns iterators delineating the full contents of the AVL tree.  Each
   * iterator acts as a pointer to a std::pair<const Key, Entry>.
   */
  iterator begin();
  iterator end();
  const_iterator begin() const;
  const_iterator end() const;

  /**
   * (const_)reverse_iterator rbegin() (const);
   * (const_)reverse_iterator rend() (const);
   * Usage: for (AVLTree<string, int>::reverse_iterator itr = s.rbegin(); 
   *             itr != s.rend(); ++itr) { ... }
   * -------------------------------------------------------------------------
   * Returns iterators delineating the full contents of the AVL tree in 
   * reverse order.
   */
  reverse_iterator rbegin();
  reverse_iterator rend();
  const_reverse_iterator rbegin() const;
  const_reverse_iterator rend() const;

  /**
   * (const_)iterator lower_bound(const Key& key) (const);
   * (const_)iterator upper_bound(const Key& key) (const);
   * Usage: for (AVLTree<string, int>::iterator itr = t.lower_bound("AVL");
   *             itr != t.upper_bound("skiplist"); ++itr) { ... }
   * -------------------------------------------------------------------------
   * lower_bound returns an iterator to the first element in the AVL tree 
   * whose key is at least as large as key.  upper_bound returns an iterator 
   * to the first element in the AVL tree whose key is strictly greater than 
   * key.
   */
  iterator lower_bound(const Key& key);
  iterator upper_bound(const Key& key);
  const_iterator lower_bound(const Key& key) const;
  const_iterator upper_bound(const Key& key) const;

  /**
   * std::pair<(const_)iterator, (const_)iterator> 
   *    equal_range(const Key& key) (const);
   * Usage: std::pair<AVLTree<int, int>::iterator, AVLTree<int, int>::iterator>
   *          range = t.equal_range("AVL");
   * -------------------------------------------------------------------------
   * Returns a range of iterators spanning the unique copy of the entry whose
   * key is key if it exists, and otherwise a pair of iterators both pointing
   * to the spot in the AVL tree where the element would be if it were.
   */
  std::pair<iterator, iterator> equal_range(const Key& key);
  std::pair<const_iterator, const_iterator> equal_range(const Key& key) const;

  /**
   * size_t size() const;
   * Usage: cout << "AVLTree contains " << s.size() << " entries." << endl;
   * -------------------------------------------------------------------------
   * Returns the number of elements stored in the AVL tree.
   */
  size_t size() const;

  /**
   * bool empty() const;
   * Usage: if (s.empty()) { ... }
   * -------------------------------------------------------------------------
   * Returns whether the AVL tree contains no elements.
   */
  bool empty() const;

  /**
   * void swap(AVLTree& other);
   * Usage: one.swap(two);
   * -------------------------------------------------------------------------
   * Exchanges the contents of this AVL tree and some other AVL tree.  All
   * outstanding iterators are invalidated.
   */
  void swap(AVLTree& other);

private:
  /* A type representing a node in the AVL tree. */
  struct Node {
    std::pair<const Key, Value> mValue; // The actual value stored here

    /* The children are stored in an array to make it easier to implement tree
     * rotations.  The first entry is the left child, the second the right.
     */
    Node* mChildren[2];

    /* Pointer to the parent node. */
    Node* mParent;

    /* Pointer to the next and previous node in the sorted sequence. */
    Node* mNext, *mPrev;

    /* The height of this node, which is stored as an integer to make
     * subtraction easier.
     */
    int mHeight;

    /* Constructor sets up the value to the specified key/value pair with the
     * specified height.
     */
    Node(const Key& key, const Value& value, int height);
  };

  /* A pointer to the first and last elements of the AVL tree. */
  Node* mHead, *mTail;

  /* A pointer to the root of the tree. */
  Node* mRoot;
  
  /* The comparator to use when storing elements. */
  Comparator mComp;

  /* The number of elements in the list. */
  size_t mSize;

  /* A utility base class for iterator and const_iterator which actually
   * supplies all of the logic necessary for the two to work together.  The
   * parameters are the derived type, the type of a pointer being visited, and
   * the type of a reference being visited.  This uses the Curiously-Recurring
   * Template Pattern to work correctly.
   */
  template <typename DerivedType, typename Pointer, typename Reference>
  class IteratorBase;
  template <typename DerivedType, typename Pointer, typename Reference>
  friend class IteratorBase;

  /* Make iterator and const_iterator friends as well so they can use the
   * Node type.
   */
  friend class iterator;
  friend class const_iterator;

  /* A utility function to perform a tree rotation to pull the child above its
   * parent.  This function is semantically const but not bitwise const, since
   * it changes the structure but not the content of the elements being
   * stored.
   */
  void rotateUp(Node* child);

  /* A utility function that, given a node, returns the height of that node.
   * If the node is NULL, 0 is returned.
   */
  static int height(const Node* node);

  /* A utility function that, given a node, returns its balance factor. */
  static int balanceFactor(const Node* node);

  /* A utility function which does a BST search on the tree, looking for the
   * indicated node.  The return result is a pair of pointers, the first of
   * which is the node being searched for, or NULL if that node is not found.
   * The second node is that node's parent, which is either the parent of the
   * found node, or the last node visited in the tree before NULL was found
   * if the node was not found.
   */
  std::pair<Node*, Node*> findNode(const Key& key) const;

  /* A utility function which walks up from the indicated node up to the root,
   * performing the tree rotations necessary to restore the balances in the
   * tree.
   */
  void rebalanceFrom(Node* where);

  /* A utility function which, given a node with at most one child, splices
   * that node out of the tree by replacing it with its one child.  The next
   * and previous pointers of that node are not modified, since this function
   * can be used to structurally remove nodes from the tree while remembering
   * where they are in sorted order.
   */
  void spliceOut(Node* where);

  /* A utility function which, given a node and the node to use as its parent,
   * recursively deep-copies the tree rooted at that node, using the parent
   * node as the new tree's parent.
   */
  static Node* cloneTree(Node* toClone, Node* parent);

  /* A utility function which, given a tree and a pointer to the predecessor
   * of that tree, rewires the linked list in that tree to represent an
   * inorder traversal.  No fields are modified.  The return value is the node
   * with the highest key.
   */
  static Node* rethreadLinkedList(Node* root, Node* predecessor);
};

/* Comparison operators for AVLTrees. */
template <typename Key, typename Value, typename Comparator>
bool operator<  (const AVLTree<Key, Value, Comparator>& lhs,
                 const AVLTree<Key, Value, Comparator>& rhs);
template <typename Key, typename Value, typename Comparator>
bool operator<= (const AVLTree<Key, Value, Comparator>& lhs,
                 const AVLTree<Key, Value, Comparator>& rhs);
template <typename Key, typename Value, typename Comparator>
bool operator== (const AVLTree<Key, Value, Comparator>& lhs,
                 const AVLTree<Key, Value, Comparator>& rhs);
template <typename Key, typename Value, typename Comparator>
bool operator!= (const AVLTree<Key, Value, Comparator>& lhs,
                 const AVLTree<Key, Value, Comparator>& rhs);
template <typename Key, typename Value, typename Comparator>
bool operator>= (const AVLTree<Key, Value, Comparator>& lhs,
                 const AVLTree<Key, Value, Comparator>& rhs);
template <typename Key, typename Value, typename Comparator>
bool operator>  (const AVLTree<Key, Value, Comparator>& lhs,
                 const AVLTree<Key, Value, Comparator>& rhs);

/* * * * * Implementation Below This Point * * * * */

/* Definition of the IteratorBase type, which is used to provide a common
 * implementation for iterator and const_iterator.
 */
template <typename Key, typename Value, typename Comparator>
template <typename DerivedType, typename Pointer, typename Reference>
class AVLTree<Key, Value, Comparator>::IteratorBase {
public:
  /* Utility typedef to talk about nodes. */
  typedef typename AVLTree<Key, Value, Comparator>::Node Node;

  /* Advance operators just construct derived type instances of the proper
   * type, then advance them.
   */
  DerivedType& operator++ () {
    mCurr = mCurr->mNext;

    /* Downcast to our actual type. */
    return static_cast<DerivedType&>(*this);
  }
  const DerivedType operator++ (int) {
    /* Copy our current value by downcasting to our real type. */
    DerivedType result = static_cast<DerivedType&>(*this);

    /* Advance to the next element. */
    ++*this;

    /* Hand back the cached value. */
    return result;
  }

  /* Backup operators work on the same principle. */
  DerivedType& operator-- () {
    /* If the current pointer is NULL, it means that we've walked off the end
     * of the structure and need to back up a step.
     */
    if (mCurr == NULL) {
      mCurr = mOwner->mTail;
    }
    /* Otherwise, just back up a step. */
    else {
      mCurr = mCurr->mPrev;
    }

    /* Downcast to our actual type. */
    return static_cast<DerivedType&>(*this);
  }
  const DerivedType operator-- (int) {
    /* Copy our current value by downcasting to our real type. */
    DerivedType result = static_cast<DerivedType&>(*this);

    /* Back up a step. */
    --*this;

    /* Hand back the cached value. */
    return result;
  }

  /* Equality and disequality operators are parameterized - we'll allow anyone
   * whose type is IteratorBase to compare with us.  This means that we can
   * compare both iterator and const_iterator against one another.
   */
  template <typename DerivedType2, typename Pointer2, typename Reference2>
  bool operator== (const IteratorBase<DerivedType2, Pointer2, Reference2>& rhs) {
    /* Just check the underlying pointers, which (fortunately!) are of the 
     * same type.
     */
    return mOwner == rhs.mOwner && mCurr == rhs.mCurr;
  }
  template <typename DerivedType2, typename Pointer2, typename Reference2>
  bool operator!= (const IteratorBase<DerivedType2, Pointer2, Reference2>& rhs) {
    /* We are disequal if equality returns false. */
    return !(*this == rhs);
  }

  /* Pointer dereference operator hands back a reference. */
  Reference operator* () const {
    return mCurr->mValue;
  }
  
  /* Arrow operator returns a pointer. */
  Pointer operator-> () const {
    /* Use the standard "&**this" trick to dereference this object and return
     * a pointer to the referenced value.
     */
    return &**this;
  }

protected:
  /* Which AVLTree we belong to.  This pointer is const even though we are
   * possibly allowing ourselves to modify the AVL tree elements to avoid having
   * to duplicate this logic once again for const vs. non-const iterators.
   */
  const AVLTree* mOwner;

  /* Where we are in the list. */
  Node* mCurr;

  /* In order for equality comparisons to work correctly, all IteratorBases
   * must be friends of one another.
   */
  template <typename Derived2, typename Pointer2, typename Reference2>
  friend class IteratorBase;

  /* Constructor sets up the AVL tree and node pointers appropriately. */
  IteratorBase(const AVLTree* owner = NULL, Node* curr = NULL) 
  : mOwner(owner), mCurr(curr) {
    // Handled in initializer list
  }
};

/* iterator and const_iterator implementations work by deriving off of
 * IteratorBase, passing in parameters that make all the operators work.
 * Additionally, we inherit from std::iterator to import all the necessary
 * typedefs to qualify as an iterator.
 */
template <typename Key, typename Value, typename Comparator>
class AVLTree<Key, Value, Comparator>::iterator:
  public std::iterator< std::bidirectional_iterator_tag,
                        std::pair<const Key, Value> >,
  public IteratorBase<iterator,                       // Our type
                      std::pair<const Key, Value>*,   // Reference type
                      std::pair<const Key, Value>&> { // Pointer type 
public:
  /* Default constructor forwards NULL to base implicity. */
  iterator() {
    // Nothing to do here.
  }

  /* All major operations inherited from the base type. */

private:
  /* Constructor for creating an iterator out of a raw node just forwards this
   * argument to the base type.  This line is absolutely awful because the
   * type of the base is so complex.
   */
  iterator(const AVLTree* owner,
           typename AVLTree<Key, Value, Comparator>::Node* node) :
    IteratorBase<iterator,
                 std::pair<const Key, Value>*,
                 std::pair<const Key, Value>&>(owner, node) {
    // Handled by initializer list
  }

  /* Make the AVLTree a friend so it can call this constructor. */
  friend class AVLTree;

  /* Make const_iterator a friend so we can do iterator-to-const_iterator
   * conversions.
   */
  friend class const_iterator;
};

/* Same as above, but with const added in. */
template <typename Key, typename Value, typename Comparator>
class AVLTree<Key, Value, Comparator>::const_iterator:
  public std::iterator< std::bidirectional_iterator_tag,
                        const std::pair<const Key, Value> >,
  public IteratorBase<const_iterator,                       // Our type
                      const std::pair<const Key, Value>*,   // Reference type
                      const std::pair<const Key, Value>&> { // Pointer type 
public:
  /* Default constructor forwards NULL to base implicity. */
  const_iterator() {
    // Nothing to do here.
  }

  /* iterator conversion constructor forwards the other iterator's base fields
   * to the base class.
   */
  const_iterator(iterator itr) :
    IteratorBase<const_iterator,
                 const std::pair<const Key, Value>*,
                 const std::pair<const Key, Value>&>(itr.mOwner, itr.mCurr) {
    // Handled in initializer list
  }

  /* All major operations inherited from the base type. */

private:
  /* See iterator implementation for details about what this does. */
  const_iterator(const AVLTree* owner,
                 typename AVLTree<Key, Value, Comparator>::Node* node) :
    IteratorBase<const_iterator,
                 const std::pair<const Key, Value>*,
                 const std::pair<const Key, Value>&>(owner, node) {
    // Handled by initializer list
  }
  
  /* Make the AVLTree a friend so it can call this constructor. */
  friend class AVLTree;
};

/**** AVLTree::Node Implementation. ****/

/* Constructor sets up the key and value, then sets the height to one.  The
 * linked list fields are left uninitialized.
 */
template <typename Key, typename Value, typename Comparator>
AVLTree<Key, Value, Comparator>::Node::Node(const Key& key,
                                            const Value& value,
                                            int height) 
  : mValue(key, value), mHeight(height) {
  // Handled in initializer list.
}

/**** AVLTree Implementation ****/

/* Constructor sets up a new, empty AVLTree. */
template <typename Key, typename Value, typename Comparator>
AVLTree<Key, Value, Comparator>::AVLTree(Comparator comp) : mComp(comp) {
  /* Initially, the list of elements is empty and the tree is NULL. */
  mHead = mTail = mRoot = NULL;

  /* The tree is created empty. */
  mSize = 0;
}

/* Destructor walks the linked list of elements, deleting all nodes it
 * encounters.
 */
template <typename Key, typename Value, typename Comparator>
AVLTree<Key, Value, Comparator>::~AVLTree() {
  /* Start at the head of the list. */
  Node* curr = mHead;
  while (curr != NULL) {
    /* Cache the next value; we're about to blow up our only pointer to it. */
    Node* next = curr->mNext;

    /* Free memory, then go to the next node. */
    delete curr;
    curr = next;
  }
}

/* Inserting a node works by walking down the tree until the insert point is
 * found, adding the value, then fixing up the balance factors on each node.
 */
template <typename Key, typename Value, typename Comparator>
std::pair<typename AVLTree<Key, Value, Comparator>::iterator, bool>
AVLTree<Key, Value, Comparator>::insert(const Key& key, const Value& value) {
  /* Recursively walk down the tree from the root, looking for where the value
   * should go.  In the course of doing so, we'll maintain some extra
   * information about the node's successor and predecessor so that we can
   * wire the new node in in O(1) time.
   *
   * The information that we'll need will be the last nodes at which we
   * visited the left and right child.  This is because if the new node ends
   * up as a left child, then its predecessor is the last ancestor on the path
   * where we followed its right pointer, and vice-versa if the node ends up
   * as a right child.
   */
  Node* lastLeft = NULL, *lastRight = NULL;
  
  /* Also keep track of our current location as a pointer to the pointer in
   * the tree where the node will end up, which allows us to insert the node
   * by simply rewiring this pointer.
   */
  Node** curr   = &mRoot;

  /* Also track the last visited node. */
  Node*  parent = NULL;

  /* Now, do a standard binary tree insert.  If we ever find the node, we can
   * stop early.
   */
  while (*curr != NULL) {
    /* Update the parent to be this node, since it's the last one visited. */
    parent = *curr;

    /* Check whether we belong in the left subtree. */
    if (mComp(key, (*curr)->mValue.first)) {
      lastLeft = *curr;
      curr = &(*curr)->mChildren[0];
    }
    /* ... or perhaps the right subtree. */
    else if (mComp((*curr)->mValue.first, key)) {
      lastRight = *curr; // Last visited node where we went right.
      curr = &(*curr)->mChildren[1];
    }
    /* Otherwise, the key must already exist in the tree.  Return a pointer to
     * it.
     */
    else
      return std::make_pair(iterator(this, *curr), false);
  }

  /* At this point we've found our insertion point and can create the node
   * we're going to wire in.  Initially, it's at height 1.
   */
  Node* toInsert = new Node(key, value, 1);
  
  /* Splice it into the tree. */
  toInsert->mParent = parent;
  *curr = toInsert;

  /* The new node has no children. */
  toInsert->mChildren[0] = toInsert->mChildren[1] = NULL;

  /* Wire this node into the linked list in-between its predecessor and
   * successor in the tree.  The successor is the last node where we went
   * left, and the predecessor is the last node where we went right.
   */
  toInsert->mNext = lastLeft;
  toInsert->mPrev = lastRight;

  /* Update the previous pointer of the next entry, or change the list tail
   * if there is no next entry.
   */
  if (toInsert->mNext)
    toInsert->mNext->mPrev = toInsert;
  else
    mTail = toInsert;

  /* Update the next pointer of the previous entry similarly. */
  if (toInsert->mPrev)
    toInsert->mPrev->mNext = toInsert;
  else
    mHead = toInsert;
  
  /* Rebalance the tree from this node upward. */
  rebalanceFrom(toInsert);

  /* Increase the size of the tree, since we just added a node. */
  ++mSize;

  /* Hand back an iterator to the new element, along with a notification that
   * it was inserted correctly.
   */
  return std::make_pair(iterator(this, toInsert), true);
}

/* To perform a tree rotation, we identify whether we're doing a left or
 * right rotation, then rewrite pointers as follows:
 *
 * In a right rotation, we do the following:
 *
 *      B            A
 *     / \          / \
 *    A   2   -->  0   B
 *   / \              / \
 *  0   1            1   2
 *
 * In a left rotation, this runs backwards.
 *
 * The reason that we've implemented the nodes as an array of pointers rather
 * than using two named pointers is that the logic is symmetric.  If the node
 * is its left child, then its parent becomes its right child, and the node's
 * right child becomes the parent's left child.  If the node is its parent's
 * right child, then the node's parent becomes its left child and the node's
 * left child becomes the parent's right child.  In other words, the general
 * formula is
 *
 * If the node is its parent's SIDE child, then the parent becomes that node's
 * OPPOSITE-SIDE child, and the node's OPPOSITE-SIDE child becomes the
 * parent's SIDE child.
 *
 * This code also updates the root if the tree root gets rotated out.  It also
 * ensures that the heights of the rotated nodes are properly adjusted.
 */
template <typename Key, typename Value, typename Comparator>
void AVLTree<Key, Value, Comparator>::rotateUp(Node* node) {
  /* Determine which side the node is on.  It's on the left (side 0) if the
   * parent's first pointer matches it, and is on the right (side 1) if the
   * node's first pointer doesn't match it.  This is, coincidentally, whether
   * the node is not equal to the first pointer of its root.
   */
  const int side = (node != node->mParent->mChildren[0]);
  
  /* The other side is the logical negation of the side itself. */
  const int otherSide = !side;

  /* Cache the displaced child and parent of the current node. */
  Node* child  = node->mChildren[otherSide];
  Node* parent = node->mParent;
  
  /* Shuffle pointers around to make the node the parent of its parent. */
  node->mParent = parent->mParent;
  node->mChildren[otherSide] = parent;

  /* Shuffle around pointers so that the parent takes on the displaced
   * child.
   */
  parent->mChildren[side] = child;
  if (child)
    child->mParent = parent;

  /* Update the grandparent (if any) so that its child is now the rotated
   * element rather than the parent.  If there is no grandparent, the node is
   * now the root.
   */
  if (parent->mParent) {
    const int parentSide = (parent != parent->mParent->mChildren[0]);
    parent->mParent->mChildren[parentSide] = node;
  } else
    mRoot = node;

  /* In either case, change the parent so that it now treats the node as the
   * parent.
   */
  parent->mParent = node;

  /* Change the heights of the nodes.  Each node is now at a height one 
   * greater than the max height of its children.  We recompute the parent's
   * height first to ensure that any changes to it propagate correctly.
   */
  parent->mHeight = 1 + std::max(height(parent->mChildren[0]), 
                                 height(parent->mChildren[1]));
  node->mHeight = 1 + std::max(height(node->mChildren[0]), 
                               height(node->mChildren[1]));
}

/* To determine the height of a node, we just hand back the node's recorded
 * height, or 0 if the node is NULL.
 */
template <typename Key, typename Value, typename Comparator>
int AVLTree<Key, Value, Comparator>::height(const Node* node) {
  return node? node->mHeight : 0;
}

/* Computing the balance factor just computes the difference in heights
 * between a node's left and right children.
 */
template <typename Key, typename Value, typename Comparator>
int AVLTree<Key, Value, Comparator>::balanceFactor(const Node* node) {
  return height(node->mChildren[0]) - height(node->mChildren[1]);
}

/* Implementation of the logic for rebalancing the AVL tree via a series of
 * rotations.  This code computes the balance factor at each node and makes
 * one of the following two rotations if the balance is either +2 or -2:
 *
 * 1. If the child on the tall side has a balance factor whose sign isn't the
 *    opposite of the real node's balance factor, perform a single rotation
 *    from that child.
 * 2. If the child on the tall side has a balance factor whose sign is the
 *    opposite of the real node's balance factor, rotate its child on its
 *    tall side upward, then rotate it again with the original node.
 */
template <typename Key, typename Value, typename Comparator>
void AVLTree<Key, Value, Comparator>::rebalanceFrom(Node* where) {
  /* Start walking up from the node toward the root, checking for any new
   * imbalances and recomputing heights as appropriate.
   */
  while (where != NULL) {
    /* Recompute the height of this node. */
    where->mHeight = 1 + std::max(height(where->mChildren[0]), 
                                  height(where->mChildren[1]));


    /* Get the balance factor. */
    const int balance = balanceFactor(where);

    /* If the balance factor is +/- 2, we need to do some rotations. */
    if (balance == 2 || balance == -2) {
      /* Determine what child is on the heavy side.  If the balance is +2,
       * this is the left child (child 0), and if it's -2 it's the right child
       * (child 1).  We use the comparison balance == -2 for this, since its
       * values match what we need in this case.
       */
      Node* tallChild = where->mChildren[balance == -2];

      /* Check its balance factor and see what kind of rotation we need. */
      const int childBalance = balanceFactor(tallChild);

      /* We do a single rotation unless the child node is balanced opposite of
       * its parent.
       */
      if (childBalance == 0 || (childBalance < 0) == (balance < 0)) {
        rotateUp(tallChild);

        /* This node is now balanced, but we still need to update heights up
         * elsewhere in the tree.  Set the search to continue from the parent
         * of this node.
         */
        where = tallChild->mParent;
      }
      /* Otherwise, we need to do a double rotation. */
      else {
        /* We need a slightly different test to determine what child is heavy
         * since the balance is going to be +1 or -1 in this case.
         */
        Node* tallGrandchild = tallChild->mChildren[childBalance == -1];

        /* Rotate this node up twice. */
        rotateUp(tallGrandchild);
        rotateUp(tallGrandchild);

        /* Again, pick up the search from this point. */
        where = tallGrandchild->mParent;
      }
    }
    /* If we didn't end up doing any rotations, have the search go up one
     * level.
     */
    else {
      /* Pick up the search from the parent of this node. */
      where = where->mParent;
    }
  }
}

/* const version of find works by doing a standard BST search for the node in
 * question.
 */
template <typename Key, typename Value, typename Comparator>
typename AVLTree<Key, Value, Comparator>::const_iterator
AVLTree<Key, Value, Comparator>::find(const Key& key) const {
  /* Do a standard BST search and wrap up whataver we found. */
  return const_iterator(this, findNode(key).first);
}

/* Non-const version of find implemented in terms of const find. */
template <typename Key, typename Value, typename Comparator>
typename AVLTree<Key, Value, Comparator>::iterator
AVLTree<Key, Value, Comparator>::find(const Key& key) {
  /* Get the underlying const_iterator by calling the const version of this
   * function.
   */
  const_iterator itr = static_cast<const AVLTree*>(this)->find(key);

  /* Strip off the constness by wrapping it up as a raw iterator. */
  return iterator(itr.mOwner, itr.mCurr);
}

/* findNode just does a standard BST lookup, recording the last node that was
 * found before the one that was ultimately returned.
 */
template <typename Key, typename Value, typename Comparator>
std::pair<typename AVLTree<Key, Value, Comparator>::Node*,
          typename AVLTree<Key, Value, Comparator>::Node*>
AVLTree<Key, Value, Comparator>::findNode(const Key& key) const {
  /* Start the search at the root and work downwards.  Keep track of the last
   * node we visited.
   */
  Node* curr = mRoot, *prev = NULL;
  while (curr != NULL) {
    /* Update the prev pointer so that it tracks the last node we visited. */
    prev = curr;

    /* If the key is less than this node, go left. */
    if (mComp(key, curr->mValue.first))
      curr = curr->mChildren[0];
    /* Otherwise if the key is greater than the node, go right. */
    else if (mComp(curr->mValue.first, key))
      curr = curr->mChildren[1];
    /* Otherwise, we found the node.  Return that node and its parent as the
     * pair in question.  We explicitly use the parent here instead of prev
     * since the first part of this loop updates prev to be equal to curr.
     */
    else
      return std::make_pair(curr, curr->mParent);
  }

  /* If we ended up here, then we know that we didn't find the node in
   * question.  Handing back the pair of NULL and the most-recently-visited
   * node.  Note that due to the fact that NULL is #defined as zero, we have
   * to explicitly cast it to a Node* so that the template argument deduction
   * will work correctly; omitting this cast yields a pair<int, Node*>, which
   * gives a type error.
   */
  return std::make_pair((Node*)NULL, prev);
}

/* begin and end return iterators wrapping the head of the list or NULL,
 * respectively.
 */
template <typename Key, typename Value, typename Comparator>
typename AVLTree<Key, Value, Comparator>::iterator
AVLTree<Key, Value, Comparator>::begin() {
  return iterator(this, mHead);
}
template <typename Key, typename Value, typename Comparator>
typename AVLTree<Key, Value, Comparator>::const_iterator
AVLTree<Key, Value, Comparator>::begin() const {
  return iterator(this, mHead);
}
template <typename Key, typename Value, typename Comparator>
typename AVLTree<Key, Value, Comparator>::iterator
AVLTree<Key, Value, Comparator>::end() {
  return iterator(this, NULL);
}
template <typename Key, typename Value, typename Comparator>
typename AVLTree<Key, Value, Comparator>::const_iterator
AVLTree<Key, Value, Comparator>::end() const {
  return iterator(this, NULL);
}

/* rbegin and rend return wrapped versions of end() and begin(),
 * respectively.
 */
template <typename Key, typename Value, typename Comparator>
typename AVLTree<Key, Value, Comparator>::reverse_iterator
AVLTree<Key, Value, Comparator>::rbegin() {
  return reverse_iterator(end());
}
template <typename Key, typename Value, typename Comparator>
typename AVLTree<Key, Value, Comparator>::const_reverse_iterator
AVLTree<Key, Value, Comparator>::rbegin() const {
  return const_reverse_iterator(end());
}
template <typename Key, typename Value, typename Comparator>
typename AVLTree<Key, Value, Comparator>::reverse_iterator
AVLTree<Key, Value, Comparator>::rend() {
  return reverse_iterator(begin());
}
template <typename Key, typename Value, typename Comparator>
typename AVLTree<Key, Value, Comparator>::const_reverse_iterator
AVLTree<Key, Value, Comparator>::rend() const {
  return const_reverse_iterator(begin());
}

/* size just returns the cached size of the AVL tree. */
template <typename Key, typename Value, typename Comparator>
size_t AVLTree<Key, Value, Comparator>::size() const {
  return mSize;
}

/* empty returns whether the size is zero. */
template <typename Key, typename Value, typename Comparator>
bool AVLTree<Key, Value, Comparator>::empty() const {
  return size() == 0;
}

/* To splice out a node in the tree, we determine where its singleton child is
 * (if there even is one), then replace it with that node.
 */
template <typename Key, typename Value, typename Comparator>
void AVLTree<Key, Value, Comparator>::spliceOut(Node* node) {
  /* Confirm that this node has at most one child. */
  assert (!node->mChildren[0] || !node->mChildren[1]);

  /* For simplicity, cache the node's pointer. */
  Node* parent = node->mParent;

  /* Get a pointer to a child node that exists, if there even is a child
   * node that exists.  This works by seeing if the right child exists and
   * picking it if it does, and otherwise picking the left child.  If there
   * are no children this picks NULL, and otherwise picks the valid child.
   */
  const size_t childIndex = (node->mChildren[1] != NULL);
  Node* child = node->mChildren[childIndex];

  /* Make sure the other is NULL. */
  assert (node->mChildren[!childIndex] == NULL);
  
  /* If there is a child, change its parent to be the parent of the node
   * that's being deleted.
   */
  if (child)
    child->mParent = parent;
  
  /* Change the parent of the node being deleted to use the new child node
   * instead of the node to delete.  However, the node in question might be
   * the root, in which case we need to change the root of the tree.
   */
  if (parent) {
    /* We need to change the correct pointer in the parent.  If the node is
     * a right child, we should change the right pointer, and otherwise we
     * change the left pointer.
     */
    parent->mChildren[node == parent->mChildren[1]] = child;
  }
  /* If there is no parent, then the new node is at the root of the tree. */
  else
    mRoot = child;
}

/* Removing a node from the AVL tree is perhaps the most difficult part of the
 * implementation.  We first need to remove the node from the tree, which
 * requires us to do some special-casing logic to figure out what will replace
 * the node.  Then, we have to do a pass upward from where we did the switch 
 * to fix up the tree structure and confirm that the invariants hold.
 */
template <typename Key, typename Value, typename Comparator>
typename AVLTree<Key, Value, Comparator>::iterator
AVLTree<Key, Value, Comparator>::erase(iterator where) {
  /* Extract the node pointer from the iterator. */
  Node* node = where.mCurr;

  /* For simplicity, cache the parent pointer. */
  Node* parent = node->mParent;

  /* Drop the number of elements; we're about to remove something. */
  --mSize;

  /* There are two cases to consider here, both of which are outlined in the
   * file comments.  The first case comes up when we're removing a node that
   * does not have both children (easy), and the second when both children
   * are present (hard).
   */
  
  /* Case 1: Missing at least one child. */
  if (!node->mChildren[0] || !node->mChildren[1]) {
    spliceOut(node);
    rebalanceFrom(parent);
  }
  /* Case 2: Both children present.  Replace the node with its successor. */
  else {
    /* The successor node is, fortunately, encoded by the linked list
     * structure.
     */
    Node* successor = node->mNext;

    /* The successor shouldn't have a left child, since otherwise that would
     * be the real successor of this node.
     */
    assert (successor->mChildren[0] == NULL);

    /* Keep track of the parent of this node, since that's where we're going
     * to have to run the cleanup step from.
     */
    Node* successorParent = successor->mParent;

    /* Cut this node out from its parent, possibly splicing its child above
     * it.
     */
    spliceOut(successor);

    /* Now, replace the node to be removed with the successor.  This means
     * that we need to copy over the children and parents of the node to
     * remove into the successor, then fix the incoming pointers into the node
     * as well.
     */
    successor->mParent = parent;
    for (size_t i = 0; i < 2; ++i)
      successor->mChildren[i] = node->mChildren[i];
    
    /* Set the parents of the children to be this node.  We still need to
     * check that these nodes aren't NULL, because it's possible that the
     * successor node was a direct child and somehow got cut.
     */
    for (size_t i = 0; i < 2; ++i)
      if (successor->mChildren[i])
        successor->mChildren[i]->mParent = successor;

    /* Change the parent of this node to point back down at it, again
     * requiring some special-case logic.
     */
    if (parent) {
      /* Check whether the node to delete, NOT the successor, is a left child
       * because the successor node can't possibly be a child.
       */
      parent->mChildren[node == parent->mChildren[1]] = successor;
    }
    else
      mRoot = successor;

    /* Whew!  We've successfully spliced out the node.  Now, run a fixup pass
     * from where we cut the successor.  There are two cases to consider,
     * though.  First, if the successor node was a direct child of the node
     * that we're deleting, we need to run the fixup pass from the successor
     * node, which has been moved.  Second, if the successor was not a direct
     * child of the node to remove, then its parent might be dealing with an
     * imbalanced tree and we need to fix it up.
     */
    rebalanceFrom(node == successorParent? successor : successorParent);
  }

  /* We've now removed the node in question from the tree structure, and now
   * we need to remove it from the doubly-linked list.
   */

  /* If there is a next node, wire its previous pointer around the current
   * node.  Otherwise, the tail just changed.
   */
  if (node->mNext)
    node->mNext->mPrev = node->mPrev;
  else
    mTail = node->mPrev;

  /* If there is a previous node, wite its next pointer around the current
   * node.  Otherwise, the head just changed.
   */
  if (node->mPrev)
    node->mPrev->mNext = node->mNext;
  else
    mHead = node->mNext;

  /* Since we need to return an iterator to the element in the tree after this
   * one, we'll cache the next pointer of the node to delete.  It won't be
   * available after we delete the node.
   */
  iterator result(this, node->mNext);

  /* Free the node's resources. */
  delete node;
  return result;
}

/* Erasing a single value just calls find to locate the element and the
 * iterator version of erase to remove it.
 */
template <typename Key, typename Value, typename Comparator>
bool AVLTree<Key, Value, Comparator>::erase(const Key& key) {
  /* Look up where this node is, then remove it if it exists. */
  iterator where = find(key);
  if (where == end()) return false;

  erase(where);
  return true;
}

/* Square brackets implemented in terms of insert(). */
template <typename Key, typename Value, typename Comparator>
Value& AVLTree<Key, Value, Comparator>::operator[] (const Key& key) {
  /* Call insert to get a pair of an iterator and a bool.  Look at the
   * iterator, then consider its second field.
   */
  return insert(key, Value()).first->second;
}

/* at implemented in terms of find. */
template <typename Key, typename Value, typename Comparator>
const Value& AVLTree<Key, Value, Comparator>::at(const Key& key) const {
  /* Look up the key, failing if we can't find it. */
  const_iterator result = find(key);
  if (result == end())
    throw std::out_of_range("Key not found in AVL tree.");

  /* Otherwise just return the value field. */
  return result->second;
}

/* non-const at implemented in terms of at using the const_cast/static_cast
 * trick.
 */
template <typename Key, typename Value, typename Comparator>
Value& AVLTree<Key, Value, Comparator>::at(const Key& key) {
  return const_cast<Value&>(static_cast<const AVLTree*>(this)->at(key));
}

/* The copy constructor is perhaps the most complex part of this entire
 * implementation.  It works in two passes.  First, the tree structure itself
 * is duplicated, without paying any attention to the next and previous
 * pointers threaded through.  Next, we run a recursive pass over the cloned
 * tree, fixing up all of the next and previous pointers as we go.
 */
template <typename Key, typename Value, typename Comparator>
AVLTree<Key, Value, Comparator>::AVLTree(const AVLTree& other) {
  /* Start off with the simple bits - copy over the size field and 
   * comparator. 
   */
  mSize = other.mSize;
  mComp = other.mComp;

  /* Clone the tree structure. */
  mRoot = cloneTree(other.mRoot, NULL);

  /* Rectify the linked list. */
  rethreadLinkedList(mRoot, NULL);

  /* Finally, fix up the first and last pointers of the list by looking for
   * the smallest and largest elements in the tree.
   */
  mTail = mHead = mRoot;
  while (mHead && mHead->mChildren[0]) mHead = mHead->mChildren[0];
  while (mTail && mTail->mChildren[1]) mTail = mTail->mChildren[1];
}

/* Cloning a tree is a simple structural recursion. */
template <typename Key, typename Value, typename Comparator>
typename AVLTree<Key, Value, Comparator>::Node*
AVLTree<Key, Value, Comparator>::cloneTree(Node* toClone, Node* parent) {
  /* Base case: the clone of the empty tree is that tree itself. */
  if (toClone == NULL) return NULL;

  /* Create a copy of the node, moving over the height and key/value pair */
  Node* result = new Node(toClone->mValue.first, toClone->mValue.second,
                          toClone->mHeight);

  /* Recursively clone the subtrees. */
  for (int i = 0; i < 2; ++i)
    result->mChildren[i] = cloneTree(toClone->mChildren[i], result);

  /* Set the parent. */
  result->mParent = parent;

  return result;
}

/* Fixing up the doubly-linked list is a bit tricky.  The function acts as an
 * inorder traversal.  We first fix up the left subtree, getting a pointer to
 * the node holding the largest value in that subtree (the predecessor of this
 * node).  We then chain the current node into the linked list, then fix up
 * the nodes to the right (which have the current node as their predecessor).
 */
template <typename Key, typename Value, typename Comparator>
typename AVLTree<Key, Value, Comparator>::Node*
AVLTree<Key, Value, Comparator>::rethreadLinkedList(Node* root, Node* predecessor) {
  /* Base case: if the root is null, then the largest element visited so far
   * is whatever we were told it was.
   */
  if (root == NULL) return predecessor;

  /* Otherwise, recursively fix up the left subtree using the actual
   * predecessor.  Store the return value as the new predecessor.
   */
  predecessor = rethreadLinkedList(root->mChildren[0], predecessor);

  /* Add ourselves to the linked list. */
  root->mPrev = predecessor;
  if (predecessor)
    predecessor->mNext = root;
  root->mNext = NULL;

  /* Recursively invoke on the right subtree, passing in this node as the
   * predecessor.
   */
  return rethreadLinkedList(root->mChildren[1], root);
}

/* Assignment operator implemented using copy-and-swap. */
template <typename Key, typename Value, typename Comparator>
AVLTree<Key, Value, Comparator>&
AVLTree<Key, Value, Comparator>::operator= (const AVLTree& other) {
  AVLTree clone = other;
  swap(clone);
  return *this;
}

/* swap just does an element-by-element swap. */
template <typename Key, typename Value, typename Comparator>
void AVLTree<Key, Value, Comparator>::swap(AVLTree& other) {
  /* Use std::swap to get the job done. */
  std::swap(mRoot, other.mRoot);
  std::swap(mSize, other.mSize);
  std::swap(mHead, other.mHead);
  std::swap(mTail, other.mTail);
  std::swap(mComp, other.mComp);
}

/* lower_bound works by walking down the tree to where the node belongs.  If
 * it's in the tree, then it's its own lower bound.  Otherwise, we either
 * found the predecessor or successor of the node in question, and correct it
 * to the resulting node.
 */
template <typename Key, typename Value, typename Comparator>
typename AVLTree<Key, Value, Comparator>::const_iterator
AVLTree<Key, Value, Comparator>::lower_bound(const Key& key) const {
  /* One unusual edge case that complicates the logic here is what to do if
   * the tree is empty.  If this happens, then the lower_bound is end().
   */
  if (empty()) return end();

  /* Locate the node in question. */
  std::pair<Node*, Node*> result = findNode(key);

  /* If we found the node we wanted, we can just wrap it up as an iterator. */
  if (result.first)
    return iterator(this, result.first);

  /* Otherwise, the value isn't here, but we do know the value in the tree
   * that would be its parent.  This value is therefore either the predecessor
   * or the successor of the value in question.  If it's the predecessor, then
   * we need to advance it forward one step to get the smallest value greater
   * than the indicated key.  Note that we can assume that there is some
   * predecessor, since we know that the tree is not empty.
   *
   * To check whether we're looking at the predecessor, we're curious whether
   * the key field of the value of the node of the second Node*.  Phew!
   */
  if (mComp(result.second->mValue.first, key))
    result.second = result.second->mNext;
  
  return iterator(this, result.second);
}

/* Non-const version of this function implemented by calling the const version
 * and stripping constness.
 */
template <typename Key, typename Value, typename Comparator>
typename AVLTree<Key, Value, Comparator>::iterator
AVLTree<Key, Value, Comparator>::lower_bound(const Key& key) {
  /* Call the const version to get the answer. */
  const_iterator result = static_cast<const AVLTree*>(this)->lower_bound(key);

  /* Rewrap it in a regular iterator to remove constness. */
  return iterator(result.mOwner, result.mCurr);
}

/* equal_range looks up where the node should be.  If it finds it, it hands
 * back iterators spanning it.  If not, it just hands back two iterators to the
 * same spot.
 */
template <typename Key, typename Value, typename Comparator>
std::pair<typename AVLTree<Key, Value, Comparator>::const_iterator,
          typename AVLTree<Key, Value, Comparator>::const_iterator>
AVLTree<Key, Value, Comparator>::equal_range(const Key& key) const {
  /* Call lower_bound to find out where we should start looking. */
  std::pair<const_iterator, const_iterator> result;
  result.first = result.second = lower_bound(key);

  /* If we hit the end, we're done. */
  if (result.first == end()) return result;

  /* Otherwise, check whether the iterator we found matches the value.  If so,
   * bump the second iterator one step.
   */
  if (!mComp(key, result.second->first))
    ++result.second;

  return result;
}

/* Non-const version calls the const version, then strips off constness. */
template <typename Key, typename Value, typename Comparator>
std::pair<typename AVLTree<Key, Value, Comparator>::iterator,
          typename AVLTree<Key, Value, Comparator>::iterator>
AVLTree<Key, Value, Comparator>::equal_range(const Key& key) {
  /* Invoke const version to get the iterators. */
  std::pair<const_iterator, const_iterator> result =
    static_cast<const AVLTree*>(this)->equal_range(key);

  /* Unwrap into regular iterators. */
  return std::make_pair(iterator(result.first.mOwner,  result.first.mCurr),
                        iterator(result.second.mOwner, result.second.mCurr));
}

/* upper_bound just calls equal_range and returns the second value. */
template <typename Key, typename Value, typename Comparator>
typename AVLTree<Key, Value, Comparator>::iterator
AVLTree<Key, Value, Comparator>::upper_bound(const Key& key) {
  return equal_range(key).second;
}
template <typename Key, typename Value, typename Comparator>
typename AVLTree<Key, Value, Comparator>::const_iterator
AVLTree<Key, Value, Comparator>::upper_bound(const Key& key) const {
  return equal_range(key).second;
}

/* Comparison operators == and < use the standard STL algorithms. */
template <typename Key, typename Value, typename Comparator>
bool operator<  (const AVLTree<Key, Value, Comparator>& lhs,
                 const AVLTree<Key, Value, Comparator>& rhs) {
  return std::lexicographical_compare(lhs.begin(), lhs.end(),
                                      rhs.begin(), rhs.end());
}
template <typename Key, typename Value, typename Comparator>
bool operator== (const AVLTree<Key, Value, Comparator>& lhs,
                 const AVLTree<Key, Value, Comparator>& rhs) {
  return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), 
                                                rhs.begin());
}

/* Remaining comparisons implemented in terms of the above comparisons. */
template <typename Key, typename Value, typename Comparator>
bool operator<= (const AVLTree<Key, Value, Comparator>& lhs,
                 const AVLTree<Key, Value, Comparator>& rhs) {
  /* x <= y   iff !(x > y)   iff !(y < x) */
  return !(rhs < lhs);
}
template <typename Key, typename Value, typename Comparator>
bool operator!= (const AVLTree<Key, Value, Comparator>& lhs,
                 const AVLTree<Key, Value, Comparator>& rhs) {
  return !(lhs == rhs);
}
template <typename Key, typename Value, typename Comparator>
bool operator>= (const AVLTree<Key, Value, Comparator>& lhs,
                 const AVLTree<Key, Value, Comparator>& rhs) {
  /* x >= y   iff !(x < y) */
  return !(lhs < rhs);
}
template <typename Key, typename Value, typename Comparator>

bool operator>  (const AVLTree<Key, Value, Comparator>& lhs,
                 const AVLTree<Key, Value, Comparator>& rhs) {
  /* x > y iff y < x */
  return rhs < lhs;
}

#endif