freepascal.compiler/packages/fcl-stl/doc/set.tex

\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}

Memory complexity:
Size of stored elements + 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, if given element is already there nothing
happens.} \\\hline\hline

\verb!function InsertAndGetIterator! & $O(\lg N)$\\
\verb!(value: T):TIterator! & \\ \hline
\multicolumn{2}{|m{15cm}|}{Inserts element into set, if given element is already there nothing
happens. Also returns iterator pointing on given element.} \\\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):TIterator! & O(lg N) \\\hline
\multicolumn{2}{|m{15cm}|}{Searches for value in set. If value is not there returns nil. Otherwise
returns iterator, which can be used for retrieving data from set.} \\\hline\hline

\verb!function FindLess(value: T):TIterator! & 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 iterator, which can be used for retrieving data from set.} \\\hline\hline

\verb!function FindLessEqual(value: T):TIterator! & 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 iterator, which can be used for retrieving data from set.} \\\hline\hline

\verb!function FindGreater(value: T):TIterator! & 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 iterator, which can be used for retrieving data from set.} \\\hline\hline

\verb!function FindGreaterEqual(value: T):TIterator! & 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 iterator, which can be used for retrieving data from set.} \\\hline\hline

\verb!function Min:TIterator! & O(lg N) \\\hline
\multicolumn{2}{|m{15cm}|}{Returns iterator pointing to the smallest element of set. If set is empty returns
nil.} \\\hline\hline

\verb!function Max:TIterator! & O(lg N) \\\hline
\multicolumn{2}{|m{15cm}|}{Returns iterator pointing to the largest element of set. If set is empty returns
nil.} \\\hline\hline

\verb!function IsEmpty(): boolean! & O(1) \\ \hline
\multicolumn{2}{|m{15cm}|}{Returns true when set is empty.} \\\hline

\end{longtable}

Some methods return type TIterator, which has following methods:
\begin{longtable}{|m{10cm}|m{5cm}|}                                                             
\hline
Method & Complexity guarantees \\ \hline                                                  
\multicolumn{2}{|m{15cm}|}{Description} \\ \hline\hline                                               
\verb!function Next:boolean! & O(lg N) worst case, but traversal from smallest element to
largest takes O(N) time \\\hline
\multicolumn{2}{|m{15cm}|}{Moves iterator to smallest larger element in set. Returns true on
success. If the iterator is already pointing on largest element returns false.} \\\hline\hline

\verb!function Prev:boolean! & O(lg N) worst case, but traversal from largest element to
smallest takes O(N) time \\\hline
\multicolumn{2}{|m{15cm}|}{Moves iterator to largest smaller element in set. Returns true on
success. If the iterator is already pointing on smallest element returns false.} \\\hline\hline

\verb!property Data:T! & $O(1)$ \\\hline
\multicolumn{2}{|m{15cm}|}{Property, which allows reading of the element.} \\\hline

\end{longtable}