hierarchy

README

Hierarchy

The hierarchy library provides a generic tree data structure for types satisfying Golang's comparable and cmp.Ordered constraints.

Install

go get -u gitlab.com/fisherprime/hierarchy/v2

Documentation

Overview

SPDX-License-Identifier: MIT

SPDX-License-Identifier: MIT

SPDX-License-Identifier: MIT

SPDX-License-Identifier: MIT

SPDX-License-Identifier: MIT

Index

• Variables
• type BuildOption
  • func IsOrdered[T Constraint]() BuildOption[T]
  • func WithBuildConfig[T Constraint](cfg *Config) BuildOption[T]
  • func WithBuilders[T Constraint](builders []Builder[T]) BuildOption[T]
• type BuildSource
  • func NewBuildSource[T Constraint](options ...BuildOption[T]) *BuildSource[T]
  • func (b *BuildSource[T]) Build(ctx context.Context, options ...Option[T]) (h *Hierarchy[T], err error)
  • func (b *BuildSource[T]) Cut(index int)
  • func (b *BuildSource[T]) Len() int
• type Builder
• type Config
  • func DefConfig() *Config
• type Constraint
• type DefaultBuilder
  • func (d *DefaultBuilder) Parent() string
  • func (d *DefaultBuilder) Value() string
• type Hierarchy
  • func Deserialize[T Constraint](ctx context.Context, l *lexer.Lexer, options ...Option[T]) (h *Hierarchy[T], err error)
  • func New[T Constraint](value T, options ...Option[T]) *Hierarchy[T]
  • func (h *Hierarchy[T]) AddChild(ctx context.Context, child *Hierarchy[T], parent ...T) (err error)
  • func (h *Hierarchy[T]) AllChildren(ctx context.Context, parentValue ...T) (children List[T], err error)
  • func (h *Hierarchy[T]) AllChildrenByLevel(ctx context.Context, parentValue ...T) (children LevelList[T], err error)
  • func (h *Hierarchy[T]) Child(_ context.Context, childValue T) (child *Hierarchy[T], ok bool)
  • func (h *Hierarchy[T]) Children(ctx context.Context) (children List[T])
  • func (h *Hierarchy[T]) Config() *Config
  • func (h *Hierarchy[T]) Leaves(ctx context.Context) (termNodes List[T], err error)
  • func (h *Hierarchy[T]) Locate(ctx context.Context, childValue T, parentValue ...T) (child *Hierarchy[T], err error)
  • func (h *Hierarchy[T]) Parent() *Hierarchy[T]
  • func (h *Hierarchy[T]) PopChild(ctx context.Context, childValue T, parentValue ...T) (child *Hierarchy[T], err error)
  • func (h *Hierarchy[T]) Serialize(ctx context.Context, cfg *lexer.Config) (output string, err error)
  • func (h *Hierarchy[T]) SetParent(parent *Hierarchy[T])
  • func (h *Hierarchy[T]) Value() T
  • func (h *Hierarchy[T]) Walk(ctx context.Context, traverseChan chan TraverseComm[T])
• type LevelList
  • func (l *LevelList[T]) Values(ctx context.Context, sortValues ...bool) (values [][]T)
• type List
  • func (l *List[T]) Len() int
  • func (l *List[T]) Less(i int, j int) bool
  • func (l *List[T]) Swap(i int, j int)
  • func (l *List[T]) Values(_ context.Context, sortValues ...bool) (values []T)
• type Option
  • func UseLocateCache[T Constraint]() Option[T]
  • func WithConfig[T Constraint](cfg *Config) Option[T]
• type TraverseComm

Variables

var (
	ErrBuildHierarchy = errors.New("failed to build hierarchy")

	ErrMissingRootNode   = errors.New("missing root node")
	ErrMultipleRootNodes = errors.New("hierarchy has multiple root nodes")

	ErrEmptyHierarchySrc      = errors.New("empty hierarchy source")
	ErrInvalidHierarchySrc    = errors.New("invalid hierarchy source")
	ErrInconsistentBuildCache = errors.New("inconsistency between the hierarchy and build cache")

	ErrLocateParents = errors.New("unable to locate parents(s)")

	ErrPanicked = errors.New("recovery from panic")
)

