diet
Discrete Interval Encoding Trees
diet
data-structure
moon add CAIMEOX/diet@0.1.3
Download zipAuthor
Version
0.1.3
License
Apache-2.0
Repository
Last updated
9 months ago
Downloads
32
README#DIET: Discrete Interval Encoding Trees for MoonBit
The DIET (Discrete Interval Encoding Tree) library provides an efficient set representation for continuous ranges of values. This data structure is particularly useful when you need to represent large sets of sequential data while maintaining memory efficiency.
#Overview
A DIET represents sets as intervals rather than individual elements. For example, instead of storing [1, 2, 3, 4, 5] as five separate values, it stores them as a single interval (1, 5). This approach provides significant memory savings when working with large, dense sets of ordered data.
#Usage Examples
- Creating a DIET:
// Create an empty set
let empty = @diet.empty()
// Create a set with a single element
let singleton = @diet.singleton('a')
// Create a set with an interval
let digits = @diet.interval('0', '9')
// Create from an array
let letters = @diet.of(['a', 'b', 'c', 'd', 'e'])- Set operations:
// Union of two sets
let combined = @diet.union(set1, set2)
// Intersection of two sets
let common = @diet.intersection(set1, set2)
// Difference between sets
let difference = @diet.difference(set1, set2)
// Complement of a set
let complement = @diet.complement(set)- Element Operations:
// Add an element
let with_element = set.add(5)
// Remove an element
let without_element = set.remove(5)
// Check if an element exists
let exists = set.contains(5)More other operations are available, including checking if a set is empty, getting the size of a set, and iterating over elements. Check the mooncakes DIET documentation for a complete list of methods.
#Supported Types
The library includes built-in support for:
- Char - for character ranges
- Int - for integer ranges You can extend support to custom types by implementing the BoundedEnum trait.
#BoundedEnum
pub(open) trait BoundedEnum : Compare {
pred(Self) -> Self
succ(Self) -> Self
lower_bound() -> Self
upper_bound() -> Self
}
#Tree
#alias(T)
type Tree[T]#Tree::add
Adds a single value to a discrete interval encoding tree.
#Tree::complement
Computes the complement of a discrete interval encoding tree.
#Tree::contains
Determines if a discrete interval encoding tree contains a specific value.
#Tree::fold_ranges
Applies a function to each interval in the tree and accumulates the results.
#Tree::intersection
Computes the intersection of two discrete interval encoding trees.
#Tree::iter
Create a new iterator over the elements represent by the tree
#Tree::iter_intervals
Create a new iterator over intervals
#Tree::remove
Removes a single value from a discrete interval encoding tree.
#Tree::slice
Returns a tree containing all elements within the specified range.
#Tree::slice_after
Returns a tree containing all elements strictly greater than x.
#Tree::slice_before
Returns a tree containing all elements strictly less than x.
#Tree::slice_from
Returns a tree containing all elements greater than or equal to x.
#Tree::slice_until
Returns a tree containing all elements less than or equal to x.
#difference
Computes the difference between two discrete interval encoding trees.
#is_subset
Checks if one discrete interval encoding tree is a subset of another.
#of
Converts an array of elements into a tree
#of_view
Converts an array view into a tree
Discrete Interval Encoding Trees
dietdata-structure
0.1.3
Apache-2.0
Updated 9 months ago
32 downloads