ids

package
v1.9.0 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Oct 3, 2022 License: BSD-3-Clause Imports: 16 Imported by: 7

Documentation

Index

Constants

View Source
const BitsPerByte = 8

BitsPerByte is the number of bits per byte

View Source
const NodeIDPrefix = "NodeID-"
View Source
const NumBits = 256

NumBits is the number of bits this patricia tree manages

Variables

View Source
var (
	// Empty is a useful all zero value
	Empty = ID{}
)
View Source
var EmptyNodeID = NodeID{}
View Source
var ShortEmpty = ShortID{}

ShortEmpty is a useful all zero value

Functions

func AliaserAliasClashTest

func AliaserAliasClashTest(require *require.Assertions, r AliaserReader, w AliaserWriter)

func AliaserAliasesEmptyTest

func AliaserAliasesEmptyTest(require *require.Assertions, r AliaserReader, w AliaserWriter)

func AliaserAliasesTest

func AliaserAliasesTest(require *require.Assertions, r AliaserReader, w AliaserWriter)

func AliaserLookupErrorTest

func AliaserLookupErrorTest(require *require.Assertions, r AliaserReader, w AliaserWriter)

func AliaserLookupTest

func AliaserLookupTest(require *require.Assertions, r AliaserReader, w AliaserWriter)

func AliaserPrimaryAliasTest

func AliaserPrimaryAliasTest(require *require.Assertions, r AliaserReader, w AliaserWriter)

func AliaserRemoveAliasTest

func AliaserRemoveAliasTest(require *require.Assertions, r AliaserReader, w AliaserWriter)

func EqualSubset

func EqualSubset(start, stop int, id1, id2 ID) bool

EqualSubset takes in two indices and two ids and returns if the ids are equal from bit start to bit end (non-inclusive). Bit indices are defined as: [7 6 5 4 3 2 1 0] [15 14 13 12 11 10 9 8] ... [255 254 253 252 251 250 249 248] Where index 7 is the MSB of byte 0.

func Equals

func Equals(a, b []ID) bool

Equals returns true if the arrays are equal

func FirstDifferenceSubset

func FirstDifferenceSubset(start, stop int, id1, id2 ID) (int, bool)

FirstDifferenceSubset takes in two indices and two ids and returns the index of the first difference between the ids inside bit start to bit end (non-inclusive). Bit indices are defined above

func GetRelevantAliases

func GetRelevantAliases(aliaser Aliaser, ids []ID) (map[ID][]string, error)

GetRelevantAliases returns the aliases with the redundant identity alias removed (each id is aliased to at least itself).

func IsSortedAndUniqueIDs

func IsSortedAndUniqueIDs(ids []ID) bool

IsSortedAndUniqueIDs returns true if the ids are sorted and unique

func IsSortedAndUniqueShortIDs

func IsSortedAndUniqueShortIDs(ids []ShortID) bool

IsSortedAndUniqueShortIDs returns true if the ids are sorted and unique

func IsUniqueShortIDs

func IsUniqueShortIDs(ids []ShortID) bool

IsUniqueShortIDs returns true iff ids are unique

func ShortIDsToStrings

func ShortIDsToStrings(ids []ShortID) []string

ShortIDsToStrings converts an array of shortIDs to an array of their string representations

func SortIDs

func SortIDs(ids []ID)

SortIDs sorts the ids lexicographically

func SortNodeIDs

func SortNodeIDs(nodeIDs []NodeID)

SortNodeIDs sorts the node IDs lexicographically

func SortShortIDs

func SortShortIDs(ids []ShortID)

SortShortIDs sorts the ids lexicographically

func UnsortedEquals

func UnsortedEquals(a, b []ID) bool

UnsortedEquals returns true if the have the same number of each ID

Types

type Aliaser

type Aliaser interface {
	AliaserReader
	AliaserWriter
	PrimaryAliasOrDefault(id ID) string
}

Aliaser allows one to give an ID aliases and lookup the aliases given to an ID.

func NewAliaser

func NewAliaser() Aliaser

type AliaserReader

type AliaserReader interface {
	Lookup(alias string) (ID, error)
	PrimaryAlias(id ID) (string, error)
	Aliases(id ID) ([]string, error)
}

