.config/coc/extensions/node_modules/coc-prettier/node_modules/functional-red-black-tree/README.md

   1 functional-red-black-tree
   2 =========================
   3 A [fully persistent](http://en.wikipedia.org/wiki/Persistent_data_structure) [red-black tree](http://en.wikipedia.org/wiki/Red%E2%80%93black_tree) written 100% in JavaScript.  Works both in node.js and in the browser via [browserify](http://browserify.org/).
   4
   5 Functional (or fully presistent) data structures allow for non-destructive updates.  So if you insert an element into the tree, it returns a new tree with the inserted element rather than destructively updating the existing tree in place.  Doing this requires using extra memory, and if one were naive it could cost as much as reallocating the entire tree.  Instead, this data structure saves some memory by recycling references to previously allocated subtrees.  This requires using only O(log(n)) additional memory per update instead of a full O(n) copy.
   6
   7 Some advantages of this is that it is possible to apply insertions and removals to the tree while still iterating over previous versions of the tree.  Functional and persistent data structures can also be useful in many geometric algorithms like point location within triangulations or ray queries, and can be used to analyze the history of executing various algorithms.  This added power though comes at a cost, since it is generally a bit slower to use a functional data structure than an imperative version.  However, if your application needs this behavior then you may consider using this module.
   8
   9 # Install
  10
  11     npm install functional-red-black-tree
  12
  13 # Example
  14
  15 Here is an example of some basic usage:
  16
  17 ```javascript
  18 //Load the library
  19 var createTree = require("functional-red-black-tree")
  20
  21 //Create a tree
  22 var t1 = createTree()
  23
  24 //Insert some items into the tree
  25 var t2 = t1.insert(1, "foo")
  26 var t3 = t2.insert(2, "bar")
  27
  28 //Remove something
  29 var t4 = t3.remove(1)
  30 ```
  31
  32
  33 # API
  34
  35 ```javascript
  36 var createTree = require("functional-red-black-tree")
  37 ```
  38
  39 ## Overview
  40
  41 - [Tree methods](#tree-methods)
  42   - [`var tree = createTree([compare])`](#var-tree-=-createtreecompare)
  43   - [`tree.keys`](#treekeys)
  44   - [`tree.values`](#treevalues)
  45   - [`tree.length`](#treelength)
  46   - [`tree.get(key)`](#treegetkey)
  47   - [`tree.insert(key, value)`](#treeinsertkey-value)
  48   - [`tree.remove(key)`](#treeremovekey)
  49   - [`tree.find(key)`](#treefindkey)
  50   - [`tree.ge(key)`](#treegekey)
  51   - [`tree.gt(key)`](#treegtkey)
  52   - [`tree.lt(key)`](#treeltkey)
  53   - [`tree.le(key)`](#treelekey)
  54   - [`tree.at(position)`](#treeatposition)
  55   - [`tree.begin`](#treebegin)
  56   - [`tree.end`](#treeend)
  57   - [`tree.forEach(visitor(key,value)[, lo[, hi]])`](#treeforEachvisitorkeyvalue-lo-hi)
  58   - [`tree.root`](#treeroot)
  59 - [Node properties](#node-properties)
  60   - [`node.key`](#nodekey)
  61   - [`node.value`](#nodevalue)
  62   - [`node.left`](#nodeleft)
  63   - [`node.right`](#noderight)
  64 - [Iterator methods](#iterator-methods)
  65   - [`iter.key`](#iterkey)
  66   - [`iter.value`](#itervalue)
  67   - [`iter.node`](#iternode)
  68   - [`iter.tree`](#itertree)
  69   - [`iter.index`](#iterindex)
  70   - [`iter.valid`](#itervalid)
  71   - [`iter.clone()`](#iterclone)
  72   - [`iter.remove()`](#iterremove)
  73   - [`iter.update(value)`](#iterupdatevalue)
  74   - [`iter.next()`](#iternext)
  75   - [`iter.prev()`](#iterprev)
  76   - [`iter.hasNext`](#iterhasnext)
  77   - [`iter.hasPrev`](#iterhasprev)
  78
  79 ## Tree methods
  80
  81 ### `var tree = createTree([compare])`
  82 Creates an empty functional tree
  83
  84 * `compare` is an optional comparison function, same semantics as array.sort()
  85
  86 **Returns** An empty tree ordered by `compare`
  87
  88 ### `tree.keys`
  89 A sorted array of all the keys in the tree
  90
  91 ### `tree.values`
  92 An array array of all the values in the tree
  93
  94 ### `tree.length`
  95 The number of items in the tree
  96
  97 ### `tree.get(key)`
  98 Retrieves the value associated to the given key
  99
 100 * `key` is the key of the item to look up
 101
 102 **Returns** The value of the first node associated to `key`
 103
 104 ### `tree.insert(key, value)`
 105 Creates a new tree with the new pair inserted.
 106
 107 * `key` is the key of the item to insert
 108 * `value` is the value of the item to insert
 109
 110 **Returns** A new tree with `key` and `value` inserted
 111
 112 ### `tree.remove(key)`
 113 Removes the first item with `key` in the tree
 114
 115 * `key` is the key of the item to remove
 116
 117 **Returns** A new tree with the given item removed if it exists
 118
 119 ### `tree.find(key)`
 120 Returns an iterator pointing to the first item in the tree with `key`, otherwise `null`.
 121
 122 ### `tree.ge(key)`
 123 Find the first item in the tree whose key is `>= key`
 124
 125 * `key` is the key to search for
 126
 127 **Returns** An iterator at the given element.
 128
 129 ### `tree.gt(key)`
 130 Finds the first item in the tree whose key is `> key`
 131
 132 * `key` is the key to search for
 133
 134 **Returns** An iterator at the given element
 135
 136 ### `tree.lt(key)`
 137 Finds the last item in the tree whose key is `< key`
 138
 139 * `key` is the key to search for
 140
 141 **Returns** An iterator at the given element
 142
 143 ### `tree.le(key)`
 144 Finds the last item in the tree whose key is `<= key`
 145
 146 * `key` is the key to search for
 147
 148 **Returns** An iterator at the given element
 149
 150 ### `tree.at(position)`
 151 Finds an iterator starting at the given element
 152
 153 * `position` is the index at which the iterator gets created
 154
 155 **Returns** An iterator starting at position
 156
 157 ### `tree.begin`
 158 An iterator pointing to the first element in the tree
 159
 160 ### `tree.end`
 161 An iterator pointing to the last element in the tree
 162
 163 ### `tree.forEach(visitor(key,value)[, lo[, hi]])`
 164 Walks a visitor function over the nodes of the tree in order.
 165
 166 * `visitor(key,value)` is a callback that gets executed on each node.  If a truthy value is returned from the visitor, then iteration is stopped.
 167 * `lo` is an optional start of the range to visit (inclusive)
 168 * `hi` is an optional end of the range to visit (non-inclusive)
 169
 170 **Returns** The last value returned by the callback
 171
 172 ### `tree.root`
 173 Returns the root node of the tree
 174
 175
 176 ## Node properties
 177 Each node of the tree has the following properties:
 178
 179 ### `node.key`
 180 The key associated to the node
 181
 182 ### `node.value`
 183 The value associated to the node
 184
 185 ### `node.left`
 186 The left subtree of the node
 187
 188 ### `node.right`
 189 The right subtree of the node
 190
 191 ## Iterator methods
 192
 193 ### `iter.key`
 194 The key of the item referenced by the iterator
 195
 196 ### `iter.value`
 197 The value of the item referenced by the iterator
 198
 199 ### `iter.node`
 200 The value of the node at the iterator's current position.  `null` is iterator is node valid.
 201
 202 ### `iter.tree`
 203 The tree associated to the iterator
 204
 205 ### `iter.index`
 206 Returns the position of this iterator in the sequence.
 207
 208 ### `iter.valid`
 209 Checks if the iterator is valid
 210
 211 ### `iter.clone()`
 212 Makes a copy of the iterator
 213
 214 ### `iter.remove()`
 215 Removes the item at the position of the iterator
 216
 217 **Returns** A new binary search tree with `iter`'s item removed
 218
 219 ### `iter.update(value)`
 220 Updates the value of the node in the tree at this iterator
 221
 222 **Returns** A new binary search tree with the corresponding node updated
 223
 224 ### `iter.next()`
 225 Advances the iterator to the next position
 226
 227 ### `iter.prev()`
 228 Moves the iterator backward one element
 229
 230 ### `iter.hasNext`
 231 If true, then the iterator is not at the end of the sequence
 232
 233 ### `iter.hasPrev`
 234 If true, then the iterator is not at the beginning of the sequence
 235
 236 # Credits
 237 (c) 2013 Mikola Lysenko. MIT License