walk.mx raw

   1  package lattice
   2  
   3  // WalkPattern encodes branch transitions as 2 bits per branch.
   4  // Values are absolute branch identifiers + 1:
   5  //   0 = stop
   6  //   1 = noun  (Branch 0 + 1)
   7  //   2 = verb  (Branch 1 + 1)
   8  //   3 = modifier (Branch 2 + 1)
   9  //
  10  // bits 0-1: after noun, go to ...
  11  // bits 2-3: after verb, go to ...
  12  // bits 4-5: after modifier, go to ...
  13  type WalkPattern uint8
  14  
  15  const (
  16  	PatNounVerbMod WalkPattern = 0x02 | (0x03 << 2)               // noun->verb->mod->stop
  17  	PatNounMod     WalkPattern = 0x03                              // noun->mod->stop
  18  	PatVerbNoun    WalkPattern = 0x01 << 2                         // verb->noun->stop
  19  	PatFull        WalkPattern = 0x02 | (0x03 << 2) | (0x01 << 4) // noun->verb->mod->noun (cycle)
  20  )
  21  
  22  func (wp WalkPattern) Next(current Branch) uint8 {
  23  	shift := uint(current) * 2
  24  	return uint8((wp >> shift) & 0x3)
  25  }
  26  
  27  // branchToLinkIndex maps a (current branch, target branch) pair to the Link index on a Record.
  28  // noun:  Link[0]=verb, Link[1]=modifier
  29  // verb:  Link[0]=noun, Link[1]=modifier
  30  // mod:   Link[0]=noun, Link[1]=verb
  31  func branchToLinkIndex(current, target Branch) int {
  32  	switch current {
  33  	case Bnoun:
  34  		if target == Bverb {
  35  			return 0
  36  		}
  37  		return 1
  38  	case Bverb:
  39  		if target == Bnoun {
  40  			return 0
  41  		}
  42  		return 1
  43  	default:
  44  		if target == Bnoun {
  45  			return 0
  46  		}
  47  		return 1
  48  	}
  49  }
  50  
  51  // CrossWalk follows Record.Link pointers across branches according to the pattern.
  52  // Records are stable across B-tree splits, so links never go stale.
  53  func (t *Tree) CrossWalk(startRecIdx uint32, pattern WalkPattern, visit func(uint32, *Record) bool) {
  54  	ri := startRecIdx
  55  	visited := uint8(0)
  56  	for {
  57  		if ri == NullRec {
  58  			return
  59  		}
  60  		rec := t.getRecord(ri)
  61  		if !visit(ri, rec) {
  62  			return
  63  		}
  64  		visited++
  65  		if visited > 3 {
  66  			return
  67  		}
  68  		current := Branch(rec.Branch)
  69  		next := pattern.Next(current)
  70  		if next == 0 {
  71  			return
  72  		}
  73  		targetBranch := Branch(next - 1)
  74  		linkIdx := branchToLinkIndex(current, targetBranch)
  75  		ri = rec.Link[linkIdx]
  76  	}
  77  }
  78  
  79  // TripleWalk looks up one key per branch and returns the three records.
  80  func (t *Tree) TripleWalk(nounKey, verbKey, modKey Key) (n, v, m *Record) {
  81  	n = t.Lookup(Bnoun, nounKey)
  82  	v = t.Lookup(Bverb, verbKey)
  83  	m = t.Lookup(Bmodifier, modKey)
  84  	return
  85  }
  86  
  87  // Linked returns the cross-branch partner record indices.
  88  func (t *Tree) Linked(recIdx uint32) (uint32, uint32) {
  89  	r := t.getRecord(recIdx)
  90  	return r.Link[0], r.Link[1]
  91  }
  92