/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

// Portions of this file were originally under the following license:
//
// Copyright (C) 2008 Jason Evans <jasone@FreeBSD.org>.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
// 1. Redistributions of source code must retain the above copyright
//    notice(s), this list of conditions and the following disclaimer
//    unmodified other than the allowable addition of one or more
//    copyright notices.
// 2. Redistributions in binary form must reproduce the above copyright
//    notice(s), this list of conditions and the following disclaimer in
//    the documentation and/or other materials provided with the
//    distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY
// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
// PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
// BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
// WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
// OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
// EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// ****************************************************************************
//
// C++ template implementation of left-leaning red-black trees.
//
// All operations are done non-recursively.  Parent pointers are not used, and
// color bits are stored in the least significant bit of right-child pointers,
// thus making node linkage as compact as is possible for red-black trees.
//
// The RedBlackTree template expects two type arguments: the type of the nodes,
// containing a RedBlackTreeNode, and a trait providing two methods:
//  - a GetTreeNode method that returns a reference to the RedBlackTreeNode
//    corresponding to a given node with the following signature:
//      static RedBlackTreeNode<T>& GetTreeNode(T*)
//  - a Compare function with the following signature:
//      static Order Compare(T* aNode, T* aOther)
//                              ^^^^^
//                           or aKey
//
// Interpretation of comparision function return values:
//
//   Order::eLess: aNode <  aOther
//   Order::eEqual: aNode == aOther
//   Order::eGreater: aNode >  aOther
//
// In all cases, the aNode or aKey argument is the first argument to the
// comparison function, which makes it possible to write comparison functions
// that treat the first argument specially.
//
// ***************************************************************************

#ifndef RB_H_
#define RB_H_

#include "mozilla/Alignment.h"
#include "mozilla/Assertions.h"
#include "Utils.h"

enum NodeColor {
  Black = 0,
  Red = 1,
};

// Node structure.
template <typename T>
class RedBlackTreeNode {
  T* mLeft;
  // The lowest bit is the color
  T* mRightAndColor;

 public:
  T* Left() { return mLeft; }

  void SetLeft(T* aValue) { mLeft = aValue; }

  T* Right() {
    return reinterpret_cast<T*>(reinterpret_cast<uintptr_t>(mRightAndColor) &
                                uintptr_t(~1));
  }

  void SetRight(T* aValue) {
    mRightAndColor = reinterpret_cast<T*>(
        (reinterpret_cast<uintptr_t>(aValue) & uintptr_t(~1)) | Color());
  }

  NodeColor Color() {
    return static_cast<NodeColor>(reinterpret_cast<uintptr_t>(mRightAndColor) &
                                  1);
  }

  bool IsBlack() { return Color() == NodeColor::Black; }

  bool IsRed() { return Color() == NodeColor::Red; }

  void SetColor(NodeColor aColor) {
    mRightAndColor = reinterpret_cast<T*>(
        (reinterpret_cast<uintptr_t>(mRightAndColor) & uintptr_t(~1)) | aColor);
  }
};

// Tree structure.
template <typename T, typename Trait>
class RedBlackTree {
 public:
  void Init() { mRoot = nullptr; }

  T* First(T* aStart = nullptr) { return First(TreeNode(aStart)).Get(); }

  T* Last(T* aStart = nullptr) { return Last(TreeNode(aStart)).Get(); }

  T* Next(T* aNode) { return Next(TreeNode(aNode)).Get(); }

  T* Prev(T* aNode) { return Prev(TreeNode(aNode)).Get(); }

  T* Search(T* aKey) { return Search(TreeNode(aKey)).Get(); }

  // Find a match if it exists. Otherwise, find the next greater node, if one
  // exists.
  T* SearchOrNext(T* aKey) { return SearchOrNext(TreeNode(aKey)).Get(); }

  void Insert(T* aNode) { Insert(TreeNode(aNode)); }

