persistent

package module
v1.0.8 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jun 16, 2025 License: MIT Imports: 4 Imported by: 0

README

persistent

Generic persistent collections for golang

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Iterator 

type Iterator[T any] interface {
	//Next advances the iterator by one position, and returns true iif the new position is valid.
	Next() bool

	//Current returns the value at the current iterator position. Will panic if the iterator position is invalid.
	Current() T
}

Iterator defines an interface for an iterator over a persistent data structure.

It is safe to use multiple iterators over the same data structure concurrently. A single Iterator instance, however, is not concurrency safe. Sharing an iterator instance between go-routines requires explicit synchronization.

Example: 

var iter = tree.Iterator()
for iter.Next() {
    fmt.Println(iter.Current())
}

type Ordered 

type Ordered[T any] interface {
	Less(rhs T) bool
}

Ordered defines an interface for a custom key type. Any type K defining a Less method can be used with TreeEx[K, V] or OrderedSet[K]. For primitive key types see Tree[K, V] and Set[K]

type Pair 

type Pair[K any, V any] struct {
	// Key is the key associated with the pair.
	Key K

	// Value is the value associated with the pair.
	Value V
}

Pair defines a struct for a Key / Value pair.

type Queue 

type Queue[T any] struct {
	// contains filtered or unexported fields
}

Queue implements a persistent queue.

Persistent queues are immutable. Each mutating operation will return a pointer to a new queue with the update applied.The implementation uses structural sharing to make immutability efficient. The implementation is concurrency safe and non-blocking. A *Queue[T] instance may be accessed from multiple go-routines without synchronization. Each mutating Queue[T] operation has amortized O(1) cost.

func EmptyQueue 

func EmptyQueue[T any]() *Queue[T]

EmptyQueue returns a new empty queue.

func (*Queue[T]) Dequeue 

func (q *Queue[T]) Dequeue() (value T, queue *Queue[T])

Dequeue removes the top item from the queue, and returns the dequeued value along with a new queue with the value removed. If the queue is empty, the returned 'value' will be the 0 value of T.

Dequeue is amortized O(1). This means an individual Dequeue operation may be O(n), but with a series of n calls the average runtime is O(1).

func (*Queue[T]) Enqueue 

func (q *Queue[T]) Enqueue(value T) *Queue[T]

Enqueue returns a new queue with 'value' added to the end. This is O(1).

func (*Queue[T]) IsEmpty 

func (q *Queue[T]) IsEmpty() bool

IsEmpty returns true iif the queue is empty.

func (*Queue[T]) MarshalJSON added in v1.0.4 

func (q *Queue[T]) MarshalJSON() ([]byte, error)

func (*Queue[T]) Size 

func (q *Queue[T]) Size() int

Size returns the number of elements in 'q'.

func (*Queue[T]) Top added in v1.0.8 

func (q *Queue[T]) Top() T

Top returns the top element in the queue without removing it. This is O(1). If the queue is empty, the returned value will be the zero value of T.

func (*Queue[T]) UnmarshalJSON added in v1.0.4 

func (q *Queue[T]) UnmarshalJSON(bytes []byte) error

type Set 

type Set[T constraints.Ordered] struct {
	// contains filtered or unexported fields
}

Set defines a set interface implemented using a persistent AVL tree. It works for all types that support the < operator. For custom types see the SetEx method.

Persistent AVL trees are immutable. Each mutating operation will return the root of a new tree with the requested update applied. The implementation uses structural sharing to make immutability efficient. For any given update, at most O(log(n)) nodes will be replaced in the new tree. The implementation is also concurrency-safe and non-blocking. A *Set[T] instance may be accessed from multiple go-routines without synchronization. See the docs on Iterator[T] for notes on concurrent use of iterators.

func EmptySet added in v1.0.5 

func EmptySet[T constraints.Ordered]() *Set[T]

func (*Set[T]) Add 

func (s *Set[T]) Add(elem T) *Set[T]

Add returns the root of a new tree with the given element added.

func (*Set[T]) Contains 

func (s *Set[T]) Contains(elem T) bool

Contains return true if the set contains the given element.

func (*Set[T]) GetKthElement added in v1.0.3 

func (s *Set[T]) GetKthElement(k int) (e T, ok bool)

GetKthElement returns the k'th smallest element in a set. If no such element exists, ok will be false.

func (*Set[T]) GreatestLowerBound 

func (s *Set[T]) GreatestLowerBound(value T) (T, bool)

