gno.land/p/moul/fifo/v0⧉

1// Package fifo implements a fixed-size FIFO (First-In-First-Out) list data structure2// using a singly-linked list. The implementation prioritizes storage efficiency by minimizing3// storage operations - each add/remove operation only updates 1-2 pointers, regardless of4// list size.5//6// Key features:7// - Fixed-size with automatic removal of oldest entries when full8// - Support for both prepend (add at start) and append (add at end) operations9// - Constant storage usage through automatic pruning10// - O(1) append operations and latest element access11// - Iterator support for sequential access12// - Dynamic size adjustment via SetMaxSize13//14// This implementation is optimized for frequent updates, as insertions and deletions only15// require updating 1-2 pointers. However, random access operations are O(n) as they require16// traversing the list. For use cases where writes are rare, a slice-based17// implementation might be more suitable.18//19// The linked list structure is equally efficient for storing both small values (like pointers)20// and larger data structures, as each node maintains a single next-pointer regardless of the21// stored value's size.22//23// Example usage:24//25//	list := fifo.New(3)        // Create a new list with max size 326//	list.Append("a")           // List: [a]27//	list.Append("b")           // List: [a b]28//	list.Append("c")           // List: [a b c]29//	list.Append("d")           // List: [b c d] (oldest element "a" was removed)30//	latest := list.Latest()    // Returns "d"31//	all := list.Entries()      // Returns ["b", "c", "d"]32package fifo3334// node represents a single element in the linked list35type node struct {36	value any37	next  *node38}3940// List represents a fixed-size FIFO list41type List struct {42	head    *node43	tail    *node44	size    int45	maxSize int46}4748// New creates a new FIFO list with the specified maximum size49func New(maxSize int) *List {50	return &List{51		maxSize: maxSize,52	}53}5455// Prepend adds a new entry at the start of the list. If the list exceeds maxSize,56// the last entry is automatically removed.57func (l *List) Prepend(entry any) {58	if l.maxSize == 0 {59		return60	}6162	newNode := &node{value: entry}6364	if l.head == nil {65		l.head = newNode66		l.tail = newNode67		l.size = 168		return69	}7071	newNode.next = l.head72	l.head = newNode7374	if l.size < l.maxSize {75		l.size++76		return77	}7879	// Remove last element by traversing to second-to-last80	if l.size == 1 {81		// Special case: if size is 1, just update both pointers82		l.head = newNode83		l.tail = newNode84		newNode.next = nil85		return8687	}8889	// Find second-to-last node90	current := l.head91	for current.next != l.tail {92		current = current.next93	}94	current.next = nil95	l.tail = current9697}9899// Append adds a new entry at the end of the list. If the list exceeds maxSize,100// the first entry is automatically removed.101func (l *List) Append(entry any) {102	if l.maxSize == 0 {103		return104	}105106	newNode := &node{value: entry}107108	if l.head == nil {109		l.head = newNode110		l.tail = newNode111		l.size = 1112		return113	}114115	l.tail.next = newNode116	l.tail = newNode117118	if l.size < l.maxSize {119		l.size++120	} else {121		l.head = l.head.next122	}123}124125// Get returns the entry at the specified index.126// Index 0 is the oldest entry, Size()-1 is the newest.127func (l *List) Get(index int) any {128	if index < 0 || index >= l.size {129		return nil130	}131132	current := l.head133	for i := 0; i < index; i++ {134		current = current.next135	}136	return current.value137}138139// Size returns the current number of entries in the list140func (l *List) Size() int {141	return l.size142}143144// MaxSize returns the maximum size configured for this list145func (l *List) MaxSize() int {146	return l.maxSize147}148149// Entries returns all current entries as a slice150func (l *List) Entries() []any {151	entries := make([]any, l.size)152	current := l.head153	for i := 0; i < l.size; i++ {154		entries[i] = current.value155		current = current.next156	}157	return entries158}159160// Iterator returns a function that can be used to iterate over the entries161// from oldest to newest. Returns nil when there are no more entries.162func (l *List) Iterator() func() any {163	current := l.head164	return func() any {165		if current == nil {166			return nil167		}168		value := current.value169		current = current.next170		return value171	}172}173174// Latest returns the most recent entry.175// Returns nil if the list is empty.176func (l *List) Latest() any {177	if l.tail == nil {178		return nil179	}180	return l.tail.value181}182183// SetMaxSize updates the maximum size of the list.184// If the new maxSize is smaller than the current size,185// the oldest entries are removed to fit the new size.186func (l *List) SetMaxSize(maxSize int) {187	if maxSize < 0 {188		maxSize = 0189	}190191	// If new maxSize is smaller than current size,192	// remove oldest entries until we fit193	if maxSize < l.size {194		// Special case: if new maxSize is 0, clear the list195		if maxSize == 0 {196			l.head = nil197			l.tail = nil198			l.size = 0199		} else {200			// Keep the newest entries by moving head forward201			diff := l.size - maxSize202			for i := 0; i < diff; i++ {203				l.head = l.head.next204			}205			l.size = maxSize206		}207	}208209	l.maxSize = maxSize210}211212// Delete removes the element at the specified index.213// Returns true if an element was removed, false if the index was invalid.214func (l *List) Delete(index int) bool {215	if index < 0 || index >= l.size {216		return false217	}218219	// Special case: deleting the only element220	if l.size == 1 {221		l.head = nil222		l.tail = nil223		l.size = 0224		return true225	}226227	// Special case: deleting first element228	if index == 0 {229		l.head = l.head.next230		l.size--231		return true232	}233234	// Find the node before the one to delete235	current := l.head236	for i := 0; i < index-1; i++ {237		current = current.next238	}239240	// Special case: deleting last element241	if index == l.size-1 {242		l.tail = current243		current.next = nil244	} else {245		current.next = current.next.next246	}247248	l.size--249	return true250}251