  void Remove(T* aNode) { Remove(TreeNode(aNode)); }

  // Helper class to avoid having all the tree traversal code further below
  // have to use Trait::GetTreeNode and do manual null pointer checks, adding
  // visual noise. Practically speaking TreeNode(nullptr) acts as a virtual
  // sentinel, that loops back to itself for Left() and Right() and is always
  // black.
  class TreeNode {
   public:
    constexpr TreeNode() : mNode(nullptr) {}

    MOZ_IMPLICIT TreeNode(T* aNode) : mNode(aNode) {}

    TreeNode& operator=(TreeNode aOther) {
      mNode = aOther.mNode;
      return *this;
    }

    TreeNode Left() {
      return TreeNode(mNode ? Trait::GetTreeNode(mNode).Left() : nullptr);
    }

    void SetLeft(TreeNode aNode) {
      MOZ_RELEASE_ASSERT(mNode);
      Trait::GetTreeNode(mNode).SetLeft(aNode.mNode);
    }

    TreeNode Right() {
      return TreeNode(mNode ? Trait::GetTreeNode(mNode).Right() : nullptr);
    }

    void SetRight(TreeNode aNode) {
      MOZ_RELEASE_ASSERT(mNode);
      Trait::GetTreeNode(mNode).SetRight(aNode.mNode);
    }

    NodeColor Color() {
      return mNode ? Trait::GetTreeNode(mNode).Color() : NodeColor::Black;
    }

    bool IsRed() { return Color() == NodeColor::Red; }

    bool IsBlack() { return Color() == NodeColor::Black; }

    void SetColor(NodeColor aColor) {
      MOZ_RELEASE_ASSERT(mNode);
      Trait::GetTreeNode(mNode).SetColor(aColor);
    }

    T* Get() { return mNode; }

    MOZ_IMPLICIT operator bool() { return !!mNode; }

    bool operator==(TreeNode& aOther) { return mNode == aOther.mNode; }

   private:
    T* mNode;
  };

 private:
  // Ideally we'd use a TreeNode for mRoot, but we need RedBlackTree to stay
  // a POD type to avoid a static initializer for gArenas.
  T* mRoot;

  TreeNode First(TreeNode aStart) {
    TreeNode ret;
    for (ret = aStart ? aStart : mRoot; ret.Left(); ret = ret.Left()) {
    }
    return ret;
  }

  TreeNode Last(TreeNode aStart) {
    TreeNode ret;
    for (ret = aStart ? aStart : mRoot; ret.Right(); ret = ret.Right()) {
    }
    return ret;
  }

  TreeNode Next(TreeNode aNode) {
    TreeNode ret;
    if (aNode.Right()) {
      ret = First(aNode.Right());
    } else {
      TreeNode rbp_n_t = mRoot;
      MOZ_ASSERT(rbp_n_t);
      ret = nullptr;
      while (true) {
        Order rbp_n_cmp = Trait::Compare(aNode.Get(), rbp_n_t.Get());
        if (rbp_n_cmp == Order::eLess) {
          ret = rbp_n_t;
          rbp_n_t = rbp_n_t.Left();
        } else if (rbp_n_cmp == Order::eGreater) {
          rbp_n_t = rbp_n_t.Right();
        } else {
          break;
        }
        MOZ_ASSERT(rbp_n_t);
      }
    }
    return ret;
  }

  TreeNode Prev(TreeNode aNode) {
    TreeNode ret;
    if (aNode.Left()) {
      ret = Last(aNode.Left());
    } else {
      TreeNode rbp_p_t = mRoot;
      MOZ_ASSERT(rbp_p_t);
      ret = nullptr;
      while (true) {
        Order rbp_p_cmp = Trait::Compare(aNode.Get(), rbp_p_t.Get());
        if (rbp_p_cmp == Order::eLess) {
          rbp_p_t = rbp_p_t.Left();
        } else if (rbp_p_cmp == Order::eGreater) {
          ret = rbp_p_t;
          rbp_p_t = rbp_p_t.Right();
        } else {
          break;
        }
        MOZ_ASSERT(rbp_p_t);
      }
    }
    return ret;
  }