GreatestLowerBound returns the largest element e in s, such that e <= value. If no such element exists, ok will be false and e will be set to the zero value for T.

func (*Set[T]) IsEmpty 

func (s *Set[T]) IsEmpty() bool

IsEmpty returns true iif s is empty.

func (*Set[T]) Iter 

func (s *Set[T]) Iter() Iterator[T]

Iter returns an in-order traversal iterator over the elements in the set.

func (*Set[T]) IterGte 

func (s *Set[T]) IterGte(e T) Iterator[T]

IterGte returns an in-order traversal iterator over all elements x in s that are >= e

func (*Set[T]) LeastUpperBound 

func (s *Set[T]) LeastUpperBound(value T) (e T, ok bool)

LeastUpperBound returns the smallest element e in s, such that value <= e. If no such element exists, ok will be false and e will be set to the zero value for T.

func (*Set[T]) MarshalJSON 

func (s *Set[T]) MarshalJSON() ([]byte, error)

MarshalJSON marshals the set s as a json array.a

func (*Set[T]) Remove 

func (s *Set[T]) Remove(elem T) *Set[T]

Remove returns the root of a new tree with the given element removed.

func (*Set[T]) Size 

func (s *Set[T]) Size() int

Size returns the number of elements in the set.

func (*Set[T]) UnmarshalJSON 

func (s *Set[T]) UnmarshalJSON(data []byte) error

UnmarshalJSON unmarshals a json array into s.

type SetEx 

type SetEx[T Ordered[T]] struct {
	// contains filtered or unexported fields
}

SetEx defines a set interface implemented using a persistent AVL tree. It works for custom types that implement the Ordered[T] interface. See Set[T] for types that support the < interface.

Persistent AVL trees are immutable. Each mutating operation will return the root of a new tree with the requested update applied. The implementation uses structural sharing to make immutability efficient. For any given update, at most O(log(n)) nodes will be replaced in the new tree. The implementation is also concurrency-safe and non-blocking. A *Set[T] instance may be accessed from multiple go-routines without synchronization. See the docs for Iterator[T] for notes on concurrent use of iterators.

func EmptySetEx added in v1.0.5 

func EmptySetEx[T Ordered[T]]() *SetEx[T]

func (*SetEx[T]) Add 

func (s *SetEx[T]) Add(elem T) *SetEx[T]

Add returns the root of a new tree with the given element added.

func (*SetEx[T]) Contains 

func (s *SetEx[T]) Contains(elem T) bool

Contains return true if the set contains the given element.

func (*SetEx[T]) GetKthElement added in v1.0.3 

func (s *SetEx[T]) GetKthElement(k int) (e T, ok bool)

GetKthElement returns the k'th smallest element in a set. If no such element exists, ok will be false.

func (*SetEx[T]) GreatestLowerBound 

func (s *SetEx[T]) GreatestLowerBound(value T) (T, bool)

GreatestLowerBound returns the largest element e in s, such that e <= value. If no such element exists, ok will be false and e will be set to the zero value for T.

func (*SetEx[T]) IsEmpty 

func (s *SetEx[T]) IsEmpty() bool

IsEmpty returns true iif s is empty.

func (*SetEx[T]) Iter 

func (s *SetEx[T]) Iter() Iterator[T]

Iter returns an in-order traversal iterator over the elements in the set.

func (*SetEx[T]) IterGte 

func (s *SetEx[T]) IterGte(e T) Iterator[T]

IterGte returns an in-order traversal iterator over all elements x in s that are >= e

func (*SetEx[T]) LeastUpperBound 

func (s *SetEx[T]) LeastUpperBound(value T) (e T, ok bool)

LeastUpperBound returns the smallest element e in s, such that value <= e. If no such element exists, ok will be false and e will be set to the zero value for T.

func (*SetEx[T]) MarshalJSON 

func (s *SetEx[T]) MarshalJSON() ([]byte, error)

MarshalJSON marshals the set s as a json array.a

func (*SetEx[T]) Remove 

func (s *SetEx[T]) Remove(elem T) *SetEx[T]

Remove returns the root of a new tree with the given element removed.

func (*SetEx[T]) Size 

func (s *SetEx[T]) Size() int

Size returns the number of elements in the set.

func (*SetEx[T]) UnmarshalJSON 

func (s *SetEx[T]) UnmarshalJSON(data []byte) error

UnmarshalJSON unmarshals a json array into s.

type SetExIterator 

type SetExIterator[T Ordered[T]] struct {
	// contains filtered or unexported fields
}

