Search Apps Documentation Source Content File Folder Download Copy Actions Download State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

README.md

2.02 Kb · 62 lines

gno.land/p/moul/deque

A doubly-linked deque, optionally bounded, written for chain storage rather than for RAM.

1d := deque.New()             // unbounded
2d = deque.NewBounded(3)      // evicts from the front past 3 elements
3
4d.PushBack("a", "b", "c")
5d.PushFront("z")
6first := d.PopFront()
7last  := d.Last()

Why not a slice

A slice-backed queue rewrites the whole backing array on append-and-grow and shifts every element on pop-front. On gno that is not a constant factor, it is the storage bill: the VM persists what changed, so touching N elements costs N.

Each operation here updates one or two node pointers and nothing else:

operation cost
PushBack, PushFront, PopFront, PopBack O(1), 1-2 node writes
First, Last, Size, IsEmpty O(1), no write
Get(i) O(n) walk, no write

Use it when you want a bounded log (the last N events), a FIFO work queue, or any list where reads are "first / last / how many / iterate" and Get(i) is rare. Use an avl tree instead when you need keyed lookup or ordering by anything but insertion.

Bounded mode

NewBounded(n) makes eviction automatic and symmetric: pushing past the limit at the back drops from the front, and pushing past it at the front drops from the back. MaxSize() returns 0 for unbounded, IsBounded() says which.

Iteration

All() walks front to back, Backward() back to front. Both return a function taking a func(any) bool callback; return false to stop early.

1d.All()(func(v any) bool {
2	println(v)
3	return true
4})

Part of moul/gno-contracts — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage.

⚠️ Disclaimer: provided as-is, without warranty; not security-audited. Full disclaimer: DISCLAIMER.