Tree maps

Files CCore/inc/TreeMap.h CCore/src/TreeMap.cpp

Here are two maps, built on red-black tree and radix tree algorithms. They are parametrized by the key type, object type, node allocator type. Node allocator is defaulted to the NodeAllocator. The only requirement for the object type is its destructor must be no-throw. There are also compact variants of these maps.

Constant maps propagate constantness to its elements.

This is the first map, built on red-black tree algorithms. There is the additional template parameter KRef. It is used to specify a key in methods. It is defaulted to the K, another typical choice would be the const K &.

template <class K,class T,class KRef=K,template <class Node> class Allocator=NodeAllocator>
class RBTreeMap : NoCopy
 {
   ....

  public: 
   
   // constructors
   
   template <class ... SS>
   explicit RBTreeMap(SS && ... ss) noexcept;
   
   ~RBTreeMap();
   
   // std move

   RBTreeMap(RBTreeMap &&obj) noexcept;

   RBTreeMap & operator = (RBTreeMap &&obj) noexcept;

   // props
   
   ulen operator + () const;
   
   bool operator ! () const;
   
   ulen getCount() const;
   
   // find
   
   T * find(KRef key);
   
   T * findMin();
   
   T * findMin(KRef key);
   
   T * findMax();
   
   T * findMax(KRef key);


   const T * find(KRef key) const;
   
   const T * findMin() const;
   
   const T * findMin(KRef key) const;
   
   const T * findMax() const;
   
   const T * findMax(KRef key) const;


   const T * find_const(KRef key) const;
   
   const T * findMin_const() const;
   
   const T * findMin_const(KRef key) const;
   
   const T * findMax_const() const;
   
   const T * findMax_const(KRef key) const;
   
   
   template <class S>
   struct NodePtr
    {
     ....

     // object ptr
     
     Node * operator + () const;
     
     bool operator ! () const;
     
     S * getPtr() const;
     
     S & operator * () const;
     
     S * operator -> () const;
     
     const K & getKey() const;
    };
   
   
   NodePtr<T> find_ptr(KRef key);
   
   NodePtr<T> findMin_ptr();
   
   NodePtr<T> findMin_ptr(KRef key);
   
   NodePtr<T> findMax_ptr();
   
   NodePtr<T> findMax_ptr(KRef key);
   
   
   NodePtr<const T> find_ptr(KRef key) const;
   
   NodePtr<const T> findMin_ptr() const;
   
   NodePtr<const T> findMin_ptr(KRef key) const;
   
   NodePtr<const T> findMax_ptr() const;
   
   NodePtr<const T> findMax_ptr(KRef key) const;
   
   
   NodePtr<const T> find_ptr_const(KRef key) const;
   
   NodePtr<const T> findMin_ptr_const() const;
   
   NodePtr<const T> findMin_ptr_const(KRef key) const;
   
   NodePtr<const T> findMax_ptr_const() const;
   
   NodePtr<const T> findMax_ptr_const(KRef key) const;
   
   // add/del
   
   struct Result
    {
     T *obj;
     bool new_flag;
     
     Result(T *obj_,bool new_flag_) : obj(obj_),new_flag(new_flag_) {}
     
     operator T * () const { return obj; }
    };
   
   template <class ... SS>
   Result find_or_add(KRef key,SS && ... ss);
   
   bool del(KRef key);
   
   bool delMin();
   
   bool delMax();
   
   template <class S>
   bool del(NodePtr<S> node_ptr);
   
   ulen erase();
   
   // apply
   
   template <class FuncInit>
   void applyIncr(FuncInit func_init);
   
   template <class FuncInit>
   void applyDecr(FuncInit func_init);
   
   template <class FuncInit>
   void applyIncr(FuncInit func_init) const;
   
   template <class FuncInit>
   void applyDecr(FuncInit func_init) const;
   
   template <class FuncInit>
   void applyIncr_const(FuncInit func_init) const;
   
   template <class FuncInit>
   void applyDecr_const(FuncInit func_init) const;
   
   // delIf
   
   template <class FuncInit>
   void delIf(FuncInit func_init);

   // swap/move objects
   
   void objSwap(RBTreeMap<K,T,KRef,Allocator> &obj);
   
   explicit RBTreeMap(ToMoveCtor<RBTreeMap<K,T,KRef,Allocator> > obj);
 };

Constructor forwards its arguments to the node allocator. Destructor destroys the map with all its elements. It's assumed that the allocator constructor does not throw.

RBTreeMap is not copyable, but std movable. The original object is nullified during the move.

operator + and operator ! can be used to check, if the list is empty.

getCount() returns the number of list elements.

find...() methods search a map element with some properties. A pointer to the found element is returned, or null if the element is not found. The properties are:

find(KRef key) — element with the given key.

findMin() — element with the minimum key.

findMin(KRef key) — element with the minimum key, greater or equal the key.

findMax() — element with the maximum key.

findMin(KRef key) — element with the maximum key, less or equal the key.

find_ptr...() methods do the same, but return a "node pointer". This object gives access to the found element through the Object Pointer Interface, the key is also can be retrieved by the method getKey(). It also can be used to delete the element from the map.

find_or_add() method finds or adds a new element to the map. The first argument is the required key. If there is a map element with this key, the element is found and returned. The field new_flag in the Result object will be false. If there is no such key in the map, the new element with this key will be added. The field new_flag in the Result object will be true. Extra arguments are forwarded to the object constructor. Exception is thrown in case of error.