func (*SetExIterator[T]) Current 

func (s *SetExIterator[T]) Current() T

func (*SetExIterator[T]) Next 

func (s *SetExIterator[T]) Next() bool

type SetIterator 

type SetIterator[T constraints.Ordered] struct {
	// contains filtered or unexported fields
}

func (*SetIterator[T]) Current 

func (s *SetIterator[T]) Current() T

func (*SetIterator[T]) Next 

func (s *SetIterator[T]) Next() bool

type Stack 

type Stack[T any] struct {
	// contains filtered or unexported fields
}

Stack implements a persistent stack.

Persistent stacks are immutable. Each mutating operation will return a pointer to a new stack with the update applied.The implementation uses structural sharing to make immutability efficient. The implementation is concurrency safe and non-blocking. A *Stack[T] instance may be accessed from multiple go-routines without synchronization. Each mutating Stack[T] operation is O(1).

func EmptyStack 

func EmptyStack[T any]() *Stack[T]

EmptyStack returns a new empty Stack[T].

func (*Stack[T]) IsEmpty 

func (s *Stack[T]) IsEmpty() bool

IsEmpty returns true iif s is empty.

func (*Stack[T]) Peek 

func (s *Stack[T]) Peek() T

Peek returns the top-most element of the stack. If the stack is empty, it will return the zero value for T.

func (*Stack[T]) Pop 

func (s *Stack[T]) Pop() *Stack[T]

Pop returns a new stack with the top element removed. If the stack s is empty, s.Pop() is also empty.

func (*Stack[T]) Push 

func (s *Stack[T]) Push(value T) *Stack[T]

Push returns a new stack with 'value' added to the top.

func (*Stack[T]) Reverse 

func (s *Stack[T]) Reverse() *Stack[T]

Reverse returns the stack s in reverse order. This is mostly used in the implementation of Queue[T].

func (*Stack[T]) Size 

func (s *Stack[T]) Size() int

Size returns the number of elements in s.

type Tree 

type Tree[K constraints.Ordered, V any] struct {
	// contains filtered or unexported fields
}

Tree implements a persistent AVL tree for keys types that support the < operator. For custom key types see TreeEx[K,V].

Note: Both an empty Tree struct and a nil *Tree are valid empty trees.

Persistent AVL trees are immutable. Each mutating operation will return the root of a new tree with the requested update applied.The implementation uses structural sharing to make immutability efficient. For any given update at most O(log(N)) nodes will be replaced in the new tree. The implementation is concurrency safe and non-blocking. A *Tree[K,V] instance may be accessed from multiple go-routines without synchronization. See the docs for Iterator[T] for notes on the concurrent use of iterators.