Hierarchy building errors.

var (
	ErrExcessiveValues     = errors.New("the deserialization source has excessive values")
	ErrExcessiveEndMarkers = fmt.Errorf("the deserialization source has excessive end markers")
)

Deserialization errors.

var (
	ErrNotFound = errors.New("not found")

	ErrNoLeaves     = errors.New("lacks leaves; tree is cyclic")
	ErrAlreadyChild = errors.New("is a child of")
	ErrNoChildren   = errors.New("lacks children ")
	ErrNotChild     = errors.New("is not a child of")
)

Errors encountered when handling a Hierarchy.

Types

type BuildOption

type BuildOption[T Constraint] func(*BuildSource[T])

BuildOption defines the BuildSource functional option type.

func IsOrdered

func IsOrdered[T Constraint]() BuildOption[T]

IsOrdered configures the BuildSource as ordered; all parent [Builder.Value] are less than their respective child's [Builder.Value].

Unordered BuildSource's have a Hierarchy build-time performance penalty.

func WithBuildConfig

func WithBuildConfig[T Constraint](cfg *Config) BuildOption[T]

WithBuildConfig configures the BuildSource's Config.

func WithBuilders

func WithBuilders[T Constraint](builders []Builder[T]) BuildOption[T]

WithBuilders configures the underlying list.

type BuildSource

type BuildSource[T Constraint] struct {
	// contains filtered or unexported fields
}

BuildSource is a wrapper type for []Builder used to generate the Hierarchy.

func NewBuildSource

func NewBuildSource[T Constraint](options ...BuildOption[T]) *BuildSource[T]

NewBuildSource instantiates a BuildSource.

func (*BuildSource[T]) Build

func (b *BuildSource[T]) Build(ctx context.Context, options ...Option[T]) (h *Hierarchy[T], err error)

Build generates a Hierarchy from a BuildSource.

func (*BuildSource[T]) Cut

func (b *BuildSource[T]) Cut(index int)

Cut a value at some index from the BuildSource.

func (*BuildSource[T]) Len

func (b *BuildSource[T]) Len() int

Len retrieves the length of the BuildSource.

type Builder

type Builder[T Constraint] interface {
	// Value obtains the value stored by the Builder.
	Value() T
	// Parent obtains the parent stored by the Builder
	Parent() T
}

Builder defines an interface for entities that can be read into a Hierarchy.

type Config

type Config struct {
	// Logger for [Hierarchy] messages.
	//
	// Preferring a public field to allow for sharing.
	Logger *slog.Logger
	Debug  bool
}

Config defines configuration options for the BuildSource & Hierarchy's operations.

func DefConfig

func DefConfig() *Config

DefConfig obtains the package's Hierarchy default options.

type Constraint

type Constraint interface {
	comparable
	cmp.Ordered
}

Constraint is a wrapper interface constraining the Hierarchy's valid datatypes.

type DefaultBuilder

type DefaultBuilder struct {
	// contains filtered or unexported fields
}

DefaultBuilder is a sample Builder interface implementation.

func (*DefaultBuilder) Parent

func (d *DefaultBuilder) Parent() string

Parent obtains the parent stored by the DefaultBuilder

func (*DefaultBuilder) Value

func (d *DefaultBuilder) Value() string

Value obtains the value stored by the DefaultBuilder.

type Hierarchy

type Hierarchy[T Constraint] struct {
	// contains filtered or unexported fields
}

Hierarchy defines an n-array tree to hold hierarchies.

Synchronization is unnecessary, the type is designed for single write multiple read.

func Deserialize

func Deserialize[T Constraint](ctx context.Context, l *lexer.Lexer, options ...Option[T]) (h *Hierarchy[T], err error)

Deserialize transforms a serialized tree into a Hierarchy.

An invalid entry will result in a truncated Hierarchy.

func New

func New[T Constraint](value T, options ...Option[T]) *Hierarchy[T]

New instantiates a Hierarchy.

func (*Hierarchy[T]) AddChild

func (h *Hierarchy[T]) AddChild(ctx context.Context, child *Hierarchy[T], parent ...T) (err error)

AddChild to a Hierarchy.

Throws an error on existing child.

func (*Hierarchy[T]) AllChildren

