intersect.go

package trie

import (
	"github.com/libp2p/go-libp2p-xor/key"
)

// Intersect computes the intersection of the keys in p and q.
// p and q must be non-nil. The returned trie is never nil.
func Intersect(p, q *Trie) *Trie {
	return IntersectAtDepth(0, p, q)
}

func IntersectAtDepth(depth int, p, q *Trie) *Trie {
	switch {
	case p.IsLeaf() && q.IsLeaf():
		if p.IsEmpty() || q.IsEmpty() {
			return &Trie{} // empty set
		} else {
			if key.Equal(p.Key, q.Key) {
				return &Trie{Key: p.Key} // singleton
			} else {
				return &Trie{} // empty set
			}
		}
	case p.IsLeaf() && !q.IsLeaf():
		if p.IsEmpty() {
			return &Trie{} // empty set
		} else {
			if _, found := q.FindAtDepth(depth, p.Key); found {
				return &Trie{Key: p.Key}
			} else {
				return &Trie{} // empty set
			}
		}
	case !p.IsLeaf() && q.IsLeaf():
		return Intersect(q, p)
	case !p.IsLeaf() && !q.IsLeaf():
		disjointUnion := &Trie{
			Branch: [2]*Trie{
				IntersectAtDepth(depth+1, p.Branch[0], q.Branch[0]),
				IntersectAtDepth(depth+1, p.Branch[1], q.Branch[1]),
			},
		}
		disjointUnion.shrink()
		return disjointUnion
	}
	panic("unreachable")
}