structs

README

structs

version: v0.1.1

This library is not production-ready. Use it only in testing environments.

This project is an effort to provide a variety of data structures and accompanying interfaces to Go developers using 1.18 or later, and was originally inspired by the Java Collections API interfaces.

The API for the current types is not stable. Significant changes may be made at any point. Some types may not fully implement interfaces which they are meant to, and documentation remains mostly incomplete.

If there are any real or potential bugs you notice within any of these data structures, incomplete test cases, or other problems, feel free to create an issue. I welcome your feedback and support.

Installation

go get github.com/zytekaron/structs

Data Structures

• bitset - A resizable bit set.

• bloom - A bloom filter backed by bitset.

• heap - A binary heap.

• list - A doubly linked list.

• queue

  • A regular double-ended queue backed by list.
  • A priority queue backed by heap.

• wrap - To use Go types as Collections (see examples below).

Usage

package main

import (
	"fmt"
	"github.com/zytekaron/structs/list"
	"github.com/zytekaron/structs/set"
	"github.com/zytekaron/structs/wrap"
)

func main() {
	l := list.NewOrdered[int]()
	l.Add(2)
	l.AddLast(3)
	l.AddFirst(1)
	l.Each(func(i int) { fmt.Println(i) }) // 1, 2, 3

	s := set.NewMapSet[int]()
	s.AddAll(wrap.OrderedValues(10, 20, 30))             // 10, 20, 30
	s.AddIterator(wrap.ValueIterator(30, 40, 50))        // 10, 20, 30, 40, 50
	s.RetainAll(wrap.OrderedSlice([]int{0, 20, 30, 60})) // 20, 30
	fmt.Println(s.Values())                              // [20, 30]
}

Possible Additions

• optional reallocation (downsizing) when, for example size / capacity < 0.25

License

structs is licensed under the MIT License.

Documentation

Index

• func CompareOrdered[V constraints.Ordered](a, b V) int
• func DoubleCapacity(before, need int) (after int)
• func EqualOrdered[V constraints.Ordered](a, b V) bool
• func Filter[V any](collection Collection[V], keep PredicateFunc[V])
• func GreaterOrdered[V constraints.Ordered](a, b V) bool
• func LessOrdered[V constraints.Ordered](a, b V) bool
• func Realloc[T any](size int, s []T) []T
• func ReverseCompareOrdered[V constraints.Ordered](a, b V) int
• type CapacityFunc
• type Collection
• type CompareFunc
  • func Reverse[V any](cmp CompareFunc[V]) CompareFunc[V]
• type Deque
• type EqualFunc
• type Iterator
• type LessFunc
• type List
• type ListIterator
• type PredicateFunc
• type Queue
• type Set

Functions

func CompareOrdered

func CompareOrdered[V constraints.Ordered](a, b V) int

CompareOrdered is a CompareFunc which compares two values of any type which implements constraints.Ordered, returning their natural ordering.

a == b: 0
a < b: -1
a > b: +1

func DoubleCapacity

func DoubleCapacity(before, need int) (after int)

DoubleCapacity returns a capacity double that of the old capacity until it exceeds need, or 1 if the old capacity was 0.

func EqualOrdered

func EqualOrdered[V constraints.Ordered](a, b V) bool

EqualOrdered is an EqualFunc which operates on a type which satisfies the constraints.Ordered interface.

func Filter

func Filter[V any](collection Collection[V], keep PredicateFunc[V])

func GreaterOrdered

func GreaterOrdered[V constraints.Ordered](a, b V) bool

GreaterOrdered is a LessFunc which compares two values of any type which implements constraints.Ordered, returning the inverse of their natural ordering.

b < a

func LessOrdered

func LessOrdered[V constraints.Ordered](a, b V) bool

LessOrdered is a LessFunc which compares two values of any type which implements constraints.Ordered, returning their natural ordering.

a < b

func Realloc

func Realloc[T any](size int, s []T) []T

Realloc reallocates a slice with the new size. It can be used to increase or decrease the slice size.

func ReverseCompareOrdered

func ReverseCompareOrdered[V constraints.Ordered](a, b V) int

ReverseCompareOrdered is a CompareFunc which compares two values of any type which implements constraints.Ordered, returning the inverse of their natural ordering.

a == b: 0
a < b: +1
a > b: -1

Types

type CapacityFunc

type CapacityFunc func(old, need int) int

CapacityFunc is a function used to return a new capacity for a slice when it needs to be increased. It must return an integer equal to or greater than need, otherwise it may cause a panic from the caller.

type Collection

type Collection[V any] interface {
	Add(value V) bool
	AddAll(other Collection[V]) bool
	AddIterator(iter Iterator[V]) bool
	Clear()
	Contains(value V) bool
	ContainsAll(other Collection[V]) bool
	ContainsIterator(iter Iterator[V]) bool
	IsEmpty() bool
	Iterator() Iterator[V]
	Remove(value V) bool
	RemoveAll(other Collection[V]) bool
	RemoveIterator(iter Iterator[V]) bool
	RetainAll(other Collection[V]) bool
	Size() int
	Values() []V
}

type CompareFunc

type CompareFunc[V any] func(a, b V) (result int)

CompareFunc is a function which returns an integer indicating the difference between the first and second value.

n == 0: a == b
n < 0: a < b
n > 0: a > b

CompareOrdered or ReverseCompareOrdered can be used for any type which implements constraints.Ordered.

func Reverse

func Reverse[V any](cmp CompareFunc[V]) CompareFunc[V]

Reverse reverses a comparison function, effectively reversing the sorting order of the values based on an existing compare function.

type Deque

type Deque[V any] interface {
	Collection[V]
	Queue[V]

	AddFirst(value V)
	AddLast(value V)
	GetFirst() V
	GetLast() V
	Offer(value V) bool
	OfferFirst(value V) bool
	OfferLast(value V) bool
	Peek() V
	PeekFirst() V
	PeekLast() V
	Poll() V
	PollFirst() V
	PollLast() V
	Pop() V
	Push(value V)
	RemoveHead() V
	RemoveFirst() V
	RemoveFirstOccurrence(value V) bool
	RemoveLast() V
	RemoveLastOccurrence(value V) bool
}

type EqualFunc

type EqualFunc[V any] func(a, b V) (equal bool)

EqualFunc is a function which returns whether the first value is equal to the second value, using custom behavior.

EqualOrdered can be used for any type which implements constraints.Ordered.

type Iterator

type Iterator[V any] interface {
	HasNext() bool
	Next() V
	Remove()
}

type LessFunc

type LessFunc[V any] func(a, b V) (less bool)

LessFunc is a function which returns whether the first value is strictly smaller than (not equal to) the second value.

type List

type List[V any] interface {
	Collection[V]

	AddIndex(index int, value V)
	Get(index int) V
	IndexOf(value V) int
	LastIndexOf(value V) int
	RemoveIndex(index int) V
	Set(index int, value V) V
	Sort(cmp LessFunc[V])
}

type ListIterator

type ListIterator[V any] interface {
	HasNext() bool
	HasPrevious() bool
	NextIndex() int
	Next() V
	PreviousIndex() int
	Previous() V
	Remove()
}

type PredicateFunc

type PredicateFunc[V any] func(v V) (result bool)

PredicateFunc is a function which returns a true or false value for a given input, for example a function used to indicate whether a particular value is a prime number.

type Queue

type Queue[V any] interface {
	Collection[V]

	Element() V
	Peek() V
	Poll() V
	RemoveHead() V
}

type Set

type Set[V any] interface {
	Collection[V]
}