distance.mx raw

   1  package iskra
   2  
   3  import "git.smesh.lol/iskradb/lattice"
   4  
   5  // WalkPath returns the node path from root to key in the given branch.
   6  // Delegates to iskradb's WalkPath which tracks intermediate nodes.
   7  func (t *Tree) WalkPath(branch lattice.Branch, key lattice.Key) []uint32 {
   8  	return t.db.WalkPath(branch, key)
   9  }
  10  
  11  // TreeDistance returns the hop count between two keys within a branch
  12  // via their lowest common ancestor. Returns -1 if either key is not found.
  13  func (t *Tree) TreeDistance(branch lattice.Branch, keyA, keyB lattice.Key) int {
  14  	if keyA == keyB {
  15  		return 0
  16  	}
  17  
  18  	pathA := t.WalkPath(branch, keyA)
  19  	pathB := t.WalkPath(branch, keyB)
  20  	if pathA == nil || pathB == nil {
  21  		return -1
  22  	}
  23  
  24  	lcaDepth := 0
  25  	minLen := len(pathA)
  26  	if len(pathB) < minLen {
  27  		minLen = len(pathB)
  28  	}
  29  	for i := 0; i < minLen; i++ {
  30  		if pathA[i] != pathB[i] {
  31  			break
  32  		}
  33  		lcaDepth = i
  34  	}
  35  
  36  	return (len(pathA) - 1 - lcaDepth) + (len(pathB) - 1 - lcaDepth)
  37  }
  38