1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
package slog
// A list[T] is an immutable sequence.
// It supports three operations: append, len and indexing (at).
// The zero value is an empty list.
//
// Repeated calls to append happen in amortized O(1) space and time. (Appending
// an element allocates one node directly, and the normalize operation always
// doubles the front slice, so we can charge two slots to each element.)
//
// The len method takes constant time.
//
// The at method requires a normalized list, and then takes constant time.
//
// It is possible to obtain quadratic behavior by alternating append and at:
// the normalize required by at is called for each appended element, causing
// front to be copied each time.
type list[T any] struct {
front []T
back *node[T] // reversed
lenBack int
}
type node[T any] struct {
el T
next *node[T]
}
// append returns a new list consisting of the receiver with x appended.
func (l list[T]) append(x T) list[T] {
if l.front == nil {
// Empty list; return one with one element.
return list[T]{
front: []T{x},
back: nil,
lenBack: 0,
}
}
if l.lenBack == len(l.front) {
// When there are as many elements in back as in front, grow
// front and move all of back to it.
l = l.normalize()
}
// Push a new node with the element onto back, which is stored in
// reverse order.
return list[T]{
front: l.front,
back: &node[T]{el: x, next: l.back},
lenBack: l.lenBack + 1,
}
}
// len returns the number of elements in the list.
func (l list[T]) len() int {
return len(l.front) + l.lenBack
}
// at returns the ith element of the list.
// The list must be normalized.
func (l list[T]) at(i int) T {
if l.back != nil {
panic("not normalized")
}
return l.front[i]
}
// normalize returns a list whose back is nil and whose front contains all the
// receiver's elements.
func (l list[T]) normalize() list[T] {
if l.back == nil {
return l
}
newFront := make([]T, len(l.front)+l.lenBack)
copy(newFront, l.front)
i := len(newFront) - 1
for b := l.back; b != nil; b = b.next {
newFront[i] = b.el
i--
}
return list[T]{
front: newFront,
back: nil,
lenBack: 0,
}
}
|
