blob: 7b505ea007d6c57220aff7c93dea23a71f93074c [file] [log] [blame]
 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, } }