tree.gno

  1package staker
  2
  3import (
  4	"strconv"
  5	"strings"
  6
  7	bptree "gno.land/p/nt/bptree/v0"
  8	ufmt "gno.land/p/nt/ufmt/v0"
  9)
 10
 11// UintTree is a wrapper around a B+ 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   *bptree.BPTree // blockTimestamp -> any
 23	fanout int
 24}
 25
 26// NewBPTreeN allocates a raw BP-tree under /r/gnoswap/staker's realm
 27// context (the realm that declares Pool/Deposit/ExternalIncentive). The tree's
 28// PkgID is therefore /r/gnoswap/staker, matching the domain values it stores,
 29// so tree.Set leaf-slot writes clear the readonly-taint gate regardless of
 30// which realm (staker/v1, mock) calls Set (borrow rule #2 borrows m.Realm to
 31// the tree's owning realm). Implementations and mocks must allocate trees that
 32// hold /r/gnoswap/staker-declared values through here rather than calling
 33// bptree.NewBPTreeN directly in their own realm.
 34func NewBPTreeN(fanout int) *bptree.BPTree {
 35	return bptree.NewBPTreeN(fanout)
 36}
 37
 38// NewUintTree creates a new UintTree instance with default fanout 64.
 39func NewUintTree() *UintTree {
 40	return NewUintTreeN(64)
 41}
 42
 43// NewUintTreeN creates a new UintTree instance with the specified fanout.
 44func NewUintTreeN(fanout int) *UintTree {
 45	return &UintTree{
 46		tree:   bptree.NewBPTreeN(fanout),
 47		fanout: fanout,
 48	}
 49}
 50
 51func (self *UintTree) Get(key int64) (any, bool) {
 52	v, ok := self.tree.Get(EncodeInt64(key))
 53	if !ok {
 54		return nil, false
 55	}
 56	return v, true
 57}
 58
 59func (self *UintTree) Set(key int64, value any) {
 60	self.tree.Set(EncodeInt64(key), value)
 61}
 62
 63func (self *UintTree) Has(key int64) bool {
 64	return self.tree.Has(EncodeInt64(key))
 65}
 66
 67func (self *UintTree) Remove(key int64) {
 68	self.tree.Remove(EncodeInt64(key))
 69}
 70
 71func (self *UintTree) Iterate(start, end int64, fn func(key int64, value any) bool) {
 72	self.tree.Iterate(EncodeInt64(start), EncodeInt64(end), func(key string, value any) bool {
 73		return fn(DecodeInt64(key), value)
 74	})
 75}
 76
 77func (self *UintTree) ReverseIterate(start, end int64, fn func(key int64, value any) bool) {
 78	self.tree.ReverseIterate(EncodeInt64(start), EncodeInt64(end), func(key string, value any) bool {
 79		return fn(DecodeInt64(key), value)
 80	})
 81}
 82
 83func (self *UintTree) Size() int {
 84	return self.tree.Size()
 85}
 86
 87func (self *UintTree) IterateByOffset(offset, count int, fn func(key int64, value any) bool) {
 88	self.tree.IterateByOffset(offset, count, func(key string, value any) bool {
 89		return fn(DecodeInt64(key), value)
 90	})
 91}
 92
 93func (self *UintTree) Clone() *UintTree {
 94	if self == nil {
 95		return nil
 96	}
 97
 98	cloned := NewUintTreeN(self.fanout)
 99	self.tree.Iterate("", "", func(key string, value any) bool {
100		cloned.tree.Set(key, value)
101		return false
102	})
103
104	return cloned
105}
106
107// EncodeUint converts a uint64 number into a zero-padded 20-character string.
108//
109// Parameters:
110// - num (uint64): The number to encode.
111//
112// Returns:
113// - string: A zero-padded string representation of the number.
114//
115// Example:
116// Input: 12345
117// Output: "00000000000000012345"
118func EncodeUint(num uint64) string {
119	// Convert the value to a decimal string.
120	s := strconv.FormatUint(num, 10)
121
122	// Zero-pad to a total length of 20 characters.
123	zerosNeeded := 20 - len(s)
124	return strings.Repeat("0", zerosNeeded) + s
125}
126
127func EncodeInt64(num int64) string {
128	if num < 0 {
129		panic(ufmt.Sprintf("negative value not supported: %d", num))
130	}
131	return EncodeUint(uint64(num))
132}
133
134// DecodeUint converts a zero-padded string back into a uint64 number.
135//
136// Parameters:
137// - s (string): The zero-padded string.
138//
139// Returns:
140// - uint64: The decoded number.
141//
142// Panics:
143// - If the string cannot be parsed into a uint64.
144//
145// Example:
146// Input: "00000000000000012345"
147// Output: 12345
148func DecodeUint(s string) uint64 {
149	num, err := strconv.ParseUint(s, 10, 64)
150	if err != nil {
151		panic(err)
152	}
153	return num
154}
155
156func DecodeInt64(s string) int64 {
157	num, err := strconv.ParseInt(s, 10, 64)
158	if err != nil {
159		panic(err)
160	}
161	return num
162}
163
164// EncodeInt takes an int32 and returns a zero-padded decimal string
165// with up to 10 digits for the absolute value.
166// If the number is negative, the '-' sign comes first, followed by zeros, then digits.
167func EncodeInt(num int32) string {
168	// Convert the absolute value to a decimal string.
169	absValue := int64(num)
170	isNegative := false
171	if num < 0 {
172		isNegative = true
173		absValue = -absValue // Safely negate into int64 to avoid overflow.
174	}
175
176	s := strconv.FormatInt(absValue, 10)
177
178	// Zero-pad to a total of 10 digits for the absolute value.
179	// (The '-' sign will be added later if needed.)
180	zerosNeeded := 10 - len(s)
181	if zerosNeeded < 0 {
182		zerosNeeded = 0
183	}
184
185	padded := strings.Repeat("0", zerosNeeded) + s
186
187	// If the original number was negative, prepend '-'.
188	if isNegative {
189		return "-" + padded
190	}
191	return padded
192}