Module `deepbook::critbit`

Struct Leaf
Struct InternalNode
Struct CritbitTree
Constants
Function new
Function size
Function is_empty
Function min_leaf
Function max_leaf
Function previous_leaf
Function next_leaf
Function left_most_leaf
Function right_most_leaf
Function insert_leaf
Function find_leaf
Function find_closest_key
Function remove_leaf_by_index
Function borrow_mut_leaf_by_index
Function borrow_leaf_by_index
Function borrow_leaf_by_key
Function drop
Function destroy_empty
Function get_closest_leaf_index_by_key
Function update_child
Function is_left_child

<pre><code>use <a href="../deepbook/math.md#deepbook_math">deepbook::math</a>; use <a href="../std/ascii.md#std_ascii">std::ascii</a>; use <a href="../std/bcs.md#std_bcs">std::bcs</a>; use <a href="../std/option.md#std_option">std::option</a>; use <a href="../std/string.md#std_string">std::string</a>; use <a href="../std/vector.md#std_vector">std::vector</a>; use <a href="../sui/address.md#sui_address">sui::address</a>; use <a href="../sui/dynamic_field.md#sui_dynamic_field">sui::dynamic_field</a>; use <a href="../sui/hex.md#sui_hex">sui::hex</a>; use <a href="../sui/object.md#sui_object">sui::object</a>; use <a href="../sui/table.md#sui_table">sui::table</a>; use <a href="../sui/tx_context.md#sui_tx_context">sui::tx_context</a>; </code></pre>

Struct `Leaf`

<pre><code>public struct <a href="../deepbook/critbit.md#deepbook_critbit_Leaf">Leaf</a><V> has <a href="../deepbook/critbit.md#deepbook_critbit_drop">drop</a>, store </code></pre> <details> <summary>Fields</summary> <dl> <dt> <code>key: u64</code> </dt> <dd> </dd> <dt> <code>value: V</code> </dt> <dd> </dd> <dt> <code>parent: u64</code> </dt> <dd> </dd> </dl> </details>

Struct `InternalNode`

<pre><code>public struct <a href="../deepbook/critbit.md#deepbook_critbit_InternalNode">InternalNode</a> has <a href="../deepbook/critbit.md#deepbook_critbit_drop">drop</a>, store </code></pre> <details> <summary>Fields</summary> <dl> <dt> <code>mask: u64</code> </dt> <dd> </dd> <dt> <code>left_child: u64</code> </dt> <dd> </dd> <dt> <code>right_child: u64</code> </dt> <dd> </dd> <dt> <code>parent: u64</code> </dt> <dd> </dd> </dl> </details>

Struct `CritbitTree`

<pre><code>public struct <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V: store> has store </code></pre> <details> <summary>Fields</summary> <dl> <dt> <code>root: u64</code> </dt> <dd> </dd> <dt> <code>internal_nodes: <a href="../sui/table.md#sui_table_Table">sui::table::Table</a><u64, <a href="../deepbook/critbit.md#deepbook_critbit_InternalNode">deepbook::critbit::InternalNode</a>></code> </dt> <dd> </dd> <dt> <code>leaves: <a href="../sui/table.md#sui_table_Table">sui::table::Table</a><u64, <a href="../deepbook/critbit.md#deepbook_critbit_Leaf">deepbook::critbit::Leaf</a><V>></code> </dt> <dd> </dd> <dt> <code><a href="../deepbook/critbit.md#deepbook_critbit_min_leaf">min_leaf</a>: u64</code> </dt> <dd> </dd> <dt> <code><a href="../deepbook/critbit.md#deepbook_critbit_max_leaf">max_leaf</a>: u64</code> </dt> <dd> </dd> <dt> <code>next_internal_node_index: u64</code> </dt> <dd> </dd> <dt> <code>next_leaf_index: u64</code> </dt> <dd> </dd> </dl> </details>

Constants

<pre><code>const <a href="../deepbook/critbit.md#deepbook_critbit_EExceedCapacity">EExceedCapacity</a>: u64 = 2; </code></pre>

<pre><code>const <a href="../deepbook/critbit.md#deepbook_critbit_ETreeNotEmpty">ETreeNotEmpty</a>: u64 = 3; </code></pre>

