tree

Documentation

Index

• Constants
• type InvalidDepthError
  • func NewInvalidDepthError(depth int) *InvalidDepthError
  • func (e *InvalidDepthError) Error() string
• type InvalidPathError
  • func NewInvalidPathError(message string) *InvalidPathError
  • func (e *InvalidPathError) Error() string
• type InvalidPathSubcomponentError
  • func NewInvalidPathSubcomponentError(message string) *InvalidPathSubcomponentError
  • func (e *InvalidPathSubcomponentError) Error() string
• type JSONRadix
  • func NewJSONRadix(marshaller JSONRadixMarshalFn, unmarshaller JSONRadixUnmarshalFn) *JSONRadix
  • func (r *JSONRadix) MarshalJSON() ([]byte, error)
  • func (r *JSONRadix) UnmarshalJSON(data []byte) error
• type JSONRadixMarshalFn
• type JSONRadixUnmarshalFn
• type Path
  • func NewPath(p string) (Path, error)
  • func NewPathFromDomain(d string) (Path, error)
  • func RootPath() Path
  • func (p Path) Child(child string) Path
  • func (p Path) Depth() int
  • func (p Path) HasPrefix(prefix Path) bool
  • func (p Path) IsRoot() bool
  • func (p Path) Leaf() (string, error)
  • func (p Path) Parent() (Path, error)
  • func (p Path) Prefix(n int) (Path, error)
  • func (p Path) Shift(n int) (Path, []string, error)
  • func (p Path) String() string
  • func (p Path) Subpaths() []string
  • func (p Path) ToDomain() string
  • func (p *Path) UnmarshalJSON(data []byte) error
• type PathSubcomponent
  • func NewPathSubcomponent(val string) (PathSubcomponent, error)
  • func NewPathSubcomponentFromParts(path Path, subcomponent string) (PathSubcomponent, error)
  • func (n PathSubcomponent) Parts() (Path, string)
  • func (n PathSubcomponent) Path() Path
  • func (n PathSubcomponent) String() string
  • func (n PathSubcomponent) Subcomponent() string
  • func (n *PathSubcomponent) UnmarshalJSON(data []byte) error
• type Radix
  • func NewRadix() *Radix
  • func (r *Radix) Delete(p Path) (interface{}, bool)
  • func (r *Radix) DeletePrefix(p Path) int
  • func (r *Radix) Get(p Path) (interface{}, bool)
  • func (r *Radix) Insert(p Path, v interface{}) (interface{}, bool)
  • func (r *Radix) Len() int
  • func (r *Radix) ReplacePrefix(p Path, other *Radix)
  • func (r *Radix) Walk(fn RadixWalkFn)
  • func (r *Radix) WalkPrefix(p Path, fn RadixWalkFn)
• type RadixWalkFn
• type WalkContinuation

Constants

const (
	// PathSeparator is the separator for the subpaths in a Path.
	PathSeparator = "/"

	// PathSubcomponentSeparator is the separator between the Path and subcomponent
	// of a PathSubcomponent.
	PathSubcomponentSeparator = ":"
)

Types

type InvalidDepthError

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

func NewInvalidDepthError

func NewInvalidDepthError(depth int) *InvalidDepthError

func (*InvalidDepthError) Error

func (e *InvalidDepthError) Error() string

type InvalidPathError

type InvalidPathError struct {
	Message string
}

func NewInvalidPathError

func NewInvalidPathError(message string) *InvalidPathError

func (*InvalidPathError) Error

func (e *InvalidPathError) Error() string

type InvalidPathSubcomponentError

type InvalidPathSubcomponentError struct {
	Message string
}

func NewInvalidPathSubcomponentError

func NewInvalidPathSubcomponentError(message string) *InvalidPathSubcomponentError

func (*InvalidPathSubcomponentError) Error

func (e *InvalidPathSubcomponentError) Error() string

type JSONRadix

type JSONRadix struct {
	*Radix
	// contains filtered or unexported fields
}

JSONRadix is a Radix tree that is capable of being (de)serialized to/from JSON using the supplied marshalling/unmarshalling functions.

func NewJSONRadix

func NewJSONRadix(marshaller JSONRadixMarshalFn, unmarshaller JSONRadixUnmarshalFn) *JSONRadix

NewJSONRadix creates a new radix with the supplied marshaller and unmarshaller functions and returns it.

func (*JSONRadix) MarshalJSON

func (r *JSONRadix) MarshalJSON() ([]byte, error)

MarshalJSON fulfills the json.Marshaller interface.

func (*JSONRadix) UnmarshalJSON

func (r *JSONRadix) UnmarshalJSON(data []byte) error

MarshalJSON fulfills the json.Unmarshaller interface.

type JSONRadixMarshalFn

type JSONRadixMarshalFn func(interface{}) (json.RawMessage, error)

type JSONRadixUnmarshalFn

type JSONRadixUnmarshalFn func(json.RawMessage) (interface{}, error)

type Path

type Path string

Path is a path from the root of a tree to a node in the tree. The components of the path are separated by slashes. For example: /a/b/c

func NewPath

func NewPath(p string) (Path, error)

NewPath validates the string passed in and returns a Path.

func NewPathFromDomain

func NewPathFromDomain(d string) (Path, error)

NewPathFromDomain validates the domain passed in and converts it to a Path.

func RootPath

func RootPath() Path

func (Path) Child

