Unbounded Interval Tree

https://docs.rs/unbounded-interval-tree/latest
Admin
A Rust implementation of an interval tree data structure that supports inclusive/exclusive bounds...
Tokens:21,881
Snippets:141
Trust Score:9.1
Update:6 months ago
Show doc for...
Tokens:
Raw
### IntervalTree Overlap Check Setup

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Initializes an IntervalTree and defines intervals for testing overlap functionality. This snippet sets up the tree structure.

```rust
let mut tree = IntervalTree::default();

let root_key = (Included(2), Included(3));
let left_key = (Included(0), Included(1));
let left_left_key = (Included(-5), Excluded(10));
```

--------------------------------

### Iterate Through Intervals in an IntervalTree

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Demonstrates iterating over all intervals stored in an IntervalTree. This example shows how to insert various types of intervals and then traverse them in order.

```rust
let mut tree = IntervalTree::default();

        assert_eq!(tree.iter().next(), None);

        let key1 = (Included(10), Excluded(20));
        let key2 = (Included(40), Unbounded);
        let key3 = (Excluded(30), Excluded(40));
        let key4 = (Unbounded, Included(50));
        let key5 = (Excluded(-10), Included(-5));
        let key6 = (Included(-10), Included(-4));

        tree.insert(key1.clone());
        tree.insert(key2.clone());
        tree.insert(key3.clone());
        tree.insert(key4.clone());
        tree.insert(key5.clone());
        tree.insert(key6.clone());

        let inorder = vec![&key4, &key6, &key5, &key1, &key3, &key2];
        for (idx, interval) in tree.iter().enumerate() {
            assert_eq!(interval, inorder[idx]);
        }
```

--------------------------------

### Get Interval Difference with String Keys

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Demonstrates how to find the difference between a query interval and existing intervals in a tree with string keys. Ensure the tree is populated with string intervals before querying.

```rust
let mut tree: IntervalTree<&str> = IntervalTree::default();

        let key1 = (Included("a"), Excluded("h"));
        let key2 = (Excluded("M"), Excluded("O"));

        tree.insert(key1.clone());
        tree.insert(key2);

        assert!(tree.get_interval_difference(&("a".."h")).is_empty());
        assert_eq!(
            tree.get_interval_difference(&("M"..="P")),
            vec![
                (Included(&"M"), Included(&"M")),
                (Included(&"O"), Included(&"P"))
            ]
        );

        let not_covered_range = "h".."k";
        assert_eq!(
            tree.get_interval_difference(&not_covered_range),
            vec![( not_covered_range.start_bound(), not_covered_range.end_bound() )]
        );
```

--------------------------------

### Get IntervalTree size

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Returns the total number of ranges currently stored in the tree.

```rust
use std::ops::Bound::{Included, Excluded, Unbounded};
use unbounded_interval_tree::interval_tree::IntervalTree;

let mut tree = IntervalTree::default();

assert_eq!(tree.len(), 0);

tree.insert((Included(5), Excluded(9)));
tree.insert((Unbounded, Included(10)));

assert_eq!(tree.len(), 2);
```

--------------------------------

### Get Tree Size

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTree.html

Returns the number of ranges currently stored in the interval tree.

```rust
use std::ops::Bound::{Included, Excluded, Unbounded);
use unbounded_interval_tree::interval_tree::IntervalTree;

let mut tree = IntervalTree::default();

assert_eq!(tree.len(), 0);

tree.insert((Included(5), Excluded(9)));
tree.insert((Unbounded, Included(10)));

assert_eq!(tree.len(), 2);
```

--------------------------------

### Get Interval Overlaps in IntervalTree

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Finds all intervals in the tree that overlap with a given range. The query range can use borrowed forms of the key type.

```rust
use std::ops::Bound::{Included, Excluded, Unbounded};
use unbounded_interval_tree::interval_tree::IntervalTree;

let mut tree = IntervalTree::default();

tree.insert((Included(0), Included(5)));
tree.insert((Included(7), Excluded(10)));

assert_eq!(tree.get_interval_overlaps(&(-5..7)),
           vec![&(Included(0), Included(5))]);
// Borrowed form of the key works as well.
assert!(tree.get_interval_overlaps(&(&10..)).is_empty());
```

--------------------------------

### Get Tree Size

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Returns the number of ranges currently stored in the interval tree.

```APIDOC
## GET /interval_tree/len

### Description
Retrieves the total number of ranges stored within the interval tree.

### Method
GET

### Endpoint
`/interval_tree/len`

### Parameters
None

### Request Example
None

### Response
#### Success Response (200)
- **size** (usize) - The number of ranges in the tree.

#### Response Example
```json
{
  "size": 5
}
```
```

--------------------------------

### IntervalTree Creation and Initialization

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Demonstrates various ways to create and initialize an IntervalTree.

```APIDOC
## IntervalTree Creation and Initialization

### Description
Provides methods for creating an `IntervalTree`.

### Methods

1.  **`IntervalTree::default()`**
    *   Creates an empty default interval tree.

2.  **`FromIterator` Trait Implementation**
    *   Creates an interval tree from an iterator of elements satisfying the `RangeBounds` trait.
    *   Example: `ranges.into_iter().collect::<IntervalTree<_>>();`

3.  **`From<[R; N]>` Trait Implementation**
    *   Creates an interval tree from an array of elements satisfying the `RangeBounds` trait.
    *   Example: `IntervalTree::from(ranges);`

### Request Body
N/A for creation methods.

### Request Example
```rust
// 1. Create an empty default interval tree.
let mut interval_tree = IntervalTree::default();
assert!(interval_tree.is_empty());
interval_tree.insert(0..9);
interval_tree.insert(27..);
assert_eq!(interval_tree.len(), 2);

