Lines Matching defs:edge
13007 // Various edge cases without formats
13112 // Float edge cases
13151 // And its edge cases
29562 /// returns a `GoDown` with the handle of the leaf edge where the key belongs.
29585 /// Descends to the nearest node where the edge matching the lower bound
29586 /// of the range is different from the edge matching the upper bound, i.e.,
29590 /// edge indices in the node delimiting the range, and the corresponding
29594 /// If not found, returns an `Err` with the leaf edge matching the entire
29660 /// Finds an edge in the node delimiting the lower bound of a range.
29674 let edge = unsafe { Handle::new_edge(self, edge_idx) };
29675 (edge, bound)
29688 let edge = unsafe { Handle::new_edge(self, edge_idx) };
29689 (edge, bound)
29696 /// returns a `GoDown` with the handle of the edge where the key might be found
29713 /// exists, or the edge index where the key belongs, starting from a particular index.
29719 /// `start_index` must be a valid edge index for the node.
29738 /// Finds an edge index in the node delimiting the lower bound of a range.
29769 /// `start_index` must be a valid edge index for the node.
30127 /// drop an entire tree without the need to first look up a `back` leaf edge.
31422 /// Contains a leaf edge preceding the next element to be returned, or the last leaf edge.
31423 /// Empty if the map has no root, if iteration went beyond the last leaf edge,
31469 let edge = self.cur_leaf_edge.as_ref()?;
31470 edge.reborrow().next_kv().ok().map(Handle::into_kv)
32138 GoDown(edge) => edge,
32144 (Internal(edge), Internal(node)) => {
32145 left_node = edge.descend();
33784 /// result will eventually reach the same edge.
33918 /// Given a leaf edge handle, returns [`Result::Ok`] with a handle to the neighboring KV
33920 /// If the leaf edge is the last one in the tree, returns [`Result::Err`] with the root node.
33927 let mut edge = self.forget_node_type();
33929 edge = match edge.right_kv() {
33939 /// Given a leaf edge handle, returns [`Result::Ok`] with a handle to the neighboring KV
33941 /// If the leaf edge is the first one in the tree, returns [`Result::Err`] with the root node.
33948 let mut edge = self.forget_node_type();
33950 edge = match edge.left_kv() {
33964 /// Given an internal edge handle, returns [`Result::Ok`] with a handle to the neighboring KV
33966 /// If the internal edge is the last one in the tree, returns [`Result::Err`] with the root node.
33973 let mut edge = self;
33975 edge = match edge.right_kv() {
33987 /// Given a leaf edge handle into a dying tree, returns the next leaf edge
33996 /// The given edge must not have been previously returned by counterpart
33999 let mut edge = self.forget_node_type();
34001 edge = match edge.right_kv() {
34015 /// Given a leaf edge handle into a dying tree, returns the next leaf edge
34024 /// The given edge must not have been previously returned by counterpart
34027 let mut edge = self.forget_node_type();
34029 edge = match edge.left_kv() {
34046 /// both sides of the tree, and have hit the same edge. As it is intended
34050 let mut edge = self.forget_node_type();
34051 while let Some(parent_edge) = unsafe { edge.into_node().deallocate_and_ascend() } {
34052 edge = parent_edge.forget_node_type();
34058 /// Moves the leaf edge handle to the next leaf edge and returns references to the
34071 /// Moves the leaf edge handle to the previous leaf edge and returns references to the
34086 /// Moves the leaf edge handle to the next leaf edge and returns references to the
34101 /// Moves the leaf edge handle to the previous leaf and returns references to the
34118 /// Moves the leaf edge handle to the next leaf edge and returns the key and value
34120 /// edge in its parent node dangling.
34136 /// Moves the leaf edge handle to the previous leaf edge and returns the key and value
34138 /// edge in its parent node dangling.
34142 /// - That leaf edge was not previously returned by counterpart `next_unchecked`
34156 /// Returns the leftmost leaf edge in or underneath a node - in other words, the edge
34169 /// Returns the rightmost leaf edge in or underneath a node - in other words, the edge
34201 let mut edge = internal.first_edge();
34203 edge = match edge.descend().force() {
34206 match edge.next_kv() {
34239 /// Returns the leaf edge closest to a KV for forward navigation.
34250 /// Returns the leaf edge closest to a KV for backward navigation.
35689 let edge = unsafe { Handle::new_edge(node, idx) };
35690 edge.descend().assert_min_len(MIN_LEN);
37477 // These are mostly for testing the algorithm that "fixes" the right edge after insertion.
37738 /// the leaf edge corresponding to that former pair. It's possible this empties
37950 // This implies that even an empty node has at least one edge.
37951 // For a leaf node, "having an edge" only means we can identify a position in the node,
37953 // an edge both identifies a position and contains a pointer to a child node.
38032 /// initialized and valid edge. This function does not set up
38033 /// such an edge.
38228 /// node actually has a parent, where `handle` points to the edge of the parent
38234 /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should
38392 /// Borrows exclusive access to an element or slice of the node's storage area for edge contents.
38401 // until the edge slice reference is dropped, as we have unique access
38435 /// Every item returned by `range` is a valid edge index for the node.
38450 /// Sets the node's link to its parent edge,
38460 /// Clears the root's link to its parent edge.
38474 /// Adds a new internal node with a single edge pointing to the previous root node,
38502 // SAFETY: the first edge is always initialized.
38548 /// Adds a key-value pair, and an edge to go to the right of that pair,
38550 pub fn push(&mut self, key: K, val: V, edge: Root<K, V>) {
38551 assert!(edge.height == self.height - 1);
38560 self.edge_area_mut(idx + 1).write(edge.node);
38618 /// A reference to a specific key-value pair or edge within a node. The `Node` parameter
38620 /// pair) or `Edge` (signifying a handle on an edge).
38624 /// pairs. For example, in a node with length 2, there would be 3 possible edge locations - one
38642 /// Retrieves the node that contains the edge or key-value pair this handle points to.
38705 /// Creates a new handle to an edge in `node`.
38735 /// Given an edge index where we want to insert into a node filled to capacity,
38753 /// this edge. This method assumes that there is enough space in the node for the new
38773 /// this edge. This method splits the node if there isn't enough room.
38800 /// Fixes the parent pointer and index in the child node that this edge
38812 /// Inserts a new key-value pair and an edge that will go to the right of that new pair
38813 /// between this edge and the key-value pair to the right of this edge. This method assumes
38815 fn insert_fit(&mut self, key: K, val: V, edge: Root<K, V>) {
38817 debug_assert!(edge.height == self.node.height - 1);
38823 slice_insert(self.node.edge_area_mut(..new_len + 1), self.idx + 1, edge.node);
38830 /// Inserts a new key-value pair and an edge that will go to the right of that new pair
38831 /// between this edge and the key-value pair to the right of this edge. This method splits
38837 edge: Root<K, V>,
38839 assert!(edge.height == self.node.height - 1);
38842 self.insert_fit(key, val, edge);
38857 insertion_edge.insert_fit(key, val, edge);
38865 /// this edge. This method splits the node if there isn't enough room, and tries to
38868 /// If the returned result is a `Fit`, its handle's node can be this edge's node or an ancestor.
38902 /// Finds the node pointed to by this edge.
38906 /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should
39015 /// Removes the key-value pair pointed to by this handle and returns it, along with the edge
39183 // of the node of this edge, thus above zero, so they are internal.
39218 /// the left child node and returns the edge handle in that child node
39219 /// where the tracked child edge ended up,
39242 /// Returns a handle to the edge in the right child corresponding to where the original
39243 /// edge specified by `track_right_edge_idx` ended up.
39254 /// Returns a handle to the edge in the left child specified by `track_left_edge_idx`,
39455 /// The first edge of `right` remains unchanged.
39640 let edge = unsafe { Handle::new_edge(node, idx) };
39641 let child = edge.descend();
39642 assert!(child.ascend().ok() == Some(edge));
39805 /// tree. The other nodes, those that are not the root nor a rightmost edge,
39825 /// The other nodes, those that are not the root nor a rightmost edge,
42614 // ABCDEFGHIJM...KL - swap until the left edge reaches the temp store
42616 // Sometimes the temp store is reached when the right edge is at the end
44348 //! for edge in &adj_list[position] {
44349 //! let next = State { cost: cost + edge.cost, position: edge.node };
44367 //! // and the edge weights symbolize the cost of moving