slog/list.go

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,
	}
}