l4/pkg/cxx/lib/tl/include/bits/bst.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 #pragma once
  25
  26 #include "type_traits.h"
  27 #include "bst_base.h"
  28 #include "bst_iter.h"
  29
  30 namespace cxx { namespace Bits {
  31
  32 /**
  33  * \brief Basic binary search tree (BST).
  34  *
  35  * This class is intended as a base class for concrete binary search trees,
  36  * such as an AVL tree.  This class already provides the basic lookup methods
  37  * and iterator definitions for a BST.
  38  */
  39 template< typename Node, typename Get_key, typename Compare >
  40 class Bst
  41 {
  42 private:
  43   typedef Direction Dir;
  44   /// Ops for forward iterators
  45   struct Fwd
  46   {
  47     static Node *child(Node const *n, Direction d)
  48     { return Bst_node::next<Node>(n, d); }
  49
  50     static bool cmp(Node const *l, Node const *r)
  51     { return Compare()(Get_key::key_of(l), Get_key::key_of(r)); }
  52   };
  53
  54   /// Ops for Reverse iterators
  55   struct Rev
  56   {
  57     static Node *child(Node const *n, Direction d)
  58     { return Bst_node::next<Node>(n, !d); }
  59
  60     static bool cmp(Node const *l, Node const *r)
  61     { return Compare()(Get_key::key_of(r), Get_key::key_of(l)); }
  62   };
  63
  64 public:
  65   /// The type of key values used to generate the total order of the elements.
  66   typedef typename Get_key::Key_type Key_type;
  67   /// The type for key parameters.
  68   typedef typename Type_traits<Key_type>::Param_type Key_param_type;
  69
  70   /// Helper for building forward iterators for different wrapper classes.
  71   typedef Fwd Fwd_iter_ops;
  72   /// Helper for building reverse iterators for different wrapper classes.
  73   typedef Rev Rev_iter_ops;
  74
  75   /// \name Iterators
  76   //@{
  77   /// Forward iterator.
  78   typedef __Bst_iter<Node, Node, Fwd> Iterator;
  79   /// Constant forward iterator.
  80   typedef __Bst_iter<Node, Node const, Fwd> Const_iterator;
  81   /// Backward iterator.
  82   typedef __Bst_iter<Node, Node, Rev> Rev_iterator;
  83   /// Constant backward.
  84   typedef __Bst_iter<Node, Node const, Rev> Const_rev_iterator;
  85   //@}
  86
  87 protected:
  88   /**
  89    * \name Interior access for descendants.
  90    *
  91    * As this class is an intended base class we provide protected access
  92    * to our interior, use 'using' to make this private in concrete
  93    * implementations.
  94    */
  95   /*@{*/
  96
  97   /// The head pointer of the tree.
  98   Bst_node *_head;
  99
 100   /// Create an empty tree.
 101   Bst() : _head(0) {}
 102
 103   /// Access the head node as object of type \a Node.
 104   Node *head() const { return static_cast<Node*>(_head); }
 105
 106   /// Get the key value of \a n.
 107   static Key_type k(Bst_node const *n)
 108   { return Get_key::key_of(static_cast<Node const *>(n)); }
 109
 110   /**
 111    * \brief Get the direction to go from \a l to search for \a r.
 112    * \param l is the key to look for.
 113    * \param r is the key at the current position.
 114    * \return #Direction::L for left, #Direction::R for right,
 115    *         and #Direction::N if \a l is equal to \a r.
 116    */
 117   static Dir dir(Key_param_type l, Key_param_type r)
 118   {
 119     Compare cmp;
 120     Dir d(cmp(r, l));
 121     if (d == Direction::L && !cmp(l, r))
 122       return Direction::N;
 123     return d;
 124   }
 125
 126   /**
 127    * \brief Get the direction to go from \a l to search for \a r.
 128    * \param l is the key to look for.
 129    * \param r is the node at the current position.
 130    * \return #Direction::L for left, #Direction::R for right,
 131    *         and #Direction::N if \a l is equal to \a r.
 132    */
 133   static Dir dir(Key_param_type l, Bst_node const *r)
 134   { return dir(l, k(r)); }
 135
 136   /// Is \a l greater than \a r.
 137   static bool greater(Key_param_type l, Key_param_type r)
 138   { return Compare()(r, l); }
 139
 140   /// Is \a l greater than \a r.
 141   static bool greater(Key_param_type l, Bst_node const *r)
 142   { return greater(l, k(r)); }
 143
 144   /// Is \a l greater than \a r.
 145   static bool greater(Bst_node const *l, Bst_node const *r)
 146   { return greater(k(l), k(r)); }
 147   /*@}*/
 148
 149 public:
 150
 151   /**
 152    * \name Get default iterators for the ordered tree.
 153    */
 154   /*@{*/
 155   /**
 156    * \brief Get the constant forward iterator for the first element in the set.
 157    * \return Constant forward iterator for the first element in the set.
 158    */
 159   Const_iterator begin() const { return Const_iterator(head()); }
 160   /**
 161    * \brief Get the end marker for the constant forward iterator.
 162    * \return The end marker for the constant forward iterator.
 163    */
 164   Const_iterator end() const { return Const_iterator(); }
 165
 166   /**
 167    * \brief Get the mutable forward iterator for the first element of the set.
 168    * \return The mutable forward iterator for the first element of the set.
 169    */
 170   Iterator begin() { return Iterator(head()); }
 171   /**
 172    * \brief Get the end marker for the mutable forward iterator.
 173    * \return The end marker for mutable forward iterator.
 174    */
 175   Iterator end() { return Iterator(); }
 176
 177   /**
 178    * \brief Get the constant backward iterator for the last element in the set.
 179    * \return The constant backward iterator for the last element in the set.
 180    */
 181   Const_rev_iterator rbegin() const { return Const_rev_iterator(head()); }
 182   /**
 183    * \brief Get the end marker for the constant backward iterator.
 184    * \return The end marker for the constant backward iterator.
 185    */
 186   Const_rev_iterator rend() const { return Const_rev_iterator(); }
 187
 188   /**
 189    * \brief Get the mutable backward iterator for the last element of the set.
 190    * \return The mutable backward iterator for the last element of the set.
 191    */
 192   Rev_iterator rbegin() { return Rev_iterator(head()); }
 193   /**
 194    * \brief Get the end marker for the mutable backward iterator.
 195    * \return The end marker for mutable backward iterator.
 196    */
 197   Rev_iterator rend() { return Rev_iterator(); }
 198   /*@}*/
 199
 200
 201   /**
 202    * \name Lookup functions.
 203    */
 204   //@{
 205   /**
 206    * \brief find the node with the given \a key.
 207    * \param key The key value of the element to search.
 208    * \return A pointer to the node with the given \a key, or
 209    *         NULL if \a key was not found.
 210    */
 211   Node *find_node(Key_param_type key) const;
 212
 213   /**
 214    * \brief find the first node with a key not less than the given \a key.
 215    * \param key The key value of the element to search.
 216    * \return A pointer to the node with the given \a key, or
 217    *         NULL if \a key was not found.
 218    */
 219   Node *lower_bound_node(Key_param_type key) const;
 220
 221   /**
 222    * \brief find the node with the given \a key.
 223    * \param key The key value of the element to search.
 224    * \return A valid iterator for the node with the given \a key,
 225    *         or an invalid iterator if \a key was not found.
 226    */
 227   Const_iterator find(Key_param_type key) const;
 228
 229   //@}
 230 };
 231
 232 /* find an element */
 233 template< typename Node, typename Get_key, class Compare>
 234 inline
 235 Node *
 236 Bst<Node, Get_key, Compare>::find_node(Key_param_type key) const
 237 {
 238   Dir d;
 239
 240   for (Bst_node *q = _head; q; q = Bst_node::next(q, d))
 241     {
 242       d = dir(key, q);
 243       if (d == Dir::N)
 244         return static_cast<Node*>(q);
 245     }
 246   return 0;
 247 }
 248
 249 template< typename Node, typename Get_key, class Compare>
 250 inline
 251 Node *
 252 Bst<Node, Get_key, Compare>::lower_bound_node(Key_param_type key) const
 253 {
 254   Dir d;
 255   Bst_node *r = 0;
 256
 257   for (Bst_node *q = _head; q; q = Bst_node::next(q, d))
 258     {
 259       d = dir(key, q);
 260       if (d == Dir::L)
 261         r = q; // found a node greater than key
 262       else if (d == Dir::N)
 263         return static_cast<Node*>(q);
 264     }
 265   return static_cast<Node*>(r);
 266 }
 267
 268 /* find an element */
 269 template< typename Node, typename Get_key, class Compare>
 270 inline
 271 typename Bst<Node, Get_key, Compare>::Const_iterator
 272 Bst<Node, Get_key, Compare>::find(Key_param_type key) const
 273 {
 274   Bst_node *q = _head;
 275   Bst_node *r = q;
 276
 277   for (Dir d; q; q = Bst_node::next(q, d))
 278     {
 279       d = dir(key, q);
 280       if (d == Dir::N)
 281         return Iterator(static_cast<Node*>(q), static_cast<Node *>(r));
 282
 283       if (d != Dir::L && q == r)
 284         r = Bst_node::next(q, d);
 285     }
 286   return Iterator();
 287 }
 288
 289 }}