// 2. Create an interval tree from an iterator.
let ranges = vec!["hello".to_string()..="hi".to_string(), "Allo".to_string()..="Bonjour".to_string()];
let interval_tree = ranges.into_iter().collect::<IntervalTree<_>>();
assert_eq!(interval_tree.len(), 2);

// 3. Create an interval tree from an array.
let ranges = [(1, 5)..(1,9), (2, 3)..(3, 7)];
let interval_tree = IntervalTree::from(ranges);
assert_eq!(interval_tree.len(), 2);
```

### Response
N/A for creation methods.
```

--------------------------------

### Create and Use IntervalTree

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Demonstrates three ways to create an IntervalTree: default, from an iterator, and from an array. Shows basic insertion and length checks.

```rust
use unbounded_interval_tree::interval_tree::IntervalTree;

// 1. Create an empty default interval tree.
let mut interval_tree = IntervalTree::default();
assert!(interval_tree.is_empty());
interval_tree.insert(0..9);
interval_tree.insert(27..);
assert_eq!(interval_tree.len(), 2);

// 2. Create an interval tree from an iterator.
let ranges = vec!["hello"...="hi", "Allo"..="Bonjour"];
let interval_tree = ranges.into_iter().collect::<IntervalTree<_>>();
assert_eq!(interval_tree.len(), 2);

// 3. Create an interval tree from an array.
let ranges = [(1, 5)..(1,9), (2, 3)..(3, 7)];
let interval_tree = IntervalTree::from(ranges);
assert_eq!(interval_tree.len(), 2);
```

--------------------------------

### Create an IntervalTree

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTree.html

Demonstrates three ways to initialize an interval tree: using default, from an iterator, or from an array.

```rust
use unbounded_interval_tree::interval_tree::IntervalTree;

// 1. Create an empty default interval tree.
let mut interval_tree = IntervalTree::default();
assert!(interval_tree.is_empty());
interval_tree.insert(0..9);
interval_tree.insert(27..);
assert_eq!(interval_tree.len(), 2);

// 2. Create an interval tree from an iterator.
let ranges = vec!["hello"..="hi", "Allo"..="Bonjour"];
let interval_tree = ranges.into_iter().collect::<IntervalTree<_>>();
assert_eq!(interval_tree.len(), 2);

// 3. Create an interval tree from an array.
let ranges = [(1, 5)..(1,9), (2, 3)..(3, 7)];
let interval_tree = IntervalTree::from(ranges);
assert_eq!(interval_tree.len(), 2);
```

--------------------------------

### Get Overlapping Intervals

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTree.html

Retrieves all intervals that overlap with a given range. The query range can use borrowed forms of the key type.

```rust
use std::ops::Bound::{Included, Excluded, Unbounded);
use unbounded_interval_tree::interval_tree::IntervalTree;

let mut tree = IntervalTree::default();

tree.insert((Included(0), Included(5)));
tree.insert((Included(7), Excluded(10)));

assert_eq!(tree.get_interval_overlaps(&(-5..7)),
           vec![&(Included(0), Included(5))]);
// Borrowed form of the key works as well.
assert!(tree.get_interval_overlaps(&(&10..)).is_empty());
```

--------------------------------

### IntervalTree Creation and Insertion

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTree.html

Demonstrates various ways to create and insert intervals into an IntervalTree.

```APIDOC
## IntervalTree Creation and Insertion

### Description
This section shows how to create an `IntervalTree` and insert intervals into it using different methods.

### Methods
- **`default()`**: Creates an empty `IntervalTree`.
- **`insert(range)`**: Inserts a given `range` into the `IntervalTree`.
- **`from(array)`**: Creates an `IntervalTree` from an array of ranges.
- **`collect::<IntervalTree<_>>()`**: Creates an `IntervalTree` from an iterator.

### Examples
```rust
use unbounded_interval_tree::interval_tree::IntervalTree;
use std::ops::RangeBounds;

// 1. Create an empty default interval tree.
let mut interval_tree = IntervalTree::default();
assert!(interval_tree.is_empty());
interval_tree.insert(0..9);
interval_tree.insert(27..);
assert_eq!(interval_tree.len(), 2);

// 2. Create an interval tree from an iterator.
let ranges = vec!["hello"..="hi", "Allo"..="Bonjour"];
let interval_tree = ranges.into_iter().collect::<IntervalTree<_>>();
assert_eq!(interval_tree.len(), 2);

// 3. Create an interval tree from an array.
let ranges = [(1, 5)..(1,9), (2, 3)..(3, 7)];
let interval_tree = IntervalTree::from(ranges);
assert_eq!(interval_tree.len(), 2);
```
```

--------------------------------

### Iterator count() Method

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTreeIter.html

Consumes the iterator and returns the total number of elements it contained. This is a convenient way to get the size of the iterated collection.

```rust
fn count(self) -> usize
where Self: Sized,
```

--------------------------------

### Get Interval Difference

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTree.html

Calculates subintervals within a given range that are not covered by the tree. Returns references to bounds from the tree or the query range.