func (h *Hierarchy[T]) AllChildren(ctx context.Context, parentValue ...T) (children List[T], err error)

AllChildren lists immediate and children-of children for a Hierarchy.

func (*Hierarchy[T]) AllChildrenByLevel

func (h *Hierarchy[T]) AllChildrenByLevel(ctx context.Context, parentValue ...T) (children LevelList[T], err error)

AllChildrenByLevel lists immediate and children-of children for a Hierarchy by level.

func (*Hierarchy[T]) Child

func (h *Hierarchy[T]) Child(_ context.Context, childValue T) (child *Hierarchy[T], ok bool)

Child retrieves an immediate child.

func (*Hierarchy[T]) Children

func (h *Hierarchy[T]) Children(ctx context.Context) (children List[T])

Children lists the immediate children for a Hierarchy.

func (*Hierarchy[T]) Config

func (h *Hierarchy[T]) Config() *Config

Config retrieves the Hierarchy's Config.

func (*Hierarchy[T]) Leaves

func (h *Hierarchy[T]) Leaves(ctx context.Context) (termNodes List[T], err error)

Leaves returns an array of terminal Hierarchy(ies).

An error here indicates a cyclic Hierarchy.

func (*Hierarchy[T]) Locate

func (h *Hierarchy[T]) Locate(ctx context.Context, childValue T, parentValue ...T) (child *Hierarchy[T], err error)

Locate searches for a value & returns it's Hierarchy.

func (*Hierarchy[T]) Parent

func (h *Hierarchy[T]) Parent() *Hierarchy[T]

Parent retrieves a reference to the Hierarchy's parent.

Value is nil for the root node.

func (*Hierarchy[T]) PopChild

func (h *Hierarchy[T]) PopChild(ctx context.Context, childValue T, parentValue ...T) (child *Hierarchy[T], err error)

PopChild removes an immediate child of the Hierarchy, returning it's reference.

func (*Hierarchy[T]) Serialize

func (h *Hierarchy[T]) Serialize(ctx context.Context, cfg *lexer.Config) (output string, err error)

Serialize transforms a Hierarchy into a string.

func (*Hierarchy[T]) SetParent

func (h *Hierarchy[T]) SetParent(parent *Hierarchy[T])

SetParent for a Hierarchy.

func (*Hierarchy[T]) Value

func (h *Hierarchy[T]) Value() T

Value retrieves the Hierarchy's data.

func (*Hierarchy[T]) Walk

func (h *Hierarchy[T]) Walk(ctx context.Context, traverseChan chan TraverseComm[T])

Walk performs breadth-first traversal on a Hierarchy, pushing its values to its channel argument.

This operation uses channels to minimize resource wastage. A context.Context is used to terminate the walk operation.

type LevelList

type LevelList[T Constraint] []List[T]

func (*LevelList[T]) Values

func (l *LevelList[T]) Values(ctx context.Context, sortValues ...bool) (values [][]T)

Values returns an array-of array of values for a [LevelList[T]].

type List

type List[T Constraint] []*Hierarchy[T]

List is a type wrapper for []*Hierarchy.

func (*List[T]) Len

func (l *List[T]) Len() int

Len is the number of elements in the collection.

func (*List[T]) Less

func (l *List[T]) Less(i int, j int) bool

Less reports whether the element with index i must sort before the element with index j.

func (*List[T]) Swap

func (l *List[T]) Swap(i int, j int)

Swap swaps the elements with indexes i and j.

func (*List[T]) Values

func (l *List[T]) Values(_ context.Context, sortValues ...bool) (values []T)

Values returns an array of values for a [List[T]].

type Option

type Option[T Constraint] func(*Hierarchy[T])

Option defines the Hierarchy functional option type.

func UseLocateCache

func UseLocateCache[T Constraint]() Option[T]

UseLocateCache enables the usage of a cache for hierarchy.Locate operations.

func WithConfig

func WithConfig[T Constraint](cfg *Config) Option[T]

WithConfig configures the Hierarchy Config.

type TraverseComm

type TraverseComm[T Constraint] struct {
	// contains filtered or unexported fields
}

TraverseComm defines a channel to communicate info between Hierarchy operations & it's callers.