tau

package
v0.1.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Oct 6, 2023 License: MIT Imports: 7 Imported by: 0

Documentation

Overview

(T)ype-(a)gnostic (u)tilities

This package contains a set of type-agnostic interface and functions. It is the core of this library and acts as a bridge between objects of different types.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func ASCmp 

func ASCmp[T constraints.Ordered](a, b T) int

ASCending order comparator. The smaller is the lesser

func Cmp 

func Cmp(a, b any) int

Tries to compare two values of generic type Given a and b the two values (in this order), it returns:

  • -1 if a < b
  • 0 if a == b
  • 1 if a > b

It accepts all types under the constraints.Ordered interface or types that implement the Comparable interface For the latter, the function tau.Comparable.Cmp must be implemented

If the type of a and b are not comparable, it will panic

func DSCmp 

func DSCmp[T constraints.Ordered](a, b T) int

DeSCending order comparator. The smaller is the greater

func Eq 

func Eq(a, b any) bool

Checks for equality between two values of generic type

See Cmp

func Hash 

func Hash(v any) uint32

Hashes a value of generic type It accepts all numeric and string types It also accepts types that implement the tau.Hashable interface For the latter, the function tau.Hashable.Hash must be implemented

If the type of given value is not hashable, it will panic

func Max 

func Max(vals ...any) any

Get maximum value from a list of values of generic type

See Cmp

func Min 

func Min(vals ...any) any

Get minimum value from a list of values of generic type

See Cmp

Types

type BSTree 

type BSTree[T any] interface {
	Collection[T]
	// Returns the node containing the given value
	Get(T) BSTreeNode[T]
	// Returns the root node
	Root() BSTreeNode[T]
	// Inserts a new node with the given value
	// The return value IS NOT the inserted node, but the root node
	// The root node can change after the insertion (e.g in case of rotations)
	Insert(T) BSTreeNode[T]
	// Removes the node containing the given value
	// The return value IS NOT the removed node, but the root node
	// The root node can change after the removal (e.g in case of rotations)
	Remove(T) BSTreeNode[T]
	// Returns the node containing the minimum value in the tree
	Min() BSTreeNode[T]
	// Returns the node containing the maximum value in the tree
	Max() BSTreeNode[T]
	// Returns the node containing the predecessor of the given value
	Pred(T) BSTreeNode[T]
	// Returns the node containing the successor of the given value
	Succ(T) BSTreeNode[T]
	// Returns an iterator that iterates over the tree in pre-order
	PreOrder() Iterator[T]
	// Returns an iterator that iterates over the tree in in-order
	InOrder() Iterator[T]
	// Returns an iterator that iterates over the tree in post-order
	PostOrder() Iterator[T]
}

Generic binary search tree

type BSTreeNode 

type BSTreeNode[T any] interface {
	Box[T]
	// Returns the left child node or nil if it does not exist
	Left() BSTreeNode[T]
	// Returns the right child node or nil if it does not exist
	Right() BSTreeNode[T]
}

Generic node for a binary tree It is allowed to be nil, hence must be implemented as a pointer

type Base 

type Base interface {
	fmt.Stringer
	Hashable
	Comparable
}

Base "building-block" interface for many objects It allows comparison, hashing and string representation

type Box 

type Box[T any] interface {
	// Returns the value contained in the box
	Value() T
}

Generic container for a value

type Collection 

type Collection[T any] interface {
	fmt.Stringer
	Comparable
	Iterable[T]
	Size() int
	// It's a shorthand for Size() == 0. But, if there are
	// more efficient ways to check emptiness, it can be overridden.
	Empty() bool
	// Removes all the elements from the collection
	Clear()
	Contains(T) bool
	// Checks if the receiver contains ALL the elements of the other collection
	ContainsAll(Collection[T]) bool
	// Checks if the receiver contains ANY (even only one) of the elements of the other collection
	ContainsAny(Collection[T]) bool
	// Makes a copy of the collection
	Clone() Collection[T]
}

Generic collection of objects. It can be iterated over and comparated with other collections.

For the comparison to be possible, the elements of the collection must be of comparable trait, i.e. the Cmp function must not panic on them.

The comparison criteria are the following

  • if the two collections have different size, the smaller is the lesser
  • else, elements are compared one by one and the comparison value of the first different pair is returned

The code is the following, where recv is the receiver and other is the argument: 

if recv.Size() != other.Size() {
	Cmp(recv.Size(), other.Size())
}
iter, otherIter := recv.Iter(), other.Iter()
for next, hasNext = iter.Next(); hasNext; next, hasNext = iter.Next() {
	otherNext, _ := otherIter.Next()
	cmp := Cmp(*next, *otherNext)
	if cmp != 0 {
		return cmp
	}
}
return 0

So, two collections are equal if of the same size and whose elements are equal in the same order. The two collections have not to be of the same kind (e.g. also a list and a set can be equal).

type Comparable 

type Comparable interface {

	// The comparison function returns
	// 	- -1 if the receiver is less than the argument
	// 	- 0 if the receiver is equal to the argument
	// 	- 1 if the receiver is greater than the argument
	//
	// It checks that the argument is of the same type as the receiver.
	// If it is not the case, it panics.
	Cmp(any) int
}

Interface for object that are comparable with each other

type Comparator 

type Comparator[T any] func(T, T) int

Interface comparator functions. Allow definition of custom comparison criteria for sorting collections. The comparison must be the same as in Cmp and Comparable

type Deque 

type Deque[T any] interface {
	Collection[T]
	// Adds the given value to the front of the queue
	PushFront(...T)
	// Adds the given value to the back of the queue
	PushBack(...T)
	// Removes the first value from the queue and returns it
	// Returns an error if the queue is empty
	PopFront() (*T, error)
	// Removes the last value from the queue and returns it
	// Returns an error if the queue is empty
	PopBack() (*T, error)
	// Returns the first value from the queue without removing it
	// Returns an error if the queue is empty
	Front() (*T, error)
	// Returns the last value from the queue without removing it
	// Returns an error if the queue is empty
	Back() (*T, error)
	// Returns an iterator that iterates over the queue in FIFO order
	FIFOIter() Iterator[T]
	// Returns an iterator that iterates over the queue in LIFO order
	LIFOIter() Iterator[T]
}

Generic (D)ouble-(e)nded (que)ue It allows both FIFO (queue-like) and LIFO (stack-like) access

type Filter 

type Filter[T any] func(T, ...any) bool

Interface for filtering functions. The value argument is compulsory, while the others are optional.

type Hashable 

type Hashable interface {
	Hash() uint32
}

Interface for object from which is possible to get a hash value.

type IdxedColl 

type IdxedColl[T any] interface {
	Collection[T]
	// Returns the element at the given index
	// Returns an error if the collection is empty
	Get(int) (*T, error)
	// Replaces the existing value at the given index with the given one
	// Does not add new elements and hence does not change the size of the collection
	Set(int, T)
	// Inserts a new "block" with given value at the given index
	// The existing "block" at that index and all the following ones are rearranged
	// The rearrangement is implementation-dependent
	Insert(int, T)
	// Removes the "block" at the given index
	// The following "blocks" are rearranged
	// The rearrangement is implementation-dependent
	// Returns an error if the collection is empty
	RemoveAt(int) (*T, error)
	// Returns the index of the first occurrence of the given value
	// Returns -1 if the value is not found
	IndexOf(T) int
	// Returns the index of the last occurrence of the given value
	// Returns -1 if the value is not found
	LastIndexOf(T) int
	// Swaps the elements at the given indices
	Swap(int, int)
	// Returns a new collection containing the elements in the range [start, end)
	// It makes a copy of involved elements, so the original collection is not modified
	// Obviously, a slice of an empty collection is an empty collection itself
	//
	// The following checks are performed:
	// 	- start == end: returns an empty collection
	// 	- start > end: start and end are swapped
	// After these checks, the aforementioned index sanification is applied
	Slice(int, int) IdxedColl[T]
}

Generic collection with indexwise access. It allows duplicates

All implementation provides a circular access, like in other languages as Python. Meaning that:

  • negative indices are allowed and will be interpreted as their absolute value, but starting from the end of the list.
  • after this check, a modulus operation is performed on the index to make sure that it is in the range [0, size)

These two operations together will be referred to as "index sanification" and are performed by a private function in the implementations. The sanification pseudo-code is the following: 

INPUT(index, size)
if index < 0:
	index = index + size
endif
index = index % size
OUTPUT(index)

type Iterable 

type Iterable[T any] interface {
	Iter() Iterator[T]
}

Interface for objects that can be iterated over.

type Iterator 

type Iterator[T any] interface {
	// Tries to get the next value from the iterator.
	// It returns a tuple (value, hasNext), where:
	// 	- value is the pointer to the next value in the iteration
	// 	- hasNext is a boolean that is true if values are still available
	// When hasNext is false, value is nil
	Next() (*T, bool)

	// This function emulates a for-each loop.
	// The given function is called for each available value.
	Each(func(T))
}

Stream-like interface, that allows to get values one by one. It is used to iterate over collections abstracting from their implementation details and internal structure

type List 

type List[T any] interface {
	IdxedColl[T]
	Append(...T)
	Prepend(...T)
	// Removes the first occurrence of the given value
	// Returns an error if the value is not found
	RemoveFirst(T) error
	// Removes all the occurrences of the given value
	// Returns an error if the value is not found
	RemoveAll(T) error
	// Sorts the list using the given comparator
	// A copy of the list is made, so the original list is not modified
	Sort(Comparator[T]) List[T]
	// Returns a new list containing the elements for which the given filter returns true
	// It makes a copy of the list, so the original one is not modified
	Sublist(Filter[T]) List[T]
}

Generic list with index access

type Map 

type Map[K any, V any] interface {
	Collection[K]
	// Associates the given value with the given key
	Put(K, V)
	// Returns the value associated with the given key
	// Returns an error if the key is not found
	Get(K) (*V, error)
	// Removes the value associated with the given key
	// Returns an error if the key is not found or if the map is empty
	Remove(K) (*V, error)
	// Returns true if the map contains the given key
	HasKey(K) bool
	// Returns an iterator that iterates over the keys of the map
	Keys() Iterator[K]
	// Returns an iterator that iterates over the values of the map
	Values() Iterator[V]
}

Generic map The key MUST be a primary type (under constraints.Ordered) while the type parameter can be really anything

type Pair 

type Pair[A any, B any] interface {
	// Returns the first element of the pair
	First() A
	Last() B
}

Generic container for a pair of values It's suitable for both ordered and unordered pairs The semantics of the First() and Last() functions is up to the concrete implementation

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.