diff options
Diffstat (limited to 'packages/fcl-stl/doc/set.tex')
| -rw-r--r-- | packages/fcl-stl/doc/set.tex | 76 |
1 files changed, 76 insertions, 0 deletions
diff --git a/packages/fcl-stl/doc/set.tex b/packages/fcl-stl/doc/set.tex new file mode 100644 index 0000000000..2e7259a118 --- /dev/null +++ b/packages/fcl-stl/doc/set.tex @@ -0,0 +1,76 @@ +\chapter{TSet} + +Implements container for storing ordered set of unique elements. +Takes 2 arguments for specialization, first one is type of elements, second one is comparator class. +Usage example: + +\lstinputlisting[language=Pascal]{setexample.pp} + +Some methods return type of PNode. It has field Data, which can be used for retrieving data from +that node. This node can be also used for navigation between elements by methods of set class. +(But don't do anything else with it, you can lose data integrity.) + +Memory complexity: +Size of stored base + constant overhead for each stored element (3 pointers + one boolean). + +Members list: + +\begin{longtable}{|m{10cm}|m{5cm}|} +\hline +Method & Complexity guarantees \\ \hline +\multicolumn{2}{|m{15cm}|}{Description} \\ \hline\hline + +\verb!Create! & O(1) \\ \hline +\multicolumn{2}{|m{15cm}|}{Constructor. Creates empty set.} \\ \hline\hline + +\verb!function Size(): SizeUInt! & O(1) \\ \hline +\multicolumn{2}{|m{15cm}|}{Returns number of elements in set.} \\\hline\hline + +\verb!procedure Insert(value: T)! & +O(lg N), N is number of elements in set \\ \hline +\multicolumn{2}{|m{15cm}|}{Inserts element into set.} \\\hline\hline + +\verb!procedure Delete(value: T)! & +O(lg N), N is number of elements in set \\ \hline +\multicolumn{2}{|m{15cm}|}{Deletes value from set. If element is not in set, nothing happens.} \\\hline\hline + +\verb!function Find(value: T):PNode! & O(lg N) \\\hline +\multicolumn{2}{|m{15cm}|}{Searches for value in set. If value is not there returns nil. Otherwise +returns pointer to tree node (type PNode), which can be used for retrieving data from set.} \\\hline\hline + +\verb!function FindLess(value: T):PNode! & O(lg N) \\\hline +\multicolumn{2}{|m{15cm}|}{Searches for greatest element less than value in set. If such element is not there returns nil. Otherwise +returns pointer to tree node (type PNode), which can be used for retrieving data from set.} \\\hline\hline + +\verb!function FindLessEqual(value: T):PNode! & O(lg N) \\\hline +\multicolumn{2}{|m{15cm}|}{Searches for greatest element less or equal than value in set. If such element is not there returns nil. Otherwise +returns pointer to tree node (type PNode), which can be used for retrieving data from set.} \\\hline\hline + +\verb!function FindGreater(value: T):PNode! & O(lg N) \\\hline +\multicolumn{2}{|m{15cm}|}{Searches for smallest element greater than value in set. If such element is not there returns nil. Otherwise +returns pointer to tree node (type PNode), which can be used for retrieving data from set.} \\\hline\hline + +\verb!function FindGreaterEqual(value: T):PNode! & O(lg N) \\\hline +\multicolumn{2}{|m{15cm}|}{Searches for smallest element greater or equal than value in set. If such element is not there returns nil. Otherwise +returns pointer to tree node (type PNode), which can be used for retrieving data from set.} \\\hline\hline + +\verb!function Min:PNode! & O(lg N) \\\hline +\multicolumn{2}{|m{15cm}|}{Returns node containing smallest element of set. If set is empty returns +nil.} \\\hline\hline + +\verb!function Max:PNode! & O(lg N) \\\hline +\multicolumn{2}{|m{15cm}|}{Returns node containing largest element of set. If set is empty returns +nil.} \\\hline\hline + +\verb!function Next(x:PNode):PNode! & O(lg N) worst case, but traversal from smallest element to +largest takes O(N) time \\\hline +\multicolumn{2}{|m{15cm}|}{Returns successor of x. If x is largest element of set, returns nil.} \\\hline\hline + +\verb!function Prev(x:PNode):PNode! & O(lg N) worst case, but traversal from largest element to +smallest takes O(N) time \\\hline +\multicolumn{2}{|m{15cm}|}{Returns predecessor of x. If x is smallest element of set, returns nil.} \\\hline\hline + +\verb!function IsEmpty(): boolean! & O(1) \\ \hline +\multicolumn{2}{|m{15cm}|}{Returns true when set is empty.} \\\hline + +\end{longtable} |