  TreeNode Search(TreeNode aKey) {
    TreeNode ret = mRoot;
    Order rbp_se_cmp;
    while (ret && (rbp_se_cmp = Trait::Compare(aKey.Get(), ret.Get())) !=
                      Order::eEqual) {
      if (rbp_se_cmp == Order::eLess) {
        ret = ret.Left();
      } else {
        ret = ret.Right();
      }
    }
    return ret;
  }

  TreeNode SearchOrNext(TreeNode aKey) {
    TreeNode ret = nullptr;
    TreeNode rbp_ns_t = mRoot;
    while (rbp_ns_t) {
      Order rbp_ns_cmp = Trait::Compare(aKey.Get(), rbp_ns_t.Get());
      if (rbp_ns_cmp == Order::eLess) {
        ret = rbp_ns_t;
        rbp_ns_t = rbp_ns_t.Left();
      } else if (rbp_ns_cmp == Order::eGreater) {
        rbp_ns_t = rbp_ns_t.Right();
      } else {
        ret = rbp_ns_t;
        break;
      }
    }
    return ret;
  }

  void Insert(TreeNode aNode) {
    // rbp_i_s is only used as a placeholder for its RedBlackTreeNode. Use
    // AlignedStorage2 to avoid running the TreeNode base class constructor.
    mozilla::AlignedStorage2<T> rbp_i_s;
    TreeNode rbp_i_g, rbp_i_p, rbp_i_c, rbp_i_t, rbp_i_u;
    Order rbp_i_cmp = Order::eEqual;
    rbp_i_g = nullptr;
    rbp_i_p = rbp_i_s.addr();
    rbp_i_p.SetLeft(mRoot);
    rbp_i_p.SetRight(nullptr);
    rbp_i_p.SetColor(NodeColor::Black);
    rbp_i_c = mRoot;
    // Iteratively search down the tree for the insertion point,
    // splitting 4-nodes as they are encountered. At the end of each
    // iteration, rbp_i_g->rbp_i_p->rbp_i_c is a 3-level path down
    // the tree, assuming a sufficiently deep tree.
    while (rbp_i_c) {
      rbp_i_t = rbp_i_c.Left();
      rbp_i_u = rbp_i_t.Left();
      if (rbp_i_t.IsRed() && rbp_i_u.IsRed()) {
        // rbp_i_c is the top of a logical 4-node, so split it.
        // This iteration does not move down the tree, due to the
        // disruptiveness of node splitting.
        //
        // Rotate right.
        rbp_i_t = RotateRight(rbp_i_c);
        // Pass red links up one level.
        rbp_i_u = rbp_i_t.Left();
        rbp_i_u.SetColor(NodeColor::Black);
        if (rbp_i_p.Left() == rbp_i_c) {
          rbp_i_p.SetLeft(rbp_i_t);
          rbp_i_c = rbp_i_t;
        } else {
          // rbp_i_c was the right child of rbp_i_p, so rotate
          // left in order to maintain the left-leaning invariant.
          MOZ_ASSERT(rbp_i_p.Right() == rbp_i_c);
          rbp_i_p.SetRight(rbp_i_t);
          rbp_i_u = LeanLeft(rbp_i_p);
          if (rbp_i_g.Left() == rbp_i_p) {
            rbp_i_g.SetLeft(rbp_i_u);
          } else {
            MOZ_ASSERT(rbp_i_g.Right() == rbp_i_p);
            rbp_i_g.SetRight(rbp_i_u);
          }
          rbp_i_p = rbp_i_u;
          rbp_i_cmp = Trait::Compare(aNode.Get(), rbp_i_p.Get());
          if (rbp_i_cmp == Order::eLess) {
            rbp_i_c = rbp_i_p.Left();
          } else {
            MOZ_ASSERT(rbp_i_cmp == Order::eGreater);
            rbp_i_c = rbp_i_p.Right();
          }
          continue;
        }
      }
      rbp_i_g = rbp_i_p;
      rbp_i_p = rbp_i_c;
      rbp_i_cmp = Trait::Compare(aNode.Get(), rbp_i_c.Get());
      if (rbp_i_cmp == Order::eLess) {
        rbp_i_c = rbp_i_c.Left();
      } else {
        MOZ_ASSERT(rbp_i_cmp == Order::eGreater);
        rbp_i_c = rbp_i_c.Right();
      }
    }
    // rbp_i_p now refers to the node under which to insert.
    aNode.SetLeft(nullptr);
    aNode.SetRight(nullptr);
    aNode.SetColor(NodeColor::Red);
    if (rbp_i_cmp == Order::eGreater) {
      rbp_i_p.SetRight(aNode);
      rbp_i_t = LeanLeft(rbp_i_p);
      if (rbp_i_g.Left() == rbp_i_p) {
        rbp_i_g.SetLeft(rbp_i_t);
      } else if (rbp_i_g.Right() == rbp_i_p) {
        rbp_i_g.SetRight(rbp_i_t);
      }
    } else {
      rbp_i_p.SetLeft(aNode);
    }
    // Update the root and make sure that it is black.
    TreeNode root = TreeNode(rbp_i_s.addr()).Left();
    root.SetColor(NodeColor::Black);
    mRoot = root.Get();
  }

  void Remove(TreeNode aNode) {
    // rbp_r_s is only used as a placeholder for its RedBlackTreeNode. Use
    // AlignedStorage2 to avoid running the TreeNode base class constructor.
    mozilla::AlignedStorage2<T> rbp_r_s;
    TreeNode rbp_r_p, rbp_r_c, rbp_r_xp, rbp_r_t, rbp_r_u;
    Order rbp_r_cmp;
    rbp_r_p = TreeNode(rbp_r_s.addr());
    rbp_r_p.SetLeft(mRoot);
    rbp_r_p.SetRight(nullptr);
    rbp_r_p.SetColor(NodeColor::Black);
    rbp_r_c = mRoot;
    rbp_r_xp = nullptr;
    // Iterate down the tree, but always transform 2-nodes to 3- or
    // 4-nodes in order to maintain the invariant that the current
    // node is not a 2-node. This allows simple deletion once a leaf
    // is reached. Handle the root specially though, since there may
    // be no way to convert it from a 2-node to a 3-node.
    rbp_r_cmp = Trait::Compare(aNode.Get(), rbp_r_c.Get());
    if (rbp_r_cmp == Order::eLess) {
      rbp_r_t = rbp_r_c.Left();
      rbp_r_u = rbp_r_t.Left();
      if (rbp_r_t.IsBlack() && rbp_r_u.IsBlack()) {
        // Apply standard transform to prepare for left move.
        rbp_r_t = MoveRedLeft(rbp_r_c);
        rbp_r_t.SetColor(NodeColor::Black);
        rbp_r_p.SetLeft(rbp_r_t);
        rbp_r_c = rbp_r_t;
      } else {
        // Move left.
        rbp_r_p = rbp_r_c;
        rbp_r_c = rbp_r_c.Left();
      }
    } else {
      if (rbp_r_cmp == Order::eEqual) {
        MOZ_ASSERT(aNode == rbp_r_c);
        if (!rbp_r_c.Right()) {
          // Delete root node (which is also a leaf node).
          if (rbp_r_c.Left()) {
            rbp_r_t = LeanRight(rbp_r_c);
            rbp_r_t.SetRight(nullptr);
          } else {
            rbp_r_t = nullptr;
          }
          rbp_r_p.SetLeft(rbp_r_t);
        } else {
          // This is the node we want to delete, but we will
          // instead swap it with its successor and delete the
          // successor. Record enough information to do the
          // swap later. rbp_r_xp is the aNode's parent.
          rbp_r_xp = rbp_r_p;
          rbp_r_cmp = Order::eGreater;  // Note that deletion is incomplete.
        }
      }
      if (rbp_r_cmp == Order::eGreater) {
        if (rbp_r_c.Right().Left().IsBlack()) {
          rbp_r_t = rbp_r_c.Left();
          if (rbp_r_t.IsRed()) {
            // Standard transform.
            rbp_r_t = MoveRedRight(rbp_r_c);
          } else {
            // Root-specific transform.
            rbp_r_c.SetColor(NodeColor::Red);
            rbp_r_u = rbp_r_t.Left();
            if (rbp_r_u.IsRed()) {
              rbp_r_u.SetColor(NodeColor::Black);
              rbp_r_t = RotateRight(rbp_r_c);
              rbp_r_u = RotateLeft(rbp_r_c);
              rbp_r_t.SetRight(rbp_r_u);
            } else {
              rbp_r_t.SetColor(NodeColor::Red);
              rbp_r_t = RotateLeft(rbp_r_c);
            }
          }
          rbp_r_p.SetLeft(rbp_r_t);
          rbp_r_c = rbp_r_t;
        } else {
          // Move right.
          rbp_r_p = rbp_r_c;
          rbp_r_c = rbp_r_c.Right();
        }
      }
    }
    if (rbp_r_cmp != Order::eEqual) {
      while (true) {
        MOZ_ASSERT(rbp_r_p);
        rbp_r_cmp = Trait::Compare(aNode.Get(), rbp_r_c.Get());
        if (rbp_r_cmp == Order::eLess) {
          rbp_r_t = rbp_r_c.Left();
          if (!rbp_r_t) {
            // rbp_r_c now refers to the successor node to
            // relocate, and rbp_r_xp/aNode refer to the
            // context for the relocation.
            if (rbp_r_xp.Left() == aNode) {
              rbp_r_xp.SetLeft(rbp_r_c);
            } else {
              MOZ_ASSERT(rbp_r_xp.Right() == (aNode));
              rbp_r_xp.SetRight(rbp_r_c);
            }
            rbp_r_c.SetLeft(aNode.Left());
            rbp_r_c.SetRight(aNode.Right());
            rbp_r_c.SetColor(aNode.Color());
            if (rbp_r_p.Left() == rbp_r_c) {
              rbp_r_p.SetLeft(nullptr);
            } else {
              MOZ_ASSERT(rbp_r_p.Right() == rbp_r_c);
              rbp_r_p.SetRight(nullptr);
            }
            break;
          }
          rbp_r_u = rbp_r_t.Left();
          if (rbp_r_t.IsBlack() && rbp_r_u.IsBlack()) {
            rbp_r_t = MoveRedLeft(rbp_r_c);
            if (rbp_r_p.Left() == rbp_r_c) {
              rbp_r_p.SetLeft(rbp_r_t);
            } else {
              rbp_r_p.SetRight(rbp_r_t);
            }
            rbp_r_c = rbp_r_t;
          } else {
            rbp_r_p = rbp_r_c;
            rbp_r_c = rbp_r_c.Left();
          }
        } else {
          // Check whether to delete this node (it has to be
          // the correct node and a leaf node).
          if (rbp_r_cmp == Order::eEqual) {
            MOZ_ASSERT(aNode == rbp_r_c);
            if (!rbp_r_c.Right()) {
              // Delete leaf node.
              if (rbp_r_c.Left()) {
                rbp_r_t = LeanRight(rbp_r_c);
                rbp_r_t.SetRight(nullptr);
              } else {
                rbp_r_t = nullptr;
              }
              if (rbp_r_p.Left() == rbp_r_c) {
                rbp_r_p.SetLeft(rbp_r_t);
              } else {
                rbp_r_p.SetRight(rbp_r_t);
              }
              break;
            }
            // This is the node we want to delete, but we
            // will instead swap it with its successor
            // and delete the successor. Record enough
            // information to do the swap later.
            // rbp_r_xp is aNode's parent.
            rbp_r_xp = rbp_r_p;
          }
          rbp_r_t = rbp_r_c.Right();
          rbp_r_u = rbp_r_t.Left();
          if (rbp_r_u.IsBlack()) {
            rbp_r_t = MoveRedRight(rbp_r_c);
            if (rbp_r_p.Left() == rbp_r_c) {
              rbp_r_p.SetLeft(rbp_r_t);
            } else {
              rbp_r_p.SetRight(rbp_r_t);
            }
            rbp_r_c = rbp_r_t;
          } else {
            rbp_r_p = rbp_r_c;
            rbp_r_c = rbp_r_c.Right();
          }
        }
      }
    }
    // Update root.
    mRoot = TreeNode(rbp_r_s.addr()).Left().Get();
    aNode.SetLeft(nullptr);
    aNode.SetRight(nullptr);
    aNode.SetColor(NodeColor::Black);
  }

