Documentation
¶
Overview ¶
Package lists provides a doubly linked list and various functions useful with lists of any type.
Index ¶
- func Back[T any](l *List[T]) T
- func Compact[T comparable](l *List[T])
- func CompactFunc[T any](l *List[T], eq gcl.EqualFn[T, T])
- func Compare[T constraints.Ordered](l1, l2 *List[T]) int
- func CompareFunc[T1 any, T2 any](l1 *List[T1], l2 *List[T2], cmp gcl.CompareFn[T1, T2]) int
- func Contains[T comparable](l *List[T], v T) bool
- func Equal[T comparable](l1, l2 *List[T]) bool
- func EqualFunc[T1 any, T2 any](l1 *List[T1], l2 *List[T2], eq gcl.EqualFn[T1, T2]) bool
- func Front[T any](l *List[T]) T
- func Index[T comparable](l *List[T], v T) int
- func IndexFunc[T comparable](l *List[T], pred func(T) bool) int
- func IsSorted[T constraints.Ordered](l *List[T]) bool
- func IsSortedFunc[T any](l *List[T], less gcl.LessFn[T]) bool
- func Len[T any](l *List[T]) int
- func PopBack[T any](l *List[T])
- func PopFront[T any](l *List[T])
- func PushBack[T any](l *List[T], elems ...T)
- func PushFront[T any](l *List[T], elems ...T)
- func Reverse[T any](l *List[T])
- func Sort[T constraints.Ordered](l *List[T])
- func SortFunc[T any](l *List[T], less gcl.LessFn[T])
- type FrwIter
- type FrwIterMut
- type List
- type RevIter
- type RevIterMut
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Back ¶
Back returns the last element in the list. It panics if the given list is empty. This function is O(1).
func Compact ¶
func Compact[T comparable](l *List[T])
Compact replaces every consecutive group of equal elements with a single copy. This is like the uniq Unix command. This function is O(n), where n is length of the list.
func CompactFunc ¶
CompactFunc is like Compact but it uses the `eq` function for comparison. This function is O(f * n), where n is length of the list and f is time complexity of the `eq` function.
func Compare ¶
func Compare[T constraints.Ordered](l1, l2 *List[T]) int
Compare compares the elements of l1 and l2. The elements are compared sequentially from the beginning, until one element is not equal to the corresponding one. The result of comparing the first non-matching elements is returned. If both lists are equal until one of them ends, the shorter list is considered less than the longer one. The result is 0 if l1 == l2, -1 if l1 < l2, and +1 if l1 > l2. Comparisons involving floating point NaNs are ignored. This function is O(min(Len(l1), Len(l2))).
func CompareFunc ¶
CompareFunc operates the same as Compare function but it uses the given `cmp` function for comparing each pair of elements. The result is the first non-zero result of cmp; if cmp always returns 0 the result is 0 if Len(l1) == Len(l2), -1 if Len(l1) < Len(l2), This function is O(f * min(Len(l1), Len(l2))), where f is the time complexity of `cmp` function.
func Contains ¶
func Contains[T comparable](l *List[T], v T) bool
Contains tests whether the given list l has value v. This function is O(n), where n is length of the list.
func Equal ¶
func Equal[T comparable](l1, l2 *List[T]) bool
Equal tests whether two lists are equal: the same length and all elements equal. Floating point NaNs are not considered equal. This function is O(min(Len(l1), Len(l2))).
func EqualFunc ¶
EqualFunc tests whether two lists are equal using the given `eq` function. For each pair of elements, `eq` determines if they are equal or not. This function is O(f * min(Len(l1), Len(l2))), where f is the time complexity of `eq` function.
func Front ¶
Front returns the first element in the list. It panics if the given list is empty. This function is O(1).
func Index ¶
func Index[T comparable](l *List[T], v T) int
Index returns the index of the first occurrence of v in l, or -1 if not present. This function is O(n), where n is length of the list.
func IndexFunc ¶
func IndexFunc[T comparable](l *List[T], pred func(T) bool) int
IndexFunc returns the index of the first element satisfying pred, or -1 if none do. This function is O(f * n), where n is length of the list and f is time complexity of the `pred` function.
func IsSorted ¶
func IsSorted[T constraints.Ordered](l *List[T]) bool
IsSorted tests whether a list of any ordered type is sorted in ascending order. This function is O(n), where n is length of the list.
func IsSortedFunc ¶
IsSortedFunc tests whether a list type is sorted in ascending order, according to the `less` comparison function. This function is O(f * n), where n is length of the list and f is time complexity of the `less` function.
func PopBack ¶
PopBack deletes the last element in the list. It requires the list to be non-empty, otherwise it panics. This function is O(1).
func PopFront ¶
PopFront deletes the first element in the list. It requires the list to be non-empty, otherwise it panics. This function is O(1).
func PushBack ¶
PushBack appends the given elements to the back of list `l`. This function is O(Len(elems)). So for a single element it would be O(1).
func PushFront ¶
PushFront appends the given elements to the beginning of list `l`. This function is O(Len(elems)). So for a single element it would be O(1).
func Reverse ¶
Reverse reverses the elements of the given list. This function is O(n), where n is length of the list.
func Sort ¶
func Sort[T constraints.Ordered](l *List[T])
Sort sorts a list of any ordered type in ascending order. This function is O(n * log(n)), where n is length of the list.
Types ¶
type FrwIter ¶
type FrwIter[T any] struct { // contains filtered or unexported fields }
FrwIter is a list forward iterator.
func Iter ¶
Iter returns an forward iterator to the beginning. Initially, the returned iterator is located at one step before the first element (one-before-first).
type FrwIterMut ¶
type FrwIterMut[T any] struct { // contains filtered or unexported fields }
FrwIterMut is a mutable forward iterator for lists. It allows mutations by returning pointers to the list elements. FrwIterMut is an iterator over pointers of type T. In other words, FrwIterMut[T] implements iters.Iterator[*T].
func IterMut ¶
func IterMut[T any](l *List[T]) *FrwIterMut[T]
IterMut returns a forward iterator to the beginning with mutable pointers. Initially, the returned iterator is located at one step before the first element (one-before-first).
func (*FrwIterMut[T]) Delete ¶
func (it *FrwIterMut[T]) Delete()
Delete deletes the element that the iterator it is pointing to. Delete requires the iterator it to point to an actual element in the list. For example, it's not possible to call Delete on the IterMut iterator (in its inital state) because this iterator is located at one step before the first element and this is not an actual list element. This function is O(1).
func (*FrwIterMut[T]) HasNext ¶
func (it *FrwIterMut[T]) HasNext() bool
func (*FrwIterMut[T]) Insert ¶
func (it *FrwIterMut[T]) Insert(elems ...T)
Insert inserts the given values next after the iterator it. This function is O(len(elems)). So inserting a single element would be O(1).
func (*FrwIterMut[T]) Next ¶
func (it *FrwIterMut[T]) Next() *T
type List ¶
type List[T any] struct { // contains filtered or unexported fields }
List is doubly linked list.
func Clone ¶
Clone returns a copy of the given list. The elements are copied using assignment, so this is a shallow clone. This function is O(n), where n is length of the list.
func (*List[T]) MarshalJSON ¶
func (*List[T]) UnmarshalJSON ¶
type RevIter ¶
type RevIter[T any] struct { // contains filtered or unexported fields }
RevIter is a list reverse iterator.
type RevIterMut ¶
type RevIterMut[T any] struct { // contains filtered or unexported fields }
RevIterMut is a mutable reverse iterator for lists. It allows mutations by returning pointers to the list elements. RevIterMut is an iterator over pointers of type T. In other words, RevIterMut[T] implements iters.Iterator[*T].
func RIterMut ¶
func RIterMut[T any](l *List[T]) *RevIterMut[T]
RIterMut returns a reverse iterator going from the end to the beginning with mutable pointers. Initially, the returned iterator is located at one step past the last element (one-past-last).
func (*RevIterMut[T]) Delete ¶
func (it *RevIterMut[T]) Delete()
Delete deletes the element that the iterator it is pointing to. Delete requires the iterator it to point to an actual element in the list. For example, it's not possible to call Delete on the RIterMut iterator (in its inital state) because this iterator is located at one step past the last element and this is not an actual list element. This function is O(1).
func (*RevIterMut[T]) HasNext ¶
func (it *RevIterMut[T]) HasNext() bool
func (*RevIterMut[T]) Insert ¶
func (it *RevIterMut[T]) Insert(elems ...T)
Insert inserts the given values next after (in a reverse direction) the iterator it. This function is O(len(elems)). So inserting a single element would be O(1).
func (*RevIterMut[T]) Next ¶
func (it *RevIterMut[T]) Next() *T
Source Files