1// Package tree implements a tree for displaying hierarchical
2// password store entries. It is loosely based on
3// https://github.com/restic/restic/blob/master/internal/restic/tree.go
4package tree
5
6import (
7	"fmt"
8	"sort"
9)
10
11// Tree is a tree
12type Tree struct {
13	Nodes []*Node
14}
15
16// NewTree creates a new tree
17func NewTree() *Tree {
18	return &Tree{
19		Nodes: []*Node{},
20	}
21}
22
23// String returns the name of this tree
24func (t *Tree) String() string {
25	return fmt.Sprintf("Tree<%d nodes>", len(t.Nodes))
26}
27
28// Equals compares to another tree
29func (t *Tree) Equals(other *Tree) bool {
30	if len(t.Nodes) != len(other.Nodes) {
31		return false
32	}
33
34	for i, node := range t.Nodes {
35		if !node.Equals(*other.Nodes[i]) {
36			return false
37		}
38	}
39
40	return true
41}
42
43// Insert adds a new node at the right position
44func (t *Tree) Insert(node *Node) (*Node, error) {
45	pos, found := t.find(node.Name)
46	if found != nil {
47		if node.Mount {
48			t.Nodes[pos] = node
49			return node, nil
50		}
51		return t.Nodes[pos], fmt.Errorf("node %q already preset", node.Name)
52	}
53
54	// https://code.google.com/p/go-wiki/wiki/SliceTricks
55	t.Nodes = append(t.Nodes, &Node{})
56	copy(t.Nodes[pos+1:], t.Nodes[pos:])
57	t.Nodes[pos] = node
58
59	return node, nil
60}
61
62func (t *Tree) find(name string) (int, *Node) {
63	pos := sort.Search(len(t.Nodes), func(i int) bool {
64		return t.Nodes[i].Name >= name
65	})
66
67	if pos < len(t.Nodes) && t.Nodes[pos].Name == name {
68		return pos, t.Nodes[pos]
69	}
70
71	return pos, nil
72}
73
74// Sort ensures this tree is sorted
75func (t *Tree) Sort() {
76	list := Nodes(t.Nodes)
77	sort.Sort(list)
78	t.Nodes = list
79}
80