Example: var root *Tree[string, int] root = root.Update("Hello", 1).Update("World, 2).Update("Apple", 3).Update("Stuff", 4) root = root.Remove("Apple") iter := root.Iter() 

for iter.MoveNext() {
    fmt.Printf("%v == %v\n", iter.Current().Key(), iter.Current.Value())
}

func EmptyTree 

func EmptyTree[K constraints.Ordered, V any]() *Tree[K, V]

func (*Tree[K, V]) Contains added in v1.0.3 

func (n *Tree[K, V]) Contains(key K) bool

Contains returns true if the tree contains the key.

func (*Tree[K, V]) Delete 

func (n *Tree[K, V]) Delete(key K) *Tree[K, V]

Delete returns the root of a new tree with the entry for 'key' removed.

func (*Tree[K, V]) Find 

func (n *Tree[K, V]) Find(key K) V

Find returns the value associated with key in the tree. Will return a zero value if no such item exists.

func (*Tree[K, V]) FindOpt added in v1.0.3 

func (n *Tree[K, V]) FindOpt(key K) (V, bool)

FindOpt returns the value associated with key in the tree. Returns true if found; otherwise false. Zero value is returned when found is false.

func (*Tree[K, V]) GetKthElement added in v1.0.3 

func (n *Tree[K, V]) GetKthElement(k int) (p Pair[K, V], ok bool)

GetKthElement returns the k'th smallest element in a Tree. If no such element exists, ok will be false.

func (*Tree[K, V]) GreatestLowerBound 

func (n *Tree[K, V]) GreatestLowerBound(key K) (Pair[K, V], bool)

GreatestLowerBound returns the key-value-par for the largest node n such that n.Key() <= key. If there is no such node then boolean is false.

func (*Tree[K, V]) Height 

func (n *Tree[K, V]) Height() int

Height returns the height of the tree rooted at node n. Will return 0 if n is empty.

func (*Tree[K, V]) IsEmpty 

func (n *Tree[K, V]) IsEmpty() bool

IsEmpty returns true iif n is empty.

func (*Tree[K, V]) Iter 

func (n *Tree[K, V]) Iter() Iterator[Pair[K, V]]

Iter returns an in-order iterator for the tree.

func (*Tree[K, V]) IterGte 

func (n *Tree[K, V]) IterGte(glb K) Iterator[Pair[K, V]]

IterGte returns an in-order iterator for the tree for all nodes n such that n.Key() >= glb.

func (*Tree[K, V]) Key 

func (n *Tree[K, V]) Key() K

Key returns the key associated with the node n. If n is empty, the zero value for K is returned.

func (*Tree[K, V]) Least 

func (n *Tree[K, V]) Least() (Pair[K, V], bool)

Least returns the key-value-pair for the lowest element in the tree. If the tree is empty then boolean is false

func (*Tree[K, V]) LeastUpperBound 

func (n *Tree[K, V]) LeastUpperBound(key K) (Pair[K, V], bool)

LeastUpperBound returns the key-value-pair for the smallest node n such that n.Key() >= key. If there is no such node then boolean is false.

func (*Tree[K, V]) Left 

func (n *Tree[K, V]) Left() *Tree[K, V]

Left returns the left subtree of the current tree. Will never be nil. For empty nodes t.Left() == t. If you are using Left() and Right() to traverse a tree, make sure to use IsEmpty() as your termination condition.

func (*Tree[K, V]) MarshalJSON 

func (n *Tree[K, V]) MarshalJSON() ([]byte, error)

func (*Tree[K, V]) Most 

func (n *Tree[K, V]) Most() (Pair[K, V], bool)

Most returns the key-value-pair for the greatest element in the tree. If the tree is empty then boolean is false

func (*Tree[K, V]) Right 

func (n *Tree[K, V]) Right() *Tree[K, V]

Right returns the right subtree of the current tree. Will never be nil. For empty nodes t.Left() == t. If you are using Left() and Right() to traverse a tree, make sure to use IsEmpty() as your termination condition.

func (*Tree[K, V]) Size 

func (n *Tree[K, V]) Size() int

func (*Tree[K, V]) UnmarshalJSON 

func (n *Tree[K, V]) UnmarshalJSON(data []byte) error

func (*Tree[K, V]) Update 

func (n *Tree[K, V]) Update(key K, value V) *Tree[K, V]

Update returns the root of a new tree with the value for 'key' set to 'value'.

func (*Tree[K, V]) Value 

func (n *Tree[K, V]) Value() V

Value returns the value associated with the node n. If n is empty, the zero value for V is returned.

type TreeEx 

type TreeEx[K Ordered[K], V any] struct {
	// contains filtered or unexported fields
}

TreeEx implements a persistent AVL tree for keys implementing the Ordered[K] interface. For built-in ordered keys (types supporting <) see Tree[K,V],

Persistent AVL trees are immutable. Each mutating operation will return the root of a new tree with the requested update applied.The implementation uses structural sharing to make immutability efficient. For any given update at most O(log(N)) nodes will be replaced in the new tree. The implementation is concurrency safe and non-blocking. A *Tree[K,V] instance may be accessed from multiple go-routines without synchronization. See the docs for Iterator[T] for notes on the concurrent use of iterators.

TreeEx also supports json encoding / decoding. To unmarshal a json map into a TreeEx[K,V] the type K should support the encoding.TextUnmarshaler interface. To marshal json, the type K should support conversion to string.

func EmptyTreeEx 

func EmptyTreeEx[K Ordered[K], V any]() *TreeEx[K, V]

func (*TreeEx[K, V]) Contains added in v1.0.3 

func (n *TreeEx[K, V]) Contains(key K) bool

Contains returns true if the tree contains the key.

func (*TreeEx[K, V]) Delete 

func (n *TreeEx[K, V]) Delete(key K) *TreeEx[K, V]

Delete returns the root of a new tree with the entry for 'key' removed.

func (*TreeEx[K, V]) Find 

func (n *TreeEx[K, V]) Find(key K) V

Find returns the pair associated with key in the tree. Will return a zero value if no such item exists.

func (*TreeEx[K, V]) FindOpt added in v1.0.3 

func (n *TreeEx[K, V]) FindOpt(key K) (V, bool)

FindOpt returns the pair associated with key in the tree. Return true if found; otherwise false. Zero value is returned when found is false.

func (*TreeEx[K, V]) GetKthElement added in v1.0.3 

func (n *TreeEx[K, V]) GetKthElement(k int) (p Pair[K, V], ok bool)

GetKthElement returns the k'th smallest element in a Tree. If no such element exists, ok will be false.

func (*TreeEx[K, V]) GreatestLowerBound 

func (n *TreeEx[K, V]) GreatestLowerBound(key K) (Pair[K, V], bool)

GreatestLowerBound returns the key-value-par for the largest node n such that n.Key() <= key. If there is no such node then false is returned.

func (*TreeEx[K, V]) Height 

func (n *TreeEx[K, V]) Height() int

Height returns the height of the tree rooted at node n. Will return 0 if n is empty.

func (*TreeEx[K, V]) IsEmpty 

func (n *TreeEx[K, V]) IsEmpty() bool

IsEmpty returns true iif n is empty.

func (*TreeEx[K, V]) Iter 

func (n *TreeEx[K, V]) Iter() Iterator[Pair[K, V]]

Iter returns an in-order iterator for the tree.

func (*TreeEx[K, V]) IterGte 

func (n *TreeEx[K, V]) IterGte(glb K) Iterator[Pair[K, V]]

IterGte returns an in-order iterator for the tree for all nodes n such that n.Key() >= glb.

func (*TreeEx[K, V]) Key 

func (n *TreeEx[K, V]) Key() K

Key returns the key associated with the node n. If n is empty, the zero value for K is returned.

func (*TreeEx[K, V]) Least 

func (n *TreeEx[K, V]) Least() (Pair[K, V], bool)

Least returns the key-value-pair for the lowest element in the tree. If the tree is empty, then return false

func (*TreeEx[K, V]) LeastUpperBound 

func (n *TreeEx[K, V]) LeastUpperBound(key K) (Pair[K, V], bool)

LeastUpperBound returns the key-value-pair for the smallest node n such that n.Key() >= key. If there is no such node then false is returned.

func (*TreeEx[K, V]) Left 

func (n *TreeEx[K, V]) Left() *TreeEx[K, V]

Left returns the left subtree of the current tree. Will never be nil. For empty nodes t.Left() == t. If you are using Left() and Right() to traverse a tree, make sure to use IsEmpty() as your termination condition.

func (*TreeEx[K, V]) MarshalJSON 

func (n *TreeEx[K, V]) MarshalJSON() ([]byte, error)

func (*TreeEx[K, V]) Most 

func (n *TreeEx[K, V]) Most() (Pair[K, V], bool)

Most returns the key-value-pair for the greatest element in the tree. If the tree is empty, the returned pair is also empty

func (*TreeEx[K, V]) Right 

func (n *TreeEx[K, V]) Right() *TreeEx[K, V]

Right returns the right subtree of the current tree. Will never be nil. For empty nodes t.Left() == t. If you are using Left() and Right() to traverse a tree, make sure to use IsEmpty() as your termination condition.

func (*TreeEx[K, V]) Size 

func (n *TreeEx[K, V]) Size() int

func (*TreeEx[K, V]) UnmarshalJSON 

func (n *TreeEx[K, V]) UnmarshalJSON(data []byte) error

func (*TreeEx[K, V]) Update 

func (n *TreeEx[K, V]) Update(key K, value V) *TreeEx[K, V]

Update returns the root of a new tree with the value for 'key' set to 'value'.

func (*TreeEx[K, V]) Value 

func (n *TreeEx[K, V]) Value() V

Value returns the value associated with the node n. If n is empty, the zero value for V is returned.

type TreeExIterator 

type TreeExIterator[K Ordered[K], V any] struct {
	// contains filtered or unexported fields
}

TreeExIterator defines an iterator over a TreeEx

func (*TreeExIterator[K, V]) Current 

func (i *TreeExIterator[K, V]) Current() Pair[K, V]

func (*TreeExIterator[K, V]) Next 

func (i *TreeExIterator[K, V]) Next() bool

type TreeIterator 

type TreeIterator[K constraints.Ordered, V any] struct {
	// contains filtered or unexported fields
}

TreeIterator defines an iterator over a Tree

func (*TreeIterator[K, V]) Current 

func (i *TreeIterator[K, V]) Current() Pair[K, V]

func (*TreeIterator[K, V]) Next 

func (i *TreeIterator[K, V]) Next() bool

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.