<pre><code>const <a href="../deepbook/critbit.md#deepbook_critbit_EKeyAlreadyExist">EKeyAlreadyExist</a>: u64 = 4; </code></pre>

<pre><code>const <a href="../deepbook/critbit.md#deepbook_critbit_ELeafNotExist">ELeafNotExist</a>: u64 = 5; </code></pre>

<pre><code>const <a href="../deepbook/critbit.md#deepbook_critbit_EIndexOutOfRange">EIndexOutOfRange</a>: u64 = 7; </code></pre>

<pre><code>const <a href="../deepbook/critbit.md#deepbook_critbit_ENullParent">ENullParent</a>: u64 = 8; </code></pre>

<pre><code>const <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>: u64 = 9223372036854775808; </code></pre>

<pre><code>const <a href="../deepbook/critbit.md#deepbook_critbit_MAX_U64">MAX_U64</a>: u64 = 18446744073709551615; </code></pre>

<pre><code>const <a href="../deepbook/critbit.md#deepbook_critbit_MAX_CAPACITY">MAX_CAPACITY</a>: u64 = 9223372036854775807; </code></pre>

Function `new`

<pre><code>public(package) fun <a href="../deepbook/critbit.md#deepbook_critbit_new">new</a><V: store>(ctx: &mut <a href="../sui/tx_context.md#sui_tx_context_TxContext">sui::tx_context::TxContext</a>): <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">deepbook::critbit::CritbitTree</a><V> </code></pre> <details> <summary>Implementation</summary> <pre><code>public(package) fun <a href="../deepbook/critbit.md#deepbook_critbit_new">new</a><V: store>(ctx: &mut TxContext): <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V> { <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V> { root: <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>, internal_nodes: table::new(ctx), leaves: table::new(ctx), <a href="../deepbook/critbit.md#deepbook_critbit_min_leaf">min_leaf</a>: <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>, <a href="../deepbook/critbit.md#deepbook_critbit_max_leaf">max_leaf</a>: <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>, next_internal_node_index: 0, next_leaf_index: 0 } } </code></pre> </details>

Function `size`

<pre><code>public(package) fun <a href="../deepbook/critbit.md#deepbook_critbit_size">size</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">deepbook::critbit::CritbitTree</a><V>): u64 </code></pre> <details> <summary>Implementation</summary> <pre><code>public(package) fun <a href="../deepbook/critbit.md#deepbook_critbit_size">size</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V>): u64 { table::length(&tree.leaves) } </code></pre> </details>

Function `is_empty`

<pre><code>public(package) fun <a href="../deepbook/critbit.md#deepbook_critbit_is_empty">is_empty</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">deepbook::critbit::CritbitTree</a><V>): bool </code></pre> <details> <summary>Implementation</summary> <pre><code>public(package) fun <a href="../deepbook/critbit.md#deepbook_critbit_is_empty">is_empty</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V>): bool { table::is_empty(&tree.leaves) } </code></pre> </details>

Function `min_leaf`

<pre><code>public fun <a href="../deepbook/critbit.md#deepbook_critbit_min_leaf">min_leaf</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">deepbook::critbit::CritbitTree</a><V>): (u64, u64) </code></pre> <details> <summary>Implementation</summary> <pre><code>public fun <a href="../deepbook/critbit.md#deepbook_critbit_min_leaf">min_leaf</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V>): (u64, u64) { assert!(!<a href="../deepbook/critbit.md#deepbook_critbit_is_empty">is_empty</a>(tree), <a href="../deepbook/critbit.md#deepbook_critbit_ELeafNotExist">ELeafNotExist</a>); let <a href="../deepbook/critbit.md#deepbook_critbit_min_leaf">min_leaf</a> = table::borrow(&tree.leaves, tree.<a href="../deepbook/critbit.md#deepbook_critbit_min_leaf">min_leaf</a>); return (<a href="../deepbook/critbit.md#deepbook_critbit_min_leaf">min_leaf</a>.key, tree.<a href="../deepbook/critbit.md#deepbook_critbit_min_leaf">min_leaf</a>) } </code></pre> </details>

Function `max_leaf`

