Documentation
¶
Overview ¶
Package pot see doc.go
Package pot (proximity order tree) implements a container similar to a binary tree. The elements are generic Val interface types.
Each fork in the trie is itself a value. Values of the subtree contained under a node all share the same order when compared to other elements in the tree.
Example of proximity order is the length of the common prefix over bitvectors. (which is equivalent to the reverse rank of order of magnitude of the MSB first X OR distance over finite set of integers).
Methods take a comparison operator (pof, proximity order function) to compare two value types. The default pof assumes Val to be or project to a byte slice using the reverse rank on the MSB first XOR logarithmic distance.
If the address space if limited, equality is defined as the maximum proximity order.
The container offers applicative (functional) style methods on PO trees: * adding/removing en element * swap (value based add/remove) * merging two PO trees (union)
as well as iterator accessors that respect proximity order
When synchronicity of membership if not 100% requirement (e.g. used as a database of network connections), applicative structures have the advantage that nodes are immutable therefore manipulation does not need locking allowing for concurrent retrievals. For the use case where the entire container is supposed to allow changes by concurrent routines,
Pot * retrieval, insertion and deletion by key involves log(n) pointer lookups * for any item retrieval (defined as common prefix on the binary key) * provide synchronous iterators respecting proximity ordering wrt any item * provide asynchronous iterator (for parallel execution of operations) over n items * allows cheap iteration over ranges * asymmetric concurrent merge (union)
Note: * as is, union only makes sense for set representations since which of two values with equal keys survives is random * intersection is not implemented * simple get accessor is not implemented (but derivable from EachNeighbour)
Pinned value on the node implies no need to copy keys of the item type.
Note that * the same set of values allows for a large number of alternative POT representations. * values on the top are accessed faster than lower ones and the steps needed to retrieve items has a logarithmic distribution.
As a consequence one can organise the tree so that items that need faster access are torwards the top. In particular for any subset where popularity has a power distriution that is independent of proximity order (content addressed storage of chunks), it is in principle possible to create a pot where the steps needed to access an item is inversely proportional to its popularity. Such organisation is not implemented as yet.
TODO: * overwrite-style merge * intersection * access frequency based optimisations
Package pot see doc.go
Index ¶
- func DefaultPof(max int) func(one, other Val, pos int) (int, bool)
- func Label(v Val) string
- func NewAddressFromString(s string) []byte
- func ProxCmp(a, x, y interface{}) int
- func ToBin(a []byte) string
- func ToBytes(v Val) []byte
- type Address
- type BytesAddress
- type Pof
- type Pot
- func (t *Pot) Each(f func(Val) bool) bool
- func (t *Pot) EachBin(val Val, pof Pof, po int, f func(int, int, func(func(val Val) bool) bool) bool)
- func (t *Pot) EachNeighbour(val Val, pof Pof, f func(Val, int) bool) bool
- func (t *Pot) EachNeighbourAsync(val Val, pof Pof, max int, maxPos int, f func(Val, int), wait bool)
- func (t *Pot) Pin() Val
- func (t *Pot) Size() int
- func (t *Pot) String() string
- type Val
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func DefaultPof ¶
DefaultPof returns a proximity order comparison operator function
func NewAddressFromString ¶
NewAddressFromString creates a byte slice from a string in binary representation
func ProxCmp ¶
func ProxCmp(a, x, y interface{}) int
ProxCmp compares the distances a->target and b->target. Returns -1 if a is closer to target, 1 if b is closer to target and 0 if they are equal.
Types ¶
type Address ¶
Address is an alias for common.Hash
func NewAddressFromBytes ¶
NewAddressFromBytes constructs an Address from a byte slice
func RandomAddressAt ¶
RandomAddressAt (address, prox) generates a random address at proximity order prox relative to address if prox is negative a random address is generated
func (Address) Bin ¶
Bin returns the string form of the binary representation of an address (only first 8 bits)
func (*Address) MarshalJSON ¶
MarshalJSON Address serialisation
func (*Address) UnmarshalJSON ¶
UnmarshalJSON Address deserialisation
type BytesAddress ¶
type BytesAddress interface {
Address() []byte
}
BytesAddress is an interface for elements addressable by a byte slice
type Pot ¶
type Pot struct {
// contains filtered or unexported fields
}
Pot is the node type (same for root, branching node and leaf)
func Add ¶
Add inserts a new value into the Pot and returns the proximity order of v and a boolean indicating if the item was found Add called on (t, v) returns a new Pot that contains all the elements of t plus the value v, using the applicative add the second return value is the proximity order of the inserted element the third is boolean indicating if the item was found
func NewPot ¶
NewPot constructor. Requires a value of type Val to pin and po to point to a span in the Val key The pinned item counts towards the size
func Remove ¶
Remove deletes element v from the Pot t and returns three parameters: 1. new Pot that contains all the elements of t minus the element v; 2. proximity order of the removed element v; 3. boolean indicating whether the item was found.
func Swap ¶
Swap called on (k, f) looks up the item at k and applies the function f to the value v at k or to nil if the item is not found if f(v) returns nil, the element is removed if f(v) returns v' <> v then v' is inserted into the Pot if (v) == v the Pot is not changed it panics if Pof(f(v), k) show that v' and v are not key-equal
func Union ¶
Union called on (t0, t1, pof) returns the union of t0 and t1 calculates the union using the applicative union the second return value is the number of common elements
func (*Pot) EachBin ¶
func (t *Pot) EachBin(val Val, pof Pof, po int, f func(int, int, func(func(val Val) bool) bool) bool)
EachBin iterates over bins of the pivot node and offers iterators to the caller on each subtree passing the proximity order and the size the iteration continues until the function's return value is false or there are no more subtries
func (*Pot) EachNeighbour ¶
EachNeighbour is a synchronous iterator over neighbours of any target val the order of elements retrieved reflect proximity order to the target TODO: add maximum proxbin to start range of iteration
func (*Pot) EachNeighbourAsync ¶
func (t *Pot) EachNeighbourAsync(val Val, pof Pof, max int, maxPos int, f func(Val, int), wait bool)
EachNeighbourAsync called on (val, max, maxPos, f, wait) is an asynchronous iterator over elements not closer than maxPos wrt val. val does not need to be match an element of the Pot, but if it does, and maxPos is keylength than it is included in the iteration Calls to f are parallelised, the order of calls is undefined. proximity order is respected in that there is no element in the Pot that is not visited if a closer node is visited. The iteration is finished when max number of nearest nodes is visited or if the entire there are no nodes not closer than maxPos that is not visited if wait is true, the iterator returns only if all calls to f are finished TODO: implement minPos for proper prox range iteration
Source Files