del...() methods delete an element from the map. If an element is deleted, true is returned.

del(KRef) deletes the element with the given key.

delMin() deletes the element with the minimum key.

delMax() deletes the element with the maximum key.

del("node pointer") deletes the element, pointed by the "node pointer".

erase() destroys all elements, the number of destroyed elements is returned.

apply...() methods apply the functor to map elements. The functor signature is void (K key,T &obj) for non-constant operations and void (K key,const T &obj) for constant ones.

applyIncr() applies the functor in the incremental key order.

applyDecr() applies the functor in the decremental key order.

RBTreeMap is swappable and movable.

KeyRange

This class defines the key value range. The K must be an unsigned integral type. It is used to specify a key range for a radix tree map.

template <class K>
struct KeyRange
 {
  K kmin;
  K kmax;
  
  KeyRange();
  
  explicit KeyRange(K kmax);
  
  KeyRange(K kmin,K kmax);
  
  void guard(K key) const;
 };

kmin is the minimum key value.

kmax is the maximum key value.

KeyRange() is the default constructor. It creates the "all value" range.

KeyRange(kmax) creates a key range with the given maximum key value, the minimum key value is zero.

KeyRange(kmin,kmax) creates a key range with the given minimum and maximum key values.

guard() is a guard method. It ensures the given key belongs to the key range.

This is the second map, built on radix tree algorithms. The K must be an unsigned integral type. Methods and behavior are the same as for RBTreeMap. The only difference is there is the additional constructor. The first argument of this constructor is the key value range.

template <class K,class T,template <class Node> class Allocator=NodeAllocator > 
class RadixTreeMap : NoCopy
 {
   ....
 
  public:
 
   // constructors
   
   template <class ... SS>
   explicit RadixTreeMap(SS && ... ss) noexcept;
   
   template <class ... SS>
   explicit RadixTreeMap(KeyRange<K> key_range,SS && ... ss) noexcept;
   
   ~RadixTreeMap();
   
   // std move

   RadixTreeMap(RadixTreeMap &&obj) noexcept;

   RadixTreeMap & operator = (RadixTreeMap &&obj) noexcept;

   // props
   
   ulen operator + () const;
   
   bool operator ! () const;
   
   ulen getCount() const;
   
   // find
   
   T * find(K key);
   
   T * findMin();
   
   T * findMin(K key);
   
   T * findMax();
   
   T * findMax(K key);
   
   
   const T * find(K key) const;
   
   const T * findMin() const;
   
   const T * findMin(K key) const;
   
   const T * findMax() const;
   
   const T * findMax(K key) const;
   
   
   const T * find_const(K key) const;
   
   const T * findMin_const() const;
   
   const T * findMin_const(K key) const;
   
   const T * findMax_const() const;
   
   const T * findMax_const(K key) const;
   
   
   template <class S>
   struct NodePtr
    {
     ....
     
     // object ptr
     
     Node * operator + () const;
     
     bool operator ! () const;
     
     S * getPtr() const;
     
     S & operator * () const;
     
     S * operator -> () const;
     
     K getKey() const;
    };
   
   
   NodePtr<T> find_ptr(K key);
   
   NodePtr<T> findMin_ptr();
   
   NodePtr<T> findMin_ptr(K key);
   
   NodePtr<T> findMax_ptr();
   
   NodePtr<T> findMax_ptr(K key);
   
   
   NodePtr<const T> find_ptr(K key) const;
   
   NodePtr<const T> findMin_ptr() const;
   
   NodePtr<const T> findMin_ptr(K key) const;
   
   NodePtr<const T> findMax_ptr() const;
   
   NodePtr<const T> findMax_ptr(K key) const;
   
   
   NodePtr<const T> find_ptr_const(K key) const;
   
   NodePtr<const T> findMin_ptr_const() const;
   
   NodePtr<const T> findMin_ptr_const(K key) const;
   
   NodePtr<const T> findMax_ptr_const() const;
   
   NodePtr<const T> findMax_ptr_const(K key) const;
   
   // add/del
   
   struct Result
    {
     T *obj;
     bool new_flag;
     
     Result(T *obj_,bool new_flag_) : obj(obj_),new_flag(new_flag_) {}
     
     operator T * () const { return obj; }
    };
   
   template <class ... SS>
   Result find_or_add(K key,SS && ... ss);
   
   bool del(K key);
   
   bool delMin();
   
   bool delMax();
   
   template <class S>
   bool del(NodePtr<S> node_ptr);
   
   ulen erase();
   
   // apply
   
   template <class FuncInit>
   void applyIncr(FuncInit func_init);
   
   template <class FuncInit>
   void applyDecr(FuncInit func_init);
   
   template <class FuncInit>
   void applyIncr(FuncInit func_init) const;
   
   template <class FuncInit>
   void applyDecr(FuncInit func_init) const;
   
   template <class FuncInit>
   void applyIncr_const(FuncInit func_init) const;
   
   template <class FuncInit>
   void applyDecr_const(FuncInit func_init) const;
   
   // delIf
   
   template <class FuncInit>
   void delIf(FuncInit func_init);

   // swap/move objects
   
   void objSwap(RadixTreeMap<K,T,Allocator> &obj);
   
   explicit RadixTreeMap(ToMoveCtor<RadixTreeMap<K,T,Allocator> > obj);
 };

delIf() performs the massive delete operation. The functor signature is boolable (K key,T &obj). If it returns true, the object is deleted.