thresholdmap

Documentation

Index

• Constants
• type Element
  • func (e *Element[K, V]) Key() K
  • func (e *Element[K, V]) Value() V
• type Iterator
  • func NewIterator[K any, V any](startingElement *Element[K, V]) *Iterator[K, V]
  • func (i *Iterator[K, V]) HasNext() bool
  • func (i *Iterator[K, V]) HasPrev() bool
  • func (i *Iterator[K, V]) Next() *Element[K, V]
  • func (i *Iterator[K, V]) Prev() *Element[K, V]
  • func (i *Iterator[K, V]) Reset()
  • func (i *Iterator[K, V]) State() IteratorState
• type IteratorState
• type Mode
• type ThresholdMap
  • func New[K constraints.Ordered, V any](mode Mode) *ThresholdMap[K, V]
  • func (t *ThresholdMap[K, V]) Ceiling(key K) (ceilingKey K, ceilingValue V, exists bool)
  • func (t *ThresholdMap[K, V]) Clear()
  • func (t *ThresholdMap[K, V]) Decode(b []byte) (bytesRead int, err error)
  • func (t *ThresholdMap[K, V]) Delete(key K) (element *Element[K, V], success bool)
  • func (t *ThresholdMap[K, V]) DeleteElement(element *Element[K, V])
  • func (t *ThresholdMap[K, V]) Empty() bool
  • func (t ThresholdMap[K, V]) Encode() ([]byte, error)
  • func (t *ThresholdMap[K, V]) Floor(key K) (floorKey K, floorValue V, exists bool)
  • func (t *ThresholdMap[K, V]) ForEach(iterator func(node *Element[K, V]) bool)
  • func (t *ThresholdMap[K, V]) Get(key K) (value V, exists bool)
  • func (t *ThresholdMap[K, V]) GetElement(key K) *Element[K, V]
  • func (t *ThresholdMap[K, V]) Init(mode Mode) *ThresholdMap[K, V]
  • func (t *ThresholdMap[K, V]) Iterator(optionalStartingNode ...*Element[K, V]) *Iterator[K, V]
  • func (t *ThresholdMap[K, V]) Keys() []K
  • func (t *ThresholdMap[K, V]) MaxElement() *Element[K, V]
  • func (t *ThresholdMap[K, V]) MinElement() *Element[K, V]
  • func (t *ThresholdMap[K, V]) Mode() Mode
  • func (t *ThresholdMap[K, V]) Set(key K, value V)
  • func (t *ThresholdMap[K, V]) Size() int
  • func (t *ThresholdMap[K, V]) Values() []V

Constants

const (
	// LowerThresholdMode interprets the keys of the ThresholdMap as lower thresholds which means that querying the map
	// will return the value of the largest node whose key is <= than the queried value.
	LowerThresholdMode = true

	// UpperThresholdMode interprets the keys of the ThresholdMap as upper thresholds which means that querying the map
	// will return the value of the smallest node whose key is >= than the queried value.
	UpperThresholdMode = false
)

Types

type Element

type Element[K any, V any] struct {
	*redblacktree.Node
}

Element is a wrapper for the Node used in the underlying red-black RedBlackTree.

func (*Element[K, V]) Key

func (e *Element[K, V]) Key() K

Key returns the Key of the Element.

func (*Element[K, V]) Value

func (e *Element[K, V]) Value() V

Value returns the Value of the Element.

type Iterator

type Iterator[K any, V any] struct {
	// contains filtered or unexported fields
}

Iterator is an object that allows to iterate over the ThresholdMap by providing methods to walk through the map in a deterministic order.

func NewIterator

func NewIterator[K any, V any](startingElement *Element[K, V]) *Iterator[K, V]

NewIterator is the constructor of the Iterator that takes the starting Element as its parameter.

func (*Iterator[K, V]) HasNext

func (i *Iterator[K, V]) HasNext() bool

HasNext returns true if there is another Element after the previously retrieved Element that can be requested via the Next method.

func (*Iterator[K, V]) HasPrev

func (i *Iterator[K, V]) HasPrev() bool

HasPrev returns true if there is another Element before the previously retrieved Element that can be requested via the Prev method.

func (*Iterator[K, V]) Next

func (i *Iterator[K, V]) Next() *Element[K, V]

Next returns the next Element in the Iterator and advances the internal pointer. The method panics if there is no next Element that can be retrieved (always use HasNext to check if another Element can be requested).

func (*Iterator[K, V]) Prev

func (i *Iterator[K, V]) Prev() *Element[K, V]

Prev returns the previous Element in the Iterator and moves back the internal pointer. The method panics if there is no previous Element that can be retrieved (always use HasPrev to check if another Element can be requested).

func (*Iterator[K, V]) Reset

func (i *Iterator[K, V]) Reset()

Reset resets the Iterator to its initial Element.

func (*Iterator[K, V]) State

func (i *Iterator[K, V]) State() IteratorState

State returns the current IteratorState that the Iterator is in.

type IteratorState

type IteratorState int

IteratorState represents the state of the Iterator that is used to track where in the set of contained Elements the pointer is currently located.

