README
¶
Collection
Collection is a Go library that aims to implement basic data structures such as List, Queue, Stack, Heap, and more.
Data Structures
- Linked list is implemented as a doubly linked list.
- Stack is implemented by using linked list as the base.
- Queue is implemented by using linked list as the base.
- Heap is implemented by using slice as the base.
Caches
Documentation
¶
Overview ¶
Collection is a Go library that aims to implement basic data structures such as List, Queue, Stack, Heap, and more.
Index ¶
- Variables
- func GreaterThan[T Orderable](current, other T) bool
- func GreaterThanOrEqual[T Orderable](current, other T) bool
- func LessThan[T Orderable](current, other T) bool
- func LessThanOrEqual[T Orderable](current, other T) bool
- func Must[T any](f func() (T, error)) T
- type Heap
- type List
- func (l *List[T]) All() iter.Seq2[int, T]
- func (l *List[T]) Append(values ...T)
- func (l *List[T]) Backward() iter.Seq2[int, T]
- func (l *List[T]) Dequeue() (T, error)
- func (l *List[T]) Head() *internal.Node[T]
- func (l *List[T]) Index(at int) (T, error)
- func (l *List[T]) Insert(value T, after int) error
- func (l *List[T]) Length() int
- func (l *List[T]) Pop() (T, error)
- func (l *List[T]) Prepend(values ...T)
- func (l *List[T]) Remove(at int) (T, error)
- func (l *List[T]) Search(target T, equal func(value, target T) bool) (int, error)
- type Orderable
- type Queue
- type Stack
- Bugs
Constants ¶
This section is empty.
Variables ¶
Functions ¶
func GreaterThan ¶ added in v0.4.0
Greater than, can be use as cmp function of Heap to create a max heap.
func GreaterThanOrEqual ¶ added in v0.4.0
Greater than or equal, can be use as cmp function of Heap to create a max heap.
func LessThanOrEqual ¶ added in v0.4.0
Less than or equal, can be use as cmp function of Heap to create a min heap.
Types ¶
type Heap ¶ added in v0.4.0
type Heap[T any] struct { // contains filtered or unexported fields }
A Heap implemented using slice, a dynamic array implementation, as the base. Heap is thread-safe, because it only allow one goroutine at a time to access it data.
func MustNewHeap ¶ added in v0.4.0
Like NewHeap but will panic if cmp is nil.
func NewHeap ¶ added in v0.4.0
NewHeap creates a new Heap. It takes a function that compares two values. During swim/heapify-up and sink/heapify-down operation if the function returns true, then the nodes will be swapped with eachother. This will return an error if cmp is nil, if you want to panic instead use MustNewHeap.
For example a max Heap[int] would need:
func maxHeapCmp(current, other int) {
return current >= other
}
A min Heap[int] would need:
func mimHeapCmp(current, other int) {
return current <= other
}
func (*Heap[T]) Pop ¶ added in v0.4.0
Get a value at the root node, and remove it from the Heap. Returns ErrIsEmpty if the Heap is empty.
func (*Heap[T]) Push ¶ added in v0.4.0
func (h *Heap[T]) Push(values ...T)
Push values into the Heap.
type List ¶
type List[T any] struct { // contains filtered or unexported fields }
List is a doubly linked list implementation. All operation on List is thread-safe, because it only allow one goroutine at a time to access it data.
func NewList ¶
NewList creates a new doubly linked List. All operation on List should be thread-safe, because it only allow one goroutine at a time to access it data.
emptyList := New[int]() initializedList := New(1, 2, 3, 4, 5)
func (*List[T]) All ¶
All return an iterator of elements in list going from head to tail. The iterator returns the index and value of the node.
for idx, val := range list.All() {
// code goes here
}
func (*List[T]) Append ¶
func (l *List[T]) Append(values ...T)
Append adds new nodes to at the end of the list
func (*List[T]) Backward ¶
Backward return an iterator of elements in list going from tail to head. The iterator returns the index and value of the node.
for idx, val := range list.Backward() {
// code goes here
}
func (*List[T]) Dequeue ¶
Dequeue removes and returns the first element of the list. If the list is empty then return ErrIsEmpty as an error.
func (*List[T]) Head ¶ added in v0.5.0
Return the head node of the List.
BUG(trviph): This function is needed by the cache package, but is leaks internal.Node to the users. We could either find a way to remove this or could just ignore this.
func (*List[T]) Index ¶
Index gets value at the specified index. If the index is out of range, it will return ErrIndexOutOfRange as error.
func (*List[T]) Insert ¶
Insert adds a new node after the node at a specified index. If the index is less than zero or greater than or equal the current length of the list, then this function will return an ErrIndexOutOfRange error. If you want to insert at the start of the list use List.Prepend instead.
func (*List[T]) Pop ¶
Pop removes and returns the last element of the list. If the list is empty then return ErrIsEmpty as an error.
func (*List[T]) Prepend ¶
func (l *List[T]) Prepend(values ...T)
Prepend adds a new node at the start of the list.
func (*List[T]) Remove ¶
Remove removes and returns the element at the specified index of the list. If the index is out of range then return ErrIndexOutOfRange as an error. Or if the list is empty then return ErrIsEmpty as an error.
func (*List[T]) Search ¶
Search searches for a value in the list. It takes the target to search for and the equal function. The equal function takes two arguments value and target, it should return true if the two arguments is considered to be equal.
It returns an index greater or equal to zero and a nil error if the value existed inside the list, else return the index of -1 and error of ErrNotFound.
type user struct {
name string
}
func main() {
user1 := user{name: "User 1"}
user2 := user{name: "User 2"}
users := NewList(user1, user2)
equal := func (value, target user) bool {
return value.name == target.name
}
idx, err := users.Search(user1, equal)
// code goes here
}
type Orderable ¶ added in v0.4.0
type Orderable interface {
int | int8 | int16 | int32 | int64 |
uint | uint8 | uint16 | uint32 | uint64 |
float32 | float64 | string
}
Orderable are types that support the following operations
- Equal
- Not equal
- Less than
- Less than or equal
- Greater than
- Greater than or equal
type Queue ¶ added in v0.3.0
type Queue[T any] struct { // contains filtered or unexported fields }
A first-in-first-out Queue implemented by using List as the base. Since List is thread-safe, Queue should also be thread-safe.
func (*Queue[T]) Dequeue ¶ added in v0.3.0
Dequeue get the value from the front of the queue, and remove it from the queue. If the queue is empty return ErrIsEmpty as an error.
func (*Queue[T]) Front ¶ added in v0.3.0
Front get the value from the front but does not remove it from the queue. If the queue is empty return ErrIsEmpty as an error.
func (*Queue[T]) Push ¶ added in v0.3.0
func (q *Queue[T]) Push(values ...T)
Push a list of values in to the queue, starting from left to right.
func (*Queue[T]) Rear ¶ added in v0.3.0
Rear get the value from the rear/end but does not remove it from the queue. If the queue is empty return ErrIsEmpty as an error.
type Stack ¶ added in v0.2.0
type Stack[T any] struct { // contains filtered or unexported fields }
A first-in-last-out Stack implemented by using List as the base. Since List is thread-safe, Stack should also be thread-safe.
func (*Stack[T]) Pop ¶ added in v0.2.0
Pop get the value of the last push, and remove the value from the stack. If the stack is empty return ErrIsEmpty as an error.
func (*Stack[T]) Push ¶ added in v0.2.0
func (s *Stack[T]) Push(values ...T)
Push a list of values in to the stack, starting from left to right.
func (*Stack[T]) Top ¶ added in v0.2.0
Top get the value of the last push but does not remove the value from the stack. If the stack is empty return ErrIsEmpty as an error.
Notes ¶
Bugs ¶
This function is needed by the cache package, but is leaks internal.Node to the users. We could either find a way to remove this or could just ignore this.
Source Files
Directories