algo

README

algo

Various common computer science algorithms implemented in Go.

This library is still in its early stages and is likely to change dramatically over time.

Documentation

Overview

Package algo provides common computer science algorithms and data structures implemented in pure Go.

Index

• Variables
• func Levenshtein(s, t string) int
• func MaxInt(is ...int) int
• func MinInt(is ...int) int
• func VerifyMerkleProof(proof *MerkleProofNode, leaf, root []byte, h hash.Hash) bool
• type BitSet
  • func DifferenceBitSets(bss ...BitSet) BitSet
  • func IntersectBitSets(bss ...BitSet) BitSet
  • func NewBitSet(n uint) BitSet
  • func UnionBitSets(bss ...BitSet) BitSet
  • func (bs BitSet) Complement() BitSet
  • func (bs *BitSet) Difference(obs BitSet)
  • func (bs *BitSet) Intersect(obs BitSet)
  • func (bs *BitSet) IsSet(n uint) bool
  • func (bs *BitSet) IsSetInt(n int) bool
  • func (bs *BitSet) Set(n uint)
  • func (bs *BitSet) SetInt(n int)
  • func (bs *BitSet) Union(obs BitSet)
  • func (bs *BitSet) Unset(n uint)
  • func (bs *BitSet) UnsetInt(n int)
• type BloomFilter
  • func NewBloomFilter(m uint, k uint) *BloomFilter
  • func NewBloomFilterEstimate(n uint, p float64) *BloomFilter
  • func (bf *BloomFilter) Add(data []byte)
  • func (bf *BloomFilter) Exists(data []byte) bool
  • func (bf *BloomFilter) FalsePositives() float64
• type MerkleProofNode
• type MerkleTree
  • func NewMerkleTree(data [][]byte, h hash.Hash) MerkleTree
  • func NewMerkleTreeFromHashes(data [][]byte, h hash.Hash) MerkleTree
  • func (mt *MerkleTree) Proof(sum []byte) *MerkleProofNode
  • func (mt *MerkleTree) Root() []byte
  • func (mt *MerkleTree) Verify(sum []byte) bool

Examples

• BitSet

Variables

var (
	// ErrNotFound means that the operation was unable to find what you
	// were looking for.
	ErrNotFound = errors.New("not found")

	// ErrOutOfRange means that the operation was unable to to do what
	// you asked because the parameters for the request were outside of
	// the limits. You should check that you are working within the
	// right range specified by the method or function.
	ErrOutOfRange = errors.New("out of range")

	// ErrWrongType means that the wrong type was given. This usually
	// occurs when an interface{} is being converted and the type isn't
	// what was needed.
	ErrWrongType = errors.New("wrong type")

	// ErrNotImplemented means that the operation is not implemented.
	ErrNotImplemented = errors.New("not implemented")

	// ErrInvalidParams means that you gave the function something
	// unexpected.
	ErrInvalidParams = errors.New("invalid params")
)

Functions

func Levenshtein

func Levenshtein(s, t string) int

Levenshtein calculates the levenshtein distance between the two given strings. For more information on what a levenshtein distance is, see: http://en.wikipedia.org/wiki/Levenshtein_distance.

func MaxInt

func MaxInt(is ...int) int

MaxInt returns the largest integer among all of the given integers. 0 is returned when no integers are given.

func MinInt

func MinInt(is ...int) int

MinInt returns the smallest integer among all of the given integers. 0 is returned when no integers are given.

func VerifyMerkleProof

func VerifyMerkleProof(proof *MerkleProofNode, leaf, root []byte, h hash.Hash) bool

VerifyMerkleProof uses the given proof to verify that the lineage given is valid. In order for the proof to succeed the leaf of the proof must be equal to the given leaf, the hashes up the proof must be align with the hashes built with the given hash, and the resulting root of the proof must be equal to the given root.

Types

type BitSet

type BitSet []int

BitSet is a set of bit that can be turned on/off. They are commonly used for space effeciency in data structures like bloom filters.

Example

bs := NewBitSet(256)
bs.Set(uint(124))
bs.SetInt(145)
bs.SetInt(512)
for x := -1; x <= 1024; x++ {
	if bs.IsSetInt(x) {
		fmt.Println(x)
	}
}

Output:

124
145
512

func DifferenceBitSets

func DifferenceBitSets(bss ...BitSet) BitSet

DifferenceBitSets creates a new BitSet whose bits are set only if they are in the first BitSet but in none of the rest of the BitSets. For example, if the given sets are A, B, and C, then this returns a new BitSet that is equivalent to A - B - C which in set theory translates to ((A - B) - C) or A - (B union C).

func IntersectBitSets

func IntersectBitSets(bss ...BitSet) BitSet

IntersectBitSets creates a new BitSet whose bits are set only if that bit is set in all of the given BitSets.

func NewBitSet

func NewBitSet(n uint) BitSet

NewBitSet creates a BitSize of size n bits.

func UnionBitSets

func UnionBitSets(bss ...BitSet) BitSet

UnionBitSets creates a new BitSet with all the bits set from the given BitSets.

func (BitSet) Complement

func (bs BitSet) Complement() BitSet

Complement returns the complement of the BitSet.

func (*BitSet) Difference

func (bs *BitSet) Difference(obs BitSet)

Difference removes all of the set values in this BitSet that are in the given BitSet.

func (*BitSet) Intersect

func (bs *BitSet) Intersect(obs BitSet)

Intersect updates this BitSet to include only those values that are both in this BitSet and the given BitSet.

func (*BitSet) IsSet

func (bs *BitSet) IsSet(n uint) bool

IsSet returns true if n has been Set(), false otherwise.

func (*BitSet) IsSetInt

func (bs *BitSet) IsSetInt(n int) bool

IsSetInt is a convienance function for using ints instead of uints. It is equivalient to bs.IsSet(uint(n)).

func (*BitSet) Set

func (bs *BitSet) Set(n uint)

Set turns on the given bit in this BitSet. More space is allocated to the BitSet if n is larger than the current size of this BitSet.

func (*BitSet) SetInt

func (bs *BitSet) SetInt(n int)

SetInt is a convienance function for using ints instead of uints. It is equivalient to bs.Set(uint(n)). Set is a noop if n < 0.

func (*BitSet) Union

func (bs *BitSet) Union(obs BitSet)

Union updates this BitSet to include all of the set values in the given BitSet.

func (*BitSet) Unset

func (bs *BitSet) Unset(n uint)

Unset clears the bit at n such that a call to IsSet(n) will return false.

func (*BitSet) UnsetInt

func (bs *BitSet) UnsetInt(n int)

UnsetInt is a convienance function for using ints instead of uints. It is equivalient to bs.Unset(uint(n)). Set is a noop if n < 0.

type BloomFilter

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

BloomFilter is a representation of the bloom filter data structure. You create one by calling NewBloomFilter or NewBloomFilterEstimate.

func NewBloomFilter

func NewBloomFilter(m uint, k uint) *BloomFilter

NewBloomFilter creates a bloom filter of size m and with k hashes. For more details on what that means, see: http://en.wikipedia.org/wiki/Bloom_filter.

func NewBloomFilterEstimate

func NewBloomFilterEstimate(n uint, p float64) *BloomFilter

NewBloomFilterEstimate creates a bloom filter with a size and number of hashes based on the given estimated number of values being added and the desired false positive rate. You should choose your false positive rate carefully based on your data set and needs. The space efficiency grows quickly the smaller your failure rate.

func (*BloomFilter) Add

func (bf *BloomFilter) Add(data []byte)

Add inserts the given value into the Bloom filter. Calls to Exists(data) will now always return true.

func (*BloomFilter) Exists

func (bf *BloomFilter) Exists(data []byte) bool

Exists determines if the given value is likely in the bloom filter. There is a possibility that, based on the number of values added and the size of the bloom filter, Add(data) was never called.

func (*BloomFilter) FalsePositives

func (bf *BloomFilter) FalsePositives() float64

FalsePositives estimates the false positive rate of this bloom filter based on the formula found at http://en.wikipedia.org/wiki/Bloom_filter#Probability_of_false_positives.

type MerkleProofNode

type MerkleProofNode struct {
	Sum          []byte
	Sibling      *MerkleProofNode
	Parent       *MerkleProofNode
	SiblingFirst bool // True if the sibling is the left childe of the

}

MerkleProofNode represents a node in a merkle tree that is used when proving membership of a leaf node.

type MerkleTree

type MerkleTree [][]byte

MerkleTree is an implementation of a Merkle tree (see: http://en.wikipedia.org/wiki/Merkle_tree). You create it with the NewMerkleTree* functions.

func NewMerkleTree

func NewMerkleTree(data [][]byte, h hash.Hash) MerkleTree

NewMerkleTree creates a Merkle tree from the given data using the given hash.

func NewMerkleTreeFromHashes

func NewMerkleTreeFromHashes(data [][]byte, h hash.Hash) MerkleTree

NewMerkleTreeFromHashes creates a Merkle tree from the given hashes of data. This is a shortcut if the hashes of the data is already known so they won't need to be recreated. The same hash used to hash the data should be given.

func (*MerkleTree) Proof

func (mt *MerkleTree) Proof(sum []byte) *MerkleProofNode

Proof returns a proof for the given leaf node. If sum is not a leaf node, nil is returned. Otherwise, the lineage of that leaf to the root node is returned.

func (*MerkleTree) Root

func (mt *MerkleTree) Root() []byte

Root returns the root of this MerkleTree.

func (*MerkleTree) Verify

func (mt *MerkleTree) Verify(sum []byte) bool

Verify verifies the given hash value against the root of this Merkle tree.