ps

README

ps

Persistent data structures for Go. See the full package documentation

Install with

go get github.com/mndrix/ps

Documentation

Overview

Fully persistent data structures. A persistent data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not update the structure in-place, but instead always yield a new structure.

Persistent data structures typically share structure among themselves. This allows operations to avoid copying the entire data structure.

Index

• type List
  • func NewList() List
• type Map
  • func NewMap() Map

Types

type List

type List interface {
	// IsNil returns true if the list is empty
	IsNil() bool

	// Cons returns a new list with val as the head
	Cons(val interface{}) List

	// Head returns the first element of the list;
	// panics if the list is empty
	Head() interface{}

	// Tail returns a list with all elements except the head;
	// panics if the list is empty
	Tail() List

	// Size returns the list's length.  This takes O(1) time.
	Size() int

	// ForEach executes a callback for each value in the list.
	ForEach(f func(interface{}))

	// Reverse returns a list whose elements are in the opposite order as
	// the original list.
	Reverse() List
}

List is a persistent list of possibly heterogenous values.

func NewList

func NewList() List

NewList returns a new, empty list. The result is a singly linked list implementation. All lists share an empty tail, so allocating empty lists is efficient in time and memory.

type Map

type Map interface {
	// IsNil returns true if the Map is empty
	IsNil() bool

	// Set returns a new map in which key and value are associated.
	// If the key didn't exist before, it's created; otherwise, the
	// associated value is changed.
	// This operation is O(log N) in the number of keys.
	Set(key string, value interface{}) Map

	// UnsafeMutableSet returns the same map in which key and value are associated in-place.
	// If the key didn't exist before, it's created; otherwise, the
	// associated value is changed.
	// This operation is O(log N) in the number of keys.
	// Only use UnsafeMutableSet if you are the only reference-holder of the Map.
	UnsafeMutableSet(key string, value interface{}) Map

	// Delete returns a new map with the association for key, if any, removed.
	// This operation is O(log N) in the number of keys.
	Delete(key string) Map

	// Lookup returns the value associated with a key, if any.  If the key
	// exists, the second return value is true; otherwise, false.
	// This operation is O(log N) in the number of keys.
	Lookup(key string) (interface{}, bool)

	// Size returns the number of key value pairs in the map.
	// This takes O(1) time.
	Size() int

	// ForEach executes a callback on each key value pair in the map.
	ForEach(f func(key string, val interface{}))

	// Keys returns a slice with all keys in this map.
	// This operation is O(N) in the number of keys.
	Keys() []string

	String() string
}

A Map associates unique keys (type string) with values (type Any).

func NewMap

func NewMap() Map

NewMap allocates a new, persistent map from strings to values of any type. This is currently implemented as a path-copying binary tree.