hamt

README

hamt

Immutable and Memory Efficient Maps and Sets in Go.

This package hamt provides immutable collection types of maps (associative arrays) and sets implemented as Hash-Array Mapped Tries (HAMTs). All operations of the collections, such as insert and delete, are immutable and create new ones keeping original ones unmodified.

Hash-Array Mapped Trie (HAMT) is a data structure popular as a map (a.k.a. associative array or dictionary) or set. Its immutable variant is adopted widely by functional programming languages like Scala and Clojure to implement immutable and memory-efficient associative arrays and sets.

Installation

go get github.com/raviqqe/hamt

Documentation

GoDoc

Technical notes

The implementation canonicalizes tree structures of HAMTs by eliminating intermediate nodes during delete operations as described in the CHAMP paper.

References

• Ideal Hash Trees
• Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections

License

The Unlicense

Documentation

Overview

Package hamt provides immutable collection types of maps (associative arrays) and sets implemented as Hash-Array Mapped Tries (HAMTs). All operations of the collections, such as insert and delete, are immutable and create new ones keeping original ones unmodified.

Index

• type Entry
• type Map
  • func NewMap() Map
  • func (m Map) Delete(k Entry) Map
  • func (m Map) Find(k Entry) interface{}
  • func (m Map) FirstRest() (Entry, interface{}, Map)
  • func (m Map) ForEach(cb func(Entry, interface{}) error) error
  • func (m Map) Include(k Entry) bool
  • func (m Map) Insert(k Entry, v interface{}) Map
  • func (m Map) Merge(n Map) Map
  • func (m Map) Size() int
• type Set
  • func NewSet() Set
  • func (s Set) Delete(e Entry) Set
  • func (s Set) FirstRest() (Entry, Set)
  • func (s Set) ForEach(cb func(Entry) error) error
  • func (s Set) Include(e Entry) bool
  • func (s Set) Insert(e Entry) Set
  • func (s Set) Merge(t Set) Set
  • func (s Set) Size() int

Types

type Entry

type Entry interface {
	Hash() uint32
	Equal(Entry) bool
}

Entry represents an entry in a collection.

type Map

type Map struct {
	// contains filtered or unexported fields
}

Map represents a map (associative array).

func NewMap

func NewMap() Map

NewMap creates a new map.

func (Map) Delete

func (m Map) Delete(k Entry) Map

Delete deletes a pair of a key and a value from a map.

func (Map) Find

func (m Map) Find(k Entry) interface{}

Find finds a value corresponding to a given key from a map. It returns nil if no value is found.

func (Map) FirstRest

func (m Map) FirstRest() (Entry, interface{}, Map)

FirstRest returns a key-value pair in a map and a rest of the map. This method is useful for iteration. The key and value would be nil if the map is empty.

func (Map) ForEach

func (m Map) ForEach(cb func(Entry, interface{}) error) error

func (Map) Include

func (m Map) Include(k Entry) bool

Include returns true if a key-value pair corresponding with a given key is included in a map, or false otherwise.

func (Map) Insert

func (m Map) Insert(k Entry, v interface{}) Map

Insert inserts a key-value pair into a map.

func (Map) Merge

func (m Map) Merge(n Map) Map

Merge merges 2 maps into one.

func (Map) Size

func (m Map) Size() int

Size returns a size of a map.

type Set

type Set struct {
	// contains filtered or unexported fields
}

Set represents a set.

func NewSet

func NewSet() Set

NewSet creates a new set.

func (Set) Delete

func (s Set) Delete(e Entry) Set

Delete deletes a value from a set.

func (Set) FirstRest

func (s Set) FirstRest() (Entry, Set)

FirstRest returns a value in a set and a rest of the set. This method is useful for iteration.

func (Set) ForEach

func (s Set) ForEach(cb func(Entry) error) error

func (Set) Include

func (s Set) Include(e Entry) bool

Include returns true if a given entry is included in a set, or false otherwise.

func (Set) Insert

func (s Set) Insert(e Entry) Set

Insert inserts a value into a set.

func (Set) Merge

func (s Set) Merge(t Set) Set

Merge merges 2 sets into one.

func (Set) Size

func (s Set) Size() int

Size returns a size of a set.