atlas

README

Intro

A connected graph of string to string pairs (map[string]string) with amortized construction costs and O(1) equality cost.

The O(1) equality comes from comparing the pointers to the struct instead of the struct itself.

Amortized cost mean that as time pass on and you stop adding more pairs the fairly high initial costs go down.

Additionally this should considerably reduce GC [citation needed] as we don't continuously make new objects.

TODO

• Count the number of nodes, for example in the root.
• Do not have any of this in the Go's memory as this just adds to things the GC needs to check but will in practice never free as we keep this memory around forever.
• Try to have a GC for nodes that haven't been accessed in a long while.

Documentation

Overview

Package atlas implement a graph of string to string pairs. It is optimzed for when a finite amount of key-value pairs will be constructed in the same way over time. It is also thread-safe. It's particularly good at taking the same root through the graph over and over again and the Node's can directly be used as map keys or compared for equality against each other.

Index

• type Node
  • func New() *Node
  • func (n *Node) AddLink(key, value string) *Node
  • func (n *Node) Contains(sub *Node) bool
  • func (n *Node) Data() (prev *Node, key string, value string)
  • func (n *Node) DeleteKey(k string) *Node
  • func (n *Node) IsRoot() bool
  • func (n *Node) Len() int
  • func (n *Node) Path() map[string]string
  • func (n *Node) ValueByKey(k string) (string, bool)

Examples

• Node.Data

Types

type Node

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

Node records a set of key-value pairs. It is unique per Root and it can directly be compared with `==` to another Node.

func New

func New() *Node

New returns a new root Node. Nodes from different roots being used together have undefined behaviour.

func (*Node) AddLink

func (n *Node) AddLink(key, value string) *Node

AddLink adds the key and value strings to the tree and returns the new Node that includes all the key and values of the parent Node plus the new key-value pair provided.

If another pair with the same key and a different value already exists in the path then the new Node will have the key replaced with the new provided value from the pair.

(e.g. adding keyA, val2 to a set of {keyA:val1, keyB:val3}
will return the set {keyA: val2, keyB: val3}).

func (*Node) Contains

func (n *Node) Contains(sub *Node) bool

Contains checks that for each key-value pair in the provided Node there will be the same key with the same value in the receiver's Node.

func (*Node) Data

func (n *Node) Data() (prev *Node, key string, value string)

Data returns the previous node and the key and value of the current one.

Example

node := New().
	AddLink("foo", "1").
	AddLink("bar", "2").
	AddLink("baz", "3")

for iter := node; !iter.IsRoot(); {
	prev, key, value := iter.Data()
	fmt.Printf("%s: %s\n", key, value)
	iter = prev
}

Output:

bar: 2
baz: 3
foo: 1

func (*Node) DeleteKey

func (n *Node) DeleteKey(k string) *Node

DeleteKey returns a Node that hasn't the provided key in its set of recorded key-value pairs.

func (*Node) IsRoot

func (n *Node) IsRoot() bool

IsRoot checks if the current Node is the root.

func (*Node) Len

func (n *Node) Len() int

Len returns the length of the all key-values pairs recorded in the Node.

func (*Node) Path

func (n *Node) Path() map[string]string

Path returns a map representing all key-value pairs recorded in the Node.

func (*Node) ValueByKey

func (n *Node) ValueByKey(k string) (string, bool)

ValueByKey gets the value of key written in this Node or any of its ancestor.