27#include <l4/cxx/std_alloc>
28#include <l4/cxx/std_ops>
29#include <l4/cxx/type_traits>
44template<
typename Node,
typename Key,
typename Node_op >
45class Avl_set_iter :
public __Bst_iter_b<Node, Node_op>
49 typedef __Bst_iter_b<Node, Node_op> Base;
52 typedef typename Type_traits<Key>::Non_const_type Non_const_key;
55 typedef Avl_set_iter<Node, Non_const_key, Node_op> Non_const_iter;
63 Avl_set_iter() =
default;
69 Avl_set_iter(Node
const *t) : Base(t) {}
75 Avl_set_iter(Base
const &o) : Base(o) {}
78 Avl_set_iter(Non_const_iter
const &o)
82 Avl_set_iter &operator = (Non_const_iter
const &o)
83 { Base::operator = (o);
return *
this; }
89 Key &operator * ()
const {
return const_cast<Node*
>(_n)->item; }
94 Key *operator -> ()
const {
return &
const_cast<Node*
>(_n)->item; }
98 Avl_set_iter &operator ++ () { inc();
return *
this; }
102 Avl_set_iter operator ++ (
int)
103 { Avl_set_iter tmp = *
this; inc();
return tmp; }
108template<
typename KEY_TYPE>
111 typedef KEY_TYPE Key_type;
112 template<
typename NODE>
113 static Key_type
const &key_of(NODE
const *n)
130template<
typename ITEM_TYPE,
class COMPARE,
131 template<
typename A>
class ALLOC,
135 friend struct ::Avl_set_tester;
174 template<
typename ...ARGS>
175 _Node(ARGS &&...args) :
Avl_tree_node(), item(cxx::forward<ARGS>(args)...)
187 friend class Base_avl_set<ITEM_TYPE, COMPARE, ALLOC, GET_KEY>;
189 explicit Node(_Node
const *n) : _n(n) {}
215 operator Item_type const * () {
return _n ? &_n->item : 0; }
233 typedef typename Type_traits<Item_type>::Param_type Item_param_type;
236 typedef Avl_set_iter<_Node, Item_type, Fwd>
Iterator;
255 : _tree(), _alloc(alloc)
295 template<
typename... Args>
308 _Node *n = _tree.
remove(item);
397 {
return _tree.
find(item); }
400 bool rec_dump(
bool print)
402 return _tree.rec_dump(print);
412template<
typename Item,
class Compare,
template<
typename A>
class Alloc,
typename KEY_TYPE>
414 : _tree(), _alloc(o._alloc)
421template<
typename Item,
class Compare,
template<
typename A >
class Alloc,
typename KEY_TYPE>
425 _Node *n = _alloc.alloc();
427 return cxx::pair(end(), -E_nomem);
429 new (n,
Nothrow()) _Node(item);
441template<
typename Item,
class Compare,
template<
typename A >
class Alloc,
typename KEY_TYPE>
442template<
typename... Args>
446 _Node *n = _alloc.alloc();
448 return cxx::pair(end(), -E_nomem);
450 new (n,
Nothrow()) _Node(cxx::forward<Args>(args)...);
458 return cxx::pair(Iterator(
typename Tree::Iterator(err.
first, err.
first)), err.
second ? 0 : -E_exist);
474template<
typename ITEM_TYPE,
class COMPARE = Lt_functor<ITEM_TYPE>,
475 template<
typename A>
class ALLOC = New_allocator>
478 Bits::Avl_set_get_key<ITEM_TYPE> >
487 Avl_set(Node_allocator
const &alloc)
AVL set for simple compareable items.
Avl_tree_node()=default
Create an uninitialized node, this is what you should do.
Pair< Node *, bool > insert(Node *new_node)
Insert a new node into this AVL tree.
Node * remove(Key_param_type key)
Remove the node with key from the tree.
A smart pointer to a tree item.
bool valid() const
Validity check.
Item_type const * operator->()
Dereferenced member access.
Node()
Default construction for NIL pointer.
Item_type const & operator*()
Dereference the pointer.
Internal: AVL set with internally managed nodes.
Avl_set_iter< _Node, Item_type, Fwd > Iterator
Forward iterator for the set.
Node find_node(Key_type const &item) const
Lookup a node equal to item.
Avl_set_iter< _Node, Item_type, Rev > Rev_iterator
Backward iterator for the set.
Const_rev_iterator rbegin() const
Get the constant backward iterator for the last element in the set.
Iterator end()
Get the end marker for the mutable forward iterator.
Rev_iterator rbegin()
Get the mutable backward iterator for the last element of the set.
GET_KEY::Key_type Key_type
Type of the sort key used for the items.
ITEM_TYPE Item_type
Type for the items store in the set.
int remove(Key_type const &item)
Remove an item from the set.
COMPARE Item_compare
Type for the comparison functor.
Base_avl_set(Node_allocator const &alloc=Node_allocator())
Create a AVL-tree based set.
Const_iterator end() const
Get the end marker for the constant forward iterator.
Const_rev_iterator rend() const
Get the end marker for the constant backward iterator.
Const_iterator begin() const
Get the constant forward iterator for the first element in the set.
ALLOC< _Node > Node_allocator
Type for the node allocator.
Rev_iterator rend()
Get the end marker for the mutable backward iterator.
Iterator begin()
Get the mutable forward iterator for the first element of the set.
Avl_set_iter< _Node, Const_item_type, Rev > Const_rev_iterator
Constant backward iterator for the set.
GET_KEY Get_key
Key-getter type to derive the sort key of an internal node.
cxx::Pair< Iterator, int > insert(Item_type const &item)
Insert an item into the set.
Type_traits< Item_type >::Const_type Const_item_type
Type used for const items within the set.
int erase(Key_type const &item)
Erase the item with the given key.
Base_avl_set(Base_avl_set const &o)
Create a copy of an AVL-tree based set.
@ E_noent
Item does not exist.
@ E_nomem
Memory allocation failed.
@ E_exist
Item exists already.
Avl_set_iter< _Node, Const_item_type, Fwd > Const_iterator
Constant forward iterator for the set.
Node lower_bound_node(Key_type const &key) const
Find the first node greater or equal to key.
Node * lower_bound_node(Key_param_type key) const
Find the first node with a key not less than the given key.
Const_rev_iterator rend() const
Get the end marker for the constant backward iterator.
Const_rev_iterator rbegin() const
Get the constant backward iterator for the last element in the set.
Rev Rev_iter_ops
Helper for building reverse iterators for different wrapper classes.
Node * find_node(Key_param_type key) const
find the node with the given key.
Const_iterator find(Key_param_type key) const
find the node with the given key.
void remove_all(FUNC &&callback)
Clear the tree.
Const_iterator end() const
Get the end marker for the constant forward iterator.
Fwd Fwd_iter_ops
Helper for building forward iterators for different wrapper classes.
Const_iterator begin() const
Get the constant forward iterator for the first element in the set.
Helper type to distinguish the oeprator new version that does not throw exceptions.
Internal, key-getter for Avl_set nodes.
Second second
Second value.