* Initial check-in of stl

git-svn-id: http://svn.freepascal.org/svn/fpc/trunk@17233 3ad0048d-3df7-0310-abae-a5850022a9f2

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}