Documentation
¶
Overview ¶
Package ds provides various data structure implementations with generics.
Prior to Go 1.18, such data structures could not be implemented in a satisfactory way, as one had to use interfaces, which ofter resulted in unreadable code, memory allocations and conditions for unexpected panics.
Now that Go has generics, this package provides some common data structures that make use of this new language feature.
Index ¶
- type Heap
- type List
- func (l *List[T]) Add(item T)
- func (l *List[T]) Clear()
- func (l *List[T]) Clip()
- func (l *List[T]) Contains(item T) bool
- func (l *List[T]) Each(iterator func(item T))
- func (l *List[T]) Equals(other *List[T]) bool
- func (l *List[T]) Get(index int) T
- func (l *List[T]) IndexOf(item T) int
- func (l *List[T]) IsEmpty() bool
- func (l *List[T]) Items() []T
- func (l *List[T]) Remove(item T) bool
- func (l *List[T]) Set(index int, value T)
- func (l *List[T]) Size() int
- func (l *List[T]) Unbox() []T
- type Pool
- type Set
- func NewSet[T comparable](initialCapacity int) *Set[T]
- func SetDifference[T comparable](first, second *Set[T]) *Set[T]
- func SetFromMapKeys[T comparable, V any](m map[T]V) *Set[T]
- func SetFromMapValues[K comparable, V comparable](m map[K]V) *Set[V]
- func SetFromSlice[T comparable](slice []T) *Set[T]
- func SetIntersection[T comparable](first, second *Set[T]) *Set[T]
- func SetUnion[T comparable](first, second *Set[T]) *Set[T]
- func (s *Set[T]) Add(item T) bool
- func (s *Set[T]) AddSet(other *Set[T]) bool
- func (s *Set[T]) Clear()
- func (s *Set[T]) Clip()
- func (s *Set[T]) Contains(item T) bool
- func (s *Set[T]) ContainsSet(other *Set[T]) bool
- func (s *Set[T]) Equals(other *Set[T]) bool
- func (s *Set[T]) IsEmpty() bool
- func (s *Set[T]) Items() []T
- func (s *Set[T]) Remove(item T) bool
- func (s *Set[T]) RemoveSet(other *Set[T]) bool
- func (s *Set[T]) Size() int
- func (s *Set[T]) Unbox() map[T]struct{}
- type Stack
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Heap ¶
type Heap[T any] struct { // contains filtered or unexported fields }
Heap is a data structure that orders items when inserted according to a specified ordering.
Example ¶
package main
import (
"fmt"
"github.com/mokiat/gog/ds"
)
func main() {
heap := ds.NewHeap(0, func(a, b int) bool {
return a < b
})
heap.Push(100)
heap.Push(20)
heap.Push(50)
heap.Push(13)
heap.Push(300)
fmt.Println(heap.Pop())
fmt.Println(heap.Pop())
fmt.Println(heap.Pop())
fmt.Println(heap.Pop())
fmt.Println(heap.Pop())
}
Output: 13 20 50 100 300
func NewHeap ¶
NewHeap creates a new Heap instance that is configured to use the specified better function to order items. When better returns true, the first argument will be placed higher in the heap. The specified initialCapacity is used to preallocate memory.
func (*Heap[T]) IsEmpty ¶
IsEmpty returns true if there are no items in this Heap and false otherwise.
func (*Heap[T]) Peek ¶
func (h *Heap[T]) Peek() T
Peek returns the top-most item from this Heap without removing it. This method panics if the Heap is empty so make sure to use IsEmpty beforehand.
type List ¶
type List[T comparable] struct { // contains filtered or unexported fields }
List represents a sequence of items.
Currently a List can only store comparable items. This restriction allows for Remove, IndexOf and Contains operations.
Example ¶
package main
import (
"fmt"
"github.com/mokiat/gog/ds"
)
func main() {
list := ds.NewList[string](0)
list.Add("first")
list.Add("second")
list.Add("third")
list.Add("fourth")
list.Remove("second")
list.Remove("third")
fmt.Printf("%#v\n", list.Items())
}
Output: []string{"first", "fourth"}
func ListFromSlice ¶ added in v0.11.0
func ListFromSlice[T comparable](items []T) *List[T]
ListFromSlice constructs a new List that is based on the items from the specified slice.
It is safe to modify the slice afterwards, as the list creates its own internal copy.
func NewList ¶
func NewList[T comparable](initialCapacity int) *List[T]
NewList creates a new List with the given capacity. The capacity can be used as a form of optimization. Regardless of the value, the initial size of the list is zero and the list can grow past the specified capacity.
func (*List[T]) Contains ¶
Contains checks whether this List has the specified item and returns true if it is contained and false otherwise.
func (*List[T]) Each ¶
func (l *List[T]) Each(iterator func(item T))
Each is a helper method allows one to iterate over all items in this List through a closure function.
func (*List[T]) Equals ¶ added in v0.11.0
Equals returns whether this list matches exactly the provided list.
func (*List[T]) Get ¶
Get returns the item in this list that is located at the specified index (starting from zero).
This method will panic if the index is outside the list bounds.
func (*List[T]) IndexOf ¶
IndexOf returns the index where the specified item is located in this List. If the item is not part of this list, this method returns -1.
func (*List[T]) Items ¶
func (l *List[T]) Items() []T
Items returns all items stored in this List as a slice. It is safe to mutate the returned slice as it is a copy of the inner representation.
If performance is needed, consider using Unbox method instead.
func (*List[T]) Remove ¶
Remove removes the specified item from this List and returns true. If the item is not contained by this List, then false is returned.
func (*List[T]) Set ¶ added in v0.11.0
Set modifies the item at the specified index.
This method will panic if the index is outside the list bounds.
func (*List[T]) Unbox ¶ added in v0.11.0
func (l *List[T]) Unbox() []T
Unbox provides direct access to the inner representation of the list. The returned slice should not be modified, otherwise there is a risk that the List might not work correctly afterwards. Even if it works now, a future version might break that behavior.
This method should only be used when performance is critical and memory allocation is not desired.
type Pool ¶ added in v0.8.0
type Pool[T any] struct { // contains filtered or unexported fields }
Pool represents a storage structure that can preseve allocated objects for faster reuse.
Example ¶
package main
import (
"bytes"
"fmt"
"github.com/mokiat/gog/ds"
)
func main() {
pool := ds.NewPool[bytes.Buffer]()
buffer := pool.Fetch()
buffer.Reset()
buffer.WriteString("this buffer is mine")
pool.Restore(buffer)
newBuffer := pool.Fetch()
// newBuffer.Reset() // commented out to show that the instance is reused
fmt.Println(newBuffer.String())
}
Output: this buffer is mine
func (*Pool[T]) Clear ¶ added in v0.8.0
func (p *Pool[T]) Clear()
Clear removes any items that were stored for reuse.
func (*Pool[T]) Fetch ¶ added in v0.8.0
func (p *Pool[T]) Fetch() *T
Fetch retrieves an available item from the pool or creates a new one if one is not available.
type Set ¶
type Set[T comparable] struct { // contains filtered or unexported fields }
Set represents a set data structure, where only one instance of a given item is stored.
Note: Using the standard map[T]struct{} approach will likely yield faster performance and should be preferred in performance-critical code. This type makes usage of sets more human-readable.
Example ¶
package main
import (
"fmt"
"github.com/mokiat/gog/ds"
)
func main() {
set := ds.NewSet[int](0)
set.Add(2)
set.Add(3)
set.Add(5)
set.Add(7)
fmt.Println(set.Contains(2))
fmt.Println(set.Contains(10))
fmt.Println(set.Contains(5))
fmt.Println(set.Contains(8))
}
Output: true false true false
func NewSet ¶
func NewSet[T comparable](initialCapacity int) *Set[T]
NewSet creates a new Set instance with the specified initial capacity, which is only used to preallocate memory and does not act as an upper bound.
func SetDifference ¶ added in v0.6.0
func SetDifference[T comparable](first, second *Set[T]) *Set[T]
SetDifference creates a new Set that holds the difference between the first and the second specified sets.
func SetFromMapKeys ¶ added in v0.5.0
func SetFromMapKeys[T comparable, V any](m map[T]V) *Set[T]
SetFromMapKeys creates a new Set instance based on the keys of the provided map.
func SetFromMapValues ¶ added in v0.5.0
func SetFromMapValues[K comparable, V comparable](m map[K]V) *Set[V]
SetFromMapValues creates a new Set instance based on the values of the provided map.
func SetFromSlice ¶ added in v0.5.0
func SetFromSlice[T comparable](slice []T) *Set[T]
SetFromSlice creates a new Set instance based on the elements contained in the provided slice.
func SetIntersection ¶ added in v0.6.0
func SetIntersection[T comparable](first, second *Set[T]) *Set[T]
SetIntersection creates a new Set that holds the intersection of the items of the two specified sets.
func SetUnion ¶ added in v0.6.0
func SetUnion[T comparable](first, second *Set[T]) *Set[T]
SetUnion creates a new Set that is the union of the specified sets.
func (*Set[T]) Add ¶
Add adds the specified item to this Set if it was not present already. This method returns true if the operation was performed and false if the item was aleady present.
func (*Set[T]) AddSet ¶ added in v0.6.0
AddSet adds the items of another Set to this Set. The operation returns true if the operation resulted in a change and false otherwise.
func (*Set[T]) ContainsSet ¶ added in v0.6.0
ContainsSet returns whether this set fully contains another set.
func (*Set[T]) Equals ¶ added in v0.11.0
Equals return whether this set is equal to the provided set.
func (*Set[T]) Items ¶
func (s *Set[T]) Items() []T
Items returns a slice containing all of the items from this Set.
Note: The items are returned in a random order which can differ between subsequent calls.
func (*Set[T]) Remove ¶
Remove removes the specified item from this Set. This method returns true if there was in fact such an item to be removed and false otherwise.
func (*Set[T]) RemoveSet ¶ added in v0.6.0
RemoveSet removes the items of another Set from this Set. The operation returns true if the operation resulted in a change and false otherwise.
func (*Set[T]) Unbox ¶ added in v0.11.0
func (s *Set[T]) Unbox() map[T]struct{}
Unbox provides direct access to the inner representation of the set. The returned map should not be modified, otherwise there is a risk that the Set might not work correctly afterwards. Even if it works now, a future version might break that behavior.
This method should only be used when performance is critical and memory allocation is not desired.
type Stack ¶
type Stack[T any] struct { // contains filtered or unexported fields }
Stack is an implementation of a stack data structure. The last inserted item is the first one to be removed (LIFO - last in, first out).
Example ¶
package main
import (
"fmt"
"github.com/mokiat/gog/ds"
)
func main() {
stack := ds.NewStack[string](3)
stack.Push("first")
stack.Push("second")
stack.Push("third")
fmt.Println(stack.Pop())
fmt.Println(stack.Pop())
fmt.Println(stack.Pop())
}
Output: third second first
func NewStack ¶
NewStack creates a new Stack instance with the specified initial capacity, which only serves to preallocate memory. Exceeding the initial capacity is allowed.
func (*Stack[T]) Peek ¶
func (s *Stack[T]) Peek() T
Peek returns the item that is at the top of the Stack without removing it. Make sure that the Stack is not empty, otherwise this method will panic.
Source Files