diff options
Diffstat (limited to 'packages/fcl-stl/doc/map.tex')
| -rw-r--r-- | packages/fcl-stl/doc/map.tex | 87 |
1 files changed, 87 insertions, 0 deletions
diff --git a/packages/fcl-stl/doc/map.tex b/packages/fcl-stl/doc/map.tex new file mode 100644 index 0000000000..72edbb0e3d --- /dev/null +++ b/packages/fcl-stl/doc/map.tex @@ -0,0 +1,87 @@ +\chapter{TMap} + +Implements container for ordered associative array with unique keys. +Takes 3 arguments for specialization, first one is type of keys, second one is type of values, third +one is comparator class for keys. +Usage example: + +\lstinputlisting[language=Pascal]{mapexample.pp} + +Some methods return type TMSet.PNode. Usefull fields are Data.Key, Data.Value, for retrieving +actual Key and Value from node. This node can be also used for navigation between elements by methods of set class. +You can also change value in node (but not key). +(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 map.} \\ \hline\hline + +\verb!function Size(): SizeUInt! & O(1) \\ \hline +\multicolumn{2}{|m{15cm}|}{Returns number of elements in map.} \\\hline\hline + +\verb!procedure Insert(key: TKey; value: TValue)! & +O(lg N), N is number of elements in map \\ \hline +\multicolumn{2}{|m{15cm}|}{Inserts key value pair into map. If key was already there, it will have +new value assigned.} \\\hline\hline + +\verb!procedure Delete(key: TKey)! & +O(lg N) \\ \hline +\multicolumn{2}{|m{15cm}|}{Deletes key (and associated value) from map. If element is not in map, nothing happens.} \\\hline\hline + +\verb!function Find(key: T):TMSet.PNode! & O(lg N) \\\hline +\multicolumn{2}{|m{15cm}|}{Searches for key in map. If value is not there returns nil. Otherwise +returns pointer to tree node (type TMSet.PNode), which can be used for retrieving data from map.} \\\hline\hline + +\verb!function FindLess(key: T):TMSet.PNode! & O(lg N) \\\hline +\multicolumn{2}{|m{15cm}|}{Searches for greatest element less than key in map. If such element is not there returns nil. Otherwise +returns pointer to tree node (type TMSet.PNode), which can be used for retrieving data from map.} \\\hline\hline + +\verb!function FindLessEqual(key: T):TMSet.PNode! & O(lg N) \\\hline +\multicolumn{2}{|m{15cm}|}{Searches for greatest element less or equal than key in map. If such element is not there returns nil. Otherwise +returns pointer to tree node (type TMSet.PNode), which can be used for retrieving data from map.} \\\hline\hline + +\verb!function FindGreater(key: T):TMSet.PNode! & O(lg N) \\\hline +\multicolumn{2}{|m{15cm}|}{Searches for smallest element greater than key in map. If such element is not there returns nil. Otherwise +returns pointer to tree node (type TMSet.PNode), which can be used for retrieving data from map.} \\\hline\hline + +\verb!function FindGreaterEqual(key: T):TMSet.PNode! & O(lg N) \\\hline +\multicolumn{2}{|m{15cm}|}{Searches for smallest element greater or equal than key in map. If such element is not there returns nil. Otherwise +returns pointer to tree node (type TMSet.PNode), which can be used for retrieving data from map.} \\\hline\hline + +\verb!function Min:TMSet.PNode! & O(lg N) \\\hline +\multicolumn{2}{|m{15cm}|}{Returns node containing smallest key of map. If map is empty returns +nil.} \\\hline\hline + +\verb!function Max:TMSet.PNode! & O(lg N) \\\hline +\multicolumn{2}{|m{15cm}|}{Returns node containing largest key of map. If map is empty returns +nil.} \\\hline\hline + +\verb!function Next(x:TMSet.PNode):TMSet.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 key of map, returns nil.} \\\hline\hline + +\verb!function Prev(x:TMSet.PNode):TMSet.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 key of map, returns nil.} \\\hline\hline + +\verb!function IsEmpty(): boolean! & O(1) \\ \hline +\multicolumn{2}{|m{15cm}|}{Returns true when map is empty.} \\\hline + +\verb!function GetValue(key:TKey):TValue! & O(lg N) \\\hline +\multicolumn{2}{|m{15cm}|}{Returns value associated with key. Is key isn't in map crashes.} \\\hline + +\verb!property item[i: Key]: TValue; default;! & O(ln N) \\\hline +\multicolumn{2}{|m{15cm}|}{Property for accessing key i in map. Can be used just by square +brackets (its default property).} \\\hline\hline + + +\end{longtable} |