KJB
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Classes | Public Types | Public Member Functions | Friends | List of all members
kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE > Class Template Reference

a balanced binary search tree storing subtree sums in each node. More...

#include <redblack.h>

Inheritance diagram for kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >:
kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE >

Classes

class  const_iterator
 iterator class for a tree – lets you access node locators. More...
 

Public Types

typedef SATELLITE_TYPE Sat_tp
 
typedef DijkstraPriorityQueue
< SATELLITE_TYPE >::Key_tp 
Key_tp
 
typedef DijkstraPriorityQueue
< SATELLITE_TYPE >::Loc_tp 
Loc_tp
 
- Public Types inherited from kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE >
typedef SATELLITE_TYPE Sat_tp
 type of satellite data More...
 
typedef float Key_tp
 type that we use for keys More...
 
typedef size_t Loc_tp
 type that we use for locators More...
 

Public Member Functions

 Redblack_subtree_sum ()
 default ctor More...
 
void clear ()
 destroy the tree or the linear array. More...
 
 Redblack_subtree_sum (const Redblack_subtree_sum< SATELLITE_TYPE > &tree)
 copy ctor (same locators will work in this one too) More...
 
Redblack_subtree_sumoperator= (const Redblack_subtree_sum< SATELLITE_TYPE > &tree)
 assignment operator (same locators will work in this one too) More...
 
 ~Redblack_subtree_sum ()
 dtor clears the structure More...
 
Loc_tp insert (const Key_tp &key, const Sat_tp &sat)
 insert a new key+value pair in the dictionary More...
 
Loc_tp ins_max_key (const Sat_tp &sat)
 the following is a hack to mimic StochasticPriorityQueue More...
 
void debug_print (std::ostream &) const
 stub: remove print code when not checking aggressively More...
 
bool tree_valid_in_nlogn_time () const
 scan dictionary in linear time to verify invariants are valid More...
 
bool find_key (const Key_tp &key, Sat_tp *sat_out, Loc_tp *loc_out)
 search for a key in the dictionary; return first one. More...
 
bool erase_key (const Key_tp &query_key, Sat_tp *sat_out)
 erase a key+value pair from the dictionary More...
 
bool access_loc (Loc_tp query_loc, Key_tp *key_out, Sat_tp *sat_out) const
 access a record via its locator, a constant-time operation. More...
 
bool erase_loc (Loc_tp query_loc)
 remove the record indicated by query_loc, or return false if bad More...
 
Loc_tp loc_min () const
 return the locator for the record with the minimum key, or 0 More...
 
Loc_tp loc_max () const
 return the locator for the record with the maximum key, or 0 More...
 
size_t size () const
 return the number of key+value pairs in the dictionary. More...
 
bool is_empty () const
 return whether the size is zero More...
 
bool rekey_loc (Loc_tp query_loc, const Key_tp &newkey)
 change the key value for a node to a new value, O(log n) time More...
 
Key_tp root_sum () const
 return subtree sum at root node (i.e., the sum of all keys). More...
 
Loc_tp loc_using_cumulative_key_sum (Key_tp cumulative_keysum) const
 fetch a node based on inorder cumulative sum of tree keys More...
 
Loc_tp Dijkstra_extraction () const
 hack proxy to make this and a stochastic pri queue work alike More...
 
const_iterator begin () const
 
const_iterator end () const
 
- Public Member Functions inherited from kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE >
virtual ~DijkstraPriorityQueue ()
 obligatory virtual destructor More...
 

Friends

class const_iterator
 

Detailed Description

template<typename SATELLITE_TYPE>
class kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >

a balanced binary search tree storing subtree sums in each node.

This is a so-called Red-Black tree, thus it maintains a height of O(log n) where n is the number of nodes.

Red-Black Tree Invariants

A Red-Black Tree is a binary search tree augmented with one bit of "color" information associated with each node. Each node is either red or black. Keys are stored only in internal nodes, not in the leaves. The critical properties of a Red-Black tree are these:

Root and all leaves are black.

No-Red-Red invariant

Every red node has two black children.

Black-height invariant

If p, q are simple descending paths starting from the same node and ending at leaves, then p and q include the same number of black nodes.

Black height

The final invariant guarantees that the tree has a well-defined value called the black height, which is the number of black nodes from the root to any leaf, along a simple path of descent.

Other features of this Red-Black tree

Subtree Sums

The tree not only maintains the Red-Black invariants, but it stores real-valued keys and stores in each node the sum of the keys in the subtree rooted at that node.

Satellite data

This is a class template, actually. The template is parameterized by one type, the satellite data that you want to store in each node. The type for the satellite data must be copyable and it must have a default constructor, just like the requirements for standard containers.

Keys are not constrained to be unique

This dictionary allows the user to insert using the same key value as already found in the tree. Both sets of satellite data will be stored. An erase operation on a key that exists in the tree multiple times will cause one of those nodes to be extracted and removed, but it is impossible to say which one it will be (it does not in general follow a LIFO or FIFO rule).

