README- UAhoCorasick
- UArcCache
- UArenaTree
- UBiMap
- UBitSet
- UBitVec
- UBloomFilter
- UBloomOptions
- UBoyerMoore
- UCacheStats
- UChainMap
- UCombinations
- UCombinationsWithReplacement
- UCountMinSketch
- UCounter
- UCuckooFilter
- UCuckooOptions
- UDaryHeap
- UDefaultMap
- UDenseSlotMap
- UDisjointSet
- UDisjointSetMap
- UExpiringCache
- UFenwick
- UFibonacciHeap
- UFlatMap
- UFlatMultiMap
- UFlatMultiSet
- UFlatSet
- UGapBuffer
- UGrayCode
- UGrowth
- UHeapKey
- UHyperLogLog
- UIndexHeap
- UIndexMap
- UIndexSet
- UIntervalKey
- UIntervalTree
- UJoinEntry
- UKmp
- ULazySegmentTree
- ULfuCache
- ULinkedList
- ULruCache
- UMatch
- UMinMaxHeap
- UMultiMap
- UMultiSet
- UOpcode
- UOrder
- UOrderStatisticTree
- UOverflow
- UOverlap
- UPairingHeap
- UPermutations
- UPhfBuild
- UPhfBuilder
- UPhfLayout
- UPhfMap
- UPhfOptions
- UPhfOrderedMap
- UPhfOrderedSet
- UPhfSet
- UPosition
- UPowerset
- UProduct
- URadixHeap
- URadixTree
- URangeMap
- URangeSet
- URefused
- URingBuffer
- URope
- URopeBuilder
- URopeView
- USecondaryMap
- USegmentTree
- USequenceMatcher
- USequenceMatcherOptions
- USkipList
- USkipListOptions
- USlab
- USlotKey
- USlotMap
- USortedMultiMap
- USortedMultiSet
- USparseSet
- USuffixArray
- USuffixAutomaton
- UTDigest
- UThetaSketch
- UTreap
- UTreeId
- UTrie
moonbitstack/moonstl/seq does not have a README file
BitSet
A set of non-negative integers stored as bits: membership is a bit test, and
the set operations run word by word. length counts the elements, not the
range, because the range has no ceiling.
test {
let set : @seq.BitSet = @seq.BitSet::new()
@test.assert_eq(set.insert(3), true)
@test.assert_eq(set.insert(3), false)
@test.assert_eq(set.contains(3), true)
@test.assert_eq(set.length(), 1)
@test.assert_eq(set.select(0), Some(3))
@test.assert_eq(set.rank(4), 1)
}BitSet::difference_in_place
BitSet::insert
Adds index and reports whether it was new.
BitSet::intersection_in_place
BitSet::length
The number of elements, not the span they cover.
BitSet::rank
How many elements are smaller than index, which is the position a select
would report and the count of set bits in [0, index).
BitSet::select
The element at position n in increasing order, or None when the set holds
no such position.
BitSet::symmetric_difference
BitVec
A vector of bits with a length: bit i lives in word i / 64 at bit
i % 64, and the bits past the length are always zero.
test {
let bits : @seq.BitVec = @seq.BitVec::new()
bits.push(true)
bits.push(false)
bits.push(true)
@test.assert_eq(bits.length(), 3)
@test.assert_eq(bits.get(2), Some(true))
@test.assert_eq(bits.count_ones(), 2)
}BitVec::blocks
The words themselves, so a caller can hash or compare a run of bits without
walking them one at a time.
BitVec::resize
Grows with zeroes or cuts the length; the bits past the new length are
cleared, so a count_ones afterwards never counts them.
BitVec::set
Sets a bit that is already inside the length. Growing is resize, so a
write cannot silently change how long the vector is.
DenseSlotMap
A slot map that also keeps the entries in a dense array, so iteration follows
insertion order and a removal moves the last entry into the hole. The keys are
the same SlotKeys a SlotMap hands out; what changes is that the entries
are contiguous while they live, which is what a caller who walks the whole
container wants.
DenseSlotMap::contains
DenseSlotMap::insert
DenseSlotMap::iter
The entries in insertion order.
DenseSlotMap::remove
DenseSlotMap::set
GapBuffer
An array with a hole in it: the elements before the hole are kept in order,
the ones after it are kept reversed, and moving the hole is the only
operation that shifts more than one element. Typing at the hole is therefore
constant time, which is what a text editor's buffer wants.
test {
let buffer : @seq.GapBuffer[Int32] = @seq.GapBuffer::new()
buffer.insert(0, 1)
buffer.insert(1, 3)
buffer.insert(1, 2)
@test.assert_eq(buffer.to_array(), [1, 2, 3])
@test.assert_eq(buffer.remove(1), Some(2))
@test.assert_eq(buffer.to_array(), [1, 3])
}GapBuffer::from_array
GapBuffer::insert
Inserts at the hole, which is constant time once the hole is there.
GapBuffer::move_gap_to
Puts the hole at index, moving as few elements as the distance allows.
LinkedList
A doubly linked list: splicing one list onto another and splitting a list in
two are constant time, because neither moves an element — they only relink
nodes. Indexing walks, which is the price of that.
test {
let list : @seq.LinkedList[Int32] = @seq.LinkedList::new()
list.push_back(1)
list.push_back(2)
list.push_front(0)
@test.assert_eq(list.to_array(), [0, 1, 2])
@test.assert_eq(list.pop_front(), Some(0))
@test.assert_eq(list.length(), 2)
}LinkedList::append
The same as splice: the name a reader of Deque already knows.
LinkedList::insert_at
LinkedList::splice
Links other onto the end of this list. other is left empty, and no
element is copied or moved: only four pointers change.
LinkedList::split_off
Cuts the list at index and returns the tail. The two halves share no node;
only the link at the cut changes.
LinkedListNode
A node of a LinkedList. The list owns every node it links; a node is
created by push_back/push_front/insert_at and is never constructed by a
caller, which is why the type carries no public constructor.
Overflow
What a full RingBuffer does with the element it cannot keep. Overwrite
drops the element at the opposite end, which is how a fixed-size buffer of
recent samples is usually written; Refuse leaves the buffer untouched and
hands the new element back, so a caller that must not lose data sees the
refusal in the return value instead of an exception.
RingBuffer
A fixed-ceiling ring of elements. The storage is a plain array with the
live elements starting at head and wrapping around, so every operation
that touches an end is constant time whatever the length.
capacity is a ceiling, not a reservation: the array starts empty and is
doubled — up to the ceiling — as the buffer fills, and empty slots beyond
len hold copies of an element already in the buffer. Those stale copies
are outside every view the buffer hands out.
impl Eq for RingBuffer[T]Two buffers are equal when they hold the same elements in the same order.
The overflow policy and the physical layout are not part of the value.
impl Hash for RingBuffer[T]Hashes the elements in logical order, so equal buffers hash alike whatever
their storage layout.
impl Show for RingBuffer[T]impl Debug for RingBuffer[T]RingBuffer::as_views
The live elements as one or two contiguous array views, in logical order:
the run from the head to the end of the storage, then the run that wrapped
around to the start. Either view may be empty. Reading both views in order
visits the buffer without copying it.
RingBuffer::at
The element index positions from the front. Aborts when out of range, as
an array index does.
RingBuffer::back
The newest element without removing it.
RingBuffer::capacity
The ceiling this buffer was built with; the number of elements cannot
exceed it.
RingBuffer::clear
Removes every element. The storage stays allocated so the buffer can be
refilled without growing again.
RingBuffer::copy
An independent buffer with the same ceiling, policy and elements. Growing
one afterwards does not touch the other.
RingBuffer::equal
RingBuffer::from_array
fn[T] RingBuffer::from_array(capacity~ : Int, values : ArrayView[T], overflow? : Overflow) -> RingBuffer[T] raise RefusedA buffer holding values in order. When the run is longer than capacity,
the policy decides which end survives: Overwrite keeps the last
capacity elements, as pushing them one by one would, and Refuse keeps
the first.
RingBuffer::from_iter
fn[T] RingBuffer::from_iter(capacity~ : Int, values : Iter[T], overflow? : Overflow) -> RingBuffer[T] raise RefusedThe lazy form of from_array; the same overflow rule picks which end of a
run longer than the ceiling survives.
RingBuffer::front
The oldest element without removing it.
RingBuffer::get
The element index positions from the front, counting from zero, or None
when there is no such element.
RingBuffer::hash_combine
RingBuffer::is_empty
Whether the buffer holds nothing.
RingBuffer::is_full
Whether the buffer holds as many elements as its ceiling allows, which is
the state that makes a push drop something.
RingBuffer::iter
The elements from oldest to newest.
RingBuffer::length
The number of elements held.
RingBuffer::linearize
Rotates the storage so the live elements start at index zero, which makes
the first of as_views cover the whole buffer. Subsequent pushes and pops
wrap again; nothing else depends on the layout.
RingBuffer::new
An empty buffer with a ceiling of capacity elements. A ceiling of zero or
less is refused because a buffer that can hold nothing could never accept a
push.
test {
let buffer : @seq.RingBuffer[Int32] = @seq.RingBuffer::new(capacity=2)
@test.assert_eq(buffer.capacity(), 2)
assert_true(buffer.is_empty())
}RingBuffer::not_equal
RingBuffer::output
RingBuffer::overflow
The policy this buffer applies when full.
RingBuffer::pop_back
Removes and returns the newest element, or None when the buffer is empty.
RingBuffer::pop_front
Removes and returns the oldest element, or None when the buffer is empty.
RingBuffer::push_back
Appends at the back. Returns the element dropped from the front when the
buffer was full and the policy is Overwrite; returns the pushed element —
and changes nothing — when the policy is Refuse and there is no room; and
returns None when the element simply fitted.
RingBuffer::push_front
Prepends at the front, with the mirror-image overflow rule: a full
Overwrite buffer drops from the back, and a full Refuse buffer returns
the element it was asked to hold.
RingBuffer::resize_capacity
Changes the ceiling. A ceiling below the current length, or zero or less,
is refused because the buffer would have to discard data to honour it.
Storage shrinks only to the new ceiling and never grows eagerly.
RingBuffer::rev_iter
The elements from newest to oldest.
RingBuffer::set
Replaces the element at index; aborts when out of range.
RingBuffer::to_array
The elements in logical order, oldest first.
SecondaryMap
A side table keyed by the slots of another map: it holds a value per slot and
never invents a slot of its own. resize tells it how many slots the owner
has; a key outside that range is refused, which is how a side table stays in
step with the store it describes instead of quietly growing past it.
SecondaryMap::contains
SecondaryMap::iter
The values that are held, in slot order.
SecondaryMap::remove
SecondaryMap::resize
Tells the side table how many slots the owning map has.
SecondaryMap::set
Slab
An index-addressed store that reuses the indices it frees. An index carries
no generation, so a caller that keeps one past a remove and a later
insert reaches the new occupant: that is the trade a Slab makes for
handing out plain integers, and the reason SlotMap exists beside it.
Slab::capacity
The number of indices ever handed out, live or free.
Slab::insert
Stores value in the lowest free index, or at the end, and returns the index.
SlotKey
A handle to a slot of a SlotMap or a DenseSlotMap. The index says which
slot, the generation says which occupant of that slot: a slot that is freed
and reused raises its generation, so a key handed out earlier can never reach
the new occupant. The type parameter exists only to stop a key of one map
from being passed to another; it carries no value.
SlotKey::from_json
SlotMap
A store whose handles stay valid only while their slot keeps its occupant:
every slot carries a generation, a key carries the generation it was handed
out under, and a freed slot raises its generation when it is reused. A stale
key therefore reads as absent instead of reaching a stranger.
SparseSet
A set whose elements are kept densely, one array for the elements and one
index from element to its position. Membership is a lookup and iteration
walks contiguous memory, which is what a caller who filters a dense
collection wants; the price is a hash index beside the array.
test {
let set : @seq.SparseSet[String] = @seq.SparseSet::new()
@test.assert_eq(set.insert("a"), true)
@test.assert_eq(set.insert("a"), false)
@test.assert_eq(set.contains("a"), true)
@test.assert_eq(set.to_array(), ["a"])
}SparseSet::contains
SparseSet::get_index
Install
Download zipData structures and algorithms the MoonBit core library leaves out.
data-structuresalgorithmscollectionscontainersstlmoonbitindex-mapindex-setmultimapbimapcounterflat-mapsorted-maprange-maptrieradix-treelru-cachelfu-cachearc-cacheexpiring-cachememoizesortingselectionbisectbinary-searchpermutationscombinationspowersetpartitionmergering-bufferslotmapgap-bufferbit-vectorbit-setlinked-listbinary-heapfibonacci-heappairing-heapmin-max-heapradix-heapdisjoint-setunion-findsegment-treefenwick-treeinterval-treeskip-listtreapbloom-filtercuckoo-filtercount-min-sketchhyperloglogtheta-sketcht-digeststring-searchsuffix-arraysuffix-automatondiffropeperfect-hash
Apache-2.0
Updated 9 hours ago
102 downloads