func (p Path) Child(child string) Path

Child returns the path of a child of the Path For example, child c of /a/b returns /a/b/c

func (Path) Depth

func (p Path) Depth() int

Depth returns the number of subpaths in the Path. For example: /a/b/c returns 3

func (Path) HasPrefix

func (p Path) HasPrefix(prefix Path) bool

HasPrefix returns a bool indicating if the the path starts with the supplied prefix.

func (Path) IsRoot

func (p Path) IsRoot() bool

IsRoot returns a bool indicating if the node is the root node (i.e. "/")

func (Path) Leaf

func (p Path) Leaf() (string, error)

Leaf returns the final subpath. Returns an error if called on the root path.

func (Path) Parent

func (p Path) Parent() (Path, error)

Parent returns the Path one level up from the Path if it is the root, and returns an error if it is the root. For example: /a/b/c returns /a/b

func (Path) Prefix

func (p Path) Prefix(n int) (Path, error)

Prefix returns the path representing the first n subpaths of the path. Returns an error if n > the path's length.

func (Path) Shift

func (p Path) Shift(n int) (Path, []string, error)

Shift returns a new Path shifted n components left as well as the components that were shifted out. Returns an error if n > the path's length. For example: /a/b/c shifted 2 would return /c and [a, b]

func (Path) String

func (p Path) String() string

String returns a string representation of the Path.

func (Path) Subpaths

func (p Path) Subpaths() []string

Subpaths returns a slice of the paths making up the Path. For example: /a/b/c returns [a, b, c].

func (Path) ToDomain

func (p Path) ToDomain() string

ToDomain returns the domain version of the path. For example: /a/b/c returns c.b.a N.B.: panics if the Path is invalid (i.e. does not contain a slash)

func (*Path) UnmarshalJSON

func (p *Path) UnmarshalJSON(data []byte) error

UnmarshalJSON implements json.Unmarshaler

type PathSubcomponent

type PathSubcomponent string

PathSubcomponent contains a node path and the name of a subcomponent The subcomponent is separated from the node path with a colon. For example: /a/b/c:foo

func NewPathSubcomponent

func NewPathSubcomponent(val string) (PathSubcomponent, error)

NewPathSubcomponent returns a validated PathSubcomponent from the supplied value.

func NewPathSubcomponentFromParts

func NewPathSubcomponentFromParts(path Path, subcomponent string) (PathSubcomponent, error)

NewPathSubcomponentFromParts returns a validated PathSubcomponent using the path and subcomponent.

func (PathSubcomponent) Parts

func (n PathSubcomponent) Parts() (Path, string)

Path returns the Path and subcomponent of the PathSubcomponent. For example: /a/b/c:foo returns /a/b/c, foo N.B.: panics if the PathSubcomponent is improperly formed.

func (PathSubcomponent) Path

func (n PathSubcomponent) Path() Path

Path returns the Path of the PathSubcomponent. For example: /a/b/c:foo returns /a/b/c N.B.: panics if the PathSubcomponent is improperly formed.

func (PathSubcomponent) String

func (n PathSubcomponent) String() string

String returns a string representation of the PathSubcomponent

func (PathSubcomponent) Subcomponent

func (n PathSubcomponent) Subcomponent() string

Path returns the subcomponent of the PathSubcomponent. For example: /a/b/c:foo returns foo N.B.: panics if the PathSubcomponent is improperly formed.

func (*PathSubcomponent) UnmarshalJSON

func (n *PathSubcomponent) UnmarshalJSON(data []byte) error

UnmarshalJSON implements json.Unmarshaler

type Radix

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

Radix provides efficient insertion, retrieval, and deletion, as well as prefixed retrieval and deletion on paths.

func NewRadix

func NewRadix() *Radix

NewRadix returns a radix tree.

func (*Radix) Delete

func (r *Radix) Delete(p Path) (interface{}, bool)

Delete deletes a path from the tree if it exists, and returns the deleted value if it exists as well as a boolean indicating whether the path existed.

func (*Radix) DeletePrefix

func (r *Radix) DeletePrefix(p Path) int

Delete prefix removes all paths that are prefixed by the given prefix (including the given prefix) from the tree.

func (*Radix) Get

func (r *Radix) Get(p Path) (interface{}, bool)

Get retrieves the value for a given path if it exists, and a bool indicating if the path exists.

func (*Radix) Insert

func (r *Radix) Insert(p Path, v interface{}) (interface{}, bool)

Insert inserts a value for the given path.

func (*Radix) Len

func (r *Radix) Len() int

Len returns the number of paths in the tree.

func (*Radix) ReplacePrefix

func (r *Radix) ReplacePrefix(p Path, other *Radix)

ReplacePrefix removes all entries under the supplied prefix in the radix tree and replaces them with the entries under the prefix from the other supplied radix tree.

func (*Radix) Walk

func (r *Radix) Walk(fn RadixWalkFn)

Walk walks the tree in order, invoking the supplied function at each node.

func (*Radix) WalkPrefix

func (r *Radix) WalkPrefix(p Path, fn RadixWalkFn)

WalkPrefix walks all paths including and under the prefix in the tree.

type RadixWalkFn

type RadixWalkFn func(Path, interface{}) WalkContinuation

type WalkContinuation

type WalkContinuation bool

const (
	ContinueWalk WalkContinuation = false
	HaltWalk     WalkContinuation = true
)