list

Documentation

Index

• type BasicList
• type PriorityQueue
  • func NewPrioirtyQueueCmp[T data.CmpOrdered[T]](order data.SortOrder) *PriorityQueue[T]
  • func NewPriorityQueue[T constraints.Ordered](order data.SortOrder) *PriorityQueue[T]
  • func NewPriorityQueueCustom[T any](order data.SortOrder, lessFunc data.LessFunc[data.Getter[T]]) *PriorityQueue[T]
  • func (q *PriorityQueue[T]) ChangeOrdering(lessFunc data.LessFunc[data.Getter[T]])
  • func (q *PriorityQueue[T]) IsEmpty() bool
  • func (q *PriorityQueue[T]) Len() int
  • func (q *PriorityQueue[T]) Less(i, j int) bool
  • func (q *PriorityQueue[T]) Pop() any
  • func (q *PriorityQueue[T]) Push(x any)
  • func (q *PriorityQueue[T]) Swap(i, j int)
• type QueueImpl
  • func NewQueue[T any]() *QueueImpl[T]
  • func (s *QueueImpl[T]) IsEmpty() bool
  • func (s *QueueImpl[T]) Len() int
  • func (s *QueueImpl[T]) Pop() *T
  • func (s *QueueImpl[T]) Push(x T)
  • func (s *QueueImpl[T]) PushSlice(slice []T)
• type SafeList
  • func NewQueueSafe[T any]() SafeList[T, *QueueImpl[T]]
  • func NewStackSafe[T any]() SafeList[T, *StackImpl[T]]
• type SafeListWrapper
  • func WrapSafeList[T any, L BasicList[T]](basicList L) *SafeListWrapper[T, L]
  • func (w *SafeListWrapper[T, L]) IsEmpty() bool
  • func (w *SafeListWrapper[T, L]) IsSafe() bool
  • func (w *SafeListWrapper[T, L]) Len() int
  • func (w *SafeListWrapper[T, L]) Pop() *T
  • func (w *SafeListWrapper[T, L]) Push(x T)
  • func (w *SafeListWrapper[T, L]) PushSlice(x []T)
• type SafeSetList
• type SetList
  • func ToSetList[T comparable](src []T) SetList[T, *SetListImpl[T]]
• type SetListImpl
  • func NewSetList[T comparable]() *SetListImpl[T]
  • func (s *SetListImpl[T]) HasDuplicate(x T) bool
  • func (s *SetListImpl[T]) IsEmpty() bool
  • func (s *SetListImpl[T]) Len() int
  • func (s *SetListImpl[T]) Pop() *T
  • func (s *SetListImpl[T]) Push(x T)
  • func (s *SetListImpl[T]) PushSlice(slice []T)
• type SetListWrapper
  • func WrapSetListKeepInner[T comparable](inner BasicList[T]) *SetListWrapper[T, BasicList[T]]
  • func (s *SetListWrapper[T, L]) HasDuplicate(x T) bool
  • func (s *SetListWrapper[T, L]) Inner() L
  • func (s *SetListWrapper[T, L]) IsEmpty() bool
  • func (s *SetListWrapper[T, L]) Len() int
  • func (s *SetListWrapper[T, L]) Pop() *T
  • func (s *SetListWrapper[T, L]) Push(x T)
  • func (s *SetListWrapper[T, L]) PushSlice(values []T)
• type StackImpl
  • func NewStack[T any]() *StackImpl[T]
  • func (s *StackImpl[T]) IsEmpty() bool
  • func (s *StackImpl[T]) Len() int
  • func (s *StackImpl[T]) Pop() *T
  • func (s *StackImpl[T]) Push(x T)
  • func (s *StackImpl[T]) PushSlice(slice []T)
• type WrappedList

Types

type BasicList

type BasicList[T any] interface {
	Push(x T)
	PushSlice(values []T)
	Pop() *T
	Len() int
	IsEmpty() bool
}

type PriorityQueue

type PriorityQueue[T any] struct {
	Items    []data.Getter[T]
	LessFunc data.LessFunc[data.Getter[T]]
}

