$ is a collection of items (type $pq\_item$). Every item contains a priority from a linearly ordered type $P$ and an information from an arbitrary type $I$. $P$ is called the priority type of $Q$ and $I$ is called the information type of $Q$. The number of items in $Q$ is called the size of $Q$. If $Q$ has size zero it is called the empty priority queue. We use $\

$ to denote a $pq\_item$\ with priority $p$ and information $i$. \creation Q \create $p\_queue\

$ {$ $} { creates an instance $Q$ of type $p\_queue\

$ and initializes it with the
empty priority queue. }
\operations 2 5
\op $P$ {prio$(pq\_item\ it)$}
{ returns the priority of item $it$.\\
\precond $it$ is an item in $Q$. }
\op $I$ {inf$(pq\_item\ it)$}
{ returns the information of item $it$.\\
\precond $it$ is an item in $Q$. }
\op $pq\_item$ {insert$( P\ x, \ I\ i)$}
{ adds a new item $\ $ is a priority queue implemented by data type $impl$.
$impl$ must be one of the priority queue implementations listed in
section \ref{Implementations Priority Queues} or a user defined data structure
fulfilling the specification given in section \ref{User Implementations
Priority Queues}. Note that the priority type $P$ must linearly ordered.
%-------include file extract/dictionary.tex
\manpage {dictionary} K,I {Dictionaries}
\definition
An instance $D$ of the parameterized data type $dictionary\ $ to denote the
item with point $p$, and information $i$. For each point $p$ there is at most
one item $\ \in S$. Beside the normal dictionary operations, the data
type $point\_set$ provides operations for rectangular range queries and
nearest neighbor queries.
\creation S
\create $point\_set\*$ is a collection
of items ($ps\_item$). Every item in $S$ contains a two-dimensional point as
key (data type $point$), and an information from data type $I$, called the
information type of $S$. The number of items in $S$ is called the size of $S$.
A point set of size zero is said to be empty. We use $\**$ {$ $}
{ creates an instance $S$ of type $point\_set\ $ and initializes $S$ to
the empty set. }
\operations 2.5 5.2
\op $point$ {key$(ps\_item\ it)$}
{ returns the point of item $it$.\\
\precond $it$ is an item in $S$. }
\op $I$ {inf$(ps\_item\ it)$}
{ returns the information of item $it$.\\
\precond $it$ is an item in $S$. }
\op $ps\_item$ {insert$(point\ p, \ I\ i)$}
{ associates the information $i$ with point $p$.
If there is an item $\*

$ in $S$ then $j$ is replaced by $i$, else a new item $\

$ is added to $S$. In both cases the item is returned. } \op $ps\_item$ {lookup$(point\ p)$} { returns the item with point $p$ (nil if no such item exists in S). } \op $ps\_item$ {nearest\_neighbor$(point\ q)$} { returns the item $\

\ \in\ S$ such that
the distance between $p$ and $q$ is minimal. }
\opl $list\ \ \in\ S$ with\\
$x_0 \le p$.xcoord() $\le x_1$ and\\
$y_0 \le p$.ycoord() $\le y_1$. }
\op $list\