persistent

Documentation

Overview

The persistent package defines various persistent data structures; that is, data structures that can be efficiently copied and modified in sublinear time.

Index

• type Map
  • func (pm *Map[K, V]) Clear()
  • func (pm *Map[K, V]) Clone() *Map[K, V]
  • func (pm *Map[K, V]) Delete(key K) bool
  • func (pm *Map[K, V]) Destroy()
  • func (pm *Map[K, V]) Get(key K) (V, bool)
  • func (pm *Map[K, V]) Keys() []K
  • func (pm *Map[K, V]) Range(f func(key K, value V))
  • func (pm *Map[K, V]) Set(key K, value V, release func(key, value any))
  • func (pm *Map[K, V]) SetAll(other *Map[K, V])
  • func (m *Map[K, V]) String() string
• type Set
  • func (s *Set[K]) Add(key K)
  • func (s *Set[K]) AddAll(other *Set[K])
  • func (s *Set[K]) Clone() *Set[K]
  • func (s *Set[K]) Contains(key K) bool
  • func (s *Set[K]) Destroy()
  • func (s *Set[K]) Range(f func(key K))
  • func (s *Set[K]) Remove(key K)

Types

type Map

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

Map is an associative mapping from keys to values.

Maps can be Cloned in constant time. Get, Set, and Delete operations are done on average in logarithmic time. Maps can be merged (via SetAll) in O(m log(n/m)) time for maps of size n and m, where m < n.

Values are reference counted, and a client-supplied release function is called when a value is no longer referenced by a map or any clone.

Internally the implementation is based on a randomized persistent treap: https://en.wikipedia.org/wiki/Treap.

The zero value is ready to use.

func (*Map[K, V]) Clear

func (pm *Map[K, V]) Clear()

Clear removes all entries from the map.

func (*Map[K, V]) Clone

func (pm *Map[K, V]) Clone() *Map[K, V]

Clone returns a copy of the given map. It is a responsibility of the caller to Destroy it at later time.

func (*Map[K, V]) Delete

func (pm *Map[K, V]) Delete(key K) bool

Delete deletes the value for a key.

The result reports whether the key was present in the map.

func (*Map[K, V]) Destroy

func (pm *Map[K, V]) Destroy()

Destroy destroys the map.

After Destroy, the Map should not be used again.

func (*Map[K, V]) Get

func (pm *Map[K, V]) Get(key K) (V, bool)

Get returns the map value associated with the specified key. The ok result indicates whether an entry was found in the map.

func (*Map[K, V]) Keys

func (pm *Map[K, V]) Keys() []K

Keys returns all keys present in the map.

func (*Map[K, V]) Range

func (pm *Map[K, V]) Range(f func(key K, value V))

Range calls f sequentially in ascending key order for all entries in the map.

func (*Map[K, V]) Set

func (pm *Map[K, V]) Set(key K, value V, release func(key, value any))

Set updates the value associated with the specified key. If release is non-nil, it will be called with entry's key and value once the key is no longer contained in the map or any clone.

func (*Map[K, V]) SetAll

func (pm *Map[K, V]) SetAll(other *Map[K, V])

SetAll updates the map with key/value pairs from the other map, overwriting existing keys. It is equivalent to calling Set for each entry in the other map but is more efficient.

func (*Map[K, V]) String

func (m *Map[K, V]) String() string

type Set

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

Set is a collection of elements of type K.

It uses immutable data structures internally, so that sets can be cloned in constant time.

The zero value is a valid empty set.

func (*Set[K]) Add

func (s *Set[K]) Add(key K)

Add adds an element to the set.

func (*Set[K]) AddAll

func (s *Set[K]) AddAll(other *Set[K])

AddAll adds all elements from other to the receiver set.

func (*Set[K]) Clone

func (s *Set[K]) Clone() *Set[K]

Clone creates a copy of the receiver.

func (*Set[K]) Contains

func (s *Set[K]) Contains(key K) bool

Contains reports whether s contains the given key.

func (*Set[K]) Destroy

func (s *Set[K]) Destroy()

Destroy destroys the set.

After Destroy, the Set should not be used again.

func (*Set[K]) Range

func (s *Set[K]) Range(f func(key K))

Range calls f sequentially in ascending key order for all entries in the set.

func (*Set[K]) Remove

func (s *Set[K]) Remove(key K)

Remove removes an element from the set.