seq

package
v0.9.4 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 18, 2023 License: Apache-2.0 Imports: 10 Imported by: 0

Documentation

Overview

Package seq provides single and double linked-list implementations and tools (e.g. heap, sorting, iterators) for using these structures.

All top level structures in this package can be trivially constructed and provide high level interfaces for most common operations. These structures are not safe for access from multiple concurrent go routines (see the queue/deque in the pubsub package as an alternative for these use cases.)

Index

Constants

This section is empty.

Variables

View Source 
var ErrUninitialized = errors.New("initialized container")

ErrUninitialized is the content of the panic produced when you attempt to perform an operation on an uninitialized sequence.

Functions

func IsSorted 

func IsSorted[T any](list *List[T], lt LessThan[T]) bool

IsSorted reports if the list is sorted from low to high, according to the LessThan function.

func LessThanCustom 

func LessThanCustom[T OrderableUser[T]](a, b T) bool

LessThanCustom converts types that implement OrderableUser interface.

func LessThanNative 

func LessThanNative[T Orderable](a, b T) bool

LessThanNative provides a wrapper around the < operator for types that support it, and can be used for sorting lists of compatible types.

func LessThanTime 

func LessThanTime(a, b time.Time) bool

LessThanTime compares time using the time.Time.Before() method.

func ListValues 

func ListValues[T any](in fun.Iterator[*Element[T]]) fun.Iterator[T]

ListValues converts an iterator of List Elements to an iterator of its values. The conversion does not have additional overhead relative to the original iterator, and only overides the behavior of the Value() method of the iterator.

func SortListMerge 

func SortListMerge[T any](list *List[T], lt LessThan[T])

SortListMerge sorts the list, using the provided comparison function and a Merge Sort operation. This is something of a novelty in most cases, as removing the elements from the list, adding to a slice and then using sort.Slice() from the standard library, and then re-adding those elements to the list, will perform better.

The operation will modify the input list, replacing it with an new list operation.

func SortListQuick 

func SortListQuick[T any](list *List[T], lt LessThan[T])

SortListQuick sorts the list, by removing the elements, adding them to a slice, and then using sort.SliceStable(). In many cases this performs better than the merge sort implementation.

func StackValues 

func StackValues[T any](in fun.Iterator[*Item[T]]) fun.Iterator[T]

StackValues converts an iterator of stack Items to an iterator of their values. The conversion does not have additional overhead relative to the original iterator, and only overides the behavior of the Value() method of the iterator.

Types

type Element 

type Element[T any] struct {
	// contains filtered or unexported fields
}

Element is the underlying component of a list, provided by iterators, the Pop operations, and the Front/Back accesses in the list. You can use the methods on this objects to iterate through the list, and the Ok() method for validating zero-valued items.

func NewElement 

func NewElement[T any](val T) *Element[T]

NewElement produces an unattached Element that you can use with Append. Element.Append(NewElement()) is essentially the same as List.PushBack().

func (*Element[T]) Append 

func (e *Element[T]) Append(new *Element[T]) *Element[T]

Append adds the element 'new' after the element 'e', inserting it in the next position in the list. Will return 'e' if 'new' is not valid for insertion into this list (e.g. it belongs to another list, or is attached to other elements, is already a member of this list, or is otherwise invalid.) PushBack and PushFront, are implemented in terms of Append.

func (*Element[T]) Drop 

func (e *Element[T]) Drop()

Drop wraps remove, and additionally, if the remove was successful, drops the value and sets the Ok value to false.

func (*Element[T]) In 

func (e *Element[T]) In(l *List[T]) bool

In checks to see if an element is in the specified list. Because elements hold a pointer to their list, this is an O(1) operation.

Returns false when the element is nil.

func (*Element[T]) MarshalJSON added in v0.3.2 

func (e *Element[T]) MarshalJSON() ([]byte, error)

