next up previous contents index
Next: Point Sets and Delaunay Up: Advanced Data Types for Previous: Advanced Data Types for   Contents   Index


Two-Dimensional Dictionaries ( d2_dictionary )

Definition

An instance D of the parameterized data type d2_dictionary<K1,K2,I> is a collection of items ( dic2$\_$item). 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 < k1, k2, i > to denote the item with first key k1, second key k2, and information i. For each pair (k1, k2) $\in$ K1 x K2 there is at most one item < k1, k2, i > $\in$ D. Additionally to the normal dictionary operations, the data type d2$\_$dictionary 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, jtex2html_wrap_inline> in D then j is replaced by i, else a new item < x, y, itex2html_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 < k1, k2, itex2html_wrap_inline> in D with x0 < = k1 < = x1 and y0 < = k2 < = y1.

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[$\alpha$] trees. Operations insert, lookup, del_item, del take time O(log2n), range_search takes time O(k + log2n), 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).


next up previous contents index
Next: Point Sets and Delaunay Up: Advanced Data Types for Previous: Advanced Data Types for   Contents   Index