```rust
use std::ops::Bound::{Included, Excluded, Unbounded);
use unbounded_interval_tree::interval_tree::IntervalTree;

let mut tree = IntervalTree::default();

tree.insert((Included(0), Excluded(10)));
tree.insert((Excluded(10), Included(30)));
tree.insert((Excluded(50), Unbounded));

assert_eq!(tree.get_interval_difference(&(-5..=30)),
           vec![(Included(&-5), Excluded(&0)),
                (Included(&10), Included(&10))]);
assert_eq!(tree.get_interval_difference(&(..10)),
           vec![(Unbounded, Excluded(&0))]);
assert!(tree.get_interval_difference(&(100..)).is_empty());
```

--------------------------------

### Create a New Node

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/node.rs.html

Constructor for the Node struct. Initializes a node with a given key range and sets the initial maximum value to the end of the key range. Requires the key type K to be Clone.

```rust
impl<K> Node<K> {
    pub fn new(range: Range<K>) -> Node<K>
    where
        K: Clone,
    {
        let max = range.1.clone();

        Node {
            key: range,
            value: max,
            left: None,
            right: None,
        }
    }
// ... other methods
```

--------------------------------

### IntervalTree Insertion

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Explains how to insert new intervals into the IntervalTree.

```APIDOC
## IntervalTree Insertion

### Description
Inserts an interval `range` into the interval tree. Insertions respect the binary search properties of this tree. It is acceptable to insert a `range` that overlaps with an existing interval in the tree.

### Method
`insert<R>(&mut self, range: R)`

### Endpoint
N/A (Method on `IntervalTree` struct)

### Parameters
- **`range`** (R: `RangeBounds<K>`) - Required - The interval to insert into the tree.

### Request Body
N/A (The `range` parameter is passed directly).

### Request Example
```rust
use std::ops::Bound::{Included, Excluded, Unbounded};
use unbounded_interval_tree::interval_tree::IntervalTree;

let mut int_tree = IntervalTree::default();

int_tree.insert((Included(5), Excluded(9)));
int_tree.insert(..=10);

let mut str_tree: IntervalTree<&str> = IntervalTree::default();

str_tree.insert("Noria"..);
```

### Response
#### Success Response (200)
- **`()`**: The insertion operation does not return a value upon success.

#### Response Example
N/A (Insertion is a side effect).
```

--------------------------------

### Get Interval Difference in IntervalTree

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Calculates the subintervals within a given range that are not covered by the tree. Returns a vector of ranges representing the uncovered segments.

```rust
use std::ops::Bound::{Included, Excluded, Unbounded};
use unbounded_interval_tree::interval_tree::IntervalTree;

let mut tree = IntervalTree::default();

tree.insert((Included(0), Excluded(10)));
tree.insert((Excluded(10), Included(30)));
tree.insert((Excluded(50), Unbounded));

assert_eq!(tree.get_interval_difference(&(-5..=30)),
           vec![(Included(&-5), Excluded(&0)),
                (Included(&10), Included(&10))]);
assert_eq!(tree.get_interval_difference(&(..10)),
           vec![(Unbounded, Excluded(&0))]);
assert!(tree.get_interval_difference(&(100..)).is_empty());
```

--------------------------------

### Insert Left and Right Nodes in IntervalTree

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Demonstrates inserting nodes into an IntervalTree, checking for the presence of left and right children, and verifying node values.

```rust
let mut tree = IntervalTree::default();

let root_key = (Included(2), Included(3));
let left_key = (Included(0), Included(1));
let left_right_key = (Excluded(1), Unbounded);

tree.insert(root_key.clone());
assert!(tree.root.is_some());
assert!(tree.root.as_ref().unwrap().left.is_none());

tree.insert(left_key.clone());
assert!(tree.root.as_ref().unwrap().right.is_none());
assert!(tree.root.as_ref().unwrap().left.is_some());
assert_eq!(
    tree.root.as_ref().unwrap().left.as_ref().unwrap().value,
    left_key.1
);

tree.insert(left_right_key.clone());
assert!(tree
    .root
    .as_ref()
    .unwrap()
    .left
    .as_ref()
    .unwrap()
    .right
    .is_some());
```

--------------------------------

### Perform TryInto Conversion

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTreeIter.html

Executes the conversion from T to U, returning a Result.

```rust
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
```

--------------------------------

### Iterator zip() Method

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTreeIter.html

Creates an iterator that yields pairs of elements, one from this iterator and one from another.

```rust
fn zip<U>(self, other: U) -> Zip<Self, <U as IntoIterator>::IntoIter>
where Self: Sized, U: IntoIterator,
```

--------------------------------

### Module interval_tree

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/index.html

Details about the interval_tree module within the unbounded_interval_tree crate.

```APIDOC
## Module interval_tree

### Summary
An interval tree implemented with a binary search tree.

### Structs

#### Struct: IntervalTree

**Description**: The interval tree storing all the underlying intervals.

#### Struct: IntervalTreeIter

**Description**: An inorder iterator through the interval tree.
```

--------------------------------

### Check Point Containment with Integer Keys

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Illustrates checking if a specific point exists within any interval in an IntervalTree with integer keys. The tree should be initialized and populated with intervals first.

```rust
let mut tree = IntervalTree::default();

        let key1 = (Included(10), Excluded(20));
        let key2 = (Excluded(30), Excluded(40));
        let key3 = 40..;

        tree.insert(key1);
        tree.insert(key2);
        tree.insert(key3);

        assert!(tree.contains_point(&10));
        assert!(!tree.contains_point(&20));
        assert!(tree.contains_point(&40));
        assert!(tree.contains_point(&100));
```

--------------------------------

### Tree Insertion and Creation Tests

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Tests for root insertion and creation from iterators.

```rust
    #[test]
    fn it_inserts_root() {
        let mut tree = IntervalTree::default();
        assert!(tree.root.is_none());

        let key = (Included(1), Included(3));

        tree.insert(key.clone());
        assert!(tree.root.is_some());
        assert_eq!(tree.root.as_ref().unwrap().key, key);
        assert_eq!(tree.root.as_ref().unwrap().value, key.1);
        assert!(tree.root.as_ref().unwrap().left.is_none());
        assert!(tree.root.as_ref().unwrap().right.is_none());
    }

    #[test]
    fn creates_from_iterator() {
        let ranges = vec![0..5, 6..10, 10..15];
```

--------------------------------

### Iterating over IntervalTree

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTree.html

Shows how to iterate through the intervals stored in an IntervalTree.

```APIDOC
## Iterating over IntervalTree

### Description
This section demonstrates how to obtain an inorder iterator for the `IntervalTree`.

### Method
- **`iter()`**: Returns an inorder iterator (`IntervalTreeIter`) over the intervals in the tree.

### Endpoint
N/A (This is a method call on the `IntervalTree` struct)

### Parameters
None

### Request Body
None

### Response
#### Success Response (Iterator)
- **`IntervalTreeIter<'a, K>`**: An iterator yielding references to the intervals.

### Request Example
```rust
use std::ops::Bound::Included;
use unbounded_interval_tree::interval_tree::IntervalTree;

let mut tree = IntervalTree::default();

tree.insert((Included(0), Included(10)));
tree.insert((Included(-5), Included(-1)));
tree.insert((Included(20), Included(30)));

let mut iter = tree.iter();
assert_eq!(iter.next(), Some(&(Included(-5), Included(-1))));
assert_eq!(iter.next(), Some(&(Included(0), Included(10))));
assert_eq!(iter.next(), Some(&(Included(20), Included(30))));
assert_eq!(iter.next(), None);
```
```

--------------------------------

### IntervalTree Comparison Methods

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTree.html

Methods for comparing two IntervalTree instances.

```APIDOC
## PartialEq for IntervalTree<K>

### Description
Provides equality comparison for IntervalTree instances.

### Methods
- **eq(&self, other: &IntervalTree<K>) -> bool**: Tests for equality.
- **ne(&self, other: &Rhs) -> bool**: Tests for inequality.
```

--------------------------------

### Interval Difference Calculation

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Demonstrates calculating the difference between a set of intervals in the tree and a query interval. This is useful for finding gaps or remaining portions after subtracting a specific range.

```rust
let mut tree = IntervalTree::default();

let key1 = 2..10;
let key2 = 4..=6;
let key3 = (Excluded(10), Excluded(20));
let key4 = (Excluded(30), Included(35));
let key5 = 30..=40;
let key6 = 30..=35;
let key7 = (Excluded(45), Unbounded);
let key8 = (Included(60), Included(70));

tree.insert(key1);
tree.insert(key2);
tree.insert(key3);
tree.insert(key4);
tree.insert(key5);
tree.insert(key6);
tree.insert(key7);
tree.insert(key8);

assert_eq!(
    tree.get_interval_difference(&(Excluded(0), Included(100))),
    vec![
        (Excluded(&0), Excluded(&2)),
        (Included(&10), Included(&10)),
        (Included(&20), Excluded(&30)),
        (Excluded(&40), Included(&45))
    ]
);
assert_eq!(
    tree.get_interval_difference(&(19..=40)),
    vec![(Included(&20), Excluded(&30))]
);
assert_eq!(
    tree.get_interval_difference(&(20..=40)),
    vec![(Included(&20), Excluded(&30))]
);
assert_eq!(
    tree.get_interval_difference(&(20..=45)),
    vec![
        (Included(&20), Excluded(&30)),
        (Excluded(&40), Included(&45))
    ]
);
assert_eq!(
    tree.get_interval_difference(&(20..45)),
    vec![
        (Included(&20), Excluded(&30)),
        (Excluded(&40), Excluded(&45))
    ]
);
assert_eq!(
    tree.get_interval_difference(&(2..=10)),
    vec![(Included(&10), Included(&10))]
);
```

--------------------------------

### Insert and Query Overlaps in Interval Tree

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Demonstrates inserting various interval types (inclusive, exclusive, unbounded) and querying for overlaps using different range specifications. This is useful for testing the tree's ability to handle diverse interval definitions and query ranges.

```rust
let right_key = (Excluded(3), Unbounded);

tree.insert(root_key.clone());
tree.insert(left_key.clone());
assert_eq!(tree.get_interval_overlaps(&root_key), vec![&root_key]);

tree.insert(left_left_key.clone());
assert_eq!(
    tree.get_interval_overlaps(&(..)),
    vec![&left_left_key, &left_key, &root_key]
);
assert!(tree.get_interval_overlaps(&(100..)).is_empty());

tree.insert(right_key);
assert_eq!(
    tree.get_interval_overlaps(&root_key),
    vec![&left_left_key, &root_key]
);
assert_eq!(
    tree.get_interval_overlaps(&(..)),
    vec![&left_left_key, &left_key, &root_key, &right_key]
);
assert_eq!(tree.get_interval_overlaps(&(100..)), vec![&right_key]);
assert_eq!(
    tree.get_interval_overlaps(&(3..10)),
    vec![&left_left_key, &root_key, &right_key]
);
assert_eq!(
    tree.get_interval_overlaps(&(Excluded(3), Excluded(10))),
    vec![&left_left_key, &right_key]
);
assert_eq!(
    tree.get_interval_overlaps(&(..2)),
    vec![&left_left_key, &left_key]
);
assert_eq!(
    tree.get_interval_overlaps(&(..=2)),
    vec![&left_left_key, &left_key, &root_key]
);
assert_eq!(
    tree.get_interval_overlaps(&(..=3)),
    vec![&left_left_key, &left_key, &root_key]
);
```

--------------------------------

### Blanket Implementations

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTreeIter.html

Common blanket implementations available for various types.

```APIDOC
## Blanket Implementations

### `impl<T> Any for T where T: 'static + ?Sized`

#### `fn type_id(&self) -> TypeId`

Gets the `TypeId` of `self`.

### `impl<T> Borrow<T> for T where T: ?Sized`

#### `fn borrow(&self) -> &T`

Immutably borrows from an owned value.

### `impl<T> BorrowMut<T> for T where T: ?Sized`

#### `fn borrow_mut(&mut self) -> &mut T`

Mutably borrows from an owned value.

### `impl<T> From<T> for T`

#### `fn from(t: T) -> T`

Returns the argument unchanged.

### `impl<T, U> Into<U> for T where U: From<T>`

#### `fn into(self) -> U`

Calls `U::from(self)`.

### `impl<I> IntoIterator for I where I: Iterator`

#### `type Item = <I as Iterator>::Item`

The type of the elements being iterated over.

#### `type IntoIter = I`

Which kind of iterator are we turning this into?

#### `fn into_iter(self) -> I`

Creates an iterator from a value.

### `impl<I> IteratorRandom for I where I: Iterator`

(Methods for `IteratorRandom` are detailed in the 'Iterator Random Selection Methods' snippet).

### `impl<T, U> TryFrom<U> for T where U: Into<T>`

#### `type Error = Infallible`

The type returned in the event of a conversion error.

#### `fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>`

Performs the conversion.
```

--------------------------------

### Serialization and Deserialization Tests

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Unit tests verifying identity, serialization, and deserialization of the interval tree.

```rust
    #[test]
    fn serialize_deserialize_identity() {
	let mut tree = IntervalTree::default();
	let serialized_empty_tree = to_string(&tree).unwrap();
	let deserialized_empty_tree = from_str(&serialized_empty_tree).unwrap();
	assert_eq!(tree, deserialized_empty_tree);

	tree.insert((Included(1), Excluded(3)));
	let serialized_tree = to_string(&tree).unwrap();
	let deserialized_tree = from_str(&serialized_tree).unwrap();
	assert_eq!(tree, deserialized_tree);
    }

    #[test]
    fn serialize() {
	let mut tree = IntervalTree::default();
	let serialized_empty_tree = to_string(&tree).unwrap();
	let deserialized_empty_value: Value = from_str(&serialized_empty_tree).unwrap();
	let expected_empty_value = json!({
	    "root": null,
	    "size": 0,
	});
	assert_eq!(expected_empty_value, deserialized_empty_value);

	tree.insert((Included(2), Included(4)));
	tree.insert((Included(1), Excluded(3)));
	
	let serialized_tree = to_string(&tree).unwrap();
	let deserialized_tree: Value = from_str(&serialized_tree).unwrap();
	let expected_value = json!({
	    "root": {
		"key": [
		    {"Included": 2},
		    {"Included": 4},
		],
		"left": {
		    "key": [
			{"Included": 1},
			{"Excluded": 3},
		    ],
		    "left": null,
		    "right": null,
		    "value": {"Excluded": 3},
		},
		"right": null,
		"value": {"Included": 4},
	    },
	    "size": 2,
	});
	assert_eq!(expected_value, deserialized_tree);
    }

    #[test]
    fn deserialize() {
	let mut expected_tree = IntervalTree::default();
	let empty_value = json!({
	    "root": null,
	    "size": 0,
	});
	let serialized_empty_value = empty_value.to_string();
	let deserialized_empty_tree = from_str(&serialized_empty_value).unwrap();
	assert_eq!(expected_tree, deserialized_empty_tree);

	expected_tree.insert((Included(2), Included(4)));
	expected_tree.insert((Included(1), Excluded(3)));
	let value = json!({
	    "root": {
		"key": [
		    {"Included": 2},
		    {"Included": 4},
		],
		"left": {
		    "key": [
			{"Included": 1},
			{"Excluded": 3},
		    ],
		    "left": null,
		    "right": null,
		    "value": {"Excluded": 3},
		},
		"right": null,
		"value": {"Included": 4},
	    },
	    "size": 2,
	});
	let serialized_value = value.to_string();
	let deserialized_tree = from_str(&serialized_value).unwrap();
	assert_eq!(expected_tree, deserialized_tree);
    }
```

--------------------------------

### Create IntervalTree from Array

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Creates an IntervalTree from a slice of ranges using `from` and `into` methods. Compares the resulting trees for equality.

```rust
let ranges = [0..5, 6..10, 10..15];
let interval_tree = IntervalTree::from(ranges.clone());
let other_interval_tree = ranges.into();

assert_eq!(interval_tree, other_interval_tree);
assert_eq!(interval_tree.len(), 3);
```

--------------------------------

### Iterator step_by() Method

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTreeIter.html

Creates a new iterator that yields elements from the original iterator, but skips elements according to the specified step.

```rust
fn step_by(self, step: usize) -> StepBy<Self>
where Self: Sized,
```

--------------------------------

### Iterator next_chunk() Method (Experimental)

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTreeIter.html

Advances the iterator and returns an array of the next N values. This is a nightly-only experimental API.

```rust
fn next_chunk<const N: usize>( &mut self, ) -> Result<[Self::Item; N], IntoIter<Self::Item, N>>
where Self: Sized,
```

--------------------------------

### Test len and is_empty methods

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Checks that the tree size and emptiness status are correctly updated after insertions and removals.

```rust
    #[test]
    fn len_and_is_empty_works_as_expected() {
        let mut tree = IntervalTree::default();

        assert_eq!(tree.len(), 0);
        assert!(tree.is_empty());

        let key1 = (Included(16), Unbounded);
        let key2 = (Included(8), Excluded(9));

        tree.insert(key1);

        assert_eq!(tree.len(), 1);
        assert!(!tree.is_empty());

        tree.insert(key2);

        assert_eq!(tree.len(), 2);
        assert!(!tree.is_empty());

        tree.remove_random_leaf();

        assert_eq!(tree.len(), 1);
        assert!(!tree.is_empty());

        tree.remove_random_leaf();

        assert_eq!(tree.len(), 0);
        assert!(tree.is_empty());
    }
```

--------------------------------

### IntervalTree Conversion Methods

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTree.html

Methods for creating an IntervalTree from arrays or iterators.

```APIDOC
## From<[R; N]> for IntervalTree<K>

### Description
Converts an array of range bounds into an IntervalTree.

### Parameters
- **intervals** ([R; N]) - Required - An array of range bounds where K: Ord + Clone.

## FromIterator<R> for IntervalTree<K>

### Description
Creates an IntervalTree from an iterator of elements satisfying the RangeBounds trait.

### Parameters
- **iter** (IntoIterator<Item = R>) - Required - An iterator of range bounds.
```

--------------------------------

### Iterator next() Method

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTreeIter.html

Advances the iterator and returns the next interval as an Option. Returns None when the iteration is complete.

```rust
fn next(&mut self) -> Option<Self::Item>
```

--------------------------------

### IntervalTree Comparison Logic

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Tests the comparison logic between different interval types using `IntervalTree::cmp`. Asserts equality and less-than relationships.

```rust
let key0 = (Unbounded, Excluded(20));
let key1 = (Included(1), Included(5));
let key2 = (Included(1), Excluded(7));
let key3 = (Included(1), Included(7));
let key4 = (Excluded(5), Excluded(9));
let key5 = (Included(7), Included(8));
let key_str1 = (Included("abc"), Excluded("def"));
let key_str2 = (Included("bbc"), Included("bde"));
let key_str3: (_, Bound<&str>) = (Included("bbc"), Unbounded);

assert_eq!(IntervalTree::cmp(&key1, &key1), Equal);
assert_eq!(IntervalTree::cmp(&key1, &key2), Less);
assert_eq!(IntervalTree::cmp(&key2, &key3), Less);
assert_eq!(IntervalTree::cmp(&key0, &key1), Less);
assert_eq!(IntervalTree::cmp(&key4, &key5), Less);
assert_eq!(IntervalTree::cmp(&key_str1, &key_str2), Less);
assert_eq!(IntervalTree::cmp(&key_str2, &key_str3), Less);
```

--------------------------------

### Iterator intersperse_with() Method (Experimental)

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTreeIter.html

Creates an iterator that inserts elements generated by a closure between original elements. This is a nightly-only experimental API.

```rust
fn intersperse_with<G>(self, separator: G) -> IntersperseWith<Self, G>
where Self: Sized, G: FnMut() -> Self::Item,
```

--------------------------------

### Check Point Containment with String Keys

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Shows how to use `contains_point` with String types as keys in an IntervalTree. Ensure the tree is populated with String intervals before performing checks.

```rust
let mut tree = IntervalTree::default();

        let key1 = String::from("a")..String::from("h");
        let key2 = (Excluded(String::from("M")), Excluded(String::from("O")));

        tree.insert(key1);
        tree.insert(key2);

        assert!(tree.contains_point("b"));
        assert!(!tree.contains_point("n"));
        assert!(tree.contains_point(&String::from("N")));
        assert!(tree.contains_point("g"));
```

--------------------------------

### Check Interval Containment with Integer Keys

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Verifies if a given interval is fully contained within any of the intervals present in an IntervalTree with integer keys. The tree needs to be populated first.

```rust
let mut tree = IntervalTree::default();

        let key1 = (Included(10), Excluded(20));
        let key2 = (Excluded(30), Excluded(40));
        let key3 = 40..;

        tree.insert(key1.clone());
        tree.insert(key2.clone());
        tree.insert(key3.clone());

        assert!(tree.contains_interval(&key1));
        assert!(!tree.contains_interval(&(Included(&10), Included(&20))));
        assert!(!tree.contains_interval(&(..=0)));
        assert!(tree.contains_interval(&(Included(35), Included(37))));
```

--------------------------------

### Iterator intersperse() Method (Experimental)

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTreeIter.html

Creates an iterator that inserts a separator between elements. This is a nightly-only experimental API.

```rust
fn intersperse(self, separator: Self::Item) -> Intersperse<Self>
where Self: Sized, Self::Item: Clone,
```

--------------------------------

### Execute VZip Operation

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTreeIter.html

Performs the vzip operation returning type V.

```rust
fn vzip(self) -> V
```

--------------------------------

### Iterator Comparison Methods

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTreeIter.html

Methods for lexicographically comparing two iterators.

```APIDOC
## fn cmp<I>

### Description
Lexicographically compares the elements of this Iterator with those of another.

### Parameters
#### Request Body
- **other** (IntoIterator) - Required - The iterator to compare against.

### Response
- **Ordering** - The result of the comparison.

## fn partial_cmp<I>

### Description
Lexicographically compares the PartialOrd elements of this Iterator with those of another.

### Parameters
#### Request Body
- **other** (IntoIterator) - Required - The iterator to compare against.

### Response
- **Option<Ordering>** - The result of the comparison.
```

--------------------------------

### Check Point Containment with String Slice Keys

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Demonstrates `contains_point` functionality using string slices (`&str`) as keys. The tree must be initialized with `&str` intervals.

```rust
let mut tree: IntervalTree<&str> = IntervalTree::default();

        let key1 = "a".."h";
        let key2 = (Excluded("M"), Excluded("O"));

        tree.insert(key1);
        tree.insert(key2);

        assert!(tree.contains_point("b"));
        assert!(!tree.contains_point("n"));
        assert!(tree.contains_point(&"N"));
        assert!(tree.contains_point("g"));
```

--------------------------------

### Iterator enumerate() Method

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTreeIter.html

Creates an iterator that yields pairs of (index, element) for each element in the original iterator.

```rust
fn enumerate(self) -> Enumerate<Self>
where Self: Sized,
```

--------------------------------

### Auto Trait Implementations for IntervalTreeIter

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTreeIter.html

Auto trait implementations for the `IntervalTreeIter` struct.

```APIDOC
## Auto Trait Implementations for IntervalTreeIter

### `impl<'a, K> Freeze for IntervalTreeIter<'a, K>`

### `impl<'a, K> RefUnwindSafe for IntervalTreeIter<'a, K> where K: RefUnwindSafe`

### `impl<'a, K> Send for IntervalTreeIter<'a, K> where K: Sync`

### `impl<'a, K> Sync for IntervalTreeIter<'a, K> where K: Sync`

### `impl<'a, K> Unpin for IntervalTreeIter<'a, K>`

### `impl<'a, K> UnwindSafe for IntervalTreeIter<'a, K> where K: RefUnwindSafe`
```

--------------------------------

### Iterator size_hint() Method

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTreeIter.html

Returns the lower and upper bounds of the remaining number of elements in the iterator. This can be used for optimizations.

```rust
fn size_hint(&self) -> (usize, Option<usize>)
```

--------------------------------

### Iterator advance_by() Method (Experimental)

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTreeIter.html

Advances the iterator by a specified number of elements. Returns Ok(()) if successful, or Err(remaining) if the iterator ended before advancing.

```rust
fn advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>>
```

--------------------------------

### Interval Bound Comparison Logic

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Encodes interval bounds into tuples for comparison, handling Included/Excluded rules.

```rust
        let e1 = match e1 {
            Included(x) => Some((x, 2)),
            Excluded(x) => Some((x, 1)),
            Unbounded => None,
        };
        let e2 = match e2 {
            Included(x) => Some((x, 2)),
            Excluded(x) => Some((x, 1)),
            Unbounded => None,
        };

        match (e1, e2) {
            (None, None) => Equal,
            (None, Some(_)) => Greater,
            (Some(_), None) => Less,
            (Some(r1), Some(ref r2)) => r1.cmp(r2),
        }
    }
}
```

--------------------------------

### Deserialize Interval Tree Nodes

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/node.rs.html

Tests the deserialization of leaf and internal nodes from JSON strings using the from_str function.

```rust
    #[test]
    fn deserialize() {
	let expected_leaf = Node::new((Included(1), Excluded(3)));
	let value = json!({
	    "key": [
		{"Included": 1},
		{"Excluded": 3},
	    ],
	    "left": null,
	    "right": null,
	    "value": {"Excluded": 3},
	});
	let serialized_value = value.to_string();
	let deserialized_leaf = from_str(&serialized_value).unwrap();
	assert_eq!(expected_leaf, deserialized_leaf);

	let mut expected_node = Node::new((Included(2), Included(4)));
	expected_node.left = Some(Box::new(expected_leaf));
	let value = json!({
	    "key": [
		{"Included": 2},
		{"Included": 4},
	    ],
	    "left": {
		"key": [
		    {"Included": 1},
		    {"Excluded": 3},
		],
		"left": null,
		"right": null,
		"value": {"Excluded": 3},
	    },
	    "right": null,
	    "value": {"Included": 4},
	});
	let serialized_value = value.to_string();
	let deserialized_node = from_str(&serialized_value).unwrap();
	assert_eq!(expected_node, deserialized_node);
    }
```

--------------------------------

### Insert intervals into an IntervalTree

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTree.html

Inserts an interval into the tree, respecting binary search properties.

```rust
use std::ops::Bound::{Included, Excluded, Unbounded};
use unbounded_interval_tree::interval_tree::IntervalTree;

let mut int_tree = IntervalTree::default();

int_tree.insert((Included(5), Excluded(9)));
int_tree.insert(..=10);

let mut str_tree: IntervalTree<&str> = IntervalTree::default();

