dryad

package module
v0.0.0-...-60ed499 Latest Latest
Warning

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

 Go to latest Published: Nov 5, 2023 License: CC0-1.0 Imports: 3 Imported by: 15

README

Package dryad

import "gitlab.com/fospathi/dryad"

Go package dryad implements generic tree nodes and tree traversals as well as other generic data structures.

Development status

Package dryad is unstable; expect breaking changes with every commit.

License

CC0{height=75}

SPDX-License-Identifier: CC0-1.0 OR MIT-0

  • dryad by Christian Stewart is marked with CC0 1.0 Universal

  • MIT No Attribution

    Copyright 2023 Christian Stewart

    Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so.

    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Documentation

Overview

Package dryad provides generic data structures.

Package dryad provides generic tree nodes.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func Identity 

func Identity[T any](v T) T

Identity function returns its argument.

func IsAwaitNotFoundError 

func IsAwaitNotFoundError(err error) bool

IsAwaitNotFoundError reports whether the given error indicates that an Await which was supplied as an argument was not found among the current awaits.

Perhaps the Await in question was deleted.

func IsUnfilledError 

func IsUnfilledError(err error) bool

IsUnfilledError reports whether the given error indicates that an Await which was supplied as an argument does not have an associated value.

Perhaps the Await is not yet closed. Or perhaps the Await is closed but is not associated with a value, as can happen for example to the final Await of a closed awaitable sequence.

func NewFirst 

func NewFirst[T any](v T) <-chan T

NewFirst constructs a new First channel which is a channel that is preloaded with one value.

Only the first receiver gets the value. Once the channel is emptied no further values can be added, the channel can never be closed, and any other channel read operations will block.

One possible use of a First is as a conditional 'once': 

select {
case <-first:
default:
   // Perform these actions more than once for non first read operations...
   return
}
// Perform the following actions only once...

Types

type Await 

type Await <-chan struct{}

Await something.

The waiting is finished when the Await is closed. Use the closed Await to access the something that was awaited.

type Final 

type Final[T any] struct {
	// contains filtered or unexported fields
}

Final can only be set once.

func (*Final[T]) Get 

func (f *Final[T]) Get() T

Get the value if set else the zero value of its type.

func (*Final[T]) Set 

func (f *Final[T]) Set(val T)

Set the value.

Has no effect after the first use.

func (*Final[T]) Value 

func (f *Final[T]) Value() (val T, ok bool)

Value stored in the final and a true if set, else the zero value of the type and a false to indicate it is unset.

type Geter 

type Geter[T any] interface {
	// Get the value.
	Get() T
}

func NewFinalised 

func NewFinalised[T any](val T) Geter[T]

NewFinalised constructs a new Finalised permanently set to the given value.

type ModSlice 

type ModSlice[T any] []T

ModSlice uses modular arithmetic indices.

func (ModSlice[T]) CanonShift 

func (vv ModSlice[T]) CanonShift(n int)

CanonShift the slice values rightwards by n positions where n is a canonical shift value, that is, positive and less than the slice length.

A value pushed off the right (highest index) edge is inserted at the left edge.

func (ModSlice[T]) Shift 

func (vv ModSlice[T]) Shift(n int)

Shift the slice values by n positions.

It is acceptable if the given number of positions to shift the values by is negative or larger in magnitude than the slice length. Positive shifts move the values right towards the highest index. A value pushed off an edge is inserted at the other edge.

func (ModSlice[T]) ShiftByOne 

func (vv ModSlice[T]) ShiftByOne(right bool)

ShiftByOne position.

A true value shifts values right towards the highest slice index.

func (ModSlice[T]) ShiftLeft 

func (vv ModSlice[T]) ShiftLeft()

ShiftLeft by one position towards slice index 0.

The first slice value is copied to the last position.

func (ModSlice[T]) ShiftRight 

func (vv ModSlice[T]) ShiftRight()

ShiftRight by one position towards the highest slice index.

The last slice value is copied to the first position.

type ModSliceOfEq 

type ModSliceOfEq[T comparable] ModSlice[T]

ModSliceOfEq uses modular arithmetic indices.

func (ModSliceOfEq[T]) StartWith 

func (vv ModSliceOfEq[T]) StartWith(v T)

StartWith the given value by shifting the slice values so the given value's first occurrence occupies index 0.

func (ModSliceOfEq[T]) StartWithFunc 

func (vv ModSliceOfEq[T]) StartWithFunc(f func(v T) bool)

StartWithFunc shifts the slice values so that the given functions first true match occupies index 0.

type Multiset 

