rankings.gno
5.12 Kb · 164 lines
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}
