coord.mx raw

   1  package lattice
   2  
   3  const TritEnd = 0
   4  
   5  // TritPath packs up to 16 trits into a uint32 (2 bits each).
   6  // Trit 0 is the branch selector (1=noun, 2=verb, 3=modifier).
   7  // Trits 1..15 encode the path within the branch.
   8  type TritPath uint32
   9  
  10  func (p TritPath) Trit(i int) uint8 {
  11  	return uint8((p >> (uint(i) * 2)) & 0x3)
  12  }
  13  
  14  func (p TritPath) Depth() int {
  15  	for i := 0; i < 16; i++ {
  16  		if p.Trit(i) == TritEnd {
  17  			return i
  18  		}
  19  	}
  20  	return 16
  21  }
  22  
  23  func (p TritPath) Branch() uint8 {
  24  	return p.Trit(0)
  25  }
  26  
  27  func MakeTritPath(trits ...uint8) TritPath {
  28  	var p TritPath
  29  	for i, t := range trits {
  30  		if i >= 16 {
  31  			break
  32  		}
  33  		p |= TritPath(t&0x3) << (uint(i) * 2)
  34  	}
  35  	return p
  36  }
  37  
  38  // BranchTritPath creates a TritPath with just the branch selector set.
  39  func BranchTritPath(b Branch) TritPath {
  40  	return TritPath(b + 1)
  41  }
  42  
  43  func Parent(p TritPath) TritPath {
  44  	d := p.Depth()
  45  	if d <= 1 {
  46  		return 0
  47  	}
  48  	// zero out the last trit
  49  	shift := uint(d-1) * 2
  50  	mask := TritPath(0x3) << shift
  51  	return p &^ mask
  52  }
  53  
  54  func Child(p TritPath, dir uint8) TritPath {
  55  	d := p.Depth()
  56  	if d >= 16 {
  57  		return p
  58  	}
  59  	return p | TritPath(dir&0x3)<<(uint(d)*2)
  60  }
  61  
  62  // LCA returns the longest common prefix of two trit paths.
  63  func LCA(a, b TritPath) TritPath {
  64  	da := a.Depth()
  65  	db := b.Depth()
  66  	limit := da
  67  	if db < limit {
  68  		limit = db
  69  	}
  70  	shared := 0
  71  	for i := 0; i < limit; i++ {
  72  		if a.Trit(i) != b.Trit(i) {
  73  			break
  74  		}
  75  		shared++
  76  	}
  77  	// mask out everything beyond shared prefix
  78  	if shared == 0 {
  79  		return 0
  80  	}
  81  	mask := TritPath((1 << (uint(shared) * 2)) - 1)
  82  	return a & mask
  83  }
  84  
  85  // Distance returns the hop count between two trit paths via their LCA.
  86  // Returns -1 if either path is unassigned.
  87  func Distance(a, b TritPath) int {
  88  	da := a.Depth()
  89  	db := b.Depth()
  90  	if da == 0 || db == 0 {
  91  		return -1
  92  	}
  93  	shared := 0
  94  	limit := da
  95  	if db < limit {
  96  		limit = db
  97  	}
  98  	for i := 0; i < limit; i++ {
  99  		if a.Trit(i) != b.Trit(i) {
 100  			break
 101  		}
 102  		shared++
 103  	}
 104  	return (da - shared) + (db - shared)
 105  }
 106  
 107  // Resolve applies an expansion multiplier to a TritPath's depth component.
 108  // Each trit beyond the branch selector gets replicated `mult` times.
 109  func Resolve(p TritPath, mult uint8) TritPath {
 110  	if mult <= 1 {
 111  		return p
 112  	}
 113  	d := p.Depth()
 114  	if d <= 1 {
 115  		return p
 116  	}
 117  	var out TritPath
 118  	out = TritPath(p.Trit(0))
 119  	pos := 1
 120  	for i := 1; i < d; i++ {
 121  		t := p.Trit(i)
 122  		for j := uint8(0); j < mult && pos < 16; j++ {
 123  			out |= TritPath(t&0x3) << (uint(pos) * 2)
 124  			pos++
 125  		}
 126  	}
 127  	return out
 128  }
 129