PriorityQueue[T] wraps items []T and implements Go's heap.Interface. tree.Heap is an alternative implementation with gsl's implementation of heaps.

func NewPrioirtyQueueCmp

func NewPrioirtyQueueCmp[T data.CmpOrdered[T]](order data.SortOrder) *PriorityQueue[T]

NewPrioirtyQueueCmp[T] returns *PriorityQueue[data.CmpOrdered[T]] with the default lessFunc for type T with Cmp(T), i.e. -1 -> less, 0 -> equal, 1 -> greater.

func NewPriorityQueue

func NewPriorityQueue[T constraints.Ordered](order data.SortOrder) *PriorityQueue[T]

func NewPriorityQueueCustom

func NewPriorityQueueCustom[T any](
	order data.SortOrder,
	lessFunc data.LessFunc[data.Getter[T]],
) *PriorityQueue[T]

NewPriorityQueueCustom use the provided lessFunc for the heapify processes.

func (*PriorityQueue[T]) ChangeOrdering

func (q *PriorityQueue[T]) ChangeOrdering(lessFunc data.LessFunc[data.Getter[T]])

func (*PriorityQueue[T]) IsEmpty

func (q *PriorityQueue[T]) IsEmpty() bool

func (*PriorityQueue[T]) Len

func (q *PriorityQueue[T]) Len() int

func (*PriorityQueue[T]) Less

func (q *PriorityQueue[T]) Less(i, j int) bool

func (*PriorityQueue[T]) Pop

func (q *PriorityQueue[T]) Pop() any

func (*PriorityQueue[T]) Push

func (q *PriorityQueue[T]) Push(x any)

func (*PriorityQueue[T]) Swap

func (q *PriorityQueue[T]) Swap(i, j int)

type QueueImpl

type QueueImpl[T any] []T

func NewQueue

func NewQueue[T any]() *QueueImpl[T]

func (*QueueImpl[T]) IsEmpty

func (s *QueueImpl[T]) IsEmpty() bool

func (*QueueImpl[T]) Len

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

func (*QueueImpl[T]) Pop

func (s *QueueImpl[T]) Pop() *T

Pop pops and returns the left-most element of self, returning nil if self is empty

func (*QueueImpl[T]) Push

func (s *QueueImpl[T]) Push(x T)

func (*QueueImpl[T]) PushSlice

func (s *QueueImpl[T]) PushSlice(slice []T)

type SafeList

type SafeList[T any, L BasicList[T]] WrappedList[T, L]

Use SafeList as parameter in function where concurrency is used.

func NewQueueSafe

func NewQueueSafe[T any]() SafeList[T, *QueueImpl[T]]

func NewStackSafe

func NewStackSafe[T any]() SafeList[T, *StackImpl[T]]

type SafeListWrapper

type SafeListWrapper[T any, L BasicList[T]] struct {
	// contains filtered or unexported fields
}

SafeListWrapper[T] wraps BasicList[T] and uses sync.RWMutex to avoid data races. L was added to make sure that the underlying list type is always accessible from the instance type, for example, SafeListWrapper[float64, *Queue[float64]] if L was not the type parameter, then a safe uint8 stack, safe uint8 queue, etc, will be indifferentiable with the same type `SafeListWrapper[uint8]`. SafeListWrapper[T, BasicList[T]] also implements BasicList[T]

func WrapSafeList

func WrapSafeList[T any, L BasicList[T]](basicList L) *SafeListWrapper[T, L]

WrapSafeList[T] wraps a BasicList[T] into SafeListWrapper[T], where T is the underlying entity (item) type and L is the underlying BasicList[T] type. If you're wrapping a variable `foo“ of type `*Stack[uint8]`, then call this function with: WrapSafeList[uint8, *Stack[uint8]](foo)

func (*SafeListWrapper[T, L]) IsEmpty

func (w *SafeListWrapper[T, L]) IsEmpty() bool

func (*SafeListWrapper[T, L]) IsSafe

func (w *SafeListWrapper[T, L]) IsSafe() bool

func (*SafeListWrapper[T, L]) Len

func (w *SafeListWrapper[T, L]) Len() int

