Structlisp

Structlisp is a portable Common Lisp library of general-purpose data structures for interactive systems. It depends only on ANSI Common Lisp.

Contents

• Circular-array deque: O(1) amortized end operations, O(1) indexed access, indexed insertion and removal, bounded predicate search, independent copying, ordered append and prepend, selective or mapped destructive transfer, maintained element weights, count- or weight-triggered eviction, and fresh snapshots
• Bounded sequence builder for strings and specialized or general vectors: exact signaling, boolean, and truncating range appends, fixed count, optional weight budgets, sticky overflow state, and detached snapshots or finish
• Stable binary min-heap with optional unique keys for cancellation and reprioritization, non-destructive stable priority-order snapshots, and O(n log k) top-K selection
• Sorted string index with cached normalized keys and binary-searched exact and prefix ranges
• Insertion-ordered hash map with O(1) expected lookup and deletion
• Keyed FIFO cache with non-promoting O(1) expected lookup, stable update positions, count and weight budgets, oldest-first eviction, predicate deletion, and detached insertion-order snapshots
• Least-recently-used cache with maintained count and weight budgets, plus a producer-backed memo cache
• Canonical half-open integer interval sets and maps with binary-search queries and linear set algebra or rewrites
• Compact monotone unsigned-integer index with lower-bound, upper-bound, and neighboring-value queries

All structures use opaque representations and live in the structlisp package. Public traversal functions use snapshots, so callbacks may mutate the traversed container. APIs that can store nil return an explicit presence value where needed.

Loading

(asdf:load-system "structlisp")

(asdf:test-system "structlisp")

Bounded sequence builder

The bounded sequence builder accumulates elements into adjustable internal storage up to its fixed count limit and optional weight limit.

• Exact appends are atomic and signal bounded-sequence-builder-overflow when a range cannot fit
• Boolean appends leave contents as they are, mark overflow, and return nil
• Truncating appends accept the longest fitting prefix, return the appended count and a true completion value when the whole range fit, and set a sticky overflow state

Range appends snapshot their requested input before invoking weight callbacks. snapshot returns a detached vector; finish returns the same kind of result and clears the builder for reuse.

A character builder finishes as a string. An octet builder finishes as a specialized vector when the implementation supports that specialization. A weight function can maintain byte, cost, or other client-defined budgets.

(let ((builder (structlisp:make-bounded-sequence-builder
                80
                :element-type 'character
                :maximum-weight 80
                :weight-function (constantly 1))))
  (structlisp:bounded-sequence-builder-append-sequence
   builder "result: ")
  (structlisp:bounded-sequence-builder-append-sequence-truncating
   builder long-text)
  (structlisp:bounded-sequence-builder-finish builder))

FIFO cache

A FIFO cache preserves insertion order independently of reads. Updating an existing key keeps its position unless fifo-cache-move-to-back is called. Count and weight budgets evict oldest entries and return them in eviction order. The optional eviction callback observes the same order. All eviction callbacks are attempted. If any fail, fifo-cache-eviction-callback-error reports the complete evicted-entry vector and ordered failure records.

(let ((cache (structlisp:make-fifo-cache
              :maximum-count 2
              :maximum-weight 8
              :weight-function (lambda (key value)
                                 (declare (ignore key))
                                 (length value)))))
  (structlisp:fifo-cache-put cache :first "one")
  (structlisp:fifo-cache-put cache :second "two")
  (structlisp:fifo-cache-get cache :first)
  (structlisp:fifo-cache-put cache :third "three")
  (structlisp:fifo-cache->alist cache))
;; => ((:SECOND . "two") (:THIRD . "three"))

Example

(let ((history (structlisp:make-deque :maximum-count 250)))
  (structlisp:deque-push-back history "first command")
  (structlisp:deque-push-back history "second command")
  (structlisp:deque-back history))

See the exported symbols in src/package.lisp and their documentation strings for the complete API.

License

Copyright 2025 Lukáš Hozda

Licensed under COLL-Attribution. See LICENSE.lisp for the authoritative terms.