Documentation
¶
Index ¶
- Variables
- func AllocDefault[T any](min, max int) ([]T, error)
- func FixAllocSize(newIntendedCap, maxCap int) int
- type AllocFunc
- type CompareFunc
- type Heap
- type List
- func (l *List[T]) Append(s ...T) error
- func (l *List[T]) At(i int) (v T)
- func (l *List[T]) Back() T
- func (l *List[T]) Cap() int
- func (l *List[T]) Clear() int
- func (l *List[T]) CopyTo(s []T, i, n int) error
- func (l *List[T]) Delete(i, j int) error
- func (l *List[T]) Free() int
- func (l *List[T]) Front() T
- func (l *List[T]) Grow(n int) error
- func (l *List[T]) GrowRange(min, max int) error
- func (l *List[T]) Heap(cmp CompareFunc[T]) Heap[T]
- func (l *List[T]) Insert(i int, s ...T) error
- func (l *List[T]) Len() int
- func (l List[T]) MarshalJSON() ([]byte, error)
- func (l *List[T]) Ordered(cmp CompareFunc[T]) Ordered[T]
- func (l *List[T]) Pop() T
- func (l *List[T]) Push(v T)
- func (l *List[T]) Replace(i, j int, s ...T) error
- func (l *List[T]) Rotate(n int)
- func (l *List[T]) Shuffle()
- func (l *List[T]) ShuffleRange(i, j int) error
- func (l *List[T]) ShuffleRangeRand(r *rand.Rand, i, j int) error
- func (l *List[T]) String() string
- func (l *List[T]) StringRange(i, n int) (string, error)
- func (l *List[T]) Swap(i, j int)
- func (l *List[T]) SwapOK(i, j int) (bool, error)
- func (l *List[T]) UnmarshalJSON(b []byte) error
- func (l *List[T]) Val(i int) (v T, ok bool)
- type Ordered
- func (o Ordered[T]) Compare(i, j int) int
- func (o Ordered[T]) Contains(v T) bool
- func (o Ordered[T]) Find(v T) (i int, found bool)
- func (o Ordered[T]) Heap() Heap[T]
- func (o Ordered[T]) Invert() Ordered[T]
- func (o Ordered[T]) IsSorted() bool
- func (o Ordered[T]) Less(i, j int) bool
- func (o Ordered[T]) Sort()
- func (o Ordered[T]) SortStable()
Constants ¶
This section is empty.
Variables ¶
var ( ErrInvalidPosition = errors.New("invalid element position") ErrInvalidRange = errors.New("invalid range") ErrInvalidAmount = errors.New("invalid amount of elements") ErrInvalidAllocation = errors.New("insufficient space allocated") )
Package level errors for List.
Functions ¶
func AllocDefault ¶
AllocDefault is the default AllocFunc[T].
func FixAllocSize ¶
FixAllocSize is a helper for implementators of AllocFunc to make sure the max capacity is not exceeded.
Types ¶
type AllocFunc ¶
AllocFunc is a function that allocates a new slice that needs to hold at least min elements. If max >=0, then expect min<=max, and the returned slice should not have a length greater than max (see FixAllocSize helper). The returned slice will not be resliced further than its returned length. Implementations should not hold references to the returned slice. Note that the returned slice will be lazily zeroed as needed, so if any references need to be clread from previous work, then it should be done before returning it.
type CompareFunc ¶
CompareFunc shoud return:
-1 if x is less than y, 0 if x equals y, +1 if x is greater than y.
It must be a strict weak ordering for sorting methods to work properly. See https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings.
func (CompareFunc[T]) Inverse ¶
func (f CompareFunc[T]) Inverse(x, y T) int
Inverse inverts the operands of f to achieve the opposite ordering.
type Heap ¶
Heap uses container/heap to implement a heap.
func NewHeap ¶
func NewHeap[T any](cmp CompareFunc[T]) Heap[T]
NewHeap creates a new Heap using the given CompareFunc.
func (Heap[T]) Fix ¶
Fix re-establishes the heap ordering after the element at index i has changed its value. Changing the value of the element at index i and then calling Fix is equivalent to, but less expensive than, calling Remove(h, i) followed by a Push of the new value.
func (Heap[T]) Init ¶
func (h Heap[T]) Init()
Init establishes the heap invariants required by the other heap methods. Init is idempotent with respect to the heap invariants and may be called whenever the heap invariants may have been invalidated.
func (Heap[T]) Pop ¶
func (h Heap[T]) Pop() T
Pop removes and returns the minimum element (according to Less) from the heap. Pop is equivalent to Remove(h, 0).
func (Heap[T]) Push ¶
func (h Heap[T]) Push(v T)
Push pushes the element x onto the heap. The complexity is O(log n) where n = h.Len().
func (Heap[T]) UnmarshalJSON ¶
UnmarshalJSON clears the heap, reads a JSON Array as a list of elements, and calls Init.
type List ¶
type List[T any] struct { // AllocFunc allows customizing allocation of a new slice when more space // is needed. If nil, AllocDefault is used. AllocFunc[T] // FreeFunc will be called, if set, with the old slice after migrating to a // newly allocated slice. This is useful if you want to put a slice back // into a pool or do something else with it, but all the items that the // list had used will have been zeroed out. FreeFunc func([]T) // StringFunc allows customizing how elements are converted to string when // printing the list. The default is using fmt.Sprintf("%v", element). StringFunc func(T) string // contains filtered or unexported fields }
List is a slice-based list container, indexed from its back to its front starting at zero. Not safe for concurrent use. It zeroes elements that are removed from the list. The implementation is panic free, so errors are returned for the cases where bounds and other input need to be validated.
func New ¶
New creates a new List using the given slice as the underlying data. If useValues is true, then the list will use all the elements of the slice as if they had been inserted in an empty list with InsertFront. Otherwise, the list will ignore the current elements and be empty. You should not hold references to s after calling this function. If useValues is false, the elements are not zeroed.
func NewN ¶
NewN is like New, but allows specifying the index in the slice that would be the back of the list, and the number of elements that would be part of the new list. The value of length must be in the range [0, len(s)]. Note that you can set length and back in a way that would wrap the slice, which is ok. You should not hold references to s after calling this function. The elemetns that are not part of the new list are not zeroed.
func (*List[T]) At ¶
At returns the element at the given position, which can wrap the list from either side. This means that At(-1) is the same as At(l.Len()-1). It returns the zero value if the list is empty.
func (*List[T]) Back ¶
func (l *List[T]) Back() T
Back returns the element at the back of the list. If the list is empty, it returns the zero value. It is equivalent to l.At(0).
func (*List[T]) Clear ¶
Clear removes all the elements in the list and returns the number of elements removed.
func (*List[T]) CopyTo ¶
CopyTo copies at most n elements starting at index i to the given slice, and returns the number of copied elements. If j<i, then it wraps the list.
func (*List[T]) Free ¶
Free returns the number of elements that can be added to the list without a new allocation.
func (*List[T]) Front ¶
func (l *List[T]) Front() T
Front returns the element at the front of the list. If the list is empty, it returns the zero value. It is equivalent to l.At(-1).
func (*List[T]) Grow ¶
Grow makes sure that the list has capacity for at least n new elements. If l.Free()<n, then a new slice will be allocated and the list migrated to it.
func (*List[T]) GrowRange ¶
GrowRange makes sure that the list has capacity for at least min and at most max new elements. If l.Free() is not in the range [min, max], then a new slice will be allocated and the list migrated to it.
func (*List[T]) Heap ¶
func (l *List[T]) Heap(cmp CompareFunc[T]) Heap[T]
Heap initializes and returns a heap from the current List. the list will be shared, so if you change it outside of the returned heap, you will need to call fix or init on the returned heap to reconcile it.
func (List[T]) MarshalJSON ¶
MarshalJSON marshals the list as a JSON Array.
func (*List[T]) Ordered ¶
func (l *List[T]) Ordered(cmp CompareFunc[T]) Ordered[T]
Ordered returns an Ordered based on this list and the given CompareFunc.
func (*List[T]) Pop ¶
func (l *List[T]) Pop() T
Pop removes the element at the front of the list and returns it. If the list is empty, it returns the zero value and does nothing.
func (*List[T]) Push ¶
func (l *List[T]) Push(v T)
Push pushes the given element to the front of the list.
func (*List[T]) Shuffle ¶
func (l *List[T]) Shuffle()
Shuffle pseudo-randomizes the order of elements using the default math/rand.Source.
func (*List[T]) ShuffleRange ¶
ShuffleN is like Shuffle, but allows specifying a specific range to be shuffled.
func (*List[T]) ShuffleRangeRand ¶
ShuffleRangeRand is like ShuffleRange but allows specifying an alternative *math/rand.Rand.
func (*List[T]) String ¶
String converts a list into a human-readable form. You can control how individual elements are printed by setting the StringFunc member of the list.
func (*List[T]) StringRange ¶
StringRange is like String but only for the given range. If j<i, then it wraps the list.
func (*List[T]) Swap ¶
Swap swaps the i-eth and j-eth elements. If either of the elements is out of range, it's a nop. Use SwapOK if you need to know if the elements were swapped.
func (*List[T]) SwapOK ¶
SwapOK swaps the i-eth and j-eth elements. If i==j, it's a nop and returns false. Otherwise, it returns true and swaps the elements.
func (*List[T]) UnmarshalJSON ¶
UnmarshalJSON clears the list and reads a JSON Array as a list of elements.
type Ordered ¶
Ordered is a List whose elements can be compared, and it satisfies sort.Interface.
func NewOrdered ¶
func NewOrdered[T any](cmp CompareFunc[T]) Ordered[T]
NewOrdered creates a new Ordered using the given CompareFunc.
func (Ordered[T]) Compare ¶
Compare returns:
-1 if the element at position i is less than the element at position j, 0 if the element at position i equals the element at position j, or if the list is empty, +1 if the element at position i is greater than the element at position j.
func (Ordered[T]) Find ¶
Find uses binary search to find and return the smallest index i at which the list element is >= v.
func (Ordered[T]) Heap ¶
heap initializes and returns a heap from the current Ordered. the list will be shared, so if you change it outside of the returned heap, you will need to call fix or init on the returned heap to reconcile it.
func (Ordered[T]) Invert ¶
Invert returns an Ordered with the comparison function inverted, reusing the same underlying data. Example:
o := NewOrdered[int](cmp.Compare) o.InsertFront(5, 3, 8, 9) fmt.Println(o) // [5, 3, 8, 9] fmt.Println(o.Heap().Pop()) // 3, true fmt.Println(o.Invert().Heap().Pop()) // 9, true o.Sort() fmt.Println(o) // [5, 8] o.Invert().Sort() fmt.Println(o) // [8, 5]
func (Ordered[T]) Less ¶
Less returns whether the given element at i is less than the element at j. If the list is empty, it always returns false.
func (Ordered[T]) Sort ¶
func (o Ordered[T]) Sort()
Sort sorts data in ascending order as determined by the Less method. The sort is not guaranteed to be stable.
func (Ordered[T]) SortStable ¶
func (o Ordered[T]) SortStable()
SortStable sorts data in ascending order as determined by the Less method, while keeping the original order of equal elements.
Source Files