<pre><code>public fun <a href="../deepbook/critbit.md#deepbook_critbit_max_leaf">max_leaf</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">deepbook::critbit::CritbitTree</a><V>): (u64, u64) </code></pre> <details> <summary>Implementation</summary> <pre><code>public fun <a href="../deepbook/critbit.md#deepbook_critbit_max_leaf">max_leaf</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V>): (u64, u64) { assert!(!<a href="../deepbook/critbit.md#deepbook_critbit_is_empty">is_empty</a>(tree), <a href="../deepbook/critbit.md#deepbook_critbit_ELeafNotExist">ELeafNotExist</a>); let <a href="../deepbook/critbit.md#deepbook_critbit_max_leaf">max_leaf</a> = table::borrow(&tree.leaves, tree.<a href="../deepbook/critbit.md#deepbook_critbit_max_leaf">max_leaf</a>); return (<a href="../deepbook/critbit.md#deepbook_critbit_max_leaf">max_leaf</a>.key, tree.<a href="../deepbook/critbit.md#deepbook_critbit_max_leaf">max_leaf</a>) } </code></pre> </details>

Function `previous_leaf`

<pre><code>public fun <a href="../deepbook/critbit.md#deepbook_critbit_previous_leaf">previous_leaf</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">deepbook::critbit::CritbitTree</a><V>, key: u64): (u64, u64) </code></pre> <details> <summary>Implementation</summary> <pre><code>public fun <a href="../deepbook/critbit.md#deepbook_critbit_previous_leaf">previous_leaf</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V>, key: u64): (u64, u64) { let (_, mut index) = <a href="../deepbook/critbit.md#deepbook_critbit_find_leaf">find_leaf</a>(tree, key); assert!(index != <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>, <a href="../deepbook/critbit.md#deepbook_critbit_ELeafNotExist">ELeafNotExist</a>); let mut ptr = <a href="../deepbook/critbit.md#deepbook_critbit_MAX_U64">MAX_U64</a> - index; let mut parent = table::borrow(&tree.leaves, index).parent; while (parent != <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a> && <a href="../deepbook/critbit.md#deepbook_critbit_is_left_child">is_left_child</a>(tree, parent, ptr)){ ptr = parent; parent = table::borrow(&tree.internal_nodes, ptr).parent; }; if(parent == <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>) { return (0, <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>) }; index = <a href="../deepbook/critbit.md#deepbook_critbit_MAX_U64">MAX_U64</a> - <a href="../deepbook/critbit.md#deepbook_critbit_right_most_leaf">right_most_leaf</a>(tree, table::borrow(&tree.internal_nodes, parent).left_child); let key = table::borrow(&tree.leaves, index).key; return (key, index) } </code></pre> </details>

Function `next_leaf`

<pre><code>public fun <a href="../deepbook/critbit.md#deepbook_critbit_next_leaf">next_leaf</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">deepbook::critbit::CritbitTree</a><V>, key: u64): (u64, u64) </code></pre> <details> <summary>Implementation</summary> <pre><code>public fun <a href="../deepbook/critbit.md#deepbook_critbit_next_leaf">next_leaf</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V>, key: u64): (u64, u64) { let (_, mut index) = <a href="../deepbook/critbit.md#deepbook_critbit_find_leaf">find_leaf</a>(tree, key); assert!(index != <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>, <a href="../deepbook/critbit.md#deepbook_critbit_ELeafNotExist">ELeafNotExist</a>); let mut ptr = <a href="../deepbook/critbit.md#deepbook_critbit_MAX_U64">MAX_U64</a> - index; let mut parent = table::borrow(&tree.leaves, index).parent; while (parent != <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a> && !<a href="../deepbook/critbit.md#deepbook_critbit_is_left_child">is_left_child</a>(tree, parent, ptr)){ ptr = parent; parent = table::borrow(&tree.internal_nodes, ptr).parent; }; if(parent == <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>) { return (0, <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>) }; index = <a href="../deepbook/critbit.md#deepbook_critbit_MAX_U64">MAX_U64</a> - <a href="../deepbook/critbit.md#deepbook_critbit_left_most_leaf">left_most_leaf</a>(tree, table::borrow(&tree.internal_nodes, parent).right_child); let key = table::borrow(&tree.leaves, index).key; return (key, index) } </code></pre> </details>

