1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. 33
34. 34
35. 35
36. 36
37. 37
38. 38
39. 39
40. 40
41. 41
42. 42
43. 43
44. 44
45. 45
46. 46
47. 47
48. 48
49. 49
50. 50
51. 51
52. 52
53. 53
54. 54
55. 55
56. 56
57. 57
58. 58
59. 59
60. 60
61. 61
62. 62
63. 63
64. 64
65. 65
66. 66
67. 67
68. 68
69. 69
70. 70
71. 71
72. 72
73. 73
74. 74
75. 75
76. 76
77. 77
78. 78
79. 79
80. 80
81. 81
82. 82
83. 83
84. 84
85. 85
86. 86
87. 87
88. 88
89. 89
90. 90
91. 91
92. 92
93. 93

// Copyright 2015, Joe Tsai. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE.md file.

package prefix

type RangeCode struct {
	Base uint32 // Starting base offset of the range
	Len  uint32 // Bit-length of a subsequent integer to add to base offset
}
type RangeCodes []RangeCode

type RangeEncoder struct {
	rcs     RangeCodes
	lut     [1024]uint32
	minBase uint
}

// End reports the non-inclusive ending range.
func (rc RangeCode) End() uint32 { return rc.Base + (1 << rc.Len) }

// MakeRangeCodes creates a RangeCodes, where each region is assumed to be
// contiguously stacked, without any gaps, with bit-lengths taken from bits.
func MakeRangeCodes(minBase uint, bits []uint) (rc RangeCodes) {
	for _, nb := range bits {
		rc = append(rc, RangeCode{Base: uint32(minBase), Len: uint32(nb)})
		minBase += 1 << nb
	}
	return rc
}

// Base reports the inclusive starting range for all ranges.
func (rcs RangeCodes) Base() uint32 { return rcs[0].Base }

// End reports the non-inclusive ending range for all ranges.
func (rcs RangeCodes) End() uint32 { return rcs[len(rcs)-1].End() }

// checkValid reports whether the RangeCodes is valid. In order to be valid,
// the following must hold true:
//	rcs[i-1].Base <= rcs[i].Base
//	rcs[i-1].End  <= rcs[i].End
//	rcs[i-1].End  >= rcs[i].Base
//
// Practically speaking, each range must be increasing and must not have any
// gaps in between. It is okay for ranges to overlap.
func (rcs RangeCodes) checkValid() bool {
	if len(rcs) == 0 {
		return false
	}
	pre := rcs[0]
	for _, cur := range rcs[1:] {
		preBase, preEnd := pre.Base, pre.End()
		curBase, curEnd := cur.Base, cur.End()
		if preBase > curBase || preEnd > curEnd || preEnd < curBase {
			return false
		}
		pre = cur
	}
	return true
}

func (re *RangeEncoder) Init(rcs RangeCodes) {
	if !rcs.checkValid() {
		panic("invalid range codes")
	}
	*re = RangeEncoder{rcs: rcs, minBase: uint(rcs.Base())}
	for sym, rc := range rcs {
		base := int(rc.Base) - int(re.minBase)
		end := int(rc.End()) - int(re.minBase)
		if base >= len(re.lut) {
			break
		}
		if end > len(re.lut) {
			end = len(re.lut)
		}
		for i := base; i < end; i++ {
			re.lut[i] = uint32(sym)
		}
	}
}

func (re *RangeEncoder) Encode(offset uint) (sym uint) {
	if idx := int(offset - re.minBase); idx < len(re.lut) {
		return uint(re.lut[idx])
	}
	sym = uint(re.lut[len(re.lut)-1])
retry:
	if int(sym) >= len(re.rcs) || re.rcs[sym].Base > uint32(offset) {
		return sym - 1
	}
	sym++
	goto retry // Avoid for-loop so that this function can be inlined
}