Read tree

Purpose: Search/update a tree.

 read-tree <tree> \
     ( equal <search key> | lesser <search key> | greater <search key> | \
         lesser-equal <search key> | greater-equal <search key> | \
         min-key | max-key ) \
     [ value <value> ] \
     [ update-value <update value> ] \
     [ key <key> ] \
     [ status <status> ] \
     [ new-cursor <cursor> ]

Copied!

read-tree will search <tree> (created with new-tree) for a node with the string key that is:

equal to <search key> ("equal" clause)
lesser than <search key> ("lesser" clause)
greater than <search key> ("greater" clause)
lesser or equal than <search key> ("lesser-equal" clause)
greater or equal than <search key> ("greater-equal" clause)
a minimum key in the tree ("min-key" clause)
a maximum key in the tree ("max-key" clause)

The <status> in "status" clause will be GG_OKAY if a key conforming to one of these criteria is found, and GG_ERR_EXIST if not.

If a key is found, the value associated with the key can be obtained with "value" clause in <value>; an existing key used to originally insert this value into the tree can be obtained with "key" clause in string <key>. If a key is not found, both <value> and <key> are unchanged.

You can update the value associated with a found key with "update-value" clause by specifying <update value> string. This update is performed after <value> has been retrieved, allowing you to obtain the previous value in the same statement.

If you'd like to iterate the ordered list of keys in a tree, create a <cursor> by using "new-cursor" clause, in which case <cursor> will be positioned on a found tree node. See use-cursor for more on using cursors. Cursors are useful in range searches; typically you'd find a key that is an upper or lower bound of a range and then keep iterating to a lesser or greater value until some criteria is met, such as when the opposite bound is found. Golf treees are by default constructed so that such iterations are O(1) in complexity, meaning each is a single tree node access (see new-tree).

Examples

In this example, a million key/value pairs are inserted into a tree, and then each of them is searched for and then displayed back (see write-tree for more on inserting into a tree). Both the key and the data are a numerical value of a key:

 %% /tree-example public

     new-tree mytree key-as "positive integer" // create new tree

     set-number i
     start-loop use i start-with 0 repeat 1000000
         number-string i to key
         set-string data=key
         write-tree mytree key (key) value data // insert key/data to the tree
     end-loop

     start-loop use i start-with 0 repeat 1000000
         number-string i to key
         // search tree for each key previously inserted
         read-tree mytree equal (key) status st value data
         if-true st not-equal GG_OKAY
             @Could not find key <<p-out key>>
         else-if
             @Found data <<p-out data>> associated with key <<p-out key>>
         end-if
         delete-string key
     end-loop
 %%

Copied!