| 1029 | } |
| 1030 | |
| 1031 | const visitBetween = <K, V, A>( |
| 1032 | node: Node.Node<K, V>, |
| 1033 | min: K, |
| 1034 | max: K, |
| 1035 | ord: Order.Order<K>, |
| 1036 | visit: (key: K, value: V) => Option.Option<A> |
| 1037 | ): Option.Option<A> => { |
| 1038 | let current: Node.Node<K, V> | undefined = node |
| 1039 | let stack: Stack.Stack<Node.Node<K, V>> | undefined = undefined |
| 1040 | let done = false |
| 1041 | while (!done) { |
| 1042 | if (current !== undefined) { |
| 1043 | stack = Stack.make(current, stack) |
| 1044 | if (ord(min, current.key) <= 0) { |
| 1045 | current = current.left |
| 1046 | } else { |
| 1047 | current = undefined |
| 1048 | } |
| 1049 | } else if (stack !== undefined && ord(max, stack.value.key) > 0) { |
| 1050 | if (ord(min, stack.value.key) <= 0) { |
| 1051 | const value = visit(stack.value.key, stack.value.value) |
| 1052 | if (Option.isSome(value)) { |
| 1053 | return value |
| 1054 | } |
| 1055 | } |
| 1056 | current = stack.value.right |
| 1057 | stack = stack.previous |
| 1058 | } else { |
| 1059 | done = true |
| 1060 | } |
| 1061 | } |
| 1062 | return Option.none() |
| 1063 | } |
| 1064 | |
| 1065 | /** |
| 1066 | * Fix up a double black node in a Red-Black Tree. |