Documentation
¶
Overview ¶
Helper for make counter-like ADTs Support two key types: string and interface
flatmap transform nested map to flatten map
Experimental ¶
Package skiplist implements skip list based maps and sets. Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.
Index ¶
- Constants
- func FlattenMap(result FlatMap, prefix string, v reflect.Value) (err error)
- func FlattenSliceArray(result FlatMap, prefix string, v reflect.Value) (err error)
- func FlattenStructure(result FlatMap, prefix string, v reflect.Value) (err error)
- type Counter
- type Counter4s
- type FlatMap
- type Item
- type Item4s
- type Item4sList
- type ItemList
- type Iterator
- type Ordered
- type Parent
- type ParentTree
- type Set
- type Set4s
- type SkipList
- func (s *SkipList) Delete(key interface{}) (value interface{}, ok bool)
- func (s *SkipList) Get(key interface{}) (value interface{}, ok bool)
- func (s *SkipList) GetGreaterOrEqual(min interface{}) (actualKey, value interface{}, ok bool)
- func (s *SkipList) Iterator() Iterator
- func (s *SkipList) Len() int
- func (s *SkipList) Range(from, to interface{}) Iterator
- func (s *SkipList) Seek(key interface{}) Iterator
- func (s *SkipList) SeekToFirst() Iterator
- func (s *SkipList) SeekToLast() Iterator
- func (s *SkipList) SkipSet(key, value interface{})
- type SkipSet
- func (s *SkipSet) Add(key interface{})
- func (s *SkipSet) Contains(key interface{}) bool
- func (s *SkipSet) GetMaxLevel() int
- func (s *SkipSet) Iterator() Iterator
- func (s *SkipSet) Len() int
- func (s *SkipSet) Range(from, to interface{}) Iterator
- func (s *SkipSet) Remove(key interface{}) (ok bool)
- func (s *SkipSet) SetMaxLevel(newMaxLevel int)
Constants ¶
const (
DefaultMaxLevel = 32
)
p is the fraction of nodes with level i pointers that also have level i+1 pointers. p equal to 1/4 is a good value from the point of view of speed and space requirements. If variability of running times is a concern, 1/2 is a better value for p.
Variables ¶
This section is empty.
Functions ¶
func FlattenSliceArray ¶
Types ¶
type Counter ¶
type Counter map[interface{}]int
Generic Counter for interface
func MakeCounter ¶
Make new Counter4s, length is the initialized size of map
func (Counter) MostMommon ¶
An optimized most common method for large counter
func (Counter) SortByValue ¶
Sort the Counter by counted values in descend order
func (Counter) SortByValueAscend ¶
Sort the Counter by counted values in ascend order
type Counter4s ¶
Counter for strings or Keys can be cast to strings
func MakeCounter4s ¶
Make new Counter4s, length is the initialized size of map
func (Counter4s) GetItems ¶
func (c4s Counter4s) GetItems() Item4sList
Get Item4sList of Counter4s without sorting
func (Counter4s) MostMommon ¶
func (c4s Counter4s) MostMommon(topN int) Item4sList
An optimized most common method for large counter
func (Counter4s) SortByValue ¶
func (c4s Counter4s) SortByValue() Item4sList
Sort the Counter4s by counted values in descend order
func (Counter4s) SortByValueAscend ¶
func (c4s Counter4s) SortByValueAscend() Item4sList
Sort the Counter4s by counted values in ascend order
type Item4sList ¶
type Item4sList []Item4s
For collect all items of Counter4s
func (Item4sList) Len ¶
func (list Item4sList) Len() int
Implement of sort interfaces for Item4sList
func (Item4sList) Less ¶
func (list Item4sList) Less(i, j int) bool
Implement of sort interfaces for Item4sList Note the default orderer is descend, means it's Great not Less
func (*Item4sList) Pop ¶
func (list *Item4sList) Pop() interface{}
Heap interface implements for most common method
func (*Item4sList) Push ¶
func (list *Item4sList) Push(value interface{})
Heap interface implements for most common method
func (Item4sList) Swap ¶
func (list Item4sList) Swap(i, j int)
Implement of sort interfaces for Item4sList
type ItemList ¶
type ItemList []Item
For collect all items of Counter
func (ItemList) Less ¶
Implement of sort interfaces for ItemList Note the default orderer is descend, means it's Great not Less
func (*ItemList) Pop ¶
func (list *ItemList) Pop() interface{}
Heap interface implements for most common method
type Iterator ¶
type Iterator interface {
// Next returns true if the iterator contains subsequent elements
// and advances its state to the next element if that is possible.
Next() (ok bool)
// Previous returns true if the iterator contains previous elements
// and rewinds its state to the previous element if that is possible.
Previous() (ok bool)
// Key returns the current key.
Key() interface{}
// Value returns the current value.
Value() interface{}
// Seek reduces iterative seek costs for searching forward into the Skip List
// by remarking the range of keys over which it has scanned before. If the
// requested key occurs prior to the point, the Skip List will start searching
// as a safeguard. It returns true if the key is within the known range of
// the list.
Seek(key interface{}) (ok bool)
// Close this iterator to reap resources associated with it. While not
// strictly required, it will provide extra hints for the garbage collector.
Close()
}
Iterator is an interface that you can use to iterate through the skip list (in its entirety or fragments). For an use example, see the documentation of SkipList.
Key and Value return the key and the value of the current node.
type Ordered ¶
Ordered is an interface which can be linearly ordered by the LessThan method, whereby this instance is deemed to be less than other. Additionally, Ordered instances should behave properly when compared using == and !=.
type ParentTree ¶
func NewParentTree ¶
func NewParentTree() *ParentTree
func (*ParentTree) Clear ¶
func (tree *ParentTree) Clear()
func (ParentTree) Exist ¶
func (tree ParentTree) Exist(id string) bool
type Set ¶
type Set map[interface{}]struct{}
A generic set(key unique) based on map
type Set4s ¶
type Set4s map[string]struct{}
A string set(key unique) based on map
type SkipList ¶
type SkipList struct {
// MaxLevel determines how many items the SkipList can store
// efficiently (2^MaxLevel).
//
// It is safe to increase MaxLevel to accomodate more
// elements. If you decrease MaxLevel and the skip list
// already contains nodes on higer levels, the effective
// MaxLevel will be the greater of the new MaxLevel and the
// level of the highest node.
//
// A SkipList with MaxLevel equal to 0 is equivalent to a
// standard linked list and will not have any of the nice
// properties of skip lists (probably not what you want).
MaxLevel int
// contains filtered or unexported fields
}
A SkipList is a map-like data structure that maintains an ordered collection of key-value pairs. Insertion, lookup, and deletion are all O(log n) operations. A SkipList can efficiently store up to 2^MaxLevel items.
To iterate over a skip list (where s is a *SkipList):
for i := s.Iterator(); i.Next(); {
// do something with i.Key() and i.Value()
}
func NewCustomMap ¶
NewCustomMap returns a new SkipList that will use lessThan as the comparison function. lessThan should define a linear order on keys you intend to use with the SkipList.
func NewSkipList ¶
func NewSkipList() *SkipList
New returns a new SkipList.
Its keys must implement the Ordered interface.
func NewStringMap ¶
func NewStringMap() *SkipList
NewStringMap returns a SkipList that accepts string keys.
func (*SkipList) Delete ¶
Delete removes the node with the given key.
It returns the old value and whether the node was present.
func (*SkipList) Get ¶
Get returns the value associated with key from s (nil if the key is not present in s). The second return value is true when the key is present.
func (*SkipList) GetGreaterOrEqual ¶
GetGreaterOrEqual finds the node whose key is greater than or equal to min. It returns its value, its actual key, and whether such a node is present in the skip list.
func (*SkipList) Range ¶
Range returns an iterator that will go through all the elements of the skip list that are greater or equal than from, but less than to.
func (*SkipList) Seek ¶
Seek returns a bidirectional iterator starting with the first element whose key is greater or equal to key; otherwise, a nil iterator is returned.
func (*SkipList) SeekToFirst ¶
SeekToFirst returns a bidirectional iterator starting from the first element in the list if the list is populated; otherwise, a nil iterator is returned.
func (*SkipList) SeekToLast ¶
SeekToLast returns a bidirectional iterator starting from the last element in the list if the list is populated; otherwise, a nil iterator is returned.
type SkipSet ¶
type SkipSet struct {
// contains filtered or unexported fields
}
SkipSet is an ordered set data structure.
Its elements must implement the Ordered interface. It uses a SkipList for storage, and it gives you similar performance guarantees.
To iterate over a set (where s is a *SkipSet):
for i := s.Iterator(); i.Next(); {
// do something with i.Key().
// i.Value() will be nil.
}
func NewCustomSet ¶
NewCustomSet returns a new SkipSet that will use lessThan as the comparison function. lessThan should define a linear order on elements you intend to use with the SkipSet.
func NewIntSet ¶
func NewIntSet() *SkipSet
NewIntSet returns a new SkipSet that accepts int elements.
func NewStringSet ¶
func NewStringSet() *SkipSet
NewStringSet returns a new SkipSet that accepts string elements.
func (*SkipSet) GetMaxLevel ¶
GetMaxLevel returns MaxLevel fo the underlying skip list.
func (*SkipSet) Range ¶
Range returns an iterator that will go through all the elements of the set that are greater or equal than from, but less than to.
func (*SkipSet) Remove ¶
Remove tries to remove key from the set. It returns true if key was present.
func (*SkipSet) SetMaxLevel ¶
SetMaxLevel sets MaxLevel in the underlying skip list.
Source Files