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.

Classes
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...

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

Macros
#define	REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY   1

Detailed Description

definition of class Redblack_subtree_sum.

Author

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

#define REDBLACK_H_2014_NOV_13_LOCATION_LIST_IMPL_USES_ARRAY   1

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