Locators

Functionally, a "locator" is an opaque pointer (see References). This tree offers the user locators that point to the nodes in the tree. The user can read, modify, and delete nodes using their corresponding locators.

The tree data structure returns a locator every time a new record is created and inserted into the tree. The user can then read the node (

See Also
access_loc), erase it (
erase_loc), or alter its key value (
rekey_loc) via reference to its locator.

The ability to alter the key value of a node is a specific requirement of Dijkstra's algorithm (and was the motivation for providing this feature).

Operationally, a locator is an integer of type size_t. Locator numbers may be recycled. When the user deletes a node, that node's locator number could be used again for a future insertion. Thus, do not use a stale locator. (That advice applies to any pointer!)

Iterators

The tree also offers a bidirectional const_iterator, which can be used to enumerate the locators of the nodes.

Implementation notes

Todo:
Consider using XOR instead of addition by LOCATOR_BASE, which would eliminate any possibility of overflow. Unfortunately then the weak invariant "loc is invalid or loc >= LOCATOR_BASE" holds no more. Would "loc is invalid or loc ^ LOCATOR_BASE <= size" be true? useful?

"Leaves" are empty

This tree is (in a sense) organized so that both keys and satellite data are stored in the internal nodes of the tree, not in the leaves. All leaves are represented by a single node called "nil." All nodes also have a parent pointer, which is not useful for the root node and for the nil node (their parent pointers should equal zero). During a deletion, however, the nil node might have its parent pointer set to the parent of the deleted node.

Linear array representation

In an attempt to simplify the code, I've made the class store its nodes in a linear array for dictionaries of size TREE_THRESH or smaller, currently set at a size of seven nodes. So this doesn't really build a red-black tree unless there are eight or more internal nodes to be kept.

References

The Red-Black tree is due to Bayer, Guibas and Sedgewick. I'm basing my code on the presentation found in CLR, but I didn't follow their pseudocode.

CLR = Cormen, Leiserson and Rivest, Introduction to Algorithms, MIT Press.

The locator pattern is described in Goodrich and Tamassia, Data Structures and Algorithms in Java, section 6.4, John Wiley, 1998.

Member Typedef Documentation

template<typename SATELLITE_TYPE>
typedef DijkstraPriorityQueue< SATELLITE_TYPE >::Key_tp kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::Key_tp
template<typename SATELLITE_TYPE>
typedef DijkstraPriorityQueue< SATELLITE_TYPE >::Loc_tp kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::Loc_tp
template<typename SATELLITE_TYPE>
typedef SATELLITE_TYPE kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::Sat_tp

Constructor & Destructor Documentation

template<typename SATELLITE_TYPE>
kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::Redblack_subtree_sum ( )
inline

default ctor

template<typename SATELLITE_TYPE>
kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::Redblack_subtree_sum ( const Redblack_subtree_sum< SATELLITE_TYPE > &  tree)
inline

copy ctor (same locators will work in this one too)

template<typename SATELLITE_TYPE>
kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::~Redblack_subtree_sum ( )
inline

dtor clears the structure

Member Function Documentation

template<typename SATELLITE_TYPE>
bool kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::access_loc ( Loc_tp  query_loc,
Key_tp key_out,
Sat_tp sat_out 
) const
inlinevirtual

access a record via its locator, a constant-time operation.

Parameters
[in]query_locLocator to look for in the tree.
[out]key_outOptional pointer at which, if not eq. to NULL, this will write the record's key value.
[out]sat_outOptional pointer at which, if not eq. to NULL, this will write the record's satellite field.
Returns
true iff success (i.e., the locator points to a valid record).
Warning
Locators get recycled! Don't erase the same locator twice!

Implements kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE >.

template<typename SATELLITE_TYPE>
const_iterator kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::begin ( ) const
inline
template<typename SATELLITE_TYPE>
void kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::clear ( )
inlinevirtual

destroy the tree or the linear array.

Postcondition
Naturally, this invalidates all iterators and locators.

Implements kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE >.

template<typename SATELLITE_TYPE>
void kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::debug_print ( std::ostream &  ) const
inline

stub: remove print code when not checking aggressively

template<typename SATELLITE_TYPE>
Loc_tp kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::Dijkstra_extraction ( ) const
inlinevirtual

hack proxy to make this and a stochastic pri queue work alike

Implements kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE >.

template<typename SATELLITE_TYPE>
const_iterator kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::end ( ) const
inline
template<typename SATELLITE_TYPE>
bool kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::erase_key ( const Key_tp query_key,
Sat_tp sat_out 
)
inline

erase a key+value pair from the dictionary

Parameters
[in]query_keyKey for which to search. If multiple key+value pairs have been inserted in the dictionary using the same key, it is undefined which one will be found.
[out]sat_outOptional pointer to which, if not equal to NULL, this will write the satellite data when and if the key value is found.
Returns
true iff the key is found
Postcondition
either this returns false, or one key+value pair is removed from the dictionary having a key equal to that of query_key (xor). As stated, it is undefined which key+value pair is removed when there are multiple records sharing the same query_key number, although of course the removed pair will be one of those records.
If the key is found, the iterators are invalidated, as is the locator corresponding to the deleted node.
template<typename SATELLITE_TYPE>
bool kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::erase_loc ( Loc_tp  query_loc)
inlinevirtual

remove the record indicated by query_loc, or return false if bad

Parameters
[in]query_locLocator of record to remove
Returns
true iff success (i.e., the locator points to a valid record).
Warning
Locators get recycled! Don't erase the same locator twice!
Postcondition
This invalidates the query locator and all iterators.

Implements kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE >.

template<typename SATELLITE_TYPE>
bool kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::find_key ( const Key_tp key,
Sat_tp sat_out,
Loc_tp loc_out 
)
inline

search for a key in the dictionary; return first one.

Parameters
[in]keykey value in node to be searched for. If multiple (key,value) pairs have been inserted in the dictionary using the same key, it is undefined which one will be found. Also remember the problems that occur when searching for exact floating-point equality.
[out]sat_outOptional output storage for satellite data. If equal to NULL, satellite data is ignored.
[out]loc_outOptional output storage for locator of this node (biased). If equal to NULL, locator is ignored.

If the key is not found, the output locations are not written.

Returns
true iff the exact key is found.
template<typename SATELLITE_TYPE>
Loc_tp kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::ins_max_key ( const Sat_tp sat)
inlinevirtual

the following is a hack to mimic StochasticPriorityQueue

Implements kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE >.

template<typename SATELLITE_TYPE>
Loc_tp kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::insert ( const Key_tp key,
const Sat_tp sat 
)
inlinevirtual

insert a new key+value pair in the dictionary

Postcondition
This invalidates the iterators.

Implements kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE >.

template<typename SATELLITE_TYPE>
bool kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::is_empty ( ) const
inlinevirtual

return whether the size is zero

Implements kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE >.

template<typename SATELLITE_TYPE>
Loc_tp kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::loc_max ( ) const
inline

return the locator for the record with the maximum key, or 0

template<typename SATELLITE_TYPE>
Loc_tp kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::loc_min ( ) const
inline

return the locator for the record with the minimum key, or 0

template<typename SATELLITE_TYPE>
Loc_tp kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::loc_using_cumulative_key_sum ( Key_tp  cumulative_keysum) const
inline

fetch a node based on inorder cumulative sum of tree keys

Parameters
cumulative_keysumvalue we want to find or minimally exceed.
Precondition
if tree contains nonpositive keys, behavior is undefined.
Returns
See exposition below: returns locator of a node such that the sum of its key and the keys of all nodes less than it is at least cumulative_keysum, in a minimal sense.

This method is most useful when keys are all positive. Keys do not need to be distinct. If keys are nonpositive, screwy things will probably occur.

Let n denote a node and n.k denote its key. Neither n or k will be used to represent integers (but i, j will).

Let n1,n2,n3,... be an inorder listing of nodes, such that n1.k <= n2.k <= n3.k <= ...

Now consider the cumulative sum of keys starting with n1: s_0 = 0; s_1 = s_0 + n1.k; s_2 = s_1 + n2.k; ... As a special case, let S equal the sum of all nodes' keys.

If it exists, this method finds a value j such that s_{j-1} < cumulative_keysum <= s_j and if such a value exists, this returns the locator of node nj.

Degenerate cases:

  • If cumulative_keysum is nonpositive, this returns the locator of n1.
  • If S <= cumulative_keysum this method returns the locator of the last node in the inorder listing.
template<typename SATELLITE_TYPE>
Redblack_subtree_sum& kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::operator= ( const Redblack_subtree_sum< SATELLITE_TYPE > &  tree)
inline

assignment operator (same locators will work in this one too)

Postcondition
Naturally, this invalidates all previous iterators and locators.
template<typename SATELLITE_TYPE>
bool kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::rekey_loc ( Loc_tp  query_loc,
const Key_tp newkey 
)
inlinevirtual

change the key value for a node to a new value, O(log n) time

Implements kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE >.

template<typename SATELLITE_TYPE>
Key_tp kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::root_sum ( ) const
inline

return subtree sum at root node (i.e., the sum of all keys).

template<typename SATELLITE_TYPE>
size_t kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::size ( ) const
inlinevirtual

return the number of key+value pairs in the dictionary.

Implements kjb::qd::DijkstraPriorityQueue< SATELLITE_TYPE >.

template<typename SATELLITE_TYPE>
bool kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::tree_valid_in_nlogn_time ( ) const
inline

scan dictionary in linear time to verify invariants are valid

Friends And Related Function Documentation

template<typename SATELLITE_TYPE>
friend class const_iterator
friend

The documentation for this class was generated from the following file: