šŸ„® mooncakes.io
    Sign in

    immut_IntervalTree

    Experimenting with implementing an immutable interval tree in Moonbit

    data-structures
    interval-tree
    immutable
    Download zip
    Author
    Version
    0.1.0
    License
    Apache-2.0
    Last updated
    last year
    Downloads
    28

    #Immutable IntervalTree

    English | ē®€ä½“äø­ę–‡

    Immutable IntervalTree is an efficient implementation of interval trees that supports various interval query operations, such as finding overlapping intervals and contained intervals. An interval tree is a special self-balancing binary search tree designed for fast processing of interval queries. Unlike the standard IntervalTree, this implementation maintains complete immutability, with all operations returning new trees instead of modifying existing ones.

    #šŸš€ Key Features

    ā€¢ šŸ›”ļø Fully Immutable - All operations return new trees while original trees remain unchanged ā€¢ šŸ”„ Multiple Construction Methods - Support for empty trees, single interval trees, and creating from arrays ā€¢ āž• Add & Query - Easily insert intervals and check for their existence ā€¢ āŒ Remove - Remove specific intervals and get new trees ā€¢ šŸ” Powerful Queries - Support for finding intervals that match specific criteria ā€¢ šŸ§  Generic Support - Can use any type that implements the Compare trait as interval endpoints ā€¢ āš” Efficient Operations - Optimized for both time and space complexity

    #šŸ“„ Installation

    moon add kesmeey/immut_IntervalTree

    #šŸš€ Usage Guide

    #šŸ”Ø Creating an Interval Tree

    You can create an immutable interval tree using the new(), singleton(), or from_array() methods.

    // An empty interval tree - O(1)
    let tree : T[Int, String] = @immut_IntervalTree.new()

    // With a single interval - O(1)
    let interval = Interval::{ low: 10, high: 20 }
    let single_tree = @immut_IntervalTree.singleton(interval, "data")

    // From an array of intervals - O(n log n)
    let intervals = [
      (Interval::{ low: 10, high: 20 }, "A"),
      (Interval::{ low: 15, high: 25 }, "B"),
      (Interval::{ low: 5, high: 15 }, "C"),
    ]
    let tree_from_array = @immut_IntervalTree.from_array(intervals)

    #āž• Adding Intervals and Data

    Use the insert() method to add intervals and their associated data to the tree. This returns a new tree containing the added interval.

    // Empty tree
    let tree : T[Int, String] = @immut_IntervalTree.new()
    // Insert interval, returns a new tree - O(log n)
    let tree2 = tree.insert(Interval::{ low: 10, high: 20 }, "A")
    // Original tree remains unchanged
    assert_eq!(tree.size, 0)
    assert_eq!(tree2.size, 1)

    #šŸ” Querying Intervals

    Use the find_exact() method to find exact interval matches.

    // Create new tree and add data
    let tree = @immut_IntervalTree.new()
      .insert(Interval::{ low: 10, high: 20 }, "A")
      .insert(Interval::{ low: 15, high: 25 }, "B")
      .insert(Interval::{ low: 5, high: 15 }, "C")

    // Exact match lookup - O(log n)
    let data = tree.find_exact(Interval::{ low: 10, high: 20 })
    assert_eq!(data, Some("A"))

    // Find overlapping intervals - O(k + log n) where k is the number of results
    let overlaps = tree.find_overlaps(Interval::{ low: 12, high: 18 })

    #āŒ Removing Intervals

    Use the remove() method to remove a specific interval, returning a new tree.

    // Create tree and add data
    let tree = @immut_IntervalTree.new()
      .insert(Interval::{ low: 10, high: 20 }, "A")
      .insert(Interval::{ low: 15, high: 25 }, "B")

    // Remove an interval, returns a new tree - O(log n)
    let tree2 = tree.remove(Interval::{ low: 10, high: 20 })
    assert_eq!(tree2.size, 1)
    assert_eq!(tree2.find_exact(Interval::{ low: 10, high: 20 }), None)

    // Original tree remains unchanged
    assert_eq!(tree.size, 2)
    assert_eq!(tree.find_exact(Interval::{ low: 10, high: 20 }), Some("A"))

    #šŸ”„ Replacing Data

    Use the replace_exact() method to replace data for a specific interval, returning a new tree.

    // Create tree and add data
    let tree = @immut_IntervalTree.new().insert(
      Interval::{ low: 10, high: 20 },
      "A",
    )

    // Replace data, returns a new tree - O(log n)
    let tree2 = tree.replace_exact(Interval::{ low: 10, high: 20 }, "Updated A")

    // Verify update
    assert_eq!(tree.find_exact(Interval::{ low: 10, high: 20 }), Some("A"))
    assert_eq!(
      tree2.find_exact(Interval::{ low: 10, high: 20 }),
      Some("Updated A"),
    )

    #šŸ§¹ Clearing the Tree

    Use the clear() method to remove all intervals from the tree, returning a new empty tree.

    // Create tree and add data
    let tree = @immut_IntervalTree.new()
      .insert(Interval::{ low: 10, high: 20 }, "A")
      .insert(Interval::{ low: 15, high: 25 }, "B")

    // Clear the tree, returns a new empty tree - O(1)
    let empty_tree = tree.clear()
    assert_eq!(empty_tree.size, 0)
    assert_eq!(empty_tree.root, None)

    // Original tree remains unchanged
    assert_eq!(tree.size, 2)

    #šŸ” Advanced Queries

    // Create tree and add data
    let tree = @immut_IntervalTree.new()
      .insert(Interval::{ low: 10, high: 20 }, "A")
      .insert(Interval::{ low: 15, high: 25 }, "B")
    // Find intervals contained within a range - O(n) in worst case
    let contained = tree.find_contained(Interval::{ low: 0, high: 30 })

    // Check if a specific interval exists - O(log n)
    let exists = tree.contains(Interval::{ low: 10, high: 20 })

    // Convert all intervals to an array - O(n)
    let all_intervals = tree.to_array()

    #šŸ§  Generic Support

    The immutable interval tree supports any type that implements the Compare trait as interval endpoints.

    // Float type intervals
    let float_tree = @immut_IntervalTree.new()
      .insert(Interval::{ low: 10.5, high: 20.5 }, "A")

    // String type intervals
    let string_tree = @immut_IntervalTree.new()
      .insert(Interval::{ low: "a", high: "z" }, 1)

    #šŸ”„ Functional Programming Style

    The immutable interval tree supports method chaining, making it well-suited for functional programming.

    // Build tree using method chaining
    let tree = @immut_IntervalTree.new()
      .insert(Interval::{ low: 10, high: 20 }, "A")
      .insert(Interval::{ low: 15, high: 25 }, "B")
      .insert(Interval::{ low: 5, high: 15 }, "C")

    // Combine query, modification, and removal operations
    let result = tree
      .replace_exact(Interval::{ low: 10, high: 20 }, "Updated A")
      .remove(Interval::{ low: 15, high: 25 })

    // Original tree unchanged, result contains all changes
    assert_eq!(tree.size, 3)
    assert_eq!(result.size, 2)

    #ā±ļø Time Complexity Summary

    OperationTime ComplexityDescription
    new()O(1)Create an empty tree
    singleton()O(1)Create a tree with one interval
    from_array()O(n log n)Create from array of intervals
    insert()O(log n)Insert a new interval
    remove()O(log n)Remove an interval
    replace_exact()O(log n)Replace data for an interval
    find_exact()O(log n)Find an exact interval match
    find_overlaps()O(k + log n)Find overlapping intervals (k = result count)
    find_contained()O(n)Find intervals contained within a range
    contains()O(log n)Check if an interval exists
    to_array()O(n)Convert tree to array
    clear()O(1)Clear all intervals

    #šŸ“œ License

    This project is licensed under the Apache-2.0 License. See LICENSE for details.

    #šŸ“¢ Contact & Support

    ā€¢ Moonbit Community: moonbit-community ā€¢ GitHub Issues: Report an Issue

    šŸ‘‹ If you like this project, give it a ā­! Happy coding! šŸš€

    InsertResult

    source
    pub struct InsertResult[V, D] {
      node : Node[V, D]
      inserted : Bool
    }

    Represents the result of an immutable insert operation

    Interval

    source
    pub(all) struct Interval[T] {
      low : T
      high : T
    }

    Represents an interval with low and high endpoints
    impl Eq for Interval[T]
    impl Show for Interval[T]

    IntervalMatch

    source
    pub(all) struct IntervalMatch[T, D] {
      interval : Interval[T]
      data : D
    }

    Result of an interval query, containing the interval and associated data
    impl Eq for IntervalMatch[T, D]
    impl Show for IntervalMatch[T, D]

    IntervalOptions

    source
    pub(all) struct IntervalOptions {
      interval_type : IntervalType
      allow_duplicates : Bool
    }

    Options for interval operations

    IntervalType

    source
    pub(all) enum IntervalType {
      Closed
      Open
      LeftClosed
      RightClosed
    }

    Represents the type of interval: closed [a,b], open (a,b), or half-open [a,b) or (a,b]
    impl Eq for IntervalType

    Node

    source
    pub(all) struct Node[V, D] {
      interval : Interval[V]
      data : D
      max_high : V
      left : Node[V, D]?
      right : Node[V, D]?
      height : Int
    }

    Internal node structure for the immutable interval tree
    impl Eq for Node[V, D]
    impl Show for Node[V, D]

    RemoveResult

    source
    pub struct RemoveResult[V, D] {
      node : Node[V, D]?
      removed : Bool
    }

    Result of removing a node
    pub(all) struct T[V, D] {
      root : Node[V, D]?
      size : Int
      options : IntervalOptions
    }

    The main immutable interval tree container

    T::clear

    source
    fn[V : Compare + Eq, D] T::clear(self : T[V, D]) -> T[V, D]

    Clears all intervals from the tree. Returns a new empty tree with the same options.

    T::contains

    source
    fn[V : Compare + Eq, D] T::contains(self : T[V, D], interval : Interval[V]) -> Bool

    ę£€ęŸ„ę ‘äø­ę˜Æ否存åœØęŒ‡å®šēš„åŒŗé—“

    T::find_contained

    source
    fn[V : Compare + Eq, D] T::find_contained(self : T[V, D], container : Interval[V]) -> Array[IntervalMatch[V, D]]

    ęŸ„ę‰¾č¢«ē»™å®šåŒŗ闓完å…Ø包含ēš„ę‰€ęœ‰åŒŗé—“ čæ”回包含匹配åŒŗé—“å’Œę•°ę®ēš„ę•°ē»„

    T::find_exact

    source
    fn[V : Compare + Eq, D] T::find_exact(self : T[V, D], interval : Interval[V]) -> D?

    Finds an exact match for an interval in the tree

    T::find_overlaps

    source
    fn[V : Compare + Eq, D] T::find_overlaps(self : T[V, D], interval : Interval[V]) -> Array[IntervalMatch[V, D]]

    ęŸ„ę‰¾äøŽē»™å®šåŒŗ闓重叠ēš„ę‰€ęœ‰åŒŗé—“ čæ”回包含匹配åŒŗé—“å’Œę•°ę®ēš„ę•°ē»„

    T::insert

    source
    fn[V : Compare + Eq, D] T::insert(self : T[V, D], interval : Interval[V], data : D) -> T[V, D]

    Inserts an interval with associated data into the tree. Returns a new tree with the interval inserted.

    T::remove

    source
    fn[V : Compare + Eq, D] T::remove(self : T[V, D], interval : Interval[V]) -> T[V, D]

    Removes an interval from the tree. Returns a new tree with the interval removed.

    T::replace_exact

    source
    fn[V : Compare + Eq, D] T::replace_exact(self : T[V, D], interval : Interval[V], new_data : D) -> T[V, D]

    Replace data for an exactly matching interval

    T::to_array

    source
    fn[V : Compare + Eq, D] T::to_array(self : T[V, D]) -> Array[IntervalMatch[V, D]]

    å°†ę ‘äø­ēš„ę‰€ęœ‰åŒŗé—“åŠå…¶ę•°ę®č½¬ę¢äøŗꕰē»„

    balance_immut

    source
    fn[V : Compare + Eq, D] balance_immut(node : Node[V, D]) -> Node[V, D]

    Balances a node in the AVL tree (immutable version)

    clear

    source
    fn[V : Compare + Eq, D] clear(self : T[V, D]) -> T[V, D]

    Clears all intervals from the tree. Returns a new empty tree with the same options.

    clone_node

    source
    fn[V, D] clone_node(node : Node[V, D]) -> Node[V, D]

    Helper function to clone a node

    contains

    source
    fn[V : Compare + Eq, D] contains(self : T[V, D], interval : Interval[V]) -> Bool

    ę£€ęŸ„ę ‘äø­ę˜Æ否存åœØęŒ‡å®šēš„åŒŗé—“

    default_options

    source
    fn default_options() -> IntervalOptions

    Default interval options: closed intervals with no duplicates allowed

    endpoints_geq

    source
    fn[V : Compare + Eq] endpoints_geq(a : V, b : V, interval_type~ : IntervalType = ..) -> Bool

    Helper: Checks if a >= b accounting for interval type

    endpoints_leq

    source
    fn[V : Compare + Eq] endpoints_leq(a : V, b : V, interval_type~ : IntervalType = ..) -> Bool

    Helper: Checks if a <= b accounting for interval type

    find_contained

    source
    fn[V : Compare + Eq, D] find_contained(self : T[V, D], container : Interval[V]) -> Array[IntervalMatch[V, D]]

    ęŸ„ę‰¾č¢«ē»™å®šåŒŗ闓完å…Ø包含ēš„ę‰€ęœ‰åŒŗé—“ čæ”回包含匹配åŒŗé—“å’Œę•°ę®ēš„ę•°ē»„

    find_exact

    source
    fn[V : Compare + Eq, D] find_exact(self : T[V, D], interval : Interval[V]) -> D?

    Finds an exact match for an interval in the tree

    find_exact_in_node

    source
    fn[V : Compare + Eq, D] find_exact_in_node(node : Node[V, D], query : Interval[V]) -> D?

    Helper function to find an exact interval match in a node

    find_min_immut

    source
    fn[V, D] find_min_immut(node : Node[V, D]) -> Node[V, D]

    Finds the node with the minimum value in the subtree (immutable version)

    find_overlaps

    source
    fn[V : Compare + Eq, D] find_overlaps(self : T[V, D], interval : Interval[V]) -> Array[IntervalMatch[V, D]]

    ęŸ„ę‰¾äøŽē»™å®šåŒŗ闓重叠ēš„ę‰€ęœ‰åŒŗé—“ čæ”回包含匹配åŒŗé—“å’Œę•°ę®ēš„ę•°ē»„

    from_array

    source
    fn[V : Compare + Eq, D] from_array(intervals : Array[(Interval[V], D)], options~ : IntervalOptions = ..) -> T[V, D]

    Creates a new interval tree from an array of intervals and data.

    get_balance

    source
    fn[V, D] get_balance(node : Node[V, D]) -> Int

    Gets the balance factor of a node

    insert

    source
    fn[V : Compare + Eq, D] insert(self : T[V, D], interval : Interval[V], data : D) -> T[V, D]

    Inserts an interval with associated data into the tree. Returns a new tree with the interval inserted.

    insert_node_immut

    source
    fn[V : Compare + Eq, D] insert_node_immut(node : Node[V, D], new_node : Node[V, D], allow_duplicates~ : Bool = ..) -> InsertResult[V, D]

    Immutable version of insert_node

    interval_contains

    source
    fn[V : Compare + Eq] interval_contains(a : Interval[V], b : Interval[V], interval_type~ : IntervalType = ..) -> Bool

    Checks if interval a completely contains interval b///|

    intervals_overlap

    source
    fn[V : Compare + Eq] intervals_overlap(a : Interval[V], b : Interval[V], interval_type~ : IntervalType = ..) -> Bool

    Checks if two intervals overlap

    is_valid_interval

    source
    fn[V : Compare + Eq] is_valid_interval(interval : Interval[V]) -> Bool

    Checks if the interval is valid (low <= high)

    left_rotate_immut

    source
    fn[V : Compare + Eq, D] left_rotate_immut(x : Node[V, D]) -> Node[V, D]

    Left rotation (immutable version)

    new

    source
    fn[V : Compare + Eq, D] new() -> T[V, D]

    new_with_options

    source
    fn[V : Compare + Eq, D] new_with_options(options : IntervalOptions) -> T[V, D]

    Creates a new interval tree with options.

    remove

    source
    fn[V : Compare + Eq, D] remove(self : T[V, D], interval : Interval[V]) -> T[V, D]

    Removes an interval from the tree. Returns a new tree with the interval removed.

    remove_node_immut

    source
    fn[V : Compare + Eq, D] remove_node_immut(node : Node[V, D], interval : Interval[V]) -> RemoveResult[V, D]

    Immutable version of remove_node

    replace_exact

    source
    fn[V : Compare + Eq, D] replace_exact(self : T[V, D], interval : Interval[V], new_data : D) -> T[V, D]

    Replace data for an exactly matching interval

    replace_exact_helper

    source
    fn[V : Compare + Eq, D] replace_exact_helper(node : Node[V, D], query : Interval[V], new_data : D) -> Node[V, D]

    Helper for replace_exact

    right_rotate_immut

    source
    fn[V : Compare + Eq, D] right_rotate_immut(y : Node[V, D]) -> Node[V, D]

    Right rotation (immutable version)

    singleton

    source
    fn[V : Compare + Eq, D] singleton(interval : Interval[V], data : D, options~ : IntervalOptions = ..) -> T[V, D]

    Creates a new interval tree with a single interval.

    to_array

    source
    fn[V : Compare + Eq, D] to_array(self : T[V, D]) -> Array[IntervalMatch[V, D]]

    å°†ę ‘äø­ēš„ę‰€ęœ‰åŒŗé—“åŠå…¶ę•°ę®č½¬ę¢äøŗꕰē»„

    update_height_and_max_high_immut

    source
    fn[V : Compare + Eq, D] update_height_and_max_high_immut(node : Node[V, D]) -> Node[V, D]

    Update height and max_high for a node (immutable version)

    Source Files

    Powered by MoonBit

    Site sourceReport issuePackagesBuild queueSkillsStatistics

    Ā© 2026 mooncakes.io