rankings.gno

  1package game
  2
  3import "strings"
  4
  5// ranking is a leaderboard on a single number that only goes up, the count of
  6// kills: the top players, best first, at most leaderboard_size lines and one
  7// line per player. With equal scores, the player who got there first stays
  8// ahead.
  9//
 10// It is kept sorted at write time, so reading it never has to look at every
 11// player. Scores only going up is what makes that exact: a player outside
 12// the list can only enter it through raise.
 13//
 14// The two slices are parallel: slices of plain values are one stored object
 15// each, where a slice of structs would be one object per line. Measured on
 16// gnodev, a line costs about 190 bytes this way.
 17type ranking struct {
 18	addrs  []address
 19	scores []int64
 20}
 21
 22// leaderboardSize returns how many lines a leaderboard may hold.
 23func leaderboardSize() int {
 24	return int(findParam(paramLeaderboardSize).value)
 25}
 26
 27// raise puts a player at their place after their score went up from old to
 28// score. It returns the ranking to store, and changed == false when it is
 29// left as it is: the player is not on a full list and still not good enough
 30// to get on.
 31func (r ranking) raise(addr address, old, score int64, size int) (next ranking, changed bool) {
 32	from := r.lineOf(addr, old)
 33	to := r.search(score - 1) // after every line with this score or more
 34	if from < 0 && to >= size {
 35		return r, false
 36	}
 37	if from >= 0 && to > from {
 38		to = from // cannot happen: a score only goes up
 39	}
 40	next = ranking{
 41		addrs:  spliceAddrs(r.addrs, from, to, addr, size),
 42		scores: spliceInts(r.scores, from, to, score, size),
 43	}
 44	return next, true
 45}
 46
 47// search returns the index of the first line with a score of limit or less,
 48// the number of lines when there is none. The list is sorted, so this is a
 49// binary search.
 50func (r ranking) search(limit int64) int {
 51	lo, hi := 0, len(r.scores)
 52	for lo < hi {
 53		mid := (lo + hi) / 2
 54		if r.scores[mid] <= limit {
 55			hi = mid
 56		} else {
 57			lo = mid + 1
 58		}
 59	}
 60	return lo
 61}
 62
 63// lineOf returns the index of a player's line, -1 when they have none. old
 64// is the player's score before the change being applied.
 65//
 66// A line always carries the current score of its player, because every
 67// change of a score goes through raise. So the line can only be among those
 68// with exactly old, which the binary search finds without reading the whole
 69// list: with 32 players credited in one call on a 100 line list, comparing
 70// every address would cost millions of gas. A player whose score was zero
 71// has never been through raise and has no line.
 72func (r ranking) lineOf(addr address, old int64) int {
 73	if old <= 0 {
 74		return -1
 75	}
 76	for i := r.search(old); i < len(r.scores) && r.scores[i] == old; i++ {
 77		if r.addrs[i] == addr {
 78			return i
 79		}
 80	}
 81	return -1
 82}
 83
 84// spliceAddrs returns a copy of a leaderboard column with v inserted at index
 85// to. With from >= 0 the element at that index, the player's previous line,
 86// is left out; to must not be past it. With from < 0 the result is kept to
 87// size elements by dropping the tail; to must be below size.
 88//
 89// The copy has exactly the length of its content, so that nothing else stays
 90// in storage, and it is built with the append builtin: on a 100 line board a
 91// loop over the lines costs several times more gas.
 92func spliceAddrs(list []address, from, to int, v address, size int) []address {
 93	if from < 0 {
 94		if len(list) >= size {
 95			list = list[:size-1]
 96		}
 97		out := make([]address, 0, len(list)+1)
 98		out = append(out, list[:to]...)
 99		out = append(out, v)
100		return append(out, list[to:]...)
101	}
102	out := make([]address, 0, len(list))
103	out = append(out, list[:to]...)
104	out = append(out, v)
105	out = append(out, list[to:from]...)
106	return append(out, list[from+1:]...)
107}
108
109// spliceInts is spliceAddrs for a column of numbers.
110func spliceInts(list []int64, from, to int, v int64, size int) []int64 {
111	if from < 0 {
112		if len(list) >= size {
113			list = list[:size-1]
114		}
115		out := make([]int64, 0, len(list)+1)
116		out = append(out, list[:to]...)
117		out = append(out, v)
118		return append(out, list[to:]...)
119	}
120	out := make([]int64, 0, len(list))
121	out = append(out, list[:to]...)
122	out = append(out, v)
123	out = append(out, list[to:from]...)
124	return append(out, list[from+1:]...)
125}
126
127// cut returns the first size lines of the ranking, in slices of exactly that
128// length, so that nothing beyond the kept lines stays in storage.
129func (r ranking) cut(size int) ranking {
130	n := len(r.addrs)
131	if n > size {
132		n = size
133	}
134	out := ranking{addrs: make([]address, n), scores: make([]int64, n)}
135	copy(out.addrs, r.addrs)
136	copy(out.scores, r.scores)
137	return out
138}
139
140// trimRankings cuts the kill leaderboard down to leaderboard_size.
141func trimRankings() {
142	if size := leaderboardSize(); len(killers.addrs) > size {
143		killers = killers.cut(size)
144	}
145}
146
147// writeRanking writes a ranking as a JSON array of
148// {"address":"g1...","<key>":<score>} objects, best first.
149func writeRanking(b *strings.Builder, r ranking, key string) {
150	b.WriteByte('[')
151	for i, addr := range r.addrs {
152		if i > 0 {
153			b.WriteByte(',')
154		}
155		b.WriteString(`{"address":"`)
156		b.WriteString(addr.String())
157		b.WriteString(`","`)
158		b.WriteString(key)
159		b.WriteString(`":`)
160		b.WriteString(itoa(r.scores[i]))
161		b.WriteByte('}')
162	}
163	b.WriteByte(']')
164}