README
¶
Collections
Generics-based, collection based data structures. Some of the collections provide thread-safe versions.
These data structures are based on Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. All credit for the algorithms goes to the authors.
The package currently has the following data structures (all generics-based):
- MaxPQ - A basic max heap.
- ConcurrentMaxPQ - Thread-safe max heap.
- RBTree - An implementation of a red-black tree.
- Set - A basic implementation of a collection with properties of a Set and allowing Set operations.
Documentation
¶
Index ¶
- type Color
- type Comparable
- type Comparator
- type CompareFn
- type ConcurrentMaxPQ
- type MaxPQ
- type Node
- type RBTree
- func (t *RBTree[K, V]) Delete(key K)
- func (t *RBTree[K, V]) DeleteMax()
- func (t *RBTree[K, V]) DeleteMin()
- func (t *RBTree[K, V]) Get(key K) (V, bool)
- func (t *RBTree[K, V]) Has(key K) bool
- func (t *RBTree[K, V]) Height() int
- func (t *RBTree[K, V]) IsEmpty() bool
- func (t *RBTree[K, V]) Keys() []K
- func (t *RBTree[K, V]) Max() *Node[K, V]
- func (t *RBTree[K, V]) Min() *Node[K, V]
- func (t *RBTree[K, V]) Put(key K, val V)
- func (t *RBTree[K, V]) Rank(key K) int
- func (t *RBTree[K, V]) Size() int
- type Set
- func (s *Set[T]) Add(e T)
- func (s *Set[T]) Contains(e T) bool
- func (s *Set[T]) Difference(s2 *Set[T]) *Set[T]
- func (s *Set[T]) Index(e T) int
- func (s *Set[T]) Intersection(s2 *Set[T]) *Set[T]
- func (s *Set[T]) IsDisjoint(s2 *Set[T]) bool
- func (s *Set[T]) IsSubsetOf(s2 *Set[T]) bool
- func (s *Set[T]) Items() []T
- func (s *Set[T]) Size() int
- func (s *Set[T]) Union(s2 *Set[T])
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Comparator ¶
type Comparator[T comparable] func(o1, o2 T) int
Comparator is a function that compares two objects o1 and o2 of type T and returns an integer. The comparator is used by the Heap to compare custom objects (non primitives).
It should return a -ve number if o1 < o2, 0 if o1 == o2 and +ve number if o1 > o2.
type CompareFn ¶
type CompareFn[K Comparable] func(key1, key2 K) int
type ConcurrentMaxPQ ¶
type ConcurrentMaxPQ[T comparable] struct { *MaxPQ[T] // contains filtered or unexported fields }
ConcurrentMaxPQ is the thread-safe version of MaxPQ. All operations of this type are thread-safe.
func NewConcurrentMaxPQ ¶
func NewConcurrentMaxPQ[T comparable](capacity uint, compareFn Comparator[T]) *ConcurrentMaxPQ[T]
func (*ConcurrentMaxPQ[T]) DelMax ¶
func (pq *ConcurrentMaxPQ[T]) DelMax() T
DelMax returns the current max element and deletes it from the collection.
func (*ConcurrentMaxPQ[T]) Insert ¶
func (pq *ConcurrentMaxPQ[T]) Insert(item T)
Insert inserts the given element in the collection.
func (*ConcurrentMaxPQ[T]) PeekMax ¶
func (pq *ConcurrentMaxPQ[T]) PeekMax() T
PeekMax returns the current max/head element.
type MaxPQ ¶
type MaxPQ[T comparable] struct { Comparator Comparator[T] // contains filtered or unexported fields }
MaxPQ is an implementation of Max Heap with generics support.
The implementation is not thread-safe. For a thread-safe implementation, use ConcurentMaxPQ.
func NewMaxPQ ¶
func NewMaxPQ[T comparable](capacity uint, compareFn Comparator[T]) *MaxPQ[T]
func (*MaxPQ[T]) DelMax ¶
func (pq *MaxPQ[T]) DelMax() T
DelMax returns the current max element and deletes it from the collection.
type Node ¶
type Node[K Comparable, V any] struct { // contains filtered or unexported fields }
type RBTree ¶
type RBTree[K Comparable, V any] struct { // contains filtered or unexported fields }
func New ¶
func New[K Comparable, V any]() *RBTree[K, V]
func NewWithComparator ¶
func NewWithComparator[K Comparable, V any](compareFn CompareFn[K]) *RBTree[K, V]
type Set ¶
type Set[T comparable] struct { // contains filtered or unexported fields }
Set provides a collection with no duplicates.
func FromArray ¶
func FromArray[T comparable](a []T) *Set[T]
FromArray creates a new set from the given array/slice.
func NewSet ¶
func NewSet[T comparable](initialSize int) *Set[T]
NewSet creates and returns a new set with the given initial capacity.
func (*Set[T]) Add ¶
func (s *Set[T]) Add(e T)
Add adds the given element to the set. If the element already exists, it is a no-op.
func (*Set[T]) Contains ¶
Contains returns true if the given element is already present in the current set, otherwise returns false.
func (*Set[T]) Difference ¶
Difference returns a new set with elements that are in the current set but not in s2.
func (*Set[T]) Index ¶
Index returns the index of the given element in the set. Returns -1 if the element is not present.
func (*Set[T]) Intersection ¶
Intersection returns a new set with elements that are present in both the sets.
func (*Set[T]) IsDisjoint ¶
IsDisjoint returns true if there are no common elements between this set and the given set, else returns true.
func (*Set[T]) IsSubsetOf ¶
IsSubsetOf returns true if this set is a subset of the given set.
func (*Set[T]) Items ¶
func (s *Set[T]) Items() []T
Items returns the elements of the set as a slice.
Source Files