func (mtt *mttNode) search(nodes []*mttNode, ns []string) []*mttNode {
	parent := mtt
	var children []*mttNode
	if parent.children == nil {
		return nodes
	}
	if len(ns) == 1 {
		switch ns[0] {
		case "*":
			children = parent.fetch([]string{})
		default:
			children = parent.gatherChildren(ns[0])
		}
		nodes = append(nodes, children...)
		return nodes
	}
	children = parent.gatherChildren(ns[0])
	for _, child := range children {
		nodes = child.search(nodes, ns[1:])
	}
	return nodes
}
search returns leaf nodes in the trie below the given namespace
package control
import (
	"fmt"
	"sort"
	"strings"
	"github.com/intelsdi-x/snap/core"
)
type mttNode struct {
	children map[string]*mttNode
	mts      map[int]*metricType
}
type MTTrie struct {
	*mttNode
}
func NewMTTrie() *MTTrie {
	m := &mttNode{
		children: map[string]*mttNode{},
	}
	return &MTTrie{m}
}
func (m *MTTrie) String() string {
	out := ""
	for _, mt := range m.gatherMetricTypes() {
		pluginKey := fmt.Sprintf("%s"+core.Separator+"%s"+core.Separator+"%d", mt.Plugin.TypeName(), mt.Plugin.Name(), mt.Plugin.Version())
		out += fmt.Sprintf("%s => %s\n", mt.Key(), pluginKey)
	}
	return out
}
func (m *MTTrie) gatherMetricTypes() []metricType {
	var mts []metricType
	var descendants []*mttNode
	for _, node := range m.children {
		descendants = gatherDescendants(descendants, node)
	}
	for _, c := range descendants {
		for _, mt := range c.mts {
			mts = append(mts, *mt)
		}
	}
	return mts
}
func (m *MTTrie) DeleteByPlugin(cp core.CatalogedPlugin) {
	for _, mt := range m.gatherMetricTypes() {
		mtPluginKey := fmt.Sprintf("%s"+core.Separator+"%s"+core.Separator+"%d", mt.Plugin.TypeName(), mt.Plugin.Name(), mt.Plugin.Version())
		cpKey := fmt.Sprintf("%s"+core.Separator+"%s"+core.Separator+"%d", cp.TypeName(), cp.Name(), cp.Version())
		if mtPluginKey == cpKey {
			m.RemoveMetric(mt)
		}
	}
}
func (m *MTTrie) RemoveMetric(mt metricType) {
	a, _ := m.find(mt.Namespace().Strings())
	if a != nil {
		for v, x := range a.mts {
			if mt.Version() == x.Version() {
				delete(a.mts, v)
			}
		}
	}
}
func (mtt *mttNode) Add(mt *metricType) {
	ns := mt.Namespace()
	node, index := mtt.walk(ns.Strings())
	if index == len(ns) {
		if node.mts == nil {
			node.mts = make(map[int]*metricType)
		}
		node.mts[mt.Version()] = mt
		return
	}
	for _, n := range ns[index:] {
		if node.children == nil {
			node.children = make(map[string]*mttNode)
		}
		node.children[n.Value] = &mttNode{}
		node = node.children[n.Value]
	}
	node.mts = make(map[int]*metricType)
	node.mts[mt.Version()] = mt
}
func (mtt *mttNode) Fetch(ns []string) ([]*metricType, error) {
	children := mtt.fetch(ns)
	var mts []*metricType
	for _, child := range children {
		for _, mt := range child.mts {
			mts = append(mts, mt)
		}
	}
	if len(mts) == 0 && len(ns) > 0 {
		return nil, errorMetricsNotFound("/" + strings.Join(ns, "/"))
	}
	return mts, nil
}
func (mtt *mttNode) Remove(ns []string) error {
	_, err := mtt.find(ns)
	if err != nil {
		return err
	}
	parent, err := mtt.find(ns[:len(ns)-1])
	if err != nil {
		return err
	}
	delete(parent.children, ns[len(ns)-1:][0])
	return nil
}
func (mtt *mttNode) GetMetric(ns []string, ver int) (*metricType, error) {
	mts, err := mtt.GetMetrics(ns, ver)
	if err != nil {
		return nil, err
	}
	if len(mts) > 1 {
		return nil, fmt.Errorf("Incoming namespace `%s` is too ambiguous (version: %d)", "/"+strings.Join(ns, "/"), ver)
	}
	return mts[0], nil
}
func (mtt *mttNode) GetMetrics(ns []string, ver int) ([]*metricType, error) {
	nodes := []*mttNode{}
	mts := []*metricType{}
	if len(ns) == 0 {
		return nil, errorEmptyNamespace()
	}
	nodes = mtt.search(nodes, ns)
	for _, node := range nodes {
		mt, err := getVersion(node.mts, ver)
		if err != nil {
			continue
		}
		mts = append(mts, mt)
	}
	if len(mts) == 0 {
		return nil, errorMetricNotFound("/"+strings.Join(ns, "/"), ver)
	}
	return mts, nil
}
func (mtt *mttNode) GetVersions(ns []string) ([]*metricType, error) {
	var nodes []*mttNode
	var mts []*metricType
	if len(ns) == 0 {
		return nil, errorEmptyNamespace()
	}
	nodes = mtt.search(nodes, ns)
	for _, node := range nodes {
		for _, mt := range node.mts {
			mts = append(mts, mt)
		}
	}
	if len(mts) == 0 {
		return nil, errorMetricNotFound("/" + strings.Join(ns, "/"))
	}
	return mts, nil
}
func (mtt *mttNode) fetch(ns []string) []*mttNode {
	node, err := mtt.find(ns)
	if err != nil {
		return nil
	}
	var children []*mttNode
	if node.mts != nil {
		children = append(children, node)
	}
	if node.children != nil {
		children = gatherDescendants(children, node)
	}
	return children
}
func (mtt *mttNode) walk(ns []string) (*mttNode, int) {
	parent := mtt
	var pp *mttNode
	for i, n := range ns {
		if parent.children == nil {
			return parent, i
		}
		pp = parent
		parent = parent.children[n]
		if parent == nil {
			return pp, i
		}
	}
	return parent, len(ns)
}