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 Luhn(s string) (string, error)
- func LuhnAppend(n string) (string, error)
- func LuhnCheck(s string) bool
- func MaxInt(is ...int) int
- func MinInt(is ...int) int
- func NPIChecksum(s string) (string, error)
- func NPIChecksumAppend(s string) (string, error)
- func NPIChecksumCheck(s string) bool
- func VerifyMerkleProof(proof *MerkleProofNode, leaf, root []byte, h hash.Hash) bool
- type 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
- type MerkleProofNode
- type MerkleTree
Examples ¶
Constants ¶
This section is empty.
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 ¶
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.
Example ¶
h := "Happy Christmas" m := "Merry Christmas" l := Levenshtein(h, m) fmt.Println(l)
Output: 4
func Luhn ¶ added in v0.2.1
Luhn calculates the Luhn checksum of the given number using the Luhn algorithm: http://en.wikipedia.org/wiki/Luhn_algorithm. It should not have a checksum at the end of it.
func LuhnAppend ¶ added in v0.2.1
LuhnAppend appends the Luhn checksum to the given number.
func LuhnCheck ¶ added in v0.2.1
LuhnCheck verifies the checksum (the last digit) of the given number using the Luhn algorithm: http://en.wikipedia.org/wiki/Luhn_algorithm.
func MaxInt ¶
MaxInt returns the largest integer among all of the given integers. 0 is returned when no integers are given.
func MinInt ¶
MinInt returns the smallest integer among all of the given integers. 0 is returned when no integers are given.
func NPIChecksum ¶ added in v0.2.1
NPIChecksum returns the Luhn checksum for the given number. It differs from a normal Luhn in that if the number doesn't begin with 80840, 80840 will be prepended to the number for determining the checksum. It should not have a checksum at the end of it.
func NPIChecksumAppend ¶ added in v0.2.1
NPIChecksumAppend calculates the checksum for the given partial NPI and appends the checksum to it. If the number doesn't begin with 80840, 80840 will be prepended to it before determing the checksum, but won't be included in the result.
func NPIChecksumCheck ¶ added in v0.2.1
NPIChecksumCheck calculates and verifies the checksum using the Luhn algorithm. If the number doesn't begin with 80840, 80840 will be prepended to it before checking.
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 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 ¶
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 ¶
IntersectBitSets creates a new BitSet whose bits are set only if that bit is set in all of the given BitSets.
func UnionBitSets ¶
UnionBitSets creates a new BitSet with all the bits set from the given BitSets.
func (BitSet) Complement ¶
Complement returns the complement of the BitSet.
func (*BitSet) Difference ¶
Difference removes all of the set values in this BitSet that are in the given BitSet.
func (*BitSet) Intersect ¶
Intersect updates this BitSet to include only those values that are both in this BitSet and the given BitSet.
func (*BitSet) IsSetInt ¶
IsSetInt is a convienance function for using ints instead of uints. It is equivalient to bs.IsSet(uint(n)).
func (*BitSet) Set ¶
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 ¶
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 ¶
Union updates this BitSet to include all of the set values in the given BitSet.
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.
Example ¶
bf := NewBloomFilter(100, 5)
for _, s := range []string{"Dog", "Cat", "Mouse", "Elephant", "Lion"} {
bf.Add([]byte(s))
}
for _, s := range []string{"Dog", "Lion", "Nothing"} {
if bf.Exists([]byte(s)) {
fmt.Println(s, "found")
} else {
fmt.Println(s, "not found")
}
}
Output: Dog found Lion found Nothing not found
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.
Example ¶
// Make the tree.
data := [][]byte{
[]byte("cat"),
[]byte("dog"),
[]byte("mouse"),
[]byte("parrot"),
[]byte("hamster"),
[]byte("goat"),
}
h := sha256.New()
mt := NewMerkleTree(data, h)
// This is the hash of a parrot. Normally you'd get it some some
// external source.
parrotHash := []byte{
0x44, 0x88, 0xb8, 0xb8, 0x6b, 0x1a, 0xc0, 0x61, 0xdb, 0xe3,
0x72, 0x42, 0x29, 0x7e, 0x58, 0x27, 0xda, 0xd8, 0x89, 0x82,
0x3f, 0xd1, 0xa5, 0xac, 0xae, 0xd4, 0x3d, 0xec, 0x1, 0x8,
0xd0, 0x48,
}
// Verify the parrot hash.
p := mt.Proof(parrotHash)
if VerifyMerkleProof(p, parrotHash, mt.Root(), sha256.New()) {
fmt.Println("parrot verified")
}
Output: parrot verified
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.
Source Files