tally.gno

  1// Package tally orders a scoreboard: highest score first, ties broken by key.
  2//
  3// Sixteen realms in this repo carry their own sort.Interface triple, because
  4// gno has no sort.Slice and every leaderboard therefore needs a named type
  5// with Len, Less and Swap. Eight of them rank on ONE score and then break the
  6// tie, which is what this package is; the rest rank on two scores and keep
  7// their own comparator. They do not agree on what happens at a tie, and one of
  8// them does not break ties at all.
  9//
 10// # The tie-break is the point
 11//
 12// A Render that reshuffles between identical calls is a bug, so the final
 13// comparison must be a total order. Comparing the score again (as
 14// r/moul/x/daily/rpgroom's third clause does) is not one: two rows with equal
 15// scores compare false in both directions, and their order then falls out of
 16// whatever the sort algorithm did with the input, which is reproducible but
 17// nobody chose it. [Sort] always ends on the key, so equal scores render in a
 18// stable, explicable order.
 19//
 20// # What is not here
 21//
 22// Storage: the caller keeps its own avl tree and maps it to [Entry]. That is
 23// what makes this adoptable by realms that already have their state, and
 24// [Board] is for new ones that do not.
 25//
 26// Rendering: a podium and a table already have an owner in
 27// [p/moul/kit/ui](/p/moul/kit/ui/v0).
 28package tally
 29
 30import (
 31	"sort"
 32
 33	"gno.land/p/nt/avl/v0"
 34)
 35
 36// Entry is one row of a scoreboard: an opaque key and its score.
 37//
 38// Key is whatever the caller ranks by, usually an address in its String form.
 39// It is the tie-break, so it must be unique within one board.
 40type Entry struct {
 41	Key   string
 42	Score int64
 43}
 44
 45type byScore []Entry
 46
 47func (e byScore) Len() int      { return len(e) }
 48func (e byScore) Swap(i, j int) { e[i], e[j] = e[j], e[i] }
 49func (e byScore) Less(i, j int) bool {
 50	if e[i].Score != e[j].Score {
 51		return e[i].Score > e[j].Score
 52	}
 53	return e[i].Key < e[j].Key
 54}
 55
 56// Sort orders entries in place: highest score first, ties by key ascending.
 57func Sort(entries []Entry) { sort.Sort(byScore(entries)) }
 58
 59// Top returns the n highest entries, sorted. A n at or below zero returns
 60// nothing; a n past the end returns everything. The input is not modified.
 61func Top(entries []Entry, n int) []Entry {
 62	if n <= 0 || len(entries) == 0 {
 63		return nil
 64	}
 65	out := make([]Entry, len(entries))
 66	copy(out, entries)
 67	Sort(out)
 68	if n > len(out) {
 69		n = len(out)
 70	}
 71	return out[:n]
 72}
 73
 74// Rank returns the 1-based position of key once entries are sorted, or 0 if
 75// the key is absent. Equal scores still get distinct ranks, decided by the
 76// same key tie-break Sort uses, so no two rows ever claim the same place.
 77func Rank(entries []Entry, key string) int {
 78	sorted := make([]Entry, len(entries))
 79	copy(sorted, entries)
 80	Sort(sorted)
 81	for i, e := range sorted {
 82		if e.Key == key {
 83			return i + 1
 84		}
 85	}
 86	return 0
 87}
 88
 89// Board is a scoreboard that owns its storage, for a realm that does not
 90// already have one. It is backed by a tree rather than a map: gno map
 91// iteration order is unspecified, and a Render built on one is not
 92// reproducible.
 93type Board struct {
 94	scores *avl.Tree // key -> int64
 95}
 96
 97// NewBoard returns an empty Board.
 98func NewBoard() *Board { return &Board{scores: avl.NewTree()} }
 99
100// Add increases key's score by delta, which may be negative, and returns the
101// new score. A key that was absent starts at zero.
102func (b *Board) Add(key string, delta int64) int64 {
103	n := b.Score(key) + delta
104	b.scores.Set(key, n)
105	return n
106}
107
108// Set replaces key's score outright.
109func (b *Board) Set(key string, score int64) { b.scores.Set(key, score) }
110
111// Score returns key's score, or zero if it has none. It does not distinguish
112// an absent key from one scoring zero; use [Board.Has] when that matters.
113func (b *Board) Score(key string) int64 {
114	v := b.scores.Get(key)
115	if v == nil {
116		return 0
117	}
118	return v.(int64)
119}
120
121// Has reports whether key has been scored at all.
122func (b *Board) Has(key string) bool { return b.scores.Get(key) != nil }
123
124// Remove drops key, reporting whether it was there.
125func (b *Board) Remove(key string) bool {
126	_, removed := b.scores.Remove(key)
127	return removed
128}
129
130// Len is the number of scored keys.
131func (b *Board) Len() int { return b.scores.Size() }
132
133// Entries returns every row, sorted by [Sort].
134func (b *Board) Entries() []Entry {
135	out := make([]Entry, 0, b.scores.Size())
136	b.scores.Iterate("", "", func(k string, v any) bool {
137		out = append(out, Entry{Key: k, Score: v.(int64)})
138		return false
139	})
140	Sort(out)
141	return out
142}
143
144// Top returns the n highest rows, sorted.
145func (b *Board) Top(n int) []Entry { return Top(b.Entries(), n) }
146
147// Rank returns key's 1-based position, or 0 if it is not on the board.
148func (b *Board) Rank(key string) int {
149	if !b.Has(key) {
150		return 0
151	}
152	return Rank(b.Entries(), key)
153}