AliaserReader allows one to lookup the aliases given to an ID.

type AliaserWriter

type AliaserWriter interface {
	Alias(id ID, alias string) error
	RemoveAliases(id ID)
}

Aliaser allows one to give an ID aliases. An ID can have arbitrarily many aliases; two IDs may not have the same alias.

type Bag

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

Bag is a multiset of IDs.

A bag has the ability to split and filter on its bits for ease of use for binary voting.

func (*Bag) Add

func (b *Bag) Add(ids ...ID)

Add increases the number of times each id has been seen by one.

func (*Bag) AddCount

func (b *Bag) AddCount(id ID, count int)

AddCount increases the number of times the id has been seen by count.

count must be >= 0

func (*Bag) Count

func (b *Bag) Count(id ID) int

Count returns the number of times the id has been added.

func (*Bag) Equals

func (b *Bag) Equals(oIDs Bag) bool

Equals returns true if the bags contain the same elements

func (*Bag) Filter

func (b *Bag) Filter(start, end int, id ID) Bag

Filter returns the bag of ids with the same counts as this bag, except all the ids in the returned bag must have the same bits in the range [start, end) as id.

func (*Bag) Len

func (b *Bag) Len() int

Len returns the number of times an id has been added.

func (*Bag) List

func (b *Bag) List() []ID

List returns a list of all ids that have been added.

func (*Bag) Mode

func (b *Bag) Mode() (ID, int)

Mode returns the id that has been seen the most and the number of times it has been seen. Ties are broken by the first id to be seen the reported number of times.

func (*Bag) PrefixedString

func (b *Bag) PrefixedString(prefix string) string

func (*Bag) SetThreshold

func (b *Bag) SetThreshold(threshold int)

SetThreshold sets the number of times an ID must be added to be contained in the threshold set.

func (*Bag) Split

func (b *Bag) Split(index uint) [2]Bag

Split returns the bags of ids with the same counts a this bag, except all ids in the 0th index have a 0 at bit [index], and all ids in the 1st index have a 1 at bit [index].

func (*Bag) String

func (b *Bag) String() string

func (*Bag) Threshold

func (b *Bag) Threshold() Set

Threshold returns the ids that have been seen at least threshold times.

type BitSet64

type BitSet64 uint64

BitSet64 is a set that can contain uints in the range [0, 64). All functions are O(1). The zero value is the empty set.

func (*BitSet64) Add

func (bs *BitSet64) Add(i uint)

Add [i] to the set of ints

func (*BitSet64) Clear

func (bs *BitSet64) Clear()

Clear removes all elements from this set

func (BitSet64) Contains

func (bs BitSet64) Contains(i uint) bool

Contains returns true if [i] was previously added to this set

func (*BitSet64) Difference

func (bs *BitSet64) Difference(s BitSet64)

Difference removes all the elements in [s] from this set

func (*BitSet64) Intersection

func (bs *BitSet64) Intersection(s BitSet64)

Intersection takes the intersection of [s] with this set

func (BitSet64) Len

func (bs BitSet64) Len() int

Len returns the number of elements in this set

func (*BitSet64) Remove

func (bs *BitSet64) Remove(i uint)

Remove [i] from the set of ints

func (BitSet64) String

func (bs BitSet64) String() string

func (*BitSet64) Union

func (bs *BitSet64) Union(s BitSet64)

Union adds all the elements in [s] to this set

type ID

type ID [32]byte

ID wraps a 32 byte hash used as an identifier

func FromString

func FromString(idStr string) (ID, error)

FromString is the inverse of ID.String()

func GenerateTestID

func GenerateTestID() ID

GenerateTestID returns a new ID that should only be used for testing

func ToID

func ToID(bytes []byte) (ID, error)

ToID attempt to convert a byte slice into an id

func (ID) Bit

func (id ID) Bit(i uint) int

Bit returns the bit value at the ith index of the byte array. Returns 0 or 1

func (ID) Hex

func (id ID) Hex() string

Hex returns a hex encoded string of this id.

func (ID) MarshalJSON

func (id ID) MarshalJSON() ([]byte, error)

