tree.gno

  1package staker
  2
  3import (
  4	"strconv"
  5	"strings"
  6
  7	"gno.land/p/nt/avl"
  8	"gno.land/p/nt/ufmt"
  9)
 10
 11// UintTree is a wrapper around an AVL tree for storing block timestamps as strings.
 12// Since block timestamps are defined as int64, we take int64 and convert it to uint64 for the tree.
 13//
 14// Methods:
 15// - Get: Retrieves a value associated with a uint64 key.
 16// - set: Stores a value with a uint64 key.
 17// - Has: Checks if a uint64 key exists in the tree.
 18// - remove: Removes a uint64 key and its associated value.
 19// - Iterate: Iterates over keys and values in a range.
 20// - ReverseIterate: Iterates in reverse order over keys and values in a range.
 21type UintTree struct {
 22	tree *avl.Tree // blockTimestamp -> any
 23}
 24
 25// NewUintTree creates a new UintTree instance.
 26func NewUintTree() *UintTree {
 27	return &UintTree{
 28		tree: avl.NewTree(),
 29	}
 30}
 31
 32func (self *UintTree) Get(key int64) (any, bool) {
 33	v, ok := self.tree.Get(EncodeInt64(key))
 34	if !ok {
 35		return nil, false
 36	}
 37	return v, true
 38}
 39
 40func (self *UintTree) Set(key int64, value any) {
 41	self.tree.Set(EncodeInt64(key), value)
 42}
 43
 44func (self *UintTree) Has(key int64) bool {
 45	return self.tree.Has(EncodeInt64(key))
 46}
 47
 48func (self *UintTree) Remove(key int64) {
 49	self.tree.Remove(EncodeInt64(key))
 50}
 51
 52func (self *UintTree) Iterate(start, end int64, fn func(key int64, value any) bool) {
 53	self.tree.Iterate(EncodeInt64(start), EncodeInt64(end), func(key string, value any) bool {
 54		return fn(DecodeInt64(key), value)
 55	})
 56}
 57
 58func (self *UintTree) ReverseIterate(start, end int64, fn func(key int64, value any) bool) {
 59	self.tree.ReverseIterate(EncodeInt64(start), EncodeInt64(end), func(key string, value any) bool {
 60		return fn(DecodeInt64(key), value)
 61	})
 62}
 63
 64func (self *UintTree) Size() int {
 65	return self.tree.Size()
 66}
 67
 68func (self *UintTree) IterateByOffset(offset, count int, fn func(key int64, value any) bool) {
 69	self.tree.IterateByOffset(offset, count, func(key string, value any) bool {
 70		return fn(DecodeInt64(key), value)
 71	})
 72}
 73
 74func (self *UintTree) Clone() *UintTree {
 75	if self == nil {
 76		return nil
 77	}
 78
 79	cloned := NewUintTree()
 80	self.tree.Iterate("", "", func(key string, value any) bool {
 81		cloned.tree.Set(key, value)
 82		return false
 83	})
 84
 85	return cloned
 86}
 87
 88// EncodeUint converts a uint64 number into a zero-padded 20-character string.
 89//
 90// Parameters:
 91// - num (uint64): The number to encode.
 92//
 93// Returns:
 94// - string: A zero-padded string representation of the number.
 95//
 96// Example:
 97// Input: 12345
 98// Output: "00000000000000012345"
 99func EncodeUint(num uint64) string {
100	// Convert the value to a decimal string.
101	s := strconv.FormatUint(num, 10)
102
103	// Zero-pad to a total length of 20 characters.
104	zerosNeeded := 20 - len(s)
105	return strings.Repeat("0", zerosNeeded) + s
106}
107
108func EncodeInt64(num int64) string {
109	if num < 0 {
110		panic(ufmt.Sprintf("negative value not supported: %d", num))
111	}
112	return EncodeUint(uint64(num))
113}
114
115// DecodeUint converts a zero-padded string back into a uint64 number.
116//
117// Parameters:
118// - s (string): The zero-padded string.
119//
120// Returns:
121// - uint64: The decoded number.
122//
123// Panics:
124// - If the string cannot be parsed into a uint64.
125//
126// Example:
127// Input: "00000000000000012345"
128// Output: 12345
129func DecodeUint(s string) uint64 {
130	num, err := strconv.ParseUint(s, 10, 64)
131	if err != nil {
132		panic(err)
133	}
134	return num
135}
136
137func DecodeInt64(s string) int64 {
138	num, err := strconv.ParseInt(s, 10, 64)
139	if err != nil {
140		panic(err)
141	}
142	return num
143}
144
145// EncodeInt takes an int32 and returns a zero-padded decimal string
146// with up to 10 digits for the absolute value.
147// If the number is negative, the '-' sign comes first, followed by zeros, then digits.
148func EncodeInt(num int32) string {
149	// Convert the absolute value to a decimal string.
150	absValue := int64(num)
151	isNegative := false
152	if num < 0 {
153		isNegative = true
154		absValue = -absValue // Safely negate into int64 to avoid overflow.
155	}
156
157	s := strconv.FormatInt(absValue, 10)
158
159	// Zero-pad to a total of 10 digits for the absolute value.
160	// (The '-' sign will be added later if needed.)
161	zerosNeeded := 10 - len(s)
162	if zerosNeeded < 0 {
163		zerosNeeded = 0
164	}
165
166	padded := strings.Repeat("0", zerosNeeded) + s
167
168	// If the original number was negative, prepend '-'.
169	if isNegative {
170		return "-" + padded
171	}
172	return padded
173}