Function `left_most_leaf`

<pre><code>fun <a href="../deepbook/critbit.md#deepbook_critbit_left_most_leaf">left_most_leaf</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">deepbook::critbit::CritbitTree</a><V>, root: u64): u64 </code></pre> <details> <summary>Implementation</summary> <pre><code>fun <a href="../deepbook/critbit.md#deepbook_critbit_left_most_leaf">left_most_leaf</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V>, root: u64): u64 { let mut ptr = root; while (ptr < <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>){ ptr = table::borrow(& tree.internal_nodes, ptr).left_child; }; ptr } </code></pre> </details>

Function `right_most_leaf`

<pre><code>fun <a href="../deepbook/critbit.md#deepbook_critbit_right_most_leaf">right_most_leaf</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">deepbook::critbit::CritbitTree</a><V>, root: u64): u64 </code></pre> <details> <summary>Implementation</summary> <pre><code>fun <a href="../deepbook/critbit.md#deepbook_critbit_right_most_leaf">right_most_leaf</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V>, root: u64): u64 { let mut ptr = root; while (ptr < <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>){ ptr = table::borrow(& tree.internal_nodes, ptr).right_child; }; ptr } </code></pre> </details>

Function `insert_leaf`

<pre><code>public(package) fun <a href="../deepbook/critbit.md#deepbook_critbit_insert_leaf">insert_leaf</a><V: store>(tree: &mut <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">deepbook::critbit::CritbitTree</a><V>, key: u64, value: V): u64 </code></pre> <details> <summary>Implementation</summary> <pre><code>public(package) fun <a href="../deepbook/critbit.md#deepbook_critbit_insert_leaf">insert_leaf</a><V: store>(tree: &mut <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V>, key: u64, value: V): u64 { let new_leaf = <a href="../deepbook/critbit.md#deepbook_critbit_Leaf">Leaf</a><V>{ key, value, parent: <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>, }; let new_leaf_index = tree.next_leaf_index; tree.next_leaf_index = tree.next_leaf_index + 1; assert!(new_leaf_index < <a href="../deepbook/critbit.md#deepbook_critbit_MAX_CAPACITY">MAX_CAPACITY</a> - 1, <a href="../deepbook/critbit.md#deepbook_critbit_EExceedCapacity">EExceedCapacity</a>); table::add(&mut tree.leaves, new_leaf_index, new_leaf); let closest_leaf_index = <a href="../deepbook/critbit.md#deepbook_critbit_get_closest_leaf_index_by_key">get_closest_leaf_index_by_key</a>(tree, key); // Handle the first insertion if (closest_leaf_index == <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>) { assert!(new_leaf_index == 0, <a href="../deepbook/critbit.md#deepbook_critbit_ETreeNotEmpty">ETreeNotEmpty</a>); tree.root = <a href="../deepbook/critbit.md#deepbook_critbit_MAX_U64">MAX_U64</a> - new_leaf_index; tree.<a href="../deepbook/critbit.md#deepbook_critbit_min_leaf">min_leaf</a> = new_leaf_index; tree.<a href="../deepbook/critbit.md#deepbook_critbit_max_leaf">max_leaf</a> = new_leaf_index; return 0 }; let closest_key = table::borrow(&tree.leaves, closest_leaf_index).key; assert!(closest_key != key, <a href="../deepbook/critbit.md#deepbook_critbit_EKeyAlreadyExist">EKeyAlreadyExist</a>); // Note that we reserve count_leading_zeros of form u128 for future use let <a href="../deepbook/critbit.md#deepbook_critbit">critbit</a> = 64 - (count_leading_zeros((closest_key ^ key) as u128) - 64); let new_mask = 1u64 << (<a href="../deepbook/critbit.md#deepbook_critbit">critbit</a> - 1); let new_internal_node= <a href="../deepbook/critbit.md#deepbook_critbit_InternalNode">InternalNode</a> { mask: new_mask, left_child: <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>, right_child: <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>, parent: <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>, }; let new_internal_node_index = tree.next_internal_node_index; tree.next_internal_node_index = tree.next_internal_node_index + 1; table::add(&mut tree.internal_nodes, new_internal_node_index, new_internal_node); let mut ptr = tree.root; let mut new_internal_node_parent_index = <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>; // Search position of the <a href="../deepbook/critbit.md#deepbook_critbit_new">new</a> internal node while (ptr < <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>) { let internal_node = table::borrow(&tree.internal_nodes, ptr); if (new_mask > internal_node.mask) { break }; new_internal_node_parent_index = ptr; if (key & internal_node.mask == 0) { ptr = internal_node.left_child; } else { ptr = internal_node.right_child; }; }; // Update the child info of <a href="../deepbook/critbit.md#deepbook_critbit_new">new</a> internal node's parent if (new_internal_node_parent_index == <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>){ // if the <a href="../deepbook/critbit.md#deepbook_critbit_new">new</a> internal node is root tree.root = new_internal_node_index; } else{ // In another case, we update the child field of the <a href="../deepbook/critbit.md#deepbook_critbit_new">new</a> internal node's parent // And the parent field of the <a href="../deepbook/critbit.md#deepbook_critbit_new">new</a> internal node let <a href="../deepbook/critbit.md#deepbook_critbit_is_left_child">is_left_child</a> = <a href="../deepbook/critbit.md#deepbook_critbit_is_left_child">is_left_child</a>(tree, new_internal_node_parent_index, ptr); <a href="../deepbook/critbit.md#deepbook_critbit_update_child">update_child</a>(tree, new_internal_node_parent_index, new_internal_node_index, <a href="../deepbook/critbit.md#deepbook_critbit_is_left_child">is_left_child</a>); }; // Finally, update the child field of the <a href="../deepbook/critbit.md#deepbook_critbit_new">new</a> internal node let <a href="../deepbook/critbit.md#deepbook_critbit_is_left_child">is_left_child</a> = new_mask & key == 0; <a href="../deepbook/critbit.md#deepbook_critbit_update_child">update_child</a>(tree, new_internal_node_index, <a href="../deepbook/critbit.md#deepbook_critbit_MAX_U64">MAX_U64</a> - new_leaf_index, <a href="../deepbook/critbit.md#deepbook_critbit_is_left_child">is_left_child</a>); <a href="../deepbook/critbit.md#deepbook_critbit_update_child">update_child</a>(tree, new_internal_node_index, ptr, !<a href="../deepbook/critbit.md#deepbook_critbit_is_left_child">is_left_child</a>); if (table::borrow(&tree.leaves, tree.<a href="../deepbook/critbit.md#deepbook_critbit_min_leaf">min_leaf</a>).key > key) { tree.<a href="../deepbook/critbit.md#deepbook_critbit_min_leaf">min_leaf</a> = new_leaf_index; }; if (table::borrow(&tree.leaves, tree.<a href="../deepbook/critbit.md#deepbook_critbit_max_leaf">max_leaf</a>).key < key) { tree.<a href="../deepbook/critbit.md#deepbook_critbit_max_leaf">max_leaf</a> = new_leaf_index; }; new_leaf_index } </code></pre> </details>

Function `find_leaf`

<pre><code>public fun <a href="../deepbook/critbit.md#deepbook_critbit_find_leaf">find_leaf</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">deepbook::critbit::CritbitTree</a><V>, key: u64): (bool, u64) </code></pre> <details> <summary>Implementation</summary> <pre><code>public fun <a href="../deepbook/critbit.md#deepbook_critbit_find_leaf">find_leaf</a><V: store>(tree: & <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V>, key: u64): (bool, u64) { if (<a href="../deepbook/critbit.md#deepbook_critbit_is_empty">is_empty</a>(tree)) { return (false, <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>) }; let closest_leaf_index = <a href="../deepbook/critbit.md#deepbook_critbit_get_closest_leaf_index_by_key">get_closest_leaf_index_by_key</a>(tree, key); let closeset_leaf = table::borrow(&tree.leaves, closest_leaf_index); if (closeset_leaf.key != key){ return (false, <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>) } else{ return (true, closest_leaf_index) } } </code></pre> </details>

Function `find_closest_key`

<pre><code>public(package) fun <a href="../deepbook/critbit.md#deepbook_critbit_find_closest_key">find_closest_key</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">deepbook::critbit::CritbitTree</a><V>, key: u64): u64 </code></pre> <details> <summary>Implementation</summary> <pre><code>public(package) fun <a href="../deepbook/critbit.md#deepbook_critbit_find_closest_key">find_closest_key</a><V: store>(tree: & <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V>, key: u64): u64 { if (<a href="../deepbook/critbit.md#deepbook_critbit_is_empty">is_empty</a>(tree)) { return 0 }; let closest_leaf_index = <a href="../deepbook/critbit.md#deepbook_critbit_get_closest_leaf_index_by_key">get_closest_leaf_index_by_key</a>(tree, key); let closeset_leaf = table::borrow(&tree.leaves, closest_leaf_index); closeset_leaf.key } </code></pre> </details>

Function `remove_leaf_by_index`

<pre><code>public(package) fun <a href="../deepbook/critbit.md#deepbook_critbit_remove_leaf_by_index">remove_leaf_by_index</a><V: store>(tree: &mut <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">deepbook::critbit::CritbitTree</a><V>, index: u64): V </code></pre> <details> <summary>Implementation</summary> <pre><code>public(package) fun <a href="../deepbook/critbit.md#deepbook_critbit_remove_leaf_by_index">remove_leaf_by_index</a><V: store>(tree: &mut <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V>, index: u64): V { let key = table::borrow(& tree.leaves, index).key; if (tree.<a href="../deepbook/critbit.md#deepbook_critbit_min_leaf">min_leaf</a> == index) { let (_, index) = <a href="../deepbook/critbit.md#deepbook_critbit_next_leaf">next_leaf</a>(tree, key); tree.<a href="../deepbook/critbit.md#deepbook_critbit_min_leaf">min_leaf</a> = index; }; if (tree.<a href="../deepbook/critbit.md#deepbook_critbit_max_leaf">max_leaf</a> == index) { let (_, index) = <a href="../deepbook/critbit.md#deepbook_critbit_previous_leaf">previous_leaf</a>(tree, key); tree.<a href="../deepbook/critbit.md#deepbook_critbit_max_leaf">max_leaf</a> = index; }; let mut is_left_child_; let <a href="../deepbook/critbit.md#deepbook_critbit_Leaf">Leaf</a><V> {key: _, value, parent: removed_leaf_parent_index} = table::remove(&mut tree.leaves, index); if (<a href="../deepbook/critbit.md#deepbook_critbit_size">size</a>(tree) == 0) { tree.root = <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>; tree.<a href="../deepbook/critbit.md#deepbook_critbit_min_leaf">min_leaf</a> = <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>; tree.<a href="../deepbook/critbit.md#deepbook_critbit_max_leaf">max_leaf</a> = <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>; tree.next_internal_node_index = 0; tree.next_leaf_index = 0; } else { assert!(removed_leaf_parent_index != <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>, <a href="../deepbook/critbit.md#deepbook_critbit_EIndexOutOfRange">EIndexOutOfRange</a>); let removed_leaf_parent = table::borrow(&tree.internal_nodes, removed_leaf_parent_index); let removed_leaf_grand_parent_index = removed_leaf_parent.parent; // Note that sibling of the removed leaf can be a leaf or an internal node is_left_child_ = <a href="../deepbook/critbit.md#deepbook_critbit_is_left_child">is_left_child</a>(tree, removed_leaf_parent_index, <a href="../deepbook/critbit.md#deepbook_critbit_MAX_U64">MAX_U64</a> - index); let sibling_index = if (is_left_child_) { removed_leaf_parent.right_child } else { removed_leaf_parent.left_child }; if (removed_leaf_grand_parent_index == <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>) { // Parent of the removed leaf is the tree root // Update the parent of the sibling node and set sibling as the tree root if (sibling_index < <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>) { // sibling is an internal node table::borrow_mut(&mut tree.internal_nodes, sibling_index).parent = <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>; } else{ // sibling is a leaf table::borrow_mut(&mut tree.leaves, <a href="../deepbook/critbit.md#deepbook_critbit_MAX_U64">MAX_U64</a> - sibling_index).parent = <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>; }; tree.root = sibling_index; } else { // grand parent of the removed leaf is a internal node // set sibling as the child of the grand parent of the removed leaf is_left_child_ = <a href="../deepbook/critbit.md#deepbook_critbit_is_left_child">is_left_child</a>(tree, removed_leaf_grand_parent_index, removed_leaf_parent_index); <a href="../deepbook/critbit.md#deepbook_critbit_update_child">update_child</a>(tree, removed_leaf_grand_parent_index, sibling_index, is_left_child_); }; table::remove(&mut tree.internal_nodes, removed_leaf_parent_index); }; value } </code></pre> </details>

Function `borrow_mut_leaf_by_index`

<pre><code>public(package) fun <a href="../deepbook/critbit.md#deepbook_critbit_borrow_mut_leaf_by_index">borrow_mut_leaf_by_index</a><V: store>(tree: &mut <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">deepbook::critbit::CritbitTree</a><V>, index: u64): &mut V </code></pre> <details> <summary>Implementation</summary> <pre><code>public(package) fun <a href="../deepbook/critbit.md#deepbook_critbit_borrow_mut_leaf_by_index">borrow_mut_leaf_by_index</a><V: store>(tree: &mut <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V>, index: u64): &mut V { let entry = table::borrow_mut(&mut tree.leaves, index); &mut entry.value } </code></pre> </details>

Function `borrow_leaf_by_index`

<pre><code>public fun <a href="../deepbook/critbit.md#deepbook_critbit_borrow_leaf_by_index">borrow_leaf_by_index</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">deepbook::critbit::CritbitTree</a><V>, index: u64): &V </code></pre> <details> <summary>Implementation</summary> <pre><code>public fun <a href="../deepbook/critbit.md#deepbook_critbit_borrow_leaf_by_index">borrow_leaf_by_index</a><V: store>(tree: & <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V>, index: u64): &V { let entry = table::borrow(&tree.leaves, index); &entry.value } </code></pre> </details>

Function `borrow_leaf_by_key`

<pre><code>public fun <a href="../deepbook/critbit.md#deepbook_critbit_borrow_leaf_by_key">borrow_leaf_by_key</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">deepbook::critbit::CritbitTree</a><V>, key: u64): &V </code></pre> <details> <summary>Implementation</summary> <pre><code>public fun <a href="../deepbook/critbit.md#deepbook_critbit_borrow_leaf_by_key">borrow_leaf_by_key</a><V: store>(tree: & <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V>, key: u64): &V { let (is_exist, index) = <a href="../deepbook/critbit.md#deepbook_critbit_find_leaf">find_leaf</a>(tree, key); assert!(is_exist, <a href="../deepbook/critbit.md#deepbook_critbit_ELeafNotExist">ELeafNotExist</a>); <a href="../deepbook/critbit.md#deepbook_critbit_borrow_leaf_by_index">borrow_leaf_by_index</a>(tree, index) } </code></pre> </details>

Function `drop`

<pre><code>public(package) fun <a href="../deepbook/critbit.md#deepbook_critbit_drop">drop</a><V: <a href="../deepbook/critbit.md#deepbook_critbit_drop">drop</a>, store>(tree: <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">deepbook::critbit::CritbitTree</a><V>) </code></pre> <details> <summary>Implementation</summary> <pre><code>public(package) fun <a href="../deepbook/critbit.md#deepbook_critbit_drop">drop</a><V: store + <a href="../deepbook/critbit.md#deepbook_critbit_drop">drop</a>>(tree: <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V>) { let <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V> { root: _, internal_nodes, leaves, <a href="../deepbook/critbit.md#deepbook_critbit_min_leaf">min_leaf</a>: _, <a href="../deepbook/critbit.md#deepbook_critbit_max_leaf">max_leaf</a>: _, next_internal_node_index: _, next_leaf_index: _, } = tree; table::drop(internal_nodes); table::drop(leaves); } </code></pre> </details>

Function `destroy_empty`

<pre><code>public(package) fun <a href="../deepbook/critbit.md#deepbook_critbit_destroy_empty">destroy_empty</a><V: store>(tree: <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">deepbook::critbit::CritbitTree</a><V>) </code></pre> <details> <summary>Implementation</summary> <pre><code>public(package) fun <a href="../deepbook/critbit.md#deepbook_critbit_destroy_empty">destroy_empty</a><V: store>(tree: <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V>) { assert!(table::length(&tree.leaves) == 0, 0); let <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V> { root: _, leaves, internal_nodes, <a href="../deepbook/critbit.md#deepbook_critbit_min_leaf">min_leaf</a>: _, <a href="../deepbook/critbit.md#deepbook_critbit_max_leaf">max_leaf</a>: _, next_internal_node_index: _, next_leaf_index: _ } = tree; table::destroy_empty(leaves); table::destroy_empty(internal_nodes); } </code></pre> </details>

Function `get_closest_leaf_index_by_key`

<pre><code>fun <a href="../deepbook/critbit.md#deepbook_critbit_get_closest_leaf_index_by_key">get_closest_leaf_index_by_key</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">deepbook::critbit::CritbitTree</a><V>, key: u64): u64 </code></pre> <details> <summary>Implementation</summary> <pre><code>fun <a href="../deepbook/critbit.md#deepbook_critbit_get_closest_leaf_index_by_key">get_closest_leaf_index_by_key</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V>, key: u64): u64 { let mut ptr = tree.root; // if tree is empty, return the patrition index if(ptr == <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>) return <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>; while (ptr < <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>){ let node = table::borrow(&tree.internal_nodes, ptr); if (key & node.mask == 0){ ptr = node.left_child; } else { ptr = node.right_child; } }; return (<a href="../deepbook/critbit.md#deepbook_critbit_MAX_U64">MAX_U64</a> - ptr) } </code></pre> </details>

Function `update_child`

<pre><code>fun <a href="../deepbook/critbit.md#deepbook_critbit_update_child">update_child</a><V: store>(tree: &mut <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">deepbook::critbit::CritbitTree</a><V>, parent_index: u64, new_child: u64, <a href="../deepbook/critbit.md#deepbook_critbit_is_left_child">is_left_child</a>: bool) </code></pre> <details> <summary>Implementation</summary> <pre><code>fun <a href="../deepbook/critbit.md#deepbook_critbit_update_child">update_child</a><V: store>(tree: &mut <a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V>, parent_index: u64, new_child: u64, <a href="../deepbook/critbit.md#deepbook_critbit_is_left_child">is_left_child</a>: bool) { assert!(parent_index != <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>, <a href="../deepbook/critbit.md#deepbook_critbit_ENullParent">ENullParent</a>); if (<a href="../deepbook/critbit.md#deepbook_critbit_is_left_child">is_left_child</a>) { table::borrow_mut(&mut tree.internal_nodes, parent_index).left_child = new_child; } else{ table::borrow_mut(&mut tree.internal_nodes, parent_index).right_child = new_child; }; if (new_child > <a href="../deepbook/critbit.md#deepbook_critbit_PARTITION_INDEX">PARTITION_INDEX</a>) { table::borrow_mut(&mut tree.leaves, <a href="../deepbook/critbit.md#deepbook_critbit_MAX_U64">MAX_U64</a> - new_child).parent = parent_index; } else { table::borrow_mut(&mut tree.internal_nodes, new_child).parent = parent_index; } } </code></pre> </details>

Function `is_left_child`

<pre><code>fun <a href="../deepbook/critbit.md#deepbook_critbit_is_left_child">is_left_child</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">deepbook::critbit::CritbitTree</a><V>, parent_index: u64, index: u64): bool </code></pre> <details> <summary>Implementation</summary> <pre><code>fun <a href="../deepbook/critbit.md#deepbook_critbit_is_left_child">is_left_child</a><V: store>(tree: &<a href="../deepbook/critbit.md#deepbook_critbit_CritbitTree">CritbitTree</a><V>, parent_index: u64, index: u64): bool { table::borrow(&tree.internal_nodes, parent_index).left_child == index } </code></pre> </details>

Struct Leaf

Struct InternalNode

Struct CritbitTree

Constants

Function new

Function size

Function is_empty

Function min_leaf

Function max_leaf

Function previous_leaf

Function next_leaf

Function left_most_leaf

Function right_most_leaf

Function insert_leaf

Function find_leaf

Function find_closest_key

Function remove_leaf_by_index

Function borrow_mut_leaf_by_index

Function borrow_leaf_by_index

Function borrow_leaf_by_key

Function drop

Function destroy_empty

Function get_closest_leaf_index_by_key

Function update_child

Function is_left_child