seqid.gno

 1// Package seqid provides a simple way to have sequential IDs which will be
 2// ordered correctly when inserted in an AVL tree.
 3//
 4// Sample usage:
 5//
 6//	var id seqid.ID
 7//	var users avl.Tree
 8//
 9//	func NewUser() {
10//		users.Set(id.Next().String(), &User{ ... })
11//	}
12package seqid
13
14import (
15	"encoding/binary"
16
17	"gno.land/p/demo/cford32"
18)
19
20// An ID is a simple sequential ID generator.
21type ID uint64
22
23// Next advances the ID i.
24// It will panic if increasing ID would overflow.
25func (i *ID) Next() ID {
26	next, ok := i.TryNext()
27	if !ok {
28		panic("seqid: next ID overflows uint64")
29	}
30	return next
31}
32
33const maxID ID = 1<<64 - 1
34
35// TryNext increases i by 1 and returns its value.
36// It returns true if successful, or false if the increment would result in
37// an overflow.
38func (i *ID) TryNext() (ID, bool) {
39	if *i == maxID {
40		// Addition will overflow.
41		return 0, false
42	}
43	*i++
44	return *i, true
45}
46
47// Binary returns a big-endian binary representation of the ID,
48// suitable to be used as an AVL key.
49func (i ID) Binary() string {
50	buf := make([]byte, 8)
51	binary.BigEndian.PutUint64(buf, uint64(i))
52	return string(buf)
53}
54
55// String encodes i using cford32's compact encoding. For more information,
56// see the documentation for package [gno.land/p/demo/cford32].
57//
58// The result of String will be a 7-byte string for IDs [0,2^34), and a
59// 13-byte string for all values following that. All generated string IDs
60// follow the same lexicographic order as their number values; that is, for any
61// two IDs (x, y) such that x < y, x.String() < y.String().
62// As such, this string representation is suitable to be used as an AVL key.
63func (i ID) String() string {
64	return string(cford32.PutCompact(uint64(i)))
65}
66
67// FromBinary creates a new ID from the given string, expected to be a binary
68// big-endian encoding of an ID (such as that of [ID.Binary]).
69// The second return value is true if the conversion was successful.
70func FromBinary(b string) (ID, bool) {
71	if len(b) != 8 {
72		return 0, false
73	}
74	return ID(binary.BigEndian.Uint64([]byte(b))), true
75}
76
77// FromString creates a new ID from the given string, expected to be a string
78// representation using cford32, such as that returned by [ID.String].
79//
80// The encoding scheme used by cford32 allows the same ID to have many
81// different representations (though the one returned by [ID.String] is only
82// one, deterministic and safe to be used in AVL). The encoding scheme is
83// "human-centric" and is thus case insensitive, and maps some ambiguous
84// characters to be the same, ie. L = I = 1, O = 0. For this reason, when
85// parsing user input to retrieve a key (encoded as a string), always sanitize
86// it first using FromString, then run String(), instead of using the user's
87// input directly.
88func FromString(b string) (ID, error) {
89	n, err := cford32.Uint64([]byte(b))
90	return ID(n), err
91}