29namespace cxx {
namespace Bits {
39template<
typename Node,
typename Node_op >
43 typedef Direction Dir;
48 __Bst_iter_b() : _n(0), _r(0) {}
55 __Bst_iter_b(Node
const *t)
59 __Bst_iter_b(Node
const *t, Node
const *r)
64 inline void _downmost();
71 bool operator == (__Bst_iter_b
const &o)
const {
return _n == o._n; }
73 bool operator != (__Bst_iter_b
const &o)
const {
return _n != o._n; }
84template<
typename Node,
typename Node_type,
typename Node_op >
85class __Bst_iter :
public __Bst_iter_b<Node, Node_op>
89 typedef __Bst_iter_b<Node, Node_op> Base;
104 __Bst_iter(Node
const *t) : Base(t) {}
105 __Bst_iter(Node
const *t, Node
const *r) : Base(t, r) {}
108 __Bst_iter(Base
const &o) : Base(o) {}
114 Node_type &operator * ()
const {
return *
const_cast<Node *
>(_n); }
119 Node_type *operator -> ()
const {
return const_cast<Node *
>(_n); }
123 __Bst_iter &operator ++ () { inc();
return *
this; }
127 __Bst_iter &operator ++ (
int)
128 { __Bst_iter tmp = *
this; inc();
return tmp; }
135template<
typename Node,
typename Node_op>
137void __Bst_iter_b<Node, Node_op>::_downmost()
141 Node *n = Node_op::child(_n, Dir::L);
149template<
typename Node,
typename Node_op>
150void __Bst_iter_b<Node, Node_op>::inc()
157 _r = _n = Node_op::child(_r, Dir::R);
162 if (Node_op::child(_n, Dir::R))
164 _n = Node_op::child(_n, Dir::R);
173 if (Node_op::cmp(_n, q))
176 q = Node_op::child(q, Dir::L);
178 else if (_n == q || Node_op::child(q, Dir::R) == _n)
184 q = Node_op::child(q, Dir::R);