MarshalJSON returns the result of json.Marshal on the value of the element. By supporting json.Marshaler and json.Unmarshaler, Elements and lists can behave as arrays in larger json objects, and can be as the output/input of json.Marshal and json.Unmarshal.

func (*Element[T]) Next 

func (e *Element[T]) Next() *Element[T]

Next produces the next element. This is always non-nil, *unless* the element is not a member of a list. At the ends of a list, the value is non-nil, but would return false for Ok.

func (*Element[T]) Ok 

func (e *Element[T]) Ok() bool

Ok checks that an element is valid. Invalid elements can be produced at the end of iterations (e.g. the list's root object,) or if you attempt to Pop an element off of an empty list.

Returns false when the element is nil.

func (*Element[T]) Previous 

func (e *Element[T]) Previous() *Element[T]

Previous produces the next element. This is always non-nil, *unless* the element is not a member of a list. At the ends of a list, the value is non-nil, but would return false for Ok.

func (*Element[T]) Remove 

func (e *Element[T]) Remove() bool

Remove removes the elemtn from the list, returning true if the operation was successful. Remove returns false when the element is not valid to be removed (e.g. is not part of a list, is the root element of the list, etc.)

func (*Element[T]) Set 

func (e *Element[T]) Set(v T) bool

Set allows you to change set the value of an item in place. Returns true if the operation is successful. The operation fails if the Element is the root item in a list or not a member of a list.

Set is safe to call on nil elements.

func (*Element[T]) String 

func (e *Element[T]) String() string

String returns the string form of the value of the element.

func (*Element[T]) Swap 

func (e *Element[T]) Swap(with *Element[T]) bool

Swap exchanges the location of two elements in a list, returning true if the operation was successful, and false if the elements are not eligable to be swapped. It is valid/possible to swap the root element of the list with another element to "move the head", causing a wrap around effect. Swap will not operate if either element is nil, or not a member of the same list.

func (*Element[T]) UnmarshalJSON added in v0.3.2 

func (e *Element[T]) UnmarshalJSON(in []byte) error

UnmarshalJSON reads the json value, and sets the value of the element to the value in the json, potentially overriding an existing value. By supporting json.Marshaler and json.Unmarshaler, Elements and lists can behave as arrays in larger json objects, and can be as the output/input of json.Marshal and json.Unmarshal.

func (*Element[T]) Value 

func (e *Element[T]) Value() T

Value accesses the element's value.

type Heap 

type Heap[T any] struct {
	LT LessThan[T]
	// contains filtered or unexported fields
}

Heap provides a min-order heap using the Heap.LT comparison operator to sort from lowest to highest. Push operations will panic if LT is not set.

func NewHeapFromIterator added in v0.9.4 

func NewHeapFromIterator[T any](ctx context.Context, cmp LessThan[T], iter fun.Iterator[T]) (*Heap[T], error)

NewHeapFromIterator constructs and populates a heap using the input iterator and corresponding comparison function. Will return the input iterators Close() error if one exists, and otherwise will return the populated heap.

func (*Heap[T]) Iterator 

func (h *Heap[T]) Iterator() fun.Iterator[T]

Iterator provides an fun.Iterator interface to the heap. The iterator consumes items from the heap, and will return when the heap is empty.

func (*Heap[T]) Len 

func (h *Heap[T]) Len() int

Len reports the size of the heap. Because the heap tracks its size with Push/Pop operations, this is a constant time operation.

func (*Heap[T]) Pop 

func (h *Heap[T]) Pop() (T, bool)

Pop removes the element from the underlying list and returns it, with an OK value, which is true when the value returned is valid.

func (*Heap[T]) Push 

func (h *Heap[T]) Push(t T)

Push adds an item to the heap.

type Item 

type Item[T any] struct {
	// contains filtered or unexported fields
}

Item is a common wrapper for the elements in a stack.

func NewItem 

func NewItem[T any](in T) *Item[T]

NewItem produces a valid Item object for the specified value.

func (*Item[T]) Append 

func (it *Item[T]) Append(n *Item[T]) *Item[T]

Append inserts a new item after the following item in the stack, returning the new item, or if the new item is not valid, the item itself.

func (*Item[T]) Attach 

func (it *Item[T]) Attach(stack *Stack[T]) bool

Attach removes items from the back of the stack and appends them to the current item. This inverts the order of items in the input stack.

func (*Item[T]) Detach 

func (it *Item[T]) Detach() *Stack[T]

Detach splits a stack into two, using the current Item as the head of the new stack. The output is always non-nil: if the item is not valid or not the member of a stack Detach creates a new empty stack. If this item is currently the head of a stack, Detach returns that stack.

func (*Item[T]) In 

func (it *Item[T]) In(s *Stack[T]) bool

In reports if an item is a member of a stack. Because item's track references to the stack, this is an O(1) operation.

func (*Item[T]) MarshalJSON added in v0.3.2 

func (it *Item[T]) MarshalJSON() ([]byte, error)

MarshalJSON returns the result of json.Marshal on the value of the item. By supporting json.Marshaler and json.Unmarshaler, Items and stacks can behave as arrays in larger json objects, and can be as the output/input of json.Marshal and json.Unmarshal.

func (*Item[T]) Next 

func (it *Item[T]) Next() *Item[T]

Next returns the following item in the stack.

func (*Item[T]) Ok 

func (it *Item[T]) Ok() bool

Ok return true if the Value() has been set. Returns false for incompletely initialized values.

Returns false when the item is nil.

func (*Item[T]) Remove 

func (it *Item[T]) Remove() bool

Remove removes the item from the stack, (at some expense, for items deeper in the stack.) If the operation isn't successful or possible the operation returns false.

func (*Item[T]) Set 

func (it *Item[T]) Set(v T) bool

Set mutates the value of an Item, returning true if the operation has been successful. The operation fails if the Item is the head item in a stack or not a member of a stack.

func (*Item[T]) String 

func (it *Item[T]) String() string

String implements fmt.Stringer, and returns the string value of the item's value.

func (*Item[T]) UnmarshalJSON added in v0.3.2 

func (it *Item[T]) UnmarshalJSON(in []byte) error

UnmarshalJSON reads the json value, and sets the value of the item to the value in the json, potentially overriding an existing value. By supporting json.Marshaler and json.Unmarshaler, Items and stacks can behave as arrays in larger json objects, and can be as the output/input of json.Marshal and json.Unmarshal.

func (*Item[T]) Value 

func (it *Item[T]) Value() T

Value returns the Item's underlying value. Use the Ok method to check the validity of the zero values.

type LessThan 

type LessThan[T any] func(a, b T) bool

LessThan describes a less than operation, typically provided by one of the following operations.

func LessThanConverter added in v0.9.4 

func LessThanConverter[T any, S Orderable](converter func(T) S) LessThan[T]

LessThanConverter provides a function to convert a non-orderable type to an orderable type. Use this for

func Reverse 

func Reverse[T any](fn LessThan[T]) LessThan[T]

Reverse wraps an existing LessThan operator and reverses it's direction.

type List 

type List[T any] struct {
	// contains filtered or unexported fields
}

List provides a doubly linked list. Callers are responsible for their own concurrency control and bounds checking, and should generally use with the same care as a slice.

The Deque implementation in the pubsub package provides a similar implementation with locking and a notification system.

func NewListFromIterator added in v0.9.4 

func NewListFromIterator[T any](ctx context.Context, iter fun.Iterator[T]) (*List[T], error)

NewListFromIterator builds a list from the elements in the iterator. In general, any error would be the result of the input iterators's close method.

func (*List[T]) Append added in v0.9.2 

func (l *List[T]) Append(items ...T)

Append adds a variadic sequence of items to the end of the list.

func (*List[T]) Back 

func (l *List[T]) Back() *Element[T]

Back returns a pointer to the last element of the list. If the list is empty, this is also the first element of the list. The operation is non-destructive. You can use this pointer to begin a c-style iteration over the list: 

for e := list.Back(); e.Ok(); e = e.Previous() {
       // operate
}

func (*List[T]) Copy 

func (l *List[T]) Copy() *List[T]

Copy duplicates the list. The element objects in the list are distinct, though if the Values are themsevles references, the values of both lists would be shared.

func (*List[T]) Extend 

func (l *List[T]) Extend(input *List[T])

Extend removes items from the front of the input list, and appends them to the end of the current list.

func (*List[T]) Front 

func (l *List[T]) Front() *Element[T]

Front returns a pointer to the first element of the list. If the list is empty, this is also the last element of the list. The operation is non-destructive. You can use this pointer to begin a c-style iteration over the list: 

for e := list.Front(); e.Ok(); e = e.Next() {
       // operate
}

func (*List[T]) Iterator 

func (l *List[T]) Iterator() fun.Iterator[*Element[T]]

Iterator returns an iterator that produces elements from the list, from the front to the back, compatible with the fun.Iterator interface and tools in fun/itertool. The Iterator is not synchronized with the values in the list, and will be exhausted when you reach the end of the list. To access an iterator of the *values* in the list, wrap this iterator using the seq.ListValues() function to produce an iterator over the values.

If you add values to the list during iteration *behind* where the iterator is, these values will not be present in the iterator; however, values added ahead of the iterator, will be visable.

func (*List[T]) IteratorPop 

func (l *List[T]) IteratorPop() fun.Iterator[*Element[T]]

IteratorPop produces an iterator that consumes elements from the list as it iterates, moving front to back. To access an iterator of the *values* in the list, wrap this iterator using the seq.ListValues() function to produce an iterator over the values.

If you add values to the list during iteration *behind* where the iterator is, these values will not be present in the iterator; however, values added ahead of the iterator, will be visible.

func (*List[T]) Len 

func (l *List[T]) Len() int

Len returns the length of the list. As the Append/Remove operations track the length of the list, this is an O(1) operation.

func (*List[T]) MarshalJSON added in v0.3.2 

func (l *List[T]) MarshalJSON() ([]byte, error)

MarshalJSON produces a JSON array representing the items in the list. By supporting json.Marshaler and json.Unmarshaler, Elements and lists can behave as arrays in larger json objects, and can be as the output/input of json.Marshal and json.Unmarshal.

func (*List[T]) PopBack 

func (l *List[T]) PopBack() *Element[T]

PopBack removes the last element from the list. If the list is empty, this returns a detached non-nil value, that will report an Ok() false value. You can use this element to produce a C-style iterator over the list, that removes items during the iteration: 

for e := list.PopBack(); e.Ok(); e = input.PopBack() {
	// do work
}

func (*List[T]) PopFront 

func (l *List[T]) PopFront() *Element[T]

PopFront removes the first element from the list. If the list is empty, this returns a nil value, that will report an Ok() false You can use this element to produce a C-style iterator over the list, that removes items during the iteration: 

for e := list.PopFront(); e.Ok(); e = input.PopFront() {
	// do work
}

func (*List[T]) PushBack 

func (l *List[T]) PushBack(it T)

PushBack creates an element and appends it to the list. The performance of PushFront and PushBack are the same.

func (*List[T]) PushFront 

func (l *List[T]) PushFront(it T)

PushFront creates an element and prepends it to the list. The performance of PushFront and PushBack are the same.

func (*List[T]) Reverse 

func (l *List[T]) Reverse() fun.Iterator[*Element[T]]

Reverse returns an iterator that produces elements from the list, from the back to the front, compatible with the fun.Iterator interface and tools in fun/itertool. The iterator is not synchronized with the values in the list, and will be exhausted when you reach the front of the list. To access an iterator of the *values* in the list, wrap this iterator using the seq.ListValues() function to produce an iterator over the values.

If you add values to the list during iteration *behind* where the iterator is, these values will not be present in the iterator; however, values added ahead of the iterator, will be visable.

func (*List[T]) ReversePop 

func (l *List[T]) ReversePop() fun.Iterator[*Element[T]]

ReversePop produces an iterator that consumes elements from the list as it iterates, moving front to back. To access an iterator of the *values* in the list, wrap this iterator using the seq.ListValues() function to produce an iterator over the values.

If you add values to the list during iteration *behind* where the iterator is, these values will not be present in the iterator; however, values added ahead of the iterator, will be visible.

func (*List[T]) UnmarshalJSON added in v0.3.2 

func (l *List[T]) UnmarshalJSON(in []byte) error

UnmarshalJSON reads json input and adds that to values in the list. If there are elements in the list, they are not removed. By supporting json.Marshaler and json.Unmarshaler, Elements and lists can behave as arrays in larger json objects, and can be as the output/input of json.Marshal and json.Unmarshal.

type Orderable 

type Orderable interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~float32 | ~float64 | ~string
}