str_tree.insert("Noria"..);
```

--------------------------------

### Iterator chain() Method

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTreeIter.html

Creates an iterator that yields elements from this iterator followed by elements from another iterator.

```rust
fn chain<U>(self, other: U) -> Chain<Self, <U as IntoIterator>::IntoIter>
where Self: Sized, U: IntoIterator<Item = Self::Item>,
```

--------------------------------

### Test remove_random_leaf on empty and single-node trees

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/interval_tree.rs.html

Verifies that removing a leaf from an empty tree returns None, and removing from a single-node tree returns the correct key.

```rust
    #[test]
    fn remove_random_leaf_empty_tree_works_as_expected() {
        let mut tree: IntervalTree<i32> = IntervalTree::default();

        assert_eq!(tree.remove_random_leaf(), None);
    }

    #[test]
    fn remove_random_leaf_one_node_tree_works_as_expected() {
        let mut tree = IntervalTree::default();

        let key1 = (Included(10), Excluded(20));
        tree.insert(key1.clone());

        let deleted = tree.remove_random_leaf();
        assert!(deleted.is_some());
        assert_eq!(deleted.unwrap(), key1);

        assert!(tree.remove_random_leaf().is_none());
    }
```

--------------------------------

### Iterator map() Method

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTreeIter.html

Creates an iterator that applies a closure to each element, transforming the elements.

```rust
fn map<B, F>(self, f: F) -> Map<Self, F>
where Self: Sized, F: FnMut(Self::Item) -> B,
```

--------------------------------

### Iterator skip() Method

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTreeIter.html

Creates an iterator that skips the first `n` elements of the original iterator.

```rust
fn skip(self, n: usize) -> Skip<Self>
where Self: Sized,
```

--------------------------------

### Iterator map_while() Method

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTreeIter.html

Creates an iterator that both maps and filters elements based on a predicate. Elements are mapped as long as the predicate returns Some.

```rust
fn map_while<B, P>(self, predicate: P) -> MapWhile<Self, P>
where Self: Sized, P: FnMut(Self::Item) -> Option<B>,
```

--------------------------------

### Implement Display for Node

Source: https://docs.rs/unbounded-interval-tree/latest/src/unbounded_interval_tree/node.rs.html

Implements the Display trait for the Node struct to provide a human-readable string representation. Handles different Bound types for keys and values, and recursively displays children.

```rust
impl<K> fmt::Display for Node<K>
where
    K: fmt::Display,
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let start = match self.key.0 {
            Included(ref x) => format!("[{{\}}}", x),
            Excluded(ref x) => format!("]{{\}}}", x),
            Unbounded => String::from("]-∞"),
        };
        let end = match self.key.1 {
            Included(ref x) => format!("{{}}]", x),
            Excluded(ref x) => format!("{{}}[ ", x),
            Unbounded => format!("∞["),
        };
        let value = match self.value {
            Included(ref x) => format!("{{}}]", x),
            Excluded(ref x) => format!("{{}}[", x),
            Unbounded => String::from("∞"),
        };

        if self.left.is_none() && self.right.is_none() {
            write!(f, " {{ {{}},{{}} ({}) }} ", start, end, value)
        } else if self.left.is_none() {
            write!(
                f,
                " {{ {{}},{{}} ({}) right:{{}}}} ",
                start,
                end,
                value,
                self.right.as_ref().unwrap()
            )
        } else if self.right.is_none() {
            write!(
                f,
                " {{ {{}},{{}} ({}) left:{{}}}} ",
                start,
                end,
                value,
                self.left.as_ref().unwrap()
            )
        } else {
            write!(
                f,
                " {{ {{}},{{}} ({}) left:{{}}right:{{}}}} ",
                start,
                end,
                value,
                self.left.as_ref().unwrap(),
                self.right.as_ref().unwrap()
            )
        }
    }
}
```

--------------------------------

### Contains Interval Query

Source: https://docs.rs/unbounded-interval-tree/latest/unbounded_interval_tree/interval_tree/struct.IntervalTree.html

Details how to check if a given interval is fully covered by intervals in the tree.

```APIDOC
## Contains Interval Query

### Description
This method checks if a given `range` is fully covered by the intervals already present in the `IntervalTree`. The bounds of the `range` can be borrowed forms of the stored type `K`.

### Method
- **`contains_interval(range)`**: Checks if the `range` is fully contained within the intervals in the tree.

### Endpoint
N/A (This is a method call on the `IntervalTree` struct)

### Parameters
- **`range`** (`&R`) - Required - The interval range to check for full coverage. `R` must implement `RangeBounds<Q>` where `Q` is comparable to `K`.

### Request Body
None

### Response
#### Success Response (200)
- **`bool`**: `true` if the `range` is fully covered by intervals in the tree, `false` otherwise.

### Request Example
```rust
use std::ops::Bound::{Included, Excluded, Unbounded};
use unbounded_interval_tree::interval_tree::IntervalTree;

let mut tree = IntervalTree::default();

tree.insert((Included(20), Included(30)));
tree.insert((Excluded(30), Excluded(50)));

assert!(tree.contains_interval(&(20..=40)));
assert!(!tree.contains_interval(&(&30..=&50)));

// Example with &str
let mut str_tree: IntervalTree<&str> = IntervalTree::default();
let key1 = (Included("a"), Excluded("h"));
let key2 = (Excluded("M"), Excluded("O"));
str_tree.insert(key1.clone());
str_tree.insert(key2);

assert!(str_tree.contains_interval(&("a".."h")));
assert!(!str_tree.contains_interval(&("N"..="O")));
assert!(str_tree.contains_interval::<&str, _>(&key1));
```
```
Tokens:
Raw