"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 dstime: O(n)
    ds["Elements"]return a list of the key-value pairs of dstime: O(n)
    ds["EmptyQ"]True, if ds has no entriestime: O(1)
    ds["Insert",keyvalue]add key to ds with the associated value and return True if the addition changed dstime: 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 dstime: O(log n)
    ds["Keys"]return the keys in ds as a sorted listtime: O(n)
    ds["KeyValueFold",fun,init]apply fun to the rules of ds, starting with init, accumulating a resulttime: O(n)
    ds["KeyValueScan",fun]apply fun to the rules of dstime: O(n)
    ds["Length"]the number of key-value pairs stored in dstime: O(1)
    ds["Lookup",key]return the value stored with key in ds; if the key is not found return a Missing objecttime: 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 dstime: O(1)
    ds["PeekLast"]return the last key-value pair in dstime: O(1)
    ds["PopFirst"]remove the first key-value pair in ds and return ittime: O(1)
    ds["PopLast"]remove the first key-value pair in ds and return ittime: O(1)
    ds["Values"]return the values in ds as a list sorted by the corresponding keystime: O(n)
    ds["Visualization"]return a visualization of dstime: O(n)
  • The following functions are also supported:
  • dsi===dsjTrue, 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 allclose all

Basic Examples  (1)

A new empty "SortedKeyStore" can be created with CreateDataStructure:

Insert a key-value pair given as a rule into the "SortedKeyStore" data structure:

Test if the key is present:

A key can be dropped from the store:

Now the key is not in the store:

Insert several keys and values:

The keys are returned in sorted order:

The values are returned in the order of their keys:

Return an expression version of ds:

A visualization of the data structure can be generated:

Scope  (3)

Information  (1)

A new "SortedKeyStore" can be created with CreateDataStructure:

Information about the data structure 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:

Each key-value pair can be visited and a function applied:

Each key-value pair can be visited and a function applied to accumulate a result:

SortDirection  (1)

By default, the keys are sorted in an increasing direction:

The "SortDirection" option allows keys to be sorted in a decreasing direction: