18namespace cxx {
namespace Bits {
28template<
typename Node,
typename Node_op >
32 typedef Direction Dir;
37 __Bst_iter_b() : _n(0), _r(0) {}
44 __Bst_iter_b(Node
const *t)
48 __Bst_iter_b(Node
const *t, Node
const *r)
53 inline void _downmost();
60 bool operator == (__Bst_iter_b
const &o)
const {
return _n == o._n; }
62 bool operator != (__Bst_iter_b
const &o)
const {
return _n != o._n; }
73template<
typename Node,
typename Node_type,
typename Node_op >
74class __Bst_iter :
public __Bst_iter_b<Node, Node_op>
78 typedef __Bst_iter_b<Node, Node_op> Base;
93 __Bst_iter(Node
const *t) : Base(t) {}
94 __Bst_iter(Node
const *t, Node
const *r) : Base(t, r) {}
97 __Bst_iter(Base
const &o) : Base(o) {}
103 Node_type &operator * ()
const {
return *
const_cast<Node *
>(_n); }
108 Node_type *operator -> ()
const {
return const_cast<Node *
>(_n); }
112 __Bst_iter &operator ++ () { inc();
return *
this; }
116 __Bst_iter &operator ++ (
int)
117 { __Bst_iter tmp = *
this; inc();
return tmp; }
124template<
typename Node,
typename Node_op>
126void __Bst_iter_b<Node, Node_op>::_downmost()
130 Node *n = Node_op::child(_n, Dir::L);
138template<
typename Node,
typename Node_op>
139void __Bst_iter_b<Node, Node_op>::inc()
146 _r = _n = Node_op::child(_r, Dir::R);
151 if (Node_op::child(_n, Dir::R))
153 _n = Node_op::child(_n, Dir::R);
162 if (Node_op::cmp(_n, q))
165 q = Node_op::child(q, Dir::L);
167 else if (_n == q || Node_op::child(q, Dir::R) == _n)
173 q = Node_op::child(q, Dir::R);