type Multiset[T comparable] map[T]int

A Multiset of comparable elements.

func (Multiset[T]) Add 

func (s Multiset[T]) Add(v T)

Add the given element to the set.

func (Multiset[T]) Cardinality 

func (s Multiset[T]) Cardinality() int

Cardinality of the set.

func (Multiset[T]) Multiplicity 

func (s Multiset[T]) Multiplicity(v T) int

Multiplicity of the given element.

type NodeOfEq 

type NodeOfEq[T comparable] struct {
	Cashpoint *NodeOfEq[T]
	Kids      []*NodeOfEq[T]
	Content   T
}

NodeOfEq is a tree node with comparable node contents.

func (*NodeOfEq[T]) AddChild 

func (node *NodeOfEq[T]) AddChild(child *NodeOfEq[T])

AddChild to detach it from its current parent, if any, and add it to the receiver's child nodes making the receiver the child's parent.

Nothing happens if the child and receiver are the same node.

func (*NodeOfEq[T]) Degree 

func (node *NodeOfEq[T]) Degree() int

Degree is the number of edges on the tree that use the receiver node.

If the receiver node is a root node it is simply the number of child nodes, otherwise it is 1 plus the number of child nodes.

func (*NodeOfEq[T]) Detach 

func (node *NodeOfEq[T]) Detach()

Detach the receiver node from its parent making it the root of its own tree.

type Set 

type Set[T comparable] map[T]struct{}

A Set of comparable elements.

func (Set[T]) Add 

func (s Set[T]) Add(v T)

Add the given element to the set.

func (Set[T]) AddAll 

func (s Set[T]) AddAll(vv ...T)

AddAll the given elements to the set.

func (Set[T]) AddSet 

func (s Set[T]) AddSet(set Set[T])

AddSet to the receiver.

The receiver set becomes the union of both sets.

func (Set[T]) Any 

func (s Set[T]) Any() T

Any pseudo random element of the non empty set.

func (Set[T]) Contains 

func (s Set[T]) Contains(v T) bool

Contains the given element if true.

func (Set[T]) ContainsAll 

func (s Set[T]) ContainsAll(vv ...T) bool

ContainsAll the elements of the given non empty slice if true.

Special cases:

  • return false if the given slice is empty. See also [.IsSuperset] for alternative behaviour for the empty set case.

func (Set[T]) Copy 

func (s Set[T]) Copy() Set[T]

Copy returns a newly allocated set containing the same elements.

func (Set[T]) Delete 

func (s Set[T]) Delete(v T)

Delete the given element from the set.

func (Set[T]) DeleteAll 

func (s Set[T]) DeleteAll(vv ...T)

DeleteAll the given elements from the set.

func (Set[T]) Difference 

func (s Set[T]) Difference(set Set[T]) Set[T]

Difference set containing those elements of the receiver set which are absent from the argument set.

func (Set[T]) Elements 

func (s Set[T]) Elements() []T

Elements of the set as a newly allocated slice.

func (Set[T]) Equals 

func (s Set[T]) Equals(set Set[T]) bool

Equals reports whether the sets are equal.

func (Set[T]) Intersection 

func (s Set[T]) Intersection(set Set[T]) Set[T]

Intersection of the sets containing the elements shared by both sets.

func (Set[T]) Intersects 

func (s Set[T]) Intersects(set Set[T]) bool

Intersects reports whether the sets share any elements.

func (Set[T]) IsEmpty 

func (s Set[T]) IsEmpty() bool

IsEmpty reports whether the set has no elements.

func (Set[T]) IsNotEmpty 

func (s Set[T]) IsNotEmpty() bool

IsNotEmpty reports whether the set has at least one element.

func (Set[T]) IsSupersetOf 

func (s Set[T]) IsSupersetOf(set Set[T]) bool

IsSupersetOf reports whether the receiver set is a superset of the given set.

Special cases:

  • return true if the given set is empty. See also [.ContainsAll] for alternative behaviour for the empty set case.

func (Set[T]) Len 

func (s Set[T]) Len() int

Len is the number of elements in the set.

func (Set[T]) Sorted 

func (s Set[T]) Sorted(less func(T, T) int) []T

Sorted elements of the set in ascending order as determined by the less function.

func (Set[T]) Union 

func (s Set[T]) Union(set Set[T]) Set[T]

Union set containing all elements from both of the sets.

type SyncAwaitSeq 

type SyncAwaitSeq[T any] struct {
	// The Done channel is closed by the Close() method.
	Done <-chan struct{}
	// contains filtered or unexported fields
}

