All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Classes | Namespaces | Macros
redblack.h File Reference

definition of class Redblack_subtree_sum. More...

#include <l/l_sys_lib.h>
#include <l/l_sys_io.h>
#include <l/l_debug.h>
#include <l_cpp/l_util.h>
#include <qd_cpp/diprique.h>
#include <iosfwd>
#include <algorithm>
#include <numeric>
#include <limits>
#include <new>
#include <iterator>
#include <vector>

Go to the source code of this file.


class  kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >
 a balanced binary search tree storing subtree sums in each node. More...
class  kjb::qd::Redblack_subtree_sum< SATELLITE_TYPE >::const_iterator
 iterator class for a tree – lets you access node locators. More...


 Classes and functions for dealing with trajectory files.
 support for the path algorithm I call the quasi-Dijkstra method.



Detailed Description

definition of class Redblack_subtree_sum.

Andrew Predoehl Recently I've been concerned about the potential for bad performance when a tree that was once very full becomes almost empty. The array implementation of location_list could be as big as the big tree in that case, which is bad. As a consequence I added a map implementation of location_list, which is much cleaner, but now access to a record via its locator uses O(log n) time, where n is the tree size, rather than O(1) time when it was an array. In tests, the array version uses about half the time as the map version, in production-mode use. But the complexity of the array version is ugly.

Macro Definition Documentation


Set this macro to 0 or 1 to select the implemenation. 1 is faster.