func (ID) MarshalText

func (id ID) MarshalText() ([]byte, error)

func (ID) Prefix

func (id ID) Prefix(prefixes ...uint64) ID

Prefix this id to create a more selective id. This can be used to store multiple values under the same key. For example: prefix1(id) -> confidence prefix2(id) -> vertex This will return a new id and not modify the original id.

func (ID) String

func (id ID) String() string

func (*ID) UnmarshalJSON

func (id *ID) UnmarshalJSON(b []byte) error

func (*ID) UnmarshalText

func (id *ID) UnmarshalText(text []byte) error

type NodeID

type NodeID ShortID

func GenerateTestNodeID

func GenerateTestNodeID() NodeID

GenerateTestNodeID returns a new ID that should only be used for testing

func NodeIDFromCert

func NodeIDFromCert(cert *x509.Certificate) NodeID

func NodeIDFromString

func NodeIDFromString(nodeIDStr string) (NodeID, error)

NodeIDFromString is the inverse of NodeID.String()

func ToNodeID

func ToNodeID(bytes []byte) (NodeID, error)

ToNodeID attempt to convert a byte slice into a node id

func (NodeID) Bytes

func (id NodeID) Bytes() []byte

func (NodeID) MarshalJSON

func (id NodeID) MarshalJSON() ([]byte, error)

func (NodeID) MarshalText

func (id NodeID) MarshalText() ([]byte, error)

func (NodeID) String

func (id NodeID) String() string

func (*NodeID) UnmarshalJSON

func (id *NodeID) UnmarshalJSON(b []byte) error

func (*NodeID) UnmarshalText

func (id *NodeID) UnmarshalText(text []byte) error

type NodeIDBag

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

NodeIDBag is a multiset of NodeIDs.

func (*NodeIDBag) Add

func (b *NodeIDBag) Add(ids ...NodeID)

Add increases the number of times each id has been seen by one.

func (*NodeIDBag) AddCount

func (b *NodeIDBag) AddCount(id NodeID, count int)

AddCount increases the nubmer of times the id has been seen by count.

count must be >= 0

func (*NodeIDBag) Count

func (b *NodeIDBag) Count(id NodeID) int

Count returns the number of times the id has been added.

func (*NodeIDBag) Equals

func (b *NodeIDBag) Equals(oIDs NodeIDBag) bool

Equals returns true if the bags contain the same elements

func (*NodeIDBag) Len

func (b *NodeIDBag) Len() int

Len returns the number of times an id has been added.

func (*NodeIDBag) List

func (b *NodeIDBag) List() []NodeID

List returns a list of all IDs that have been added, without duplicates. e.g. a bag with {ID1, ID1, ID2} returns ids.ShortID[]{ID1, ID2}

func (*NodeIDBag) PrefixedString

func (b *NodeIDBag) PrefixedString(prefix string) string

func (*NodeIDBag) Remove

func (b *NodeIDBag) Remove(id NodeID)

Remove sets the count of the provided ID to zero.

func (*NodeIDBag) String

func (b *NodeIDBag) String() string

type NodeIDSet

type NodeIDSet map[NodeID]struct{}

NodeIDSet is a set of NodeIDs

func NewNodeIDSet

func NewNodeIDSet(size int) NodeIDSet

Return a new NodeIDSet with initial capacity [size]. More or less than [size] elements can be added to this set. Using NewNodeIDSet() rather than ids.NodeIDSet{} is just an optimization that can be used if you know how many elements will be put in this set.

func (*NodeIDSet) Add

func (ids *NodeIDSet) Add(idList ...NodeID)

Add all the ids to this set, if the id is already in the set, nothing happens

func (NodeIDSet) CappedList

func (ids NodeIDSet) CappedList(size int) []NodeID

CappedList returns a list of length at most [size]. Size should be >= 0. If size < 0, returns nil.

func (*NodeIDSet) Clear

func (ids *NodeIDSet) Clear()

Clear empties this set

func (*NodeIDSet) Contains

func (ids *NodeIDSet) Contains(id NodeID) bool

Contains returns true if the set contains this id, false otherwise

func (*NodeIDSet) Difference

func (ids *NodeIDSet) Difference(idSet NodeIDSet)

