Loading...
Searching...
No Matches
bst_iter.h
Go to the documentation of this file.
// vi:ft=cpp
/*
* (c) 2008-2009 Alexander Warg <warg@os.inf.tu-dresden.de>,
* Carsten Weinhold <weinhold@os.inf.tu-dresden.de>
* economic rights: Technische Universität Dresden (Germany)
*
* License: see LICENSE.spdx (in this directory or the directories above)
*/
#pragma once
#include "bst_base.h"
namespace cxx { namespace Bits {
template< typename Node, typename Node_op >
class __Bst_iter_b
{
protected:
typedef Direction Dir;
Node const *_n;
Node const *_r;
__Bst_iter_b() : _n(0), _r(0) {}
__Bst_iter_b(Node const *t)
: _n(t), _r(_n)
{ _downmost(); }
__Bst_iter_b(Node const *t, Node const *r)
: _n(t), _r(r)
{}
inline void _downmost();
inline void inc();
public:
bool operator == (__Bst_iter_b const &o) const { return _n == o._n; }
bool operator != (__Bst_iter_b const &o) const { return _n != o._n; }
};
template< typename Node, typename Node_type, typename Node_op >
class __Bst_iter : public __Bst_iter_b<Node, Node_op>
{
private:
typedef __Bst_iter_b<Node, Node_op> Base;
using Base::_n;
using Base::_r;
using Base::inc;
public:
__Bst_iter() {}
__Bst_iter(Node const *t) : Base(t) {}
__Bst_iter(Node const *t, Node const *r) : Base(t, r) {}
// template<typename Key2>
__Bst_iter(Base const &o) : Base(o) {}
Node_type &operator * () const { return *const_cast<Node *>(_n); }
Node_type *operator -> () const { return const_cast<Node *>(_n); }
__Bst_iter &operator ++ () { inc(); return *this; }
__Bst_iter &operator ++ (int)
{ __Bst_iter tmp = *this; inc(); return tmp; }
};
//----------------------------------------------------------------------------
/* IMPLEMENTATION: __Bst_iter_b */
template< typename Node, typename Node_op>
inline
void __Bst_iter_b<Node, Node_op>::_downmost()
{
while (_n)
{
Node *n = Node_op::child(_n, Dir::L);
if (n)
_n = n;
else
return;
}
}
template< typename Node, typename Node_op>
void __Bst_iter_b<Node, Node_op>::inc()
{
if (!_n)
return;
if (_n == _r)
{
_r = _n = Node_op::child(_r, Dir::R);
_downmost();
return;
}
if (Node_op::child(_n, Dir::R))
{
_n = Node_op::child(_n, Dir::R);
_downmost();
return;
}
Node const *q = _r;
Node const *p = _r;
while (1)
{
if (Node_op::cmp(_n, q))
{
p = q;
q = Node_op::child(q, Dir::L);
}
else if (_n == q || Node_op::child(q, Dir::R) == _n)
{
_n = p;
return;
}
else
q = Node_op::child(q, Dir::R);
}
}
}}
bst_base.h
AVL tree.
cxx::Bits
Internal helpers for the cxx package.
Definition avl_map:21
cxx
Our C++ library.
Definition arith:11