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

1// Package deque provides a doubly-linked deque with optional size limits,2// optimized for minimal storage updates and O(1) operations in Gno environments.3//4// This implementation uses a doubly-linked list structure that provides:5// - O(1) push back operations6// - O(1) pop front operations7// - O(1) access to first/last elements8// - No array resizing or slice shifting9// - Minimal allocations (one node per element)10// - Minimal storage updates (typically 1-2 pointer updates per operation)11// - Optional max-size eviction policy12//13// Optimized for Gno blockchain storage: each operation updates only specific nodes14// rather than entire data structures, making it ideal for storage-efficient lists15// that need simple read operations like first/last access, size checks, list16// enumeration, and iteration with minimal storage update overhead.17//18// Example usage:19//20//	// Unbounded deque21//	d := deque.New()22//	d.PushBack("a", "b", "c")23//24//	// Bounded deque with automatic eviction25//	d = deque.NewBounded(3)26//	d.PushBack("a", "b", "c", "d")  // "a" gets evicted27//28//	first := d.PopFront()  // Returns "b"29//	last := d.Last()       // Returns "d"30//31//	// Iterate forward32//	iter := d.All()33//	iter(func(val any) bool {34//	    println(val)35//	    return true // continue36//	})37//38//	// Iterate backward39//	iter = d.Backward()40//	iter(func(val any) bool {41//	    println(val)42//	    return true // continue43//	})44package deque4546// Node represents a single element in the doubly-linked list47type Node struct {48	value any49	prev  *Node50	next  *Node51}5253// Deque represents a doubly-linked deque with optional size limits54type Deque struct {55	head *Node56	tail *Node57	size int58	max  int // 0 = unlimited59}6061// New creates a new unbounded deque.62func New() *Deque {63	return &Deque{64		max: 0, // unlimited65	}66}6768// NewBounded creates a new bounded deque with the specified maximum size.69// When the deque exceeds maxSize, elements are removed from the front.70func NewBounded(maxSize int) *Deque {71	if maxSize <= 0 {72		maxSize = 173	}74	return &Deque{75		max: maxSize,76	}77}7879// PushBack adds one or more elements to the back of the deque.80// If the deque exceeds maxSize, elements are removed from the front.81func (d *Deque) PushBack(items ...any) {82	for _, item := range items {83		d.pushBackSingle(item)84	}85}8687// pushBackSingle adds a single element to the back88func (d *Deque) pushBackSingle(item any) {89	node := &Node{value: item}9091	if d.tail == nil {92		// First element93		d.head = node94		d.tail = node95	} else {96		// Link to existing tail97		d.tail.next = node98		node.prev = d.tail99		d.tail = node100	}101102	d.size++103104	// Handle size limit by removing from front105	if d.max > 0 && d.size > d.max {106		d.popFrontNode()107	}108}109110// PopFront removes and returns the front element.111// Returns nil if the deque is empty.112func (d *Deque) PopFront() any {113	if d.head == nil {114		return nil115	}116117	value := d.head.value118	d.popFrontNode()119	return value120}121122// popFrontNode removes the front node123func (d *Deque) popFrontNode() {124	if d.head == nil {125		return126	}127128	if d.head == d.tail {129		// Only one element130		d.head = nil131		d.tail = nil132	} else {133		// Move head forward134		d.head = d.head.next135		d.head.prev = nil136	}137138	d.size--139}140141// PopBack removes and returns the back element.142// Returns nil if the deque is empty.143func (d *Deque) PopBack() any {144	if d.tail == nil {145		return nil146	}147148	value := d.tail.value149	d.popBackNode()150	return value151}152153// popBackNode removes the back node154func (d *Deque) popBackNode() {155	if d.tail == nil {156		return157	}158159	if d.head == d.tail {160		// Only one element161		d.head = nil162		d.tail = nil163	} else {164		// Move tail backward165		d.tail = d.tail.prev166		d.tail.next = nil167	}168169	d.size--170}171172// PushFront adds one or more elements to the front of the deque.173// If bounded and size limit is exceeded, elements are removed from the back.174func (d *Deque) PushFront(items ...any) {175	for _, item := range items {176		d.pushFrontSingle(item)177	}178}179180// pushFrontSingle adds a single element to the front181func (d *Deque) pushFrontSingle(item any) {182	node := &Node{value: item}183184	if d.head == nil {185		// First element186		d.head = node187		d.tail = node188	} else {189		// Link to existing head190		d.head.prev = node191		node.next = d.head192		d.head = node193	}194195	d.size++196197	// Handle size limit by removing from back198	if d.max > 0 && d.size > d.max {199		d.popBackNode()200	}201}202203// Size returns the current number of elements204func (d *Deque) Size() int {205	return d.size206}207208// MaxSize returns the maximum size limit (0 = unlimited)209func (d *Deque) MaxSize() int {210	return d.max211}212213// IsEmpty returns true if the deque is empty214func (d *Deque) IsEmpty() bool {215	return d.size == 0216}217218// IsBounded returns true if the deque has a size limit219func (d *Deque) IsBounded() bool {220	return d.max > 0221}222223// First returns the front element without removing it.224// Returns nil if the deque is empty.225func (d *Deque) First() any {226	if d.head == nil {227		return nil228	}229	return d.head.value230}231232// Last returns the back element without removing it.233// Returns nil if the deque is empty.234func (d *Deque) Last() any {235	if d.tail == nil {236		return nil237	}238	return d.tail.value239}240241// Get returns the element at the specified index (0 = front).242// Returns nil if index is out of bounds.243func (d *Deque) Get(index int) any {244	if index < 0 || index >= d.size {245		return nil246	}247248	node := d.head249	for i := 0; i < index; i++ {250		node = node.next251	}252	return node.value253}254255// List returns all elements as a slice, ordered from front to back256func (d *Deque) List() []any {257	if d.size == 0 {258		return nil259	}260261	result := make([]any, d.size)262	node := d.head263	for i := 0; i < d.size; i++ {264		result[i] = node.value265		node = node.next266	}267	return result268}269270// Enumerate calls fn for each element with its index (0-based from front)271func (d *Deque) Enumerate(fn func(index int, value any) bool) {272	node := d.head273	for i := 0; i < d.size; i++ {274		if fn(i, node.value) {275			break276		}277		node = node.next278	}279}280281// Clear removes all elements from the deque282func (d *Deque) Clear() {283	d.head = nil284	d.tail = nil285	d.size = 0286}287288// SetMaxSize changes the maximum size limit.289// If the new limit is smaller than current size, elements are removed from front.290func (d *Deque) SetMaxSize(maxSize int) {291	d.max = maxSize292293	if maxSize > 0 {294		for d.size > maxSize {295			d.popFrontNode()296		}297	}298}299300// All returns an iterator function for forward traversal (Go 1.23+ compatible)301// Note: range-over-func syntax is not yet supported in Gno, use iter() directly302func (d *Deque) All() func(yield func(any) bool) {303	return func(yield func(any) bool) {304		current := d.head305		for current != nil {306			if !yield(current.value) {307				return308			}309			current = current.next310		}311	}312}313314// Backward returns an iterator function for backward traversal (Go 1.23+ compatible)315// Note: range-over-func syntax is not yet supported in Gno, use iter() directly316func (d *Deque) Backward() func(yield func(any) bool) {317	return func(yield func(any) bool) {318		current := d.tail319		for current != nil {320			if !yield(current.value) {321				return322			}323			current = current.prev324		}325	}326}327