l4/pkg/cxx/lib/tl/include/bits/bst_iter.h

   1 // vi:ft=cpp
   2 /**
   3  * \file
   4  * \brief AVL tree
   5  */
   6 /*
   7  * (c) 2008-2009 Alexander Warg <warg@os.inf.tu-dresden.de>,
   8  *               Carsten Weinhold <weinhold@os.inf.tu-dresden.de>
   9  *     economic rights: Technische Universität Dresden (Germany)
  10  *
  11  * This file is part of TUD:OS and distributed under the terms of the
  12  * GNU General Public License 2.
  13  * Please see the COPYING-GPL-2 file for details.
  14  *
  15  * As a special exception, you may use this file as part of a free software
  16  * library without restriction.  Specifically, if other files instantiate
  17  * templates or use macros or inline functions from this file, or you compile
  18  * this file and link it with other files to produce an executable, this
  19  * file does not by itself cause the resulting executable to be covered by
  20  * the GNU General Public License.  This exception does not however
  21  * invalidate any other reasons why the executable file might be covered by
  22  * the GNU General Public License.
  23  */
  24
  25 #pragma once
  26
  27 #include "bst_base.h"
  28
  29 namespace cxx { namespace Bits {
  30
  31 /**
  32  * \internal
  33  * \ingroup cxx_api
  34  * \brief Generic iterator for the AVL-tree based set.
  35  * \param Cmp the type of the comparison functor.
  36  * \param Node the type of a node.
  37  * \param Node_op the type used to determine the direction of the iterator.
  38  */
  39 template< typename Node, typename Node_op >
  40 class __Bst_iter_b
  41 {
  42 protected:
  43   typedef Direction Dir;
  44   Node const *_n;   ///< Current node
  45   Node const *_r;   ///< Root node of current subtree
  46
  47   /// Create an invalid iterator, used as end marker.
  48   __Bst_iter_b() : _n(0), _r(0) {}
  49
  50   /**
  51    * \brief Create an iterator for the given AVL tree.
  52    * \param t the root node of the tree to iterate.
  53    * \param cmp the comparison functor for tree elements.
  54    */
  55   __Bst_iter_b(Node const *t)
  56     : _n(t), _r(_n)
  57   { _downmost(); }
  58
  59   __Bst_iter_b(Node const *t, Node const *r)
  60     : _n(t), _r(r)
  61   {}
  62
  63   /// traverse the subtree down to the leftmost/rightmost leave.
  64   inline void _downmost();
  65
  66   /// Increment to the next element.
  67   inline void inc();
  68
  69 public:
  70   /// Check two iterators for equality.
  71   bool operator == (__Bst_iter_b const &o) const { return _n == o._n; }
  72   /// Check two iterators for non equality.
  73   bool operator != (__Bst_iter_b const &o) const { return _n != o._n; }
  74 };
  75
  76 /**
  77  * \internal
  78  * \ingroup cxx_api
  79  * \brief Generic iterator for the AVL-tree based set.
  80  * \param Node the type of a node.
  81  * \param Node_type the type of the node to return stored in a node.
  82  * \param Node_op the type used to determine the direction of the iterator.
  83  */
  84 template< typename Node, typename Node_type, typename Node_op >
  85 class __Bst_iter : public __Bst_iter_b<Node, Node_op>
  86 {
  87 private:
  88   /// Super-class type
  89   typedef __Bst_iter_b<Node, Node_op> Base;
  90
  91   using Base::_n;
  92   using Base::_r;
  93   using Base::inc;
  94
  95 public:
  96   /// Create an invalid iterator (end marker)
  97   __Bst_iter() {}
  98
  99   /**
 100    * \brief Create an iterator for the given tree.
 101    * \param t the root node of the tree to iterate.
 102    * \param cmp the conmparison functor for tree elements.
 103    */
 104   __Bst_iter(Node const *t) : Base(t) {}
 105   __Bst_iter(Node const *t, Node const *r) : Base(t, r) {}
 106
 107 //  template<typename Key2>
 108   __Bst_iter(Base const &o) : Base(o) {}
 109
 110   /**
 111    * \brief Dereference the iterator and get the item out of the tree.
 112    * \return A reference to the data stored in the AVL tree.
 113    */
 114   Node_type &operator * () const { return *const_cast<Node *>(_n); }
 115   /**
 116    * \brief Member access to the item the iterator points to.
 117    * \return A pointer to the item in the node.
 118    */
 119   Node_type *operator -> () const { return const_cast<Node *>(_n); }
 120   /**
 121    * \brief Set the iterator to the next element (pre increment).
 122    */
 123   __Bst_iter &operator ++ () { inc(); return *this; }
 124   /**
 125    * \brief Set the iterator to the next element (post increment).
 126    */
 127   __Bst_iter &operator ++ (int)
 128   { __Bst_iter tmp = *this; inc(); return tmp; }
 129 };
 130
 131
 132 //----------------------------------------------------------------------------
 133 /* IMPLEMENTATION: __Bst_iter_b */
 134
 135 template< typename Node, typename Node_op>
 136 inline
 137 void __Bst_iter_b<Node, Node_op>::_downmost()
 138 {
 139   while (_n)
 140     {
 141       Node *n = Node_op::child(_n, Dir::L);
 142       if (n)
 143         _n = n;
 144       else
 145         return;
 146     }
 147 }
 148
 149 template< typename Node, typename Node_op>
 150 void __Bst_iter_b<Node, Node_op>::inc()
 151 {
 152   if (!_n)
 153     return;
 154
 155   if (_n == _r)
 156     {
 157       _r = _n = Node_op::child(_r, Dir::R);
 158       _downmost();
 159       return;
 160     }
 161
 162   if (Node_op::child(_n, Dir::R))
 163     {
 164       _n = Node_op::child(_n, Dir::R);
 165       _downmost();
 166       return;
 167     }
 168
 169   Node const *q = _r;
 170   Node const *p = _r;
 171   while (1)
 172     {
 173       if (Node_op::cmp(_n, q))
 174         {
 175           p = q;
 176           q = Node_op::child(q, Dir::L);
 177         }
 178       else if (_n == q || Node_op::child(q, Dir::R) == _n)
 179         {
 180           _n = p;
 181           return;
 182         }
 183       else
 184         q = Node_op::child(q, Dir::R);
 185     }
 186 }
 187
 188 }}