A SyncAwaitSeq is a concurrency safe awaitable sequence of values.

An Await shall be closed before using it to await the next position or getting the value at that position.

func NewSyncAwaitSeq 

func NewSyncAwaitSeq[T any]() *SyncAwaitSeq[T]

NewSyncAwaitSeq constructs a new SyncAwaitSeq.

func (*SyncAwaitSeq[T]) Advance 

func (seq *SyncAwaitSeq[T]) Advance(await Await) (Await, error)

Advance to the next position in the sequence after the given Await position.

Supply a nil argument to await the first position in the sequence. Otherwise, to await a position, you need to supply the already closed Await of the preceding position.

If the returned Await is not already closed, the position of the Await is as yet unfilled.

An Await closes upon a value being appended to the sequence. An Await also closes upon closure of the sequence leaving the last unfilled position forever unfilled.

Return an error if no such Await exists or the position is not filled. You cannot advance past the unfilled last position.

func (*SyncAwaitSeq[T]) Append 

func (seq *SyncAwaitSeq[T]) Append(v T)

Append the given value to the end of the sequence.

func (*SyncAwaitSeq[T]) AppendAll 

func (seq *SyncAwaitSeq[T]) AppendAll(vv []T)

AppendAll the given values to the end of the sequence.

func (*SyncAwaitSeq[T]) Await 

func (seq *SyncAwaitSeq[T]) Await(await Await) (Await, error)

Await is a synonym for [Advance].

func (*SyncAwaitSeq[T]) Close 

func (seq *SyncAwaitSeq[T]) Close()

Close the sequence.

No more values can be added afterwards.

func (*SyncAwaitSeq[T]) Delete 

func (seq *SyncAwaitSeq[T]) Delete(await Await) (T, error)

Delete the position in the sequence associated with the given Await, reducing the length of the sequence by 1.

Return the value occupying that position before deletion.

Return an error if no such Await exists or the position is not filled.

func (*SyncAwaitSeq[T]) Length 

func (seq *SyncAwaitSeq[T]) Length() int

Length of the sequence.

func (*SyncAwaitSeq[T]) Value 

func (seq *SyncAwaitSeq[T]) Value(await Await) (T, error)

Value in the sequence at the given awaited position.

Return an error if no such Await exists or the position is not filled.

func (*SyncAwaitSeq[T]) Values 

func (seq *SyncAwaitSeq[T]) Values() []T

Values of the sequence as a new slice.

type SyncNode 

type SyncNode[T any] struct {
	sync.Mutex
	Cashpoint *SyncNode[T]
	Kids      []*SyncNode[T]
	Content   T
}

SyncNode is a tree node with concurrency safe methods.

Accessing fields directly by bypassing the methods is not concurrency safe.

func (*SyncNode[T]) AddChild 

func (nde *SyncNode[T]) AddChild(child *SyncNode[T])

AddChild to detach it from its current parent, if any, and add it to the receiver's child nodes making the receiver the child's parent.

Nothing happens if the child and receiver are the same node.

Adding a child is not an atomic operation: the detach is done first as a separate op.

func (*SyncNode[T]) Children 

func (nde *SyncNode[T]) Children() []*SyncNode[T]

Children of the receiver node.

func (*SyncNode[T]) Degree 

func (nde *SyncNode[T]) Degree() int

Degree is the number of edges on the tree that use the receiver node.

If the receiver node is a root node it is simply the number of child nodes, otherwise it is 1 plus the number of child nodes.

func (*SyncNode[T]) Detach 

func (nde *SyncNode[T]) Detach()

Detach the receiver node from its parent making it the root of its own tree.

func (*SyncNode[T]) Get 

func (nde *SyncNode[T]) Get() T

Get the value stored in the node.

func (*SyncNode[T]) IsMe 

func (nde *SyncNode[T]) IsMe(node *SyncNode[T]) bool

IsMe reports whether the argument is the same instance as the receiver.

func (*SyncNode[T]) IsRoot 

func (nde *SyncNode[T]) IsRoot() bool

IsRoot reports whether the receiver node has no parent.

func (*SyncNode[T]) Parent 

func (nde *SyncNode[T]) Parent() *SyncNode[T]

Parent of the receiver or nil for a root node.

func (*SyncNode[T]) Set 

func (nde *SyncNode[T]) Set(val T)

Set the value stored in the node.

Source Files

View all Source files

Directories

Path Synopsis
Package leafstar implements a tree traversal that fans out from a given node to the tree's leaf nodes.
 Package leafstar implements a tree traversal that fans out from a given node to the tree's leaf nodes.

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.