  TreeNode RotateLeft(TreeNode aNode) {
    TreeNode node = aNode.Right();
    aNode.SetRight(node.Left());
    node.SetLeft(aNode);
    return node;
  }

  TreeNode RotateRight(TreeNode aNode) {
    TreeNode node = aNode.Left();
    aNode.SetLeft(node.Right());
    node.SetRight(aNode);
    return node;
  }

  TreeNode LeanLeft(TreeNode aNode) {
    TreeNode node = RotateLeft(aNode);
    NodeColor color = aNode.Color();
    node.SetColor(color);
    aNode.SetColor(NodeColor::Red);
    return node;
  }

  TreeNode LeanRight(TreeNode aNode) {
    TreeNode node = RotateRight(aNode);
    NodeColor color = aNode.Color();
    node.SetColor(color);
    aNode.SetColor(NodeColor::Red);
    return node;
  }

  TreeNode MoveRedLeft(TreeNode aNode) {
    TreeNode node;
    TreeNode rbp_mrl_t, rbp_mrl_u;
    rbp_mrl_t = aNode.Left();
    rbp_mrl_t.SetColor(NodeColor::Red);
    rbp_mrl_t = aNode.Right();
    rbp_mrl_u = rbp_mrl_t.Left();
    if (rbp_mrl_u.IsRed()) {
      rbp_mrl_u = RotateRight(rbp_mrl_t);
      aNode.SetRight(rbp_mrl_u);
      node = RotateLeft(aNode);
      rbp_mrl_t = aNode.Right();
      if (rbp_mrl_t.IsRed()) {
        rbp_mrl_t.SetColor(NodeColor::Black);
        aNode.SetColor(NodeColor::Red);
        rbp_mrl_t = RotateLeft(aNode);
        node.SetLeft(rbp_mrl_t);
      } else {
        aNode.SetColor(NodeColor::Black);
      }
    } else {
      aNode.SetColor(NodeColor::Red);
      node = RotateLeft(aNode);
    }
    return node;
  }

  TreeNode MoveRedRight(TreeNode aNode) {
    TreeNode node;
    TreeNode rbp_mrr_t;
    rbp_mrr_t = aNode.Left();
    if (rbp_mrr_t.IsRed()) {
      TreeNode rbp_mrr_u, rbp_mrr_v;
      rbp_mrr_u = rbp_mrr_t.Right();
      rbp_mrr_v = rbp_mrr_u.Left();
      if (rbp_mrr_v.IsRed()) {
        rbp_mrr_u.SetColor(aNode.Color());
        rbp_mrr_v.SetColor(NodeColor::Black);
        rbp_mrr_u = RotateLeft(rbp_mrr_t);
        aNode.SetLeft(rbp_mrr_u);
        node = RotateRight(aNode);
        rbp_mrr_t = RotateLeft(aNode);
        node.SetRight(rbp_mrr_t);
      } else {
        rbp_mrr_t.SetColor(aNode.Color());
        rbp_mrr_u.SetColor(NodeColor::Red);
        node = RotateRight(aNode);
        rbp_mrr_t = RotateLeft(aNode);
        node.SetRight(rbp_mrr_t);
      }
      aNode.SetColor(NodeColor::Red);
    } else {
      rbp_mrr_t.SetColor(NodeColor::Red);
      rbp_mrr_t = rbp_mrr_t.Left();
      if (rbp_mrr_t.IsRed()) {
        rbp_mrr_t.SetColor(NodeColor::Black);
        node = RotateRight(aNode);
        rbp_mrr_t = RotateLeft(aNode);
        node.SetRight(rbp_mrr_t);
      } else {
        node = RotateLeft(aNode);
      }
    }
    return node;
  }

  // The iterator simulates recursion via an array of pointers that store the
  // current path.  This is critical to performance, since a series of calls to
  // rb_{next,prev}() would require time proportional to (n lg n), whereas this
  // implementation only requires time proportional to (n).
  //
  // Since the iterator caches a path down the tree, any tree modification may
  // cause the cached path to become invalid. Don't modify the tree during an
  // iteration.

  // Size the path arrays such that they are always large enough, even if a
  // tree consumes all of memory.  Since each node must contain a minimum of
  // two pointers, there can never be more nodes than:
  //
  //   1 << ((sizeof(void*)<<3) - (log2(sizeof(void*))+1))
  //
  // Since the depth of a tree is limited to 3*lg(#nodes), the maximum depth
  // is:
  //
  //   (3 * ((sizeof(void*)<<3) - (log2(sizeof(void*))+1)))
  //
  // This works out to a maximum depth of 87 and 180 for 32- and 64-bit
  // systems, respectively (approximately 348 and 1440 bytes, respectively).
 public:
  class Iterator {
    TreeNode mPath[3 * ((sizeof(void*) << 3) - (LOG2(sizeof(void*)) + 1))];
    unsigned mDepth;

   public:
    explicit Iterator(RedBlackTree<T, Trait>* aTree) : mDepth(0) {
      // Initialize the path to contain the left spine.
      if (aTree->mRoot) {
        TreeNode node;
        mPath[mDepth++] = aTree->mRoot;
        while ((node = mPath[mDepth - 1].Left())) {
          mPath[mDepth++] = node;
        }
      }
    }

    template <typename Iterator>
    class Item {
      Iterator* mIterator;
      T* mItem;

     public:
      Item(Iterator* aIterator, T* aItem)
          : mIterator(aIterator), mItem(aItem) {}

      bool operator!=(const Item& aOther) const {
        return (mIterator != aOther.mIterator) || (mItem != aOther.mItem);
      }

      T* operator*() const { return mItem; }

      const Item& operator++() {
        mItem = mIterator->Next();
        return *this;
      }
    };

    Item<Iterator> begin() {
      return Item<Iterator>(this,
                            mDepth > 0 ? mPath[mDepth - 1].Get() : nullptr);
    }

    Item<Iterator> end() { return Item<Iterator>(this, nullptr); }

    T* Next() {
      TreeNode node;
      if ((node = mPath[mDepth - 1].Right())) {
        // The successor is the left-most node in the right subtree.
        mPath[mDepth++] = node;
        while ((node = mPath[mDepth - 1].Left())) {
          mPath[mDepth++] = node;
        }
      } else {
        // The successor is above the current node.  Unwind until a
        // left-leaning edge is removed from the path, of the path is empty.
        for (mDepth--; mDepth > 0; mDepth--) {
          if (mPath[mDepth - 1].Left() == mPath[mDepth]) {
            break;
          }
        }
      }
      return mDepth > 0 ? mPath[mDepth - 1].Get() : nullptr;
    }
  };

  Iterator iter() { return Iterator(this); }
};

#endif  // RB_H_