const (
	// InitialState is the state of the Iterator before the first Element has been retrieved.
	InitialState IteratorState = iota

	// IterationStartedState is the state of the Iterator after the first Element has been retrieved and before we have
	// reached either the first or the last Element.
	IterationStartedState

	// LeftEndReachedState is the state of the Iterator after we have reached the smallest Element.
	LeftEndReachedState

	// RightEndReachedState is the state of the Iterator after we have reached the largest Element.
	RightEndReachedState
)

type Mode

type Mode bool

Mode encodes different modes of function for the ThresholdMap that specifies if the defines keys act as upper or lower thresholds.

type ThresholdMap

type ThresholdMap[K constraints.Ordered, V any] struct {
	sync.RWMutex
	// contains filtered or unexported fields
}

ThresholdMap is a data structure that allows to map keys bigger or lower than a certain threshold to a given value.

func New

func New[K constraints.Ordered, V any](mode Mode) *ThresholdMap[K, V]

New returns a ThresholdMap that operates in the given Mode.

func (*ThresholdMap[K, V]) Ceiling

func (t *ThresholdMap[K, V]) Ceiling(key K) (ceilingKey K, ceilingValue V, exists bool)

Ceiling returns the smallest key that is >= the given key, it's value and a boolean flag indicating if it exists.

func (*ThresholdMap[K, V]) Clear

func (t *ThresholdMap[K, V]) Clear()

Clear removes all Elements from the map.

func (*ThresholdMap[K, V]) Decode

func (t *ThresholdMap[K, V]) Decode(b []byte) (bytesRead int, err error)

Decode deserializes bytes into a valid object.

func (*ThresholdMap[K, V]) Delete

func (t *ThresholdMap[K, V]) Delete(key K) (element *Element[K, V], success bool)

Delete removes a threshold from the map.

func (*ThresholdMap[K, V]) DeleteElement

func (t *ThresholdMap[K, V]) DeleteElement(element *Element[K, V])

DeleteElement removes the given Element from the map.

func (*ThresholdMap[K, V]) Empty

func (t *ThresholdMap[K, V]) Empty() bool

Empty returns true of the map has no thresholds.

func (ThresholdMap[K, V]) Encode

func (t ThresholdMap[K, V]) Encode() ([]byte, error)

Encode returns a serialized byte slice of the object.

func (*ThresholdMap[K, V]) Floor

func (t *ThresholdMap[K, V]) Floor(key K) (floorKey K, floorValue V, exists bool)

Floor returns the largest key that is <= the given key, it's value and a boolean flag indicating if it exists.

func (*ThresholdMap[K, V]) ForEach

func (t *ThresholdMap[K, V]) ForEach(iterator func(node *Element[K, V]) bool)

ForEach provides a callback based iterator that iterates through all Elements in the map.

func (*ThresholdMap[K, V]) Get

func (t *ThresholdMap[K, V]) Get(key K) (value V, exists bool)

Get returns the value of the next higher or lower existing threshold (depending on the mode) and a flag that indicates if there is a threshold that covers the given value.

func (*ThresholdMap[K, V]) GetElement

func (t *ThresholdMap[K, V]) GetElement(key K) *Element[K, V]

GetElement returns the Element that is used to store the next higher or lower threshold (depending on the mode) belonging to the given key (or nil if none exists).

func (*ThresholdMap[K, V]) Init

func (t *ThresholdMap[K, V]) Init(mode Mode) *ThresholdMap[K, V]

Init initializes the ThresholdMap with the given Mode and comparator function.

func (*ThresholdMap[K, V]) Iterator

func (t *ThresholdMap[K, V]) Iterator(optionalStartingNode ...*Element[K, V]) *Iterator[K, V]

Iterator returns an Iterator object that can be used to manually iterate through the Elements in the map. It accepts an optional starting Element where the iteration begins.

func (*ThresholdMap[K, V]) Keys

func (t *ThresholdMap[K, V]) Keys() []K

Keys returns a list of thresholds that have been set in the map.

func (*ThresholdMap[K, V]) MaxElement

func (t *ThresholdMap[K, V]) MaxElement() *Element[K, V]

MaxElement returns the largest threshold in the map (or nil if the map is empty).

func (*ThresholdMap[K, V]) MinElement

func (t *ThresholdMap[K, V]) MinElement() *Element[K, V]

MinElement returns the smallest threshold in the map (or nil if the map is empty).

func (*ThresholdMap[K, V]) Mode

func (t *ThresholdMap[K, V]) Mode() Mode

Mode returns the mode of this ThresholdMap.

func (*ThresholdMap[K, V]) Set

func (t *ThresholdMap[K, V]) Set(key K, value V)

Set adds a new threshold that maps all keys >= or <= (depending on the Mode) the value given by key to a certain value.

func (*ThresholdMap[K, V]) Size

func (t *ThresholdMap[K, V]) Size() int

Size returns the amount of thresholds that are stored in the map.

func (*ThresholdMap[K, V]) Values

func (t *ThresholdMap[K, V]) Values() []V

Values returns a list of values that are associated to the thresholds in the map.