func (*SafeListWrapper[T, L]) Pop

func (w *SafeListWrapper[T, L]) Pop() *T

func (*SafeListWrapper[T, L]) Push

func (w *SafeListWrapper[T, L]) Push(x T)

func (*SafeListWrapper[T, L]) PushSlice

func (w *SafeListWrapper[T, L]) PushSlice(x []T)

type SafeSetList

type SafeSetList[T comparable, L BasicList[T]] SafeList[T, SetList[T, L]]

TODO: WTF?

type SetList

type SetList[T comparable, L BasicList[T]] interface {
	WrappedList[T, L]
	data.Set[T]
}

Use SetList as parameter in function where you'll need characteristics of a set.

func ToSetList

func ToSetList[T comparable](src []T) SetList[T, *SetListImpl[T]]

ToSetList iterates over src T and push it to a new SetListImpl[T]

type SetListImpl

type SetListImpl[T comparable] struct {
	// contains filtered or unexported fields
}

SetListImpl implements SetList[T, L] and BasicList[T]

A *set list* is a list (implements BasicList[T]) that has characteristics of a set. No duplicate is allowed in a set list.

If you want set functionality for other types, e.g., for QueueImpl[T], then you can wrap the queue using WrapSetList(l BasicList[T]) to get a SetList[T, *QueueImpl[T]].

func NewSetList

func NewSetList[T comparable]() *SetListImpl[T]

func (*SetListImpl[T]) HasDuplicate

func (s *SetListImpl[T]) HasDuplicate(x T) bool

func (*SetListImpl[T]) IsEmpty

func (s *SetListImpl[T]) IsEmpty() bool

func (*SetListImpl[T]) Len

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

func (*SetListImpl[T]) Pop

func (s *SetListImpl[T]) Pop() *T

func (*SetListImpl[T]) Push

func (s *SetListImpl[T]) Push(x T)

func (*SetListImpl[T]) PushSlice

func (s *SetListImpl[T]) PushSlice(slice []T)

type SetListWrapper

type SetListWrapper[T comparable, L BasicList[T]] struct {
	// contains filtered or unexported fields
}

SetListWrapper wraps BasicList[T] into field `basicList`, and maintains a hash map of seen items and the basicList length so that determining duplicates and getting the length take O(1) time.

func WrapSetListKeepInner

func WrapSetListKeepInner[T comparable](inner BasicList[T]) *SetListWrapper[T, BasicList[T]]

WrapSetListKeepInner returns a SetListWrapper over inner. It does not remove duplicates in inner - only elements pushed thereafter are checked against the hash table.

func (*SetListWrapper[T, L]) HasDuplicate

func (s *SetListWrapper[T, L]) HasDuplicate(x T) bool

O(1)

func (*SetListWrapper[T, L]) Inner

func (s *SetListWrapper[T, L]) Inner() L

func (*SetListWrapper[T, L]) IsEmpty

func (s *SetListWrapper[T, L]) IsEmpty() bool

func (*SetListWrapper[T, L]) Len

func (s *SetListWrapper[T, L]) Len() int

func (*SetListWrapper[T, L]) Pop

func (s *SetListWrapper[T, L]) Pop() *T

func (*SetListWrapper[T, L]) Push

func (s *SetListWrapper[T, L]) Push(x T)

func (*SetListWrapper[T, L]) PushSlice

func (s *SetListWrapper[T, L]) PushSlice(values []T)

type StackImpl

type StackImpl[T any] []T

func NewStack

func NewStack[T any]() *StackImpl[T]

func (*StackImpl[T]) IsEmpty

func (s *StackImpl[T]) IsEmpty() bool

func (*StackImpl[T]) Len

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

func (*StackImpl[T]) Pop

func (s *StackImpl[T]) Pop() *T

Pop pops and returns the right-most element of self, returning nil if self is empty

func (*StackImpl[T]) Push

func (s *StackImpl[T]) Push(x T)

func (*StackImpl[T]) PushSlice

func (s *StackImpl[T]) PushSlice(slice []T)

type WrappedList

type WrappedList[T any, L BasicList[T]] BasicList[T]