"SortedKeyStore" (Data Structure)
"SortedKeyStore"
represents a store of keys and values that maintains the keys in a sorted order.
Details
- A sorted key store is typically used to store keys and values.
- The keys in a sorted key store are maintained in a sorted order:
-
CreateDataStructure[ "SortedKeyStore"] create a new empty "SortedKeyStore" Typed[x,"SortedKeyStore"] give x the type "SortedKeyStore" - For a data structure of type "SortedKeyStore", the following operations can be used:
-
ds["Copy"] return a copy of ds time: O(n) ds["Elements"] return a list of the key-value pairs of ds time: O(n) ds["EmptyQ"] True, if ds has no entries time: O(1) ds["Insert",keyvalue] add key to ds with the associated value and return True if the addition changed ds time: O(log n) ds["KeyDrop",key] drop key and its value from ds time: O(log n) ds["KeyDropAll"] drop all the keys and their values from ds time: O(n) ds["KeyExistsQ",key] True, if the key exists in ds time: O(log n) ds["Keys"] return the keys in ds as a sorted list time: O(n) ds["KeyValueFold",fun,init] apply fun to the rules of ds, starting with init, accumulating a result time: O(n) ds["KeyValueScan",fun] apply fun to the rules of ds time: O(n) ds["Length"] the number of key-value pairs stored in ds time: O(1) ds["Lookup",key] return the value stored with key in ds; if the key is not found return a Missing object time: O(log n) ds["Lookup",key,defFun] return the value stored with key in ds; if the key is not found return defFun[key] time: O(log n) ds["PeekFirst"] return the first key-value pair in ds time: O(1) ds["PeekLast"] return the last key-value pair in ds time: O(1) ds["PopFirst"] remove the first key-value pair in ds and return it time: O(1) ds["PopLast"] remove the first key-value pair in ds and return it time: O(1) ds["Values"] return the values in ds as a list sorted by the corresponding keys time: O(n) ds["Visualization"] return a visualization of ds time: O(n) - The following functions are also supported:
-
dsi===dsj True, if dsi equals dsj FullForm[ds] full form of ds Information[ds] information about ds InputForm[ds] input form of ds Normal[ds] convert ds to a normal expression - A data structure of type "SortedKeyStore" can be created with the following option:
-
"SortDirection" "Forward" whether to sort the keys in forward or reverse mode
Examples
open all close allBasic Examples (1)
A new empty "SortedKeyStore" can be created with CreateDataStructure:
ds = CreateDataStructure["SortedKeyStore"]Insert a key-value pair given as a rule into the "SortedKeyStore" data structure:
ds["Insert", 4 -> f[4]]ds["KeyExistsQ", 4]A key can be dropped from the store:
ds["KeyDrop", 4]Now the key is not in the store:
ds["KeyExistsQ", 4]Insert several keys and values:
Do[ds["Insert", i -> -i], {i, 20}]The keys are returned in sorted order:
ds["Keys"]The values are returned in the order of their keys:
ds["Values"]Return an expression version of ds:
Normal[ds]A visualization of the data structure can be generated:
ds["Visualization"]Scope (3)
Information (1)
A new "SortedKeyStore" can be created with CreateDataStructure:
ds = CreateDataStructure["SortedKeyStore"]Information about the data structure ds:
Information[ds]Traversal (1)
Functional traversals can be made. They traverse the entries in order.
A new "SortedKeyStore" can be created with CreateDataStructure and a number of elements inserted:
ds = CreateDataStructure["SortedKeyStore"];
Do[ds["Insert", i -> -i], {i, 10}];Each key-value pair can be visited and a function applied:
ds["KeyValueScan", Print]
Each key-value pair can be visited and a function applied to accumulate a result:
ds["KeyValueFold", #1 + Last[#2]&, 0]SortDirection (1)
By default, the keys are sorted in an increasing direction:
ds = CreateDataStructure["SortedKeyStore"];
Do[ds["Insert", i -> i], {i, 10}];
ds["Keys"]The "SortDirection" option allows keys to be sorted in a decreasing direction:
ds = CreateDataStructure["SortedKeyStore", "SortDirection" -> "Reverse"];
Do[ds["Insert", i -> i], {i, 10}];
ds["Keys"]