Definition
An instance D of the parameterized data type d2_dictionary<K1,K2,I> is a collection of items ( dic2item ). Every item in D contains a key from the linearly ordered data type K1 , a key from the linearly ordered data type K2 , and an information from data type I . K1 and K2 are called the key types of D , and I is called the information type of D . If K1 resp. K2 are user-defined types, you have to provide a compare function for type K1 resp. K2 (see Section User Defined Parameter Types). The number of items in D is called the size of D . A two-dimensional dictionary of size zero is said to be empty. We use < k_{1}, k_{2}, i > to denote the item with first key k_{1} , second key k_{2} , and information i . For each pair (k_{1}, k_{2}) K1 x K2 there is at most one item < k_{1}, k_{2}, i > D . Additionally to the normal dictionary operations, the data type d2dictionary supports rectangular range queries on K1 x K2 .
#include < LEDA/geo/d2_dictionary.h >
Creation
d2_dictionary< K1,K2,I> | D | creates an instance D of type d2_dictionary<K1,K2,I> and initializes D to the empty dictionary. |
Operations
const K1& | D.key1(dic2_item it) | returns the first key of item it
.
Precondition it is an item in D. |
const K2& | D.key2(dic2_item it) | returns the second key of item it
.
Precondition it is an item in D. |
const I& | D.inf(dic2_item it) | returns the information of item it
.
Precondition it is an item in D. |
I& | D[dic2_item it] | returns a reference to the information of item it
.
Precondition it is an item in D. |
dic2_item | D.min_key1() | returns the item with minimal first key. |
dic2_item | D.min_key2() | returns the item with minimal second key. |
dic2_item | D.max_key1() | returns the item with maximal first key. |
dic2_item | D.max_key2() | returns the item with maximal second key. |
dic2_item | D.insert(const K1& x, const K2& y, const I& i) | |
associates the information i with the keys x and y . If there is an item < x, y, j tex2html_wrap_inline> in D then j is replaced by i , else a new item < x, y, i tex2html_wrap_inline> is added to D . In both cases the item is returned. | ||
dic2_item | D.lookup(const K1& x, const K2& y) | |
returns the item with keys x and y (nil if no such item exists in D). | ||
list< dic2_item> | D.range_search(const K1& x0, const K1& x1, const K2& y0, const K2& y1) | |
returns the list of all items < k_{1}, k_{2}, i tex2html_wrap_inline> in D with x_{0} < = k_{1} < = x_{1} and y_{0} < = k_{2} < = y_{1} . | ||
list< dic2_item> | D.all_items() | returns the list of all items of D. |
void | D.del(const K1& x, const K2& y) | |
deletes the item with keys x and y from D. | ||
void | D.del_item(dic2_item it) | removes item it
from D.
Precondition it is an item in D. |
void | D.change_inf(dic2_item it, const I& i) | |
makes i
the information of item it
.
Precondition it is an item in D. |
||
void | D.clear() | makes D the empty d2_dictionary. |
bool | D.empty() | returns true if D is empty, false otherwise. |
int | D.size() | returns the size of D. |
Implementation
Two-dimensional dictionaries are implemented by dynamic two-dimensional range trees [90,57] based on BB[ ] trees. Operations insert, lookup, del_item, del take time O(log^{2}n) , range_search takes time O(k + log^{2}n) , where k is the size of the returned list, key, inf, empty, size, change_inf take time O(1) , and clear takes time O(n log n) . Here n is the current size of the dictionary. The space requirement is O(n log n) .