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