aboutsummaryrefslogtreecommitdiff
path: root/src/pds.go
diff options
context:
space:
mode:
Diffstat (limited to 'src/pds.go')
-rw-r--r--src/pds.go403
1 files changed, 210 insertions, 193 deletions
diff --git a/src/pds.go b/src/pds.go
index 0ce9ade..564afbd 100644
--- a/src/pds.go
+++ b/src/pds.go
@@ -4,7 +4,7 @@
//
// Immutable collections provide an efficient, safe way to share collections
// of data while minimizing locks. The collections in this package provide
-// List, Map, and SortedMap implementations. These act similarly to slices
+// Vector, Map, and SortedMap implementations. These act similarly to slices
// and maps, respectively, except that altering a collection returns a new
// copy of the collection with that change.
//
@@ -16,9 +16,9 @@
//
// # Collection Types
//
-// The List type provides an API similar to Go slices. They allow appending,
+// The Vector type provides an API similar to Go slices. They allow appending,
// prepending, and updating of elements. Elements can also be fetched by index
-// or iterated over using a ListIterator.
+// or iterated over using a VectorIterator.
//
// The Map & SortedMap types provide an API similar to Go maps. They allow
// values to be assigned to unique keys and allow for the deletion of keys.
@@ -50,20 +50,20 @@ import (
"strings"
)
-// List is a dense, ordered, indexed collections. They are analogous to slices
-// in Go. They can be updated by appending to the end of the list, prepending
-// values to the beginning of the list, or updating existing indexes in the
-// list.
-type List[T any] struct {
- root listNode[T] // root node
+// Vector is a dense, ordered, indexed collections. They are analogous to slices
+// in Go. They can be updated by appending to the end of the vector, prepending
+// values to the beginning of the vector, or updating existing indexes in the
+// vector.
+type Vector[T any] struct {
+ root vectorNode[T] // root node
origin int // offset to zero index element
size int // total number of elements in use
}
-// NewList returns a new empty instance of List.
-func NewList[T any](values ...T) *List[T] {
- l := &List[T]{
- root: &listLeafNode[T]{},
+// NewVector returns a new empty instance of Vector.
+func NewVector[T any](values ...T) *Vector[T] {
+ l := &Vector[T]{
+ root: &vectorLeafNode[T]{},
}
for _, value := range values {
l.append(value, true)
@@ -71,41 +71,47 @@ func NewList[T any](values ...T) *List[T] {
return l
}
-// clone returns a copy of the list.
-func (l *List[T]) clone() *List[T] {
+// clone returns a copy of the vector.
+func (l *Vector[T]) clone() *Vector[T] {
other := *l
return &other
}
-// Len returns the number of elements in the list.
-func (l *List[T]) Len() int {
+// Len returns the number of elements in the vector.
+func (l *Vector[T]) Len() int {
return l.size
}
// cap returns the total number of possible elements for the current depth.
-func (l *List[T]) cap() int {
- return 1 << (l.root.depth() * listNodeBits)
+func (l *Vector[T]) cap() int {
+ return 1 << (l.root.depth() * vectorNodeBits)
}
// Get returns the value at the given index. Similar to slices, this method will
-// panic if index is below zero or is greater than or equal to the list size.
-func (l *List[T]) Get(index int) T {
+// panic if index is below zero or is greater than or equal to the vector size.
+func (l *Vector[T]) Get(index int) T {
if index < 0 || index >= l.size {
- panic(fmt.Sprintf("immutable.List.Get: index %d out of bounds", index))
+ panic(fmt.Sprintf(
+ "immutable.Vector.Get: index %d out of bounds",
+ index,
+ ))
}
return l.root.get(l.origin + index)
}
-// Set returns a new list with value set at index. Similar to slices, this
+// Set returns a new vector with value set at index. Similar to slices, this
// method will panic if index is below zero or if the index is greater than
-// or equal to the list size.
-func (l *List[T]) Set(index int, value T) *List[T] {
+// or equal to the vector size.
+func (l *Vector[T]) Set(index int, value T) *Vector[T] {
return l.set(index, value, false)
}
-func (l *List[T]) set(index int, value T, mutable bool) *List[T] {
+func (l *Vector[T]) set(index int, value T, mutable bool) *Vector[T] {
if index < 0 || index >= l.size {
- panic(fmt.Sprintf("immutable.List.Set: index %d out of bounds", index))
+ panic(fmt.Sprintf(
+ "immutable.Vector.Set: index %d out of bounds",
+ index,
+ ))
}
other := l
if !mutable {
@@ -115,20 +121,20 @@ func (l *List[T]) set(index int, value T, mutable bool) *List[T] {
return other
}
-// Append returns a new list with value added to the end of the list.
-func (l *List[T]) Append(value T) *List[T] {
+// Append returns a new vector with value added to the end of the vector.
+func (l *Vector[T]) Append(value T) *Vector[T] {
return l.append(value, false)
}
-func (l *List[T]) append(value T, mutable bool) *List[T] {
+func (l *Vector[T]) append(value T, mutable bool) *Vector[T] {
other := l
if !mutable {
other = l.clone()
}
- // Expand list to the right if no slots remain.
+ // Expand vector to the right if no slots remain.
if other.size+other.origin >= l.cap() {
- newRoot := &listBranchNode[T]{d: other.root.depth() + 1}
+ newRoot := &vectorBranchNode[T]{d: other.root.depth() + 1}
newRoot.children[0] = other.root
other.root = newRoot
}
@@ -139,23 +145,25 @@ func (l *List[T]) append(value T, mutable bool) *List[T] {
return other
}
-// Prepend returns a new list with value(s) added to the beginning of the list.
-func (l *List[T]) Prepend(value T) *List[T] {
+// Prepend returns a new vector with value(s) added to the beginning of the
+// vector.
+func (l *Vector[T]) Prepend(value T) *Vector[T] {
return l.prepend(value, false)
}
-func (l *List[T]) prepend(value T, mutable bool) *List[T] {
+func (l *Vector[T]) prepend(value T, mutable bool) *Vector[T] {
other := l
if !mutable {
other = l.clone()
}
- // Expand list to the left if no slots remain.
+ // Expand vector to the left if no slots remain.
if other.origin == 0 {
- newRoot := &listBranchNode[T]{d: other.root.depth() + 1}
- newRoot.children[listNodeSize-1] = other.root
+ newRoot := &vectorBranchNode[T]{d: other.root.depth() + 1}
+ newRoot.children[vectorNodeSize-1] = other.root
other.root = newRoot
- other.origin += (listNodeSize - 1) << (other.root.depth() * listNodeBits)
+ other.origin += (vectorNodeSize - 1) <<
+ ((other.root.depth() * vectorNodeBits))
}
// Increase size and move origin back. Update first element to value.
@@ -165,28 +173,31 @@ func (l *List[T]) prepend(value T, mutable bool) *List[T] {
return other
}
-// Slice returns a new list of elements between start index and end index.
+// Slice returns a new vector of elements between start index and end index.
// Similar to slices, this method will panic if start or end are below zero or
-// greater than the list size. A panic will also occur if start is greater than
-// end.
+// greater than the vector size. A panic will also occur if start is greater
+// than end.
//
// Unlike Go slices, references to inaccessible elements will be automatically
// removed so they can be garbage collected.
-func (l *List[T]) Slice(start, end int) *List[T] {
+func (l *Vector[T]) Slice(start, end int) *Vector[T] {
return l.slice(start, end, false)
}
-func (l *List[T]) slice(start, end int, mutable bool) *List[T] {
+func (l *Vector[T]) slice(start, end int, mutable bool) *Vector[T] {
// Panics similar to Go slices.
if start < 0 || start > l.size {
- panic(fmt.Sprintf("immutable.List.Slice: start index %d out of bounds", start))
+ panic(fmt.Sprintf(
+ "immutable.Vector.Slice: start index %d out of bounds",
+ start,
+ ))
} else if end < 0 || end > l.size {
- panic(fmt.Sprintf("immutable.List.Slice: end index %d out of bounds", end))
+ panic(fmt.Sprintf("immutable.Vector.Slice: end index %d out of bounds", end))
} else if start > end {
- panic(fmt.Sprintf("immutable.List.Slice: invalid slice index: [%d:%d]", start, end))
+ panic(fmt.Sprintf("immutable.Vector.Slice: invalid slice index: [%d:%d]", start, end))
}
- // Return the same list if the start and end are the entire range.
+ // Return the same vector if the start and end are the entire range.
if start == 0 && end == l.size {
return l
}
@@ -203,15 +214,16 @@ func (l *List[T]) slice(start, end int, mutable bool) *List[T] {
// Contract tree while the start & end are in the same child node.
for other.root.depth() > 1 {
- i := (other.origin >> (other.root.depth() * listNodeBits)) & listNodeMask
- j := ((other.origin + other.size - 1) >> (other.root.depth() * listNodeBits)) & listNodeMask
+ i := (other.origin >> (other.root.depth() * vectorNodeBits)) & vectorNodeMask
+ j := ((other.origin + other.size - 1) >> (other.root.depth() * vectorNodeBits)) & vectorNodeMask
if i != j {
break // branch contains at least two nodes, exit
}
- // Replace the current root with the single child & update origin offset.
- other.origin -= i << (other.root.depth() * listNodeBits)
- other.root = other.root.(*listBranchNode[T]).children[i]
+ // Replace the current root with the single child & update
+ // origin offset.
+ other.origin -= i << (other.root.depth() * vectorNodeBits)
+ other.root = other.root.(*vectorBranchNode[T]).children[i]
}
// Ensure all references are removed before start & after end.
@@ -221,133 +233,138 @@ func (l *List[T]) slice(start, end int, mutable bool) *List[T] {
return other
}
-// Iterator returns a new iterator for this list positioned at the first index.
-func (l *List[T]) Iterator() *ListIterator[T] {
- itr := &ListIterator[T]{list: l}
+// Iterator returns a new iterator for this vector positioned at the first
+// index.
+func (l *Vector[T]) Iterator() *VectorIterator[T] {
+ itr := &VectorIterator[T]{vector: l}
itr.First()
return itr
}
-// ListBuilder represents an efficient builder for creating new Lists.
-type ListBuilder[T any] struct {
- list *List[T] // current state
+// VectorBuilder represents an efficient builder for creating new Vectors.
+type VectorBuilder[T any] struct {
+ vector *Vector[T] // current state
}
-// NewListBuilder returns a new instance of ListBuilder.
-func NewListBuilder[T any]() *ListBuilder[T] {
- return &ListBuilder[T]{list: NewList[T]()}
+// NewVectorBuilder returns a new instance of VectorBuilder.
+func NewVectorBuilder[T any]() *VectorBuilder[T] {
+ return &VectorBuilder[T]{vector: NewVector[T]()}
}
-// List returns the current copy of the list.
-// The builder should not be used again after the list after this call.
-func (b *ListBuilder[T]) List() *List[T] {
- assert(b.list != nil, "immutable.ListBuilder.List(): duplicate call to fetch list")
- list := b.list
- b.list = nil
- return list
+// Vector returns the current copy of the vector.
+// The builder should not be used again after the vector after this call.
+func (b *VectorBuilder[T]) Vector() *Vector[T] {
+ assert(b.vector != nil, "immutable.VectorBuilder.Vector(): duplicate call to fetch vector")
+ vector := b.vector
+ b.vector = nil
+ return vector
}
-// Len returns the number of elements in the underlying list.
-func (b *ListBuilder[T]) Len() int {
- assert(b.list != nil, "immutable.ListBuilder: builder invalid after List() invocation")
- return b.list.Len()
+// Len returns the number of elements in the underlying vector.
+func (b *VectorBuilder[T]) Len() int {
+ assert(b.vector != nil, "immutable.VectorBuilder: builder invalid after Vector() invocation")
+ return b.vector.Len()
}
// Get returns the value at the given index. Similar to slices, this method will
-// panic if index is below zero or is greater than or equal to the list size.
-func (b *ListBuilder[T]) Get(index int) T {
- assert(b.list != nil, "immutable.ListBuilder: builder invalid after List() invocation")
- return b.list.Get(index)
+// panic if index is below zero or is greater than or equal to the vector size.
+func (b *VectorBuilder[T]) Get(index int) T {
+ assert(b.vector != nil, "immutable.VectorBuilder: builder invalid after Vector() invocation")
+ return b.vector.Get(index)
}
// Set updates the value at the given index. Similar to slices, this method will
// panic if index is below zero or if the index is greater than or equal to the
-// list size.
-func (b *ListBuilder[T]) Set(index int, value T) {
- assert(b.list != nil, "immutable.ListBuilder: builder invalid after List() invocation")
- b.list = b.list.set(index, value, true)
+// vector size.
+func (b *VectorBuilder[T]) Set(index int, value T) {
+ assert(b.vector != nil, "immutable.VectorBuilder: builder invalid after Vector() invocation")
+ b.vector = b.vector.set(index, value, true)
}
-// Append adds value to the end of the list.
-func (b *ListBuilder[T]) Append(value T) {
- assert(b.list != nil, "immutable.ListBuilder: builder invalid after List() invocation")
- b.list = b.list.append(value, true)
+// Append adds value to the end of the vector.
+func (b *VectorBuilder[T]) Append(value T) {
+ assert(b.vector != nil, "immutable.VectorBuilder: builder invalid after Vector() invocation")
+ b.vector = b.vector.append(value, true)
}
-// Prepend adds value to the beginning of the list.
-func (b *ListBuilder[T]) Prepend(value T) {
- assert(b.list != nil, "immutable.ListBuilder: builder invalid after List() invocation")
- b.list = b.list.prepend(value, true)
+// Prepend adds value to the beginning of the vector.
+func (b *VectorBuilder[T]) Prepend(value T) {
+ assert(b.vector != nil, "immutable.VectorBuilder: builder invalid after Vector() invocation")
+ b.vector = b.vector.prepend(value, true)
}
-// Slice updates the list with a sublist of elements between start and end index.
-// See List.Slice() for more details.
-func (b *ListBuilder[T]) Slice(start, end int) {
- assert(b.list != nil, "immutable.ListBuilder: builder invalid after List() invocation")
- b.list = b.list.slice(start, end, true)
+// Slice updates the vector with a subvector of elements between start and end
+// index.
+// See Vector.Slice() for more details.
+func (b *VectorBuilder[T]) Slice(start, end int) {
+ assert(b.vector != nil, "immutable.VectorBuilder: builder invalid after Vector() invocation")
+ b.vector = b.vector.slice(start, end, true)
}
-// Iterator returns a new iterator for the underlying list.
-func (b *ListBuilder[T]) Iterator() *ListIterator[T] {
- assert(b.list != nil, "immutable.ListBuilder: builder invalid after List() invocation")
- return b.list.Iterator()
+// Iterator returns a new iterator for the underlying vector.
+func (b *VectorBuilder[T]) Iterator() *VectorIterator[T] {
+ assert(b.vector != nil, "immutable.VectorBuilder: builder invalid after Vector() invocation")
+ return b.vector.Iterator()
}
-// Constants for bit shifts used for levels in the List trie.
+// Constants for bit shifts used for levels in the Vector trie.
const (
- listNodeBits = 5
- listNodeSize = 1 << listNodeBits
- listNodeMask = listNodeSize - 1
+ vectorNodeBits = 5
+ vectorNodeSize = 1 << vectorNodeBits
+ vectorNodeMask = vectorNodeSize - 1
)
-// listNode represents either a branch or leaf node in a List.
-type listNode[T any] interface {
+// vectorNode represents either a branch or leaf node in a Vector.
+type vectorNode[T any] interface {
depth() uint
get(index int) T
- set(index int, v T, mutable bool) listNode[T]
+ set(index int, v T, mutable bool) vectorNode[T]
containsBefore(index int) bool
containsAfter(index int) bool
- deleteBefore(index int, mutable bool) listNode[T]
- deleteAfter(index int, mutable bool) listNode[T]
+ deleteBefore(index int, mutable bool) vectorNode[T]
+ deleteAfter(index int, mutable bool) vectorNode[T]
}
-// newListNode returns a leaf node for depth zero, otherwise returns a branch node.
-func newListNode[T any](depth uint) listNode[T] {
+// newVectorNode returns a leaf node for depth zero, otherwise returns a branch
+// node.
+func newVectorNode[T any](depth uint) vectorNode[T] {
if depth == 0 {
- return &listLeafNode[T]{}
+ return &vectorLeafNode[T]{}
}
- return &listBranchNode[T]{d: depth}
+ return &vectorBranchNode[T]{d: depth}
}
-// listBranchNode represents a branch of a List tree at a given depth.
-type listBranchNode[T any] struct {
+// vectorBranchNode represents a branch of a Vector tree at a given depth.
+type vectorBranchNode[T any] struct {
d uint // depth
- children [listNodeSize]listNode[T]
+ children [vectorNodeSize]vectorNode[T]
}
// depth returns the depth of this branch node from the leaf.
-func (n *listBranchNode[T]) depth() uint { return n.d }
+func (n *vectorBranchNode[T]) depth() uint { return n.d }
// get returns the child node at the segment of the index for this depth.
-func (n *listBranchNode[T]) get(index int) T {
- idx := (index >> (n.d * listNodeBits)) & listNodeMask
+func (n *vectorBranchNode[T]) get(index int) T {
+ idx := (index >> (n.d * vectorNodeBits)) & vectorNodeMask
return n.children[idx].get(index)
}
-// set recursively updates the value at index for each lower depth from the node.
-func (n *listBranchNode[T]) set(index int, v T, mutable bool) listNode[T] {
- idx := (index >> (n.d * listNodeBits)) & listNodeMask
+// set recursively updates the value at index for each lower depth from the
+// node.
+func (n *vectorBranchNode[T]) set(index int, v T, mutable bool) vectorNode[T] {
+ idx := (index >> (n.d * vectorNodeBits)) & vectorNodeMask
- // Find child for the given value in the branch. Create new if it doesn't exist.
+ // Find child for the given value in the branch. Create new if it
+ // doesn't exist.
child := n.children[idx]
if child == nil {
- child = newListNode[T](n.depth() - 1)
+ child = newVectorNode[T](n.depth() - 1)
}
// Return a copy of this branch with the new child.
- var other *listBranchNode[T]
+ var other *vectorBranchNode[T]
if mutable {
other = n
} else {
@@ -359,8 +376,8 @@ func (n *listBranchNode[T]) set(index int, v T, mutable bool) listNode[T] {
}
// containsBefore returns true if non-nil values exists between [0,index).
-func (n *listBranchNode[T]) containsBefore(index int) bool {
- idx := (index >> (n.d * listNodeBits)) & listNodeMask
+func (n *vectorBranchNode[T]) containsBefore(index int) bool {
+ idx := (index >> (n.d * vectorNodeBits)) & vectorNodeMask
// Quickly check if any direct children exist before this segment of the index.
for i := 0; i < idx; i++ {
@@ -376,9 +393,9 @@ func (n *listBranchNode[T]) containsBefore(index int) bool {
return false
}
-// containsAfter returns true if non-nil values exists between (index,listNodeSize).
-func (n *listBranchNode[T]) containsAfter(index int) bool {
- idx := (index >> (n.d * listNodeBits)) & listNodeMask
+// containsAfter returns true if non-nil values exists between (index,vectorNodeSize).
+func (n *vectorBranchNode[T]) containsAfter(index int) bool {
+ idx := (index >> (n.d * vectorNodeBits)) & vectorNodeMask
// Quickly check if any direct children exist after this segment of the index.
for i := idx + 1; i < len(n.children); i++ {
@@ -395,23 +412,23 @@ func (n *listBranchNode[T]) containsAfter(index int) bool {
}
// deleteBefore returns a new node with all elements before index removed.
-func (n *listBranchNode[T]) deleteBefore(index int, mutable bool) listNode[T] {
+func (n *vectorBranchNode[T]) deleteBefore(index int, mutable bool) vectorNode[T] {
// Ignore if no nodes exist before the given index.
if !n.containsBefore(index) {
return n
}
// Return a copy with any nodes prior to the index removed.
- idx := (index >> (n.d * listNodeBits)) & listNodeMask
+ idx := (index >> (n.d * vectorNodeBits)) & vectorNodeMask
- var other *listBranchNode[T]
+ var other *vectorBranchNode[T]
if mutable {
other = n
for i := 0; i < idx; i++ {
n.children[i] = nil
}
} else {
- other = &listBranchNode[T]{d: n.d}
+ other = &vectorBranchNode[T]{d: n.d}
copy(other.children[idx:][:], n.children[idx:][:])
}
@@ -422,23 +439,23 @@ func (n *listBranchNode[T]) deleteBefore(index int, mutable bool) listNode[T] {
}
// deleteBefore returns a new node with all elements before index removed.
-func (n *listBranchNode[T]) deleteAfter(index int, mutable bool) listNode[T] {
+func (n *vectorBranchNode[T]) deleteAfter(index int, mutable bool) vectorNode[T] {
// Ignore if no nodes exist after the given index.
if !n.containsAfter(index) {
return n
}
// Return a copy with any nodes after the index removed.
- idx := (index >> (n.d * listNodeBits)) & listNodeMask
+ idx := (index >> (n.d * vectorNodeBits)) & vectorNodeMask
- var other *listBranchNode[T]
+ var other *vectorBranchNode[T]
if mutable {
other = n
for i := idx + 1; i < len(n.children); i++ {
n.children[i] = nil
}
} else {
- other = &listBranchNode[T]{d: n.d}
+ other = &vectorBranchNode[T]{d: n.d}
copy(other.children[:idx+1], n.children[:idx+1])
}
@@ -448,25 +465,25 @@ func (n *listBranchNode[T]) deleteAfter(index int, mutable bool) listNode[T] {
return other
}
-// listLeafNode represents a leaf node in a List.
-type listLeafNode[T any] struct {
- children [listNodeSize]T
+// vectorLeafNode represents a leaf node in a Vector.
+type vectorLeafNode[T any] struct {
+ children [vectorNodeSize]T
// bitset with ones at occupied positions, position 0 is the LSB
occupied uint32
}
// depth always returns 0 for leaf nodes.
-func (n *listLeafNode[T]) depth() uint { return 0 }
+func (n *vectorLeafNode[T]) depth() uint { return 0 }
// get returns the value at the given index.
-func (n *listLeafNode[T]) get(index int) T {
- return n.children[index&listNodeMask]
+func (n *vectorLeafNode[T]) get(index int) T {
+ return n.children[index&vectorNodeMask]
}
// set returns a copy of the node with the value at the index updated to v.
-func (n *listLeafNode[T]) set(index int, v T, mutable bool) listNode[T] {
- idx := index & listNodeMask
- var other *listLeafNode[T]
+func (n *vectorLeafNode[T]) set(index int, v T, mutable bool) vectorNode[T] {
+ idx := index & vectorNodeMask
+ var other *vectorLeafNode[T]
if mutable {
other = n
} else {
@@ -479,26 +496,26 @@ func (n *listLeafNode[T]) set(index int, v T, mutable bool) listNode[T] {
}
// containsBefore returns true if non-nil values exists between [0,index).
-func (n *listLeafNode[T]) containsBefore(index int) bool {
- idx := index & listNodeMask
+func (n *vectorLeafNode[T]) containsBefore(index int) bool {
+ idx := index & vectorNodeMask
return bits.TrailingZeros32(n.occupied) < idx
}
-// containsAfter returns true if non-nil values exists between (index,listNodeSize).
-func (n *listLeafNode[T]) containsAfter(index int) bool {
- idx := index & listNodeMask
+// containsAfter returns true if non-nil values exists between (index,vectorNodeSize).
+func (n *vectorLeafNode[T]) containsAfter(index int) bool {
+ idx := index & vectorNodeMask
lastSetPos := 31 - bits.LeadingZeros32(n.occupied)
return lastSetPos > idx
}
// deleteBefore returns a new node with all elements before index removed.
-func (n *listLeafNode[T]) deleteBefore(index int, mutable bool) listNode[T] {
+func (n *vectorLeafNode[T]) deleteBefore(index int, mutable bool) vectorNode[T] {
if !n.containsBefore(index) {
return n
}
- idx := index & listNodeMask
- var other *listLeafNode[T]
+ idx := index & vectorNodeMask
+ var other *vectorLeafNode[T]
if mutable {
other = n
var empty T
@@ -506,7 +523,7 @@ func (n *listLeafNode[T]) deleteBefore(index int, mutable bool) listNode[T] {
other.children[i] = empty
}
} else {
- other = &listLeafNode[T]{occupied: n.occupied}
+ other = &vectorLeafNode[T]{occupied: n.occupied}
copy(other.children[idx:][:], n.children[idx:][:])
}
// Set the first idx bits to 0.
@@ -515,13 +532,13 @@ func (n *listLeafNode[T]) deleteBefore(index int, mutable bool) listNode[T] {
}
// deleteAfter returns a new node with all elements after index removed.
-func (n *listLeafNode[T]) deleteAfter(index int, mutable bool) listNode[T] {
+func (n *vectorLeafNode[T]) deleteAfter(index int, mutable bool) vectorNode[T] {
if !n.containsAfter(index) {
return n
}
- idx := index & listNodeMask
- var other *listLeafNode[T]
+ idx := index & vectorNodeMask
+ var other *vectorLeafNode[T]
if mutable {
other = n
var empty T
@@ -529,7 +546,7 @@ func (n *listLeafNode[T]) deleteAfter(index int, mutable bool) listNode[T] {
other.children[i] = empty
}
} else {
- other = &listLeafNode[T]{occupied: n.occupied}
+ other = &vectorLeafNode[T]{occupied: n.occupied}
copy(other.children[:idx+1][:], n.children[:idx+1][:])
}
// Set bits after idx to 0. idx < 31 because n.containsAfter(index) == true.
@@ -537,55 +554,55 @@ func (n *listLeafNode[T]) deleteAfter(index int, mutable bool) listNode[T] {
return other
}
-// ListIterator represents an ordered iterator over a list.
-type ListIterator[T any] struct {
- list *List[T] // source list
+// VectorIterator represents an ordered iterator over a vector.
+type VectorIterator[T any] struct {
+ vector *Vector[T] // source vector
index int // current index position
- stack [32]listIteratorElem[T] // search stack
+ stack [32]vectorIteratorElem[T] // search stack
depth int // stack depth
}
// Done returns true if no more elements remain in the iterator.
-func (itr *ListIterator[T]) Done() bool {
- return itr.index < 0 || itr.index >= itr.list.Len()
+func (itr *VectorIterator[T]) Done() bool {
+ return itr.index < 0 || itr.index >= itr.vector.Len()
}
// First positions the iterator on the first index.
-// If source list is empty then no change is made.
-func (itr *ListIterator[T]) First() {
- if itr.list.Len() != 0 {
+// If source vector is empty then no change is made.
+func (itr *VectorIterator[T]) First() {
+ if itr.vector.Len() != 0 {
itr.Seek(0)
}
}
// Last positions the iterator on the last index.
-// If source list is empty then no change is made.
-func (itr *ListIterator[T]) Last() {
- if n := itr.list.Len(); n != 0 {
+// If source vector is empty then no change is made.
+func (itr *VectorIterator[T]) Last() {
+ if n := itr.vector.Len(); n != 0 {
itr.Seek(n - 1)
}
}
-// Seek moves the iterator position to the given index in the list.
+// Seek moves the iterator position to the given index in the vector.
// Similar to Go slices, this method will panic if index is below zero or if
-// the index is greater than or equal to the list size.
-func (itr *ListIterator[T]) Seek(index int) {
+// the index is greater than or equal to the vector size.
+func (itr *VectorIterator[T]) Seek(index int) {
// Panic similar to Go slices.
- if index < 0 || index >= itr.list.Len() {
- panic(fmt.Sprintf("immutable.ListIterator.Seek: index %d out of bounds", index))
+ if index < 0 || index >= itr.vector.Len() {
+ panic(fmt.Sprintf("immutable.VectorIterator.Seek: index %d out of bounds", index))
}
itr.index = index
// Reset to the bottom of the stack at seek to the correct position.
- itr.stack[0] = listIteratorElem[T]{node: itr.list.root}
+ itr.stack[0] = vectorIteratorElem[T]{node: itr.vector.root}
itr.depth = 0
itr.seek(index)
}
// Next returns the current index and its value & moves the iterator forward.
// Returns an index of -1 if the there are no more elements to return.
-func (itr *ListIterator[T]) Next() (index int, value T) {
+func (itr *VectorIterator[T]) Next() (index int, value T) {
// Exit immediately if there are no elements remaining.
var empty T
if itr.Done() {
@@ -594,7 +611,7 @@ func (itr *ListIterator[T]) Next() (index int, value T) {
// Retrieve current index & value.
elem := &itr.stack[itr.depth]
- index, value = itr.index, elem.node.(*listLeafNode[T]).children[elem.index]
+ index, value = itr.index, elem.node.(*vectorLeafNode[T]).children[elem.index]
// Increase index. If index is at the end then return immediately.
itr.index++
@@ -603,7 +620,7 @@ func (itr *ListIterator[T]) Next() (index int, value T) {
}
// Move up stack until we find a node that has remaining position ahead.
- for ; itr.depth > 0 && itr.stack[itr.depth].index >= listNodeSize-1; itr.depth-- {
+ for ; itr.depth > 0 && itr.stack[itr.depth].index >= vectorNodeSize-1; itr.depth-- {
}
// Seek to correct position from current depth.
@@ -614,7 +631,7 @@ func (itr *ListIterator[T]) Next() (index int, value T) {
// Prev returns the current index and value and moves the iterator backward.
// Returns an index of -1 if the there are no more elements to return.
-func (itr *ListIterator[T]) Prev() (index int, value T) {
+func (itr *VectorIterator[T]) Prev() (index int, value T) {
// Exit immediately if there are no elements remaining.
var empty T
if itr.Done() {
@@ -623,7 +640,7 @@ func (itr *ListIterator[T]) Prev() (index int, value T) {
// Retrieve current index & value.
elem := &itr.stack[itr.depth]
- index, value = itr.index, elem.node.(*listLeafNode[T]).children[elem.index]
+ index, value = itr.index, elem.node.(*vectorLeafNode[T]).children[elem.index]
// Decrease index. If index is past the beginning then return immediately.
itr.index--
@@ -643,26 +660,26 @@ func (itr *ListIterator[T]) Prev() (index int, value T) {
// seek positions the stack to the given index from the current depth.
// Elements and indexes below the current depth are assumed to be correct.
-func (itr *ListIterator[T]) seek(index int) {
+func (itr *VectorIterator[T]) seek(index int) {
// Iterate over each level until we reach a leaf node.
for {
elem := &itr.stack[itr.depth]
- elem.index = ((itr.list.origin + index) >> (elem.node.depth() * listNodeBits)) & listNodeMask
+ elem.index = ((itr.vector.origin + index) >> (elem.node.depth() * vectorNodeBits)) & vectorNodeMask
switch node := elem.node.(type) {
- case *listBranchNode[T]:
+ case *vectorBranchNode[T]:
child := node.children[elem.index]
- itr.stack[itr.depth+1] = listIteratorElem[T]{node: child}
+ itr.stack[itr.depth+1] = vectorIteratorElem[T]{node: child}
itr.depth++
- case *listLeafNode[T]:
+ case *vectorLeafNode[T]:
return
}
}
}
-// listIteratorElem represents the node and it's child index within the stack.
-type listIteratorElem[T any] struct {
- node listNode[T]
+// vectorIteratorElem represents the node and it's child index within the stack.
+type vectorIteratorElem[T any] struct {
+ node vectorNode[T]
index int
}
@@ -940,7 +957,7 @@ func (n *mapArrayNode[K, V]) set(key K, value V, shift uint, keyHash uint32, h H
}
// Update existing entry if a match is found.
- // Otherwise append to the end of the element list if it doesn't exist.
+ // Otherwise append to the end of the element vector if it doesn't exist.
var other mapArrayNode[K, V]
if idx != -1 {
other.entries = make([]mapEntry[K, V], len(n.entries))
@@ -1059,7 +1076,7 @@ func (n *mapBitmapIndexedNode[K, V]) set(key K, value V, shift uint, keyHash uin
}
// If node exists at given slot then overwrite it with new node.
- // Otherwise expand the node list and insert new node into appropriate position.
+ // Otherwise expand the node vector and insert new node into appropriate position.
other := &mapBitmapIndexedNode[K, V]{bitmap: n.bitmap | bit}
if exists {
other.nodes = make([]mapNode[K, V], len(n.nodes))
@@ -1113,7 +1130,7 @@ func (n *mapBitmapIndexedNode[K, V]) delete(key K, shift uint, keyHash uint32, h
return n
}
- // Return copy with bit removed from bitmap and node removed from node list.
+ // Return copy with bit removed from bitmap and node removed from node vector.
other := &mapBitmapIndexedNode[K, V]{bitmap: n.bitmap ^ bit, nodes: make([]mapNode[K, V], len(n.nodes)-1)}
copy(other.nodes[:idx], n.nodes[:idx])
copy(other.nodes[idx:], n.nodes[idx+1:])
@@ -2691,7 +2708,7 @@ func (s SortedSetBuilder[T]) Len() int {
}
// SortedSet returns the current copy of the set.
-// The builder should not be used again after the list after this call.
+// The builder should not be used again after the vector after this call.
func (s SortedSetBuilder[T]) SortedSet() SortedSet[T] {
assert(s.s != nil, "immutable.SortedSetBuilder.SortedSet(): duplicate call to fetch sorted set")
set := s.s
generated by cgit v1.2.3 (git 2.49.0) at 2025-07-13 03:54:47 +0000