Orderable describes all native types which (currently) support the < operator. To order custom types, use the OrderableUser interface.

In the future an equivalent oderable type specification is likely to enter the standard library, which will supercede this type.

type OrderableUser 

type OrderableUser[T any] interface{ LessThan(T) bool }

OrderableUser allows users to define a method on their types which implement a method to provide a LessThan operation.

type Stack 

type Stack[T any] struct {
	// contains filtered or unexported fields
}

Stack provides a generic singly linked list, with an interface that is broadly similar to seq.List.

func NewStackFromIterator added in v0.9.4 

func NewStackFromIterator[T any](ctx context.Context, iter fun.Iterator[T]) (*Stack[T], error)

NewListFromIterator builds a stack from the elements in the iterator. In general, any error would be the result of the input iterators's close method.

func (*Stack[T]) Append added in v0.9.2 

func (s *Stack[T]) Append(items ...T)

Append adds a variadic sequence of items to the list.

func (*Stack[T]) Head 

func (s *Stack[T]) Head() *Item[T]

Head returns the item at the top of this stack. This is a non destructive operation.

func (*Stack[T]) Iterator 

func (s *Stack[T]) Iterator() fun.Iterator[*Item[T]]

Iterator returns a non-destructive iterator over the Items in a stack. Iterator will not observe new items added to the stack during iteration.

