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. 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) in K1 x K2 there is at most one item <k_1,k_2,i> in D. Additionally to the normal dictionary operations, the data type d2_dictionary supports rectangular range queries on K1x K2.

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

K1	D.key1(dic2_item it)	returns the first key of item it. Precondition: it is an item in D.
K2	D.key2(dic2_item it)	returns the second key of item it. Precondition: it is an item in D.
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(K1 x, K2 y, I i)	associates the information i with the keys x and y. If there is an item <x,y,j >in D then j is replaced by i, else a new item <x,y,i >is added to D. In both cases the item is returned.
dic2_item	D.lookup(K1 x, K2 y)	returns the item with keys x and y (nil if no such item exists in D).
list<dic2_item>	D.range_search(K1 x0, K1 x1, K2 y0, K2 y1)
		returns the list of all items <k_1,k_2,i >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(K1 x, 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, 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 [79,51] based on BB[alpha] 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(nlog n). Here n is the current size of the dictionary. The space requirement is O(nlog n).