Difference removes all the ids from the provided set to this set.

func (NodeIDSet) Equals

func (ids NodeIDSet) Equals(oIDs NodeIDSet) bool

Equals returns true if the sets contain the same elements

func (NodeIDSet) Len

func (ids NodeIDSet) Len() int

Len returns the number of ids in this set

func (NodeIDSet) List

func (ids NodeIDSet) List() []NodeID

List converts this set into a list

func (*NodeIDSet) Peek

func (ids *NodeIDSet) Peek() (NodeID, bool)

Returns an element. If the set is empty, returns false

func (*NodeIDSet) Pop

func (ids *NodeIDSet) Pop() (NodeID, bool)

Removes and returns an element. If the set is empty, does nothing and returns false

func (*NodeIDSet) Remove

func (ids *NodeIDSet) Remove(idList ...NodeID)

Remove all the id from this set, if the id isn't in the set, nothing happens

func (NodeIDSet) SortedList

func (ids NodeIDSet) SortedList() []NodeID

SortedList returns this set as a sorted list

func (NodeIDSet) String

func (ids NodeIDSet) String() string

String returns the string representation of a set

func (*NodeIDSet) Union

func (ids *NodeIDSet) Union(idSet NodeIDSet)

Union adds all the ids from the provided set to this set.

type Set

type Set map[ID]struct{}

Set is a set of IDs

func NewSet

func NewSet(size int) Set

Return a new set with initial capacity [size]. More or less than [size] elements can be added to this set. Using NewSet() rather than ids.Set{} is just an optimization that can be used if you know how many elements will be put in this set.

func (*Set) Add

func (ids *Set) Add(idList ...ID)

Add all the ids to this set, if the id is already in the set, nothing happens

func (Set) CappedList

func (ids Set) CappedList(size int) []ID

CappedList returns a list of length at most [size]. Size should be >= 0. If size < 0, returns nil.

func (*Set) Clear

func (ids *Set) Clear()

Clear empties this set

func (*Set) Contains

func (ids *Set) Contains(id ID) bool

Contains returns true if the set contains this id, false otherwise

func (*Set) Difference

func (ids *Set) Difference(set Set)

Difference removes all the ids from the provided set to this set.

func (Set) Equals

func (ids Set) Equals(oIDs Set) bool

Equals returns true if the sets contain the same elements

func (Set) Len

func (ids Set) Len() int

Len returns the number of ids in this set

func (Set) List

func (ids Set) List() []ID

List converts this set into a list

func (*Set) MarshalJSON

func (ids *Set) MarshalJSON() ([]byte, error)

func (*Set) Overlaps

func (ids *Set) Overlaps(big Set) bool

Overlaps returns true if the intersection of the set is non-empty

func (*Set) Pop

func (ids *Set) Pop() (ID, bool)

Removes and returns an element. If the set is empty, does nothing and returns false.

func (*Set) Remove

func (ids *Set) Remove(idList ...ID)

Remove all the id from this set, if the id isn't in the set, nothing happens

func (Set) SortedList

func (ids Set) SortedList() []ID

SortedList returns this set as a sorted list

func (Set) String

func (ids Set) String() string

String returns the string representation of a set

func (*Set) Union

func (ids *Set) Union(set Set)

Union adds all the ids from the provided set to this set.

type ShortID

type ShortID [20]byte

ShortID wraps a 20 byte hash as an identifier

func GenerateTestShortID

func GenerateTestShortID() ShortID

GenerateTestShortID returns a new ID that should only be used for testing

func ShortFromPrefixedString

func ShortFromPrefixedString(idStr, prefix string) (ShortID, error)

ShortFromPrefixedString returns a ShortID assuming the cb58 format is prefixed

func ShortFromString

func ShortFromString(idStr string) (ShortID, error)

ShortFromString is the inverse of ShortID.String()

func ToShortID

func ToShortID(bytes []byte) (ShortID, error)

ToShortID attempt to convert a byte slice into an id

func (ShortID) Bytes

func (id ShortID) Bytes() []byte

Bytes returns the 20 byte hash as a slice. It is assumed this slice is not modified.

func (ShortID) Hex

func (id ShortID) Hex() string

Hex returns a hex encoded string of this id.

func (ShortID) MarshalJSON

func (id ShortID) MarshalJSON() ([]byte, error)

func (ShortID) MarshalText

func (id ShortID) MarshalText() ([]byte, error)

func (ShortID) PrefixedString

func (id ShortID) PrefixedString(prefix string) string

PrefixedString returns the String representation with a prefix added

func (ShortID) String

func (id ShortID) String() string

func (*ShortID) UnmarshalJSON

func (id *ShortID) UnmarshalJSON(b []byte) error

func (*ShortID) UnmarshalText

func (id *ShortID) UnmarshalText(text []byte) error

type ShortSet

type ShortSet map[ShortID]struct{}

ShortSet is a set of ShortIDs

func NewShortSet

func NewShortSet(size int) ShortSet

Return a new ShortSet with initial capacity [size]. More or less than [size] elements can be added to this set. Using NewShortSet() rather than ids.ShortSet{} is just an optimization that can be used if you know how many elements will be put in this set.

func (*ShortSet) Add

func (ids *ShortSet) Add(idList ...ShortID)

Add all the ids to this set, if the id is already in the set, nothing happens

func (ShortSet) CappedList

func (ids ShortSet) CappedList(size int) []ShortID

CappedList returns a list of length at most [size]. Size should be >= 0. If size < 0, returns nil.

func (*ShortSet) Clear

func (ids *ShortSet) Clear()

Clear empties this set

func (*ShortSet) Contains

func (ids *ShortSet) Contains(id ShortID) bool

Contains returns true if the set contains this id, false otherwise

func (*ShortSet) Difference

func (ids *ShortSet) Difference(idSet ShortSet)

Difference removes all the ids from the provided set to this set.

func (ShortSet) Equals

func (ids ShortSet) Equals(oIDs ShortSet) bool

Equals returns true if the sets contain the same elements

func (ShortSet) Len

func (ids ShortSet) Len() int

Len returns the number of ids in this set

func (ShortSet) List

func (ids ShortSet) List() []ShortID

List converts this set into a list

func (*ShortSet) Peek

func (ids *ShortSet) Peek() (ShortID, bool)

Returns an element. If the set is empty, returns false

func (*ShortSet) Pop

func (ids *ShortSet) Pop() (ShortID, bool)

Removes and returns an element. If the set is empty, does nothing and returns false

func (*ShortSet) Remove

func (ids *ShortSet) Remove(idList ...ShortID)

Remove all the id from this set, if the id isn't in the set, nothing happens

func (ShortSet) SortedList

func (ids ShortSet) SortedList() []ShortID

SortedList returns this set as a sorted list

func (ShortSet) String

func (ids ShortSet) String() string

String returns the string representation of a set

func (*ShortSet) Union

func (ids *ShortSet) Union(idSet ShortSet)

Union adds all the ids from the provided set to this set.

type SliceStringer

type SliceStringer []ID

func (SliceStringer) String

func (s SliceStringer) String() string

type UniqueBag

type UniqueBag map[ID]BitSet64

func (*UniqueBag) Add

func (b *UniqueBag) Add(setID uint, idSet ...ID)

func (*UniqueBag) Bag

func (b *UniqueBag) Bag(alpha int) Bag

func (*UniqueBag) Clear

func (b *UniqueBag) Clear()

func (*UniqueBag) Difference

func (b *UniqueBag) Difference(diff *UniqueBag)

func (*UniqueBag) DifferenceSet

func (b *UniqueBag) DifferenceSet(id ID, set BitSet64)

func (*UniqueBag) GetSet

func (b *UniqueBag) GetSet(id ID) BitSet64

func (*UniqueBag) List

func (b *UniqueBag) List() []ID

func (*UniqueBag) PrefixedString

func (b *UniqueBag) PrefixedString(prefix string) string

func (*UniqueBag) RemoveSet

func (b *UniqueBag) RemoveSet(id ID)

func (*UniqueBag) String

func (b *UniqueBag) String() string

func (*UniqueBag) UnionSet

func (b *UniqueBag) UnionSet(id ID, set BitSet64)

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL