fifo.gno

  1// Package fifo implements a fixed-size FIFO (First-In-First-Out) list data structure
  2// using a singly-linked list. The implementation prioritizes storage efficiency by minimizing
  3// storage operations - each add/remove operation only updates 1-2 pointers, regardless of
  4// list size.
  5//
  6// Key features:
  7// - Fixed-size with automatic removal of oldest entries when full
  8// - Support for both prepend (add at start) and append (add at end) operations
  9// - Constant storage usage through automatic pruning
 10// - O(1) append operations and latest element access
 11// - Iterator support for sequential access
 12// - Dynamic size adjustment via SetMaxSize
 13//
 14// This implementation is optimized for frequent updates, as insertions and deletions only
 15// require updating 1-2 pointers. However, random access operations are O(n) as they require
 16// traversing the list. For use cases where writes are rare, a slice-based
 17// 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 the
 21// stored value's size.
 22//
 23// Example usage:
 24//
 25//	list := fifo.New(3)        // Create a new list with max size 3
 26//	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 fifo
 33
 34// node represents a single element in the linked list
 35type node struct {
 36	value any
 37	next  *node
 38}
 39
 40// List represents a fixed-size FIFO list
 41type List struct {
 42	head    *node
 43	tail    *node
 44	size    int
 45	maxSize int
 46}
 47
 48// New creates a new FIFO list with the specified maximum size
 49func New(maxSize int) *List {
 50	return &List{
 51		maxSize: maxSize,
 52	}
 53}
 54
 55// 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		return
 60	}
 61
 62	newNode := &node{value: entry}
 63
 64	if l.head == nil {
 65		l.head = newNode
 66		l.tail = newNode
 67		l.size = 1
 68		return
 69	}
 70
 71	newNode.next = l.head
 72	l.head = newNode
 73
 74	if l.size < l.maxSize {
 75		l.size++
 76		return
 77	}
 78
 79	// Remove last element by traversing to second-to-last
 80	if l.size == 1 {
 81		// Special case: if size is 1, just update both pointers
 82		l.head = newNode
 83		l.tail = newNode
 84		newNode.next = nil
 85		return
 86
 87	}
 88
 89	// Find second-to-last node
 90	current := l.head
 91	for current.next != l.tail {
 92		current = current.next
 93	}
 94	current.next = nil
 95	l.tail = current
 96
 97}
 98
 99// 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		return
104	}
105
106	newNode := &node{value: entry}
107
108	if l.head == nil {
109		l.head = newNode
110		l.tail = newNode
111		l.size = 1
112		return
113	}
114
115	l.tail.next = newNode
116	l.tail = newNode
117
118	if l.size < l.maxSize {
119		l.size++
120	} else {
121		l.head = l.head.next
122	}
123}
124
125// 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 nil
130	}
131
132	current := l.head
133	for i := 0; i < index; i++ {
134		current = current.next
135	}
136	return current.value
137}
138
139// Size returns the current number of entries in the list
140func (l *List) Size() int {
141	return l.size
142}
143
144// MaxSize returns the maximum size configured for this list
145func (l *List) MaxSize() int {
146	return l.maxSize
147}
148
149// Entries returns all current entries as a slice
150func (l *List) Entries() []any {
151	entries := make([]any, l.size)
152	current := l.head
153	for i := 0; i < l.size; i++ {
154		entries[i] = current.value
155		current = current.next
156	}
157	return entries
158}
159
160// Iterator returns a function that can be used to iterate over the entries
161// from oldest to newest. Returns nil when there are no more entries.
162func (l *List) Iterator() func() any {
163	current := l.head
164	return func() any {
165		if current == nil {
166			return nil
167		}
168		value := current.value
169		current = current.next
170		return value
171	}
172}
173
174// 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 nil
179	}
180	return l.tail.value
181}
182
183// 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 = 0
189	}
190
191	// If new maxSize is smaller than current size,
192	// remove oldest entries until we fit
193	if maxSize < l.size {
194		// Special case: if new maxSize is 0, clear the list
195		if maxSize == 0 {
196			l.head = nil
197			l.tail = nil
198			l.size = 0
199		} else {
200			// Keep the newest entries by moving head forward
201			diff := l.size - maxSize
202			for i := 0; i < diff; i++ {
203				l.head = l.head.next
204			}
205			l.size = maxSize
206		}
207	}
208
209	l.maxSize = maxSize
210}
211
212// 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 false
217	}
218
219	// Special case: deleting the only element
220	if l.size == 1 {
221		l.head = nil
222		l.tail = nil
223		l.size = 0
224		return true
225	}
226
227	// Special case: deleting first element
228	if index == 0 {
229		l.head = l.head.next
230		l.size--
231		return true
232	}
233
234	// Find the node before the one to delete
235	current := l.head
236	for i := 0; i < index-1; i++ {
237		current = current.next
238	}
239
240	// Special case: deleting last element
241	if index == l.size-1 {
242		l.tail = current
243		current.next = nil
244	} else {
245		current.next = current.next.next
246	}
247
248	l.size--
249	return true
250}