func (*Stack[T]) IteratorPop 

func (s *Stack[T]) IteratorPop() fun.Iterator[*Item[T]]

IteratorPop returns a destructive iterator over the Items in a stack. IteratorPop will not observe new items added to the stack during iteration.

func (*Stack[T]) Len 

func (s *Stack[T]) Len() int

Len returns the length of the stack. Because stack's track their own size, this is an O(1) operation.

func (*Stack[T]) MarshalJSON added in v0.3.2 

func (s *Stack[T]) MarshalJSON() ([]byte, error)

MarshalJSON produces a JSON array representing the items in the stack. By supporting json.Marshaler and json.Unmarshaler, Items and stacks can behave as arrays in larger json objects, and can be as the output/input of json.Marshal and json.Unmarshal.

func (*Stack[T]) Pop 

func (s *Stack[T]) Pop() *Item[T]

Pop removes the item on the top of the stack, and returns it. If the stack is empty, this will return, but not detach, the root item of the stack, which will report a false Ok() value.

func (*Stack[T]) Push 

func (s *Stack[T]) Push(it T)

Push appends an item to the stack.

func (*Stack[T]) UnmarshalJSON added in v0.3.2 

func (s *Stack[T]) UnmarshalJSON(in []byte) error

UnmarshalJSON reads json input and adds that to values in the stack. If there are items in the stack, they are not removed. By supporting json.Marshaler and json.Unmarshaler, Items and stacks can behave as arrays in larger json objects, and can be as the output/input of json.Marshal and json.Unmarshal.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.