Stores an Interval Tree. More...
#include <intervaltree.hpp>
Inheritance diagram for ygg::IntervalTree< Node, NodeTraits, Options, Tag >:
Classes | |
| class | QueryResult |
Public Types | |
| using | Key = typename NodeTraits::key_type |
| using | MyClass = IntervalTree< Node, NodeTraits, Options, Tag > |
| using | INB = ITreeNodeBase< Node, NodeTraits, Options, Tag > |
| using | ENodeTraits = intervaltree_internal::ExtendedNodeTraits< Node, INB, NodeTraits > |
| using | BaseTree = RBTree< Node, intervaltree_internal::ExtendedNodeTraits< Node, INB, NodeTraits >, Options, Tag, intervaltree_internal::IntervalCompare< Node, NodeTraits > > |
Public Member Functions | |
| bool | verify_integrity () const |
| void | dump_to_dot (const std::string &filename) const |
| template<class Comparable > | |
| QueryResult< Comparable > | query (const Comparable &q) const |
| Queries intervals contained in the interval tree. More... | |
| template<class Comparable > | |
| BaseTree::template const_iterator< false > | interval_upper_bound (const Comparable &query_range) const |
| void | fixup_maxima (Node &lowest) |
Private Types | |
| using | NB = RBTreeNodeBase< Node, Options, Tag > |
| using | TB = bst::BinarySearchTree< Node, Options, Tag, intervaltree_internal::IntervalCompare< Node, NodeTraits >, rbtree_internal::ColorParentStorage< Node, Options::compress_color > > |
| using | iterator = typename TB::template iterator< reverse > |
| using | const_iterator = typename TB::template const_iterator< reverse > |
| using | Path = std::vector< Node *> |
Private Member Functions | |
| void | insert (Node &node) CMP_NOEXCEPT(node) |
| Inserts <node> into the tree. More... | |
| void | insert (Node &node, Node &hint) CMP_NOEXCEPT(node) |
| void | insert (Node &node, iterator< false > hint) CMP_NOEXCEPT(node) |
| void | remove (Node &node) CMP_NOEXCEPT(node) |
| Removes <node> from the tree. More... | |
| utilities::select_type_t< size_t, Node *, Options::stl_erase > | erase (const Comparable &c) CMP_NOEXCEPT(c) |
Deletes a node that compares equally to from the tree. More... | |
| utilities::select_type_t< const iterator< reverse >, Node *, Options::stl_erase > | erase (const iterator< reverse > &it) CMP_NOEXCEPT(*it) |
| Deletes a node by iterator. More... | |
| void | remove_to_leaf (Node &node) CMP_NOEXCEPT(node) |
| void | fixup_after_delete (Node *parent, bool deleted_left) noexcept |
| void | insert_leaf_base (Node &node, Node *start) CMP_NOEXCEPT(node) |
| void | fixup_after_insert (Node *node) noexcept |
| void | rotate_left (Node *parent) noexcept |
| void | rotate_right (Node *parent) noexcept |
| void | swap_nodes (Node *n1, Node *n2, bool swap_colors=true) noexcept |
| void | replace_node (Node *to_be_replaced, Node *replace_with) noexcept |
| void | swap_unrelated_nodes (Node *n1, Node *n2) noexcept |
| void | swap_neighbors (Node *parent, Node *child) noexcept |
| void | verify_black_root () const |
| void | verify_black_paths (const Node *node, unsigned int *path_length) const |
| void | verify_red_black (const Node *node) const |
| Node * | get_first_equal (Node *n) noexcept |
| const_iterator< false > | find (const Comparable &query) const CMP_NOEXCEPT(query) |
| Finds an element in the tree. More... | |
| iterator< false > | find (const Comparable &query) CMP_NOEXCEPT(query) |
| iterator< false > | find (const Comparable &query, Callbacks *cbs) |
| const_iterator< false > | upper_bound (const Comparable &query) const CMP_NOEXCEPT(query) |
| Upper-bounds an element. More... | |
| iterator< false > | upper_bound (const Comparable &query) CMP_NOEXCEPT(query) |
| const_iterator< false > | lower_bound (const Comparable &query) const CMP_NOEXCEPT(query) |
| Lower-bounds an element. More... | |
| iterator< false > | lower_bound (const Comparable &query) CMP_NOEXCEPT(query) |
| const_iterator< false > | cbegin () const noexcept |
| const_iterator< false > | cend () const noexcept |
| const_iterator< false > | begin () const noexcept |
| iterator< false > | begin () noexcept |
| const_iterator< false > | end () const noexcept |
| iterator< false > | end () noexcept |
| const_iterator< true > | crbegin () const noexcept |
| const_iterator< true > | crend () const noexcept |
| const_iterator< true > | rbegin () const noexcept |
| iterator< true > | rbegin () noexcept |
| const_iterator< true > | rend () const noexcept |
| iterator< true > | rend () noexcept |
| const_iterator< false > | iterator_to (const Node &node) const noexcept |
| iterator< false > | iterator_to (Node &node) noexcept |
| size_t | size () const noexcept |
| void | clear () noexcept |
| Removes all elements from the tree. More... | |
| bool | empty () const noexcept |
| Returns whether the tree is empty. More... | |
| Node * | get_root () const noexcept |
| Node * | get_smallest () const noexcept |
| Node * | get_largest () const noexcept |
| Node * | get_uncle (Node *node) const noexcept |
| void | dump_to_dot_base (const std::string &filename, NodeNameGetter name_getter) const |
| void | output_node_base (const Node *node, std::ofstream &out, NodeNameGetter name_getter) const |
Static Private Member Functions | |
| static Node * | get_parent (Node *n) noexcept |
| static Node * | get_left_child (Node *n) noexcept |
| static Node * | get_right_child (Node *n) noexcept |
Private Attributes | |
| Node * | root |
| intervaltree_internal::IntervalCompare< Node, NodeTraits > | cmp |
| SizeHolder< Options::constant_time_size > | s |
Detailed Description
template<class Node, class NodeTraits, class Options = DefaultOptions, class Tag = int>
class ygg::IntervalTree< Node, NodeTraits, Options, Tag >
Stores an Interval Tree.
This class stores an interval tree on the nodes it contains. It is implemented via the 'augmented red-black tree' described by Cormen et al.
- Template Parameters
-
Node The node class for this Interval Tree. Must be derived from ITreeNodeBase. NodeTraits The node traits for this Interval Tree. Must be derived from Options Passed through to RBTree. See there for documentation. Tag Used to add nodes to multiple interval trees. See RBTree documentation for details.
Member Function Documentation
◆ query()
template<class Node , class NodeTraits , class Options = DefaultOptions, class Tag = int>
template<class Comparable >
| QueryResult<Comparable> ygg::IntervalTree< Node, NodeTraits, Options, Tag >::query | ( | const Comparable & | q | ) | const |
Queries intervals contained in the interval tree.
This method queries for intervals overlapping a query interval. The query parameter q can be anything that is comparable to an interval. A class <Comparable> is comparable to an interval if the NodeTraits implement a get_lower(const Comparable &) and get_upper(const Comparable &) method.
The return value is a QueryResult that contains all intervals that overlap the given query.
- Parameters
-
q Anything that is comparable (i.e., has get_lower() and get_upper() methods in NodeTraits) to an interval
- Returns
- A QueryResult holding all intervals in the tree that overlap q
The documentation for this class was generated from the following file:
- /home/lukas/src/intervaltree/ygg/src/intervaltree.hpp
