prefixmap

README

• 
• 
• 

PrefixMap

PrefixMap is a prefix-enhanced map that eases the retrieval of values based on key prefixes.

Quick Start

Creating a PrefixMap

// creates the map object
prefixMap := prefixmap.New()

Inserting a value

 // inserts values 1, "value 2" and false for key 'someKey'
prefixMap.Insert("someKey", 1, "value 2", false)

// map now contains
//
// 'someKey' => [1, "value 2", false]

Replace values for key

prefixMap.Insert("key", "hello")

// map contents:
//
// 'key' => ["hello"]

prefixMap.Insert("key", "world")

// map contents:
//
// 'key' => ["hello", "world"]

// now replacing the contents for key
prefixMap.Replace("key", "new value")

// map contents:
//
// 'key' => ["new value"]

Checking if a key exists

prefixMap.Insert("key", "hello")

prefixMap.Contains("k") // #=> false
prefixMap.Contains("key") // #=> true
prefixMap.ContainsPrefix("k") // #=> true

Getting by key

prefixMap.Insert("foo", "bar", "baz", "quz")

data := prefixMap.Get("foo") // #=> [bar, baz, quz]

Getting by keys prefix

prefixMap.Insert("prefix1", "prefix1")
prefixMap.Insert("prefix2", "prefix2")
prefixMap.Insert("prefix3", "prefix3")

data := prefixMap.GetByPrefix("prefix") // #=> [prefix1, prefix2, prefix3]

Iterate over prefixes

PrefixMap exposes an EachPrefix method that executes a callback function against every prefix in the map. The prefixes are iterated over using a Depth First Search algorithm. At each iteration the given callback is invoked. The callback allows you to skip a branch iteration altogether if you're not satisfied with what you're looking for. Check out PrefixCallback documentation for more information.

prefixMap.EachPrefix(func(prefix Prefix) (bool, bool) {
    
    // do something with the current prefix
    doSomething(prefix.Key)
    
    // keep iterating
    return false, false
})

License

The code contained in this repository is provided as is under the terms of the MIT license as specified here.

Documentation

Index

• type Node
  • func (m *Node) Depth() int
  • func (m *Node) Key() string
• type Prefix
  • func (p *Prefix) Depth() int
• type PrefixCallback
• type PrefixMap
  • func New() *PrefixMap
  • func (m *PrefixMap) Contains(key string) bool
  • func (m *PrefixMap) ContainsPrefix(key string) bool
  • func (m *PrefixMap) EachPrefix(callback PrefixCallback)
  • func (m *PrefixMap) Get(key string) []interface{}
  • func (m *PrefixMap) GetByPrefix(key string) []interface{}
  • func (m *PrefixMap) Insert(key string, values ...interface{})
  • func (m *PrefixMap) Replace(key string, values ...interface{})

Types

type Node

type Node struct {
	// true if this node is a leaf node
	IsLeaf bool

	// the reference to the parent node
	Parent *Node

	// the children nodes
	Children []*Node
	// contains filtered or unexported fields
}

Node is a single node within the map

func (*Node) Depth

func (m *Node) Depth() int

Depth returns the depth of the current node within the map

func (*Node) Key

func (m *Node) Key() string

Key Retrieves current node key complexity: MAX|O(log(N))| where N is the number of nodes in the map. Number of nodes in the map cannot exceed number of keys + 1.

type Prefix

type Prefix struct {

	// The current prefix string
	Key string

	// The values associated to the current prefix
	Values []interface{}
	// contains filtered or unexported fields
}

Prefix holds prefix information passed to the PrefixCallback instance by the EachPrefifx method.

func (*Prefix) Depth

func (p *Prefix) Depth() int

Depth returns the depth of the corresponding node for this prefix in the map.

type PrefixCallback

type PrefixCallback func(prefix Prefix) (skipBranch bool, halt bool)

PrefixCallback is invoked by EachPrefix for each prefix reached by the traversal. The callback has the ability to affect the traversal. Returning skipBranch = true will make the traversal skip the current branch and jump to the sibling node in the map. Returning halt = true, instead, will halt the traversal altogether.

type PrefixMap

type PrefixMap Node

PrefixMap type

func New

func New() *PrefixMap

New returns a new empty map

func (*PrefixMap) Contains

func (m *PrefixMap) Contains(key string) bool

Contains checks if the given key is present in the map In this case, an exact match case is considered If you're interested in prefix-based check: ContainsPrefix

func (*PrefixMap) ContainsPrefix

func (m *PrefixMap) ContainsPrefix(key string) bool

ContainsPrefix checks if the given prefix is present as key in the map

func (*PrefixMap) EachPrefix

func (m *PrefixMap) EachPrefix(callback PrefixCallback)

EachPrefix iterates over the prefixes contained in the map using a DFS algorithm. The callback can be used to skip a prefix branch altogether or halt the iteration.

func (*PrefixMap) Get

func (m *PrefixMap) Get(key string) []interface{}

Get returns the data associated with the given key in the map or nil if no such key is present in the map

func (*PrefixMap) GetByPrefix

func (m *PrefixMap) GetByPrefix(key string) []interface{}

GetByPrefix returns a flattened collection of values associated with the given prefix key

func (*PrefixMap) Insert

func (m *PrefixMap) Insert(key string, values ...interface{})

Insert inserts a new value in the map for the specified key If the key is already present in the map, the value is appended to the values list associated with the given key

func (*PrefixMap) Replace

func (m *PrefixMap) Replace(key string, values ...interface{})

Replace replaces the value(s) for the given key in the map with the give ones. If no such key is present, this method behaves the same as Insert