ids

package
v1.4.6-internal.2 Latest Latest
Warning

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

 Go to latest Published: May 24, 2021 License: BSD-3-Clause Imports: 13 Imported by: 1,042

Documentation

Index

Constants

View Source 
const BitsPerByte = 8

BitsPerByte is the number of bits per byte

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 ShortEmpty = ShortID{}

ShortEmpty is a useful all zero value

Functions

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 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 added in v0.8.0 

func IsUniqueShortIDs(ids []ShortID) bool

IsUniqueShortIDs returns true iff ids are unique

func SortIDs 

func SortIDs(ids []ID)

SortIDs sorts the 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 struct {
	// contains filtered or unexported fields
}

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

func (*Aliaser) Alias 

func (a *Aliaser) Alias(id ID, alias string) error

Alias gives [id] the alias [alias]

func (*Aliaser) Aliases 

func (a *Aliaser) Aliases(id ID) []string

Aliases returns the aliases of an ID

func (*Aliaser) Initialize 

func (a *Aliaser) Initialize()

Initialize the aliaser to have no aliases

func (*Aliaser) Lookup 

func (a *Aliaser) Lookup(alias string) (ID, error)

Lookup returns the ID associated with alias

func (*Aliaser) PrimaryAlias 

func (a *Aliaser) PrimaryAlias(id ID) (string, error)

PrimaryAlias returns the first alias of [id]

func (*Aliaser) RemoveAliases added in v0.8.0 

func (a *Aliaser) RemoveAliases(id ID)

RemoveAliases of the provided ID

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) 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 BitSet 

type BitSet uint64

BitSet 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 (*BitSet) Add 

func (bs *BitSet) Add(i uint)

Add [i] to the set of ints

func (*BitSet) Clear 

func (bs *BitSet) Clear()

Clear removes all elements from this set

func (BitSet) Contains 

func (bs BitSet) Contains(i uint) bool

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

func (*BitSet) Difference 

func (bs *BitSet) Difference(s BitSet)

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

func (*BitSet) Intersection 

func (bs *BitSet) Intersection(s BitSet)

Intersection takes the intersection of [s] with this set

func (BitSet) Len 

func (bs BitSet) Len() int

Len returns the number of elements in this set

func (*BitSet) Remove 

func (bs *BitSet) Remove(i uint)

Remove [i] from the set of ints

func (BitSet) String 

func (bs BitSet) String() string

func (*BitSet) Union 

func (bs *BitSet) Union(s BitSet)

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 added in v0.8.0 

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)

MarshalJSON ...

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

UnmarshalJSON ...

type QueueSet 

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

QueueSet is a set of IDs stored in fifo order

func (*QueueSet) Append 

func (qs *QueueSet) Append(id ID)

Append ...

func (*QueueSet) GetTail 

func (qs *QueueSet) GetTail() ID

GetTail ...

func (*QueueSet) SetHead 

func (qs *QueueSet) SetHead(id ID)

SetHead ...

type Set 

type Set map[ID]struct{}

Set is a set of IDs

func NewSet added in v1.4.5 

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 added in v0.8.0 

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) 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) Overlaps 

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

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

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) 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 sets to this set.

type ShortBag added in v0.8.0 

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

ShortBag is a multiset of ShortIDs.

func (*ShortBag) Add added in v0.8.0 

func (b *ShortBag) Add(ids ...ShortID)

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

func (*ShortBag) AddCount added in v0.8.0 

func (b *ShortBag) AddCount(id ShortID, count int)

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

count must be >= 0

func (*ShortBag) Count added in v0.8.0 

func (b *ShortBag) Count(id ShortID) int

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

func (*ShortBag) Equals added in v0.8.0 

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

Equals returns true if the bags contain the same elements

func (*ShortBag) Len added in v0.8.0 

func (b *ShortBag) Len() int

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

func (*ShortBag) List added in v0.8.0 

func (b *ShortBag) List() []ShortID

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

func (*ShortBag) PrefixedString added in v0.8.0 

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

PrefixedString ...

func (*ShortBag) Remove added in v0.8.0 

func (b *ShortBag) Remove(id ShortID)

Remove sets the count of the provided ID to zero.

func (*ShortBag) String added in v0.8.0 

func (b *ShortBag) String() string

type ShortID 

type ShortID [20]byte

ShortID wraps a 20 byte hash as an identifier

func GenerateTestShortID added in v0.8.0 

func GenerateTestShortID() ShortID

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

func ShortFromPrefixedString added in v0.8.0 

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)

MarshalJSON ...

func (ShortID) PrefixedString added in v0.8.0 

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

UnmarshalJSON ...

type ShortSet 

type ShortSet map[ShortID]struct{}

ShortSet is a set of ShortIDs

func NewShortSet added in v1.4.5 

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 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 (*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) 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) 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) 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 sets to this set.

type UniqueBag 

type UniqueBag map[ID]BitSet

UniqueBag ...

func (*UniqueBag) Add 

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

Add ...

func (*UniqueBag) Bag 

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

Bag ...

func (*UniqueBag) Difference 

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

Difference ...

func (*UniqueBag) DifferenceSet 

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

DifferenceSet ...

func (*UniqueBag) GetSet 

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

GetSet ...

func (*UniqueBag) List 

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

List ...

func (*UniqueBag) RemoveSet added in v0.8.0 

func (b *UniqueBag) RemoveSet(id ID)

RemoveSet ...

func (*UniqueBag) String 

func (b *UniqueBag) String() string

func (*UniqueBag) UnionSet 

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

UnionSet ...

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.