package main
import (
"flag"
"fmt"
"runtime"
"algo/metrics"
)
// ── Stack: the undo history ─────────────────────────────────────────────
//
// Last in, first out. Push and Pop touch only the end of a slice, which is
// the one place a slice is cheap to change.
type History struct {
items []Item
}
func (h *History) Push(it Item) { h.items = append(h.items, it) }
func (h *History) Pop() (Item, bool) {
if len(h.items) == 0 {
return Item{}, false
}
it := h.items[len(h.items)-1]
h.items = h.items[:len(h.items)-1]
return it, true
}
func (h *History) Len() int { return len(h.items) }
// ── Queue: three ways to take from the front ────────────────────────────
// dequeueReslice drops the front by moving the slice header forward.
// It moves NO elements. It also never lets go of the array underneath.
func dequeueReslice(q []Item, c *metrics.Counter) ([]Item, Item, bool) {
if len(q) == 0 {
return q, Item{}, false
}
it := q[0]
return q[1:], it, true
}
// dequeueCopyDown drops the front by shifting everything left one place.
// Every shift is counted.
func dequeueCopyDown(q []Item, c *metrics.Counter) ([]Item, Item, bool) {
if len(q) == 0 {
return q, Item{}, false
}
it := q[0]
for i := 0; i+1 < len(q); i++ {
c.Hit()
q[i] = q[i+1]
}
return q[:len(q)-1], it, true
}
// Ring is a fixed-size circular buffer: head and tail chase each other around
// one array that never moves and never grows.
type Ring struct {
buf []Item
head, tail int
n int
}
func NewRing(capacity int) *Ring { return &Ring{buf: make([]Item, capacity)} }
func (r *Ring) Enqueue(it Item) bool {
if r.n == len(r.buf) {
return false
}
r.buf[r.tail] = it
r.tail = (r.tail + 1) % len(r.buf)
r.n++
return true
}
func (r *Ring) Dequeue(c *metrics.Counter) (Item, bool) {
if r.n == 0 {
return Item{}, false
}
it := r.buf[r.head]
r.buf[r.head] = Item{} // let the item go, so the ring does not pin it
r.head = (r.head + 1) % len(r.buf)
r.n--
return it, true
}
func (r *Ring) Len() int { return r.n }
// heapKB forces a collection and reports the live heap. Used to show the one
// thing an operation count cannot: which queue is still holding the data.
func heapKB() uint64 {
runtime.GC()
var m runtime.MemStats
runtime.ReadMemStats(&m)
return m.HeapAlloc / 1024
}
func cmdQueue(args []string) error {
fs := flag.NewFlagSet("queue", flag.ContinueOnError)
n := fs.Int("n", 100000, "how many items to put through the queue")
if err := fs.Parse(args); err != nil {
return err
}
newQueue := func() []Item {
q := make([]Item, *n)
for i := range q {
q[i] = Item{ID: i + 1, Title: fmt.Sprintf("track-%d", i+1)}
}
return q
}
// ── PART 1: how many elements each strategy moves ───────────────────
fmt.Printf("enqueue %d items, then dequeue every one\n\n", *n)
fmt.Printf("%-22s %18s\n", "strategy", "elements moved")
q1 := newQueue()
var c1 metrics.Counter
for {
var ok bool
if q1, _, ok = dequeueReslice(q1, &c1); !ok {
break
}
}
fmt.Printf("%-22s %18d\n", "q = q[1:]", c1.N())
q2 := newQueue()
var c2 metrics.Counter
for {
var ok bool
if q2, _, ok = dequeueCopyDown(q2, &c2); !ok {
break
}
}
fmt.Printf("%-22s %18d\n", "copy-down", c2.N())
r := NewRing(*n)
for _, it := range newQueue() {
r.Enqueue(it)
}
var c3 metrics.Counter
for {
if _, ok := r.Dequeue(&c3); !ok {
break
}
}
fmt.Printf("%-22s %18d\n", "ring buffer", c3.N())
// ── PART 2: what the counter cannot see ─────────────────────────────
//
// Drain the queue down to ONE item and keep only that. Nothing else is
// referenced. Whatever is still on the heap afterwards is being held by
// the one-element slice — or is not being held at all.
baseline := heapKB()
kept := newQueue()
for len(kept) > 1 {
kept, _, _ = dequeueReslice(kept, &c1)
}
leaked := heapKB() - baseline
runtime.KeepAlive(kept)
copied := newQueue()
last := []Item{copied[len(copied)-1]} // copy the survivor OUT
copied = nil
_ = copied
freed := heapKB() - baseline
runtime.KeepAlive(last)
fmt.Printf("\nkeeping only the LAST item of a %d-item queue:\n", *n)
fmt.Printf("%-38s %8d KB still on the heap\n", "q = q[1:] (header points into array)", leaked)
fmt.Printf("%-38s %8d KB still on the heap\n", "copied the survivor out", freed)
return nil
}
func cmdHistory(args []string) error {
fs := flag.NewFlagSet("history", flag.ContinueOnError)
in := fs.String("in", "library.jsonl", "library file")
n := fs.Int("n", 5, "how many items to view, then undo")
if err := fs.Parse(args); err != nil {
return err
}
items, err := load(*in)
if err != nil {
return err
}
if *n > len(items) {
*n = len(items)
}
var h History
fmt.Println("viewing:")
for i := 0; i < *n; i++ {
h.Push(items[i])
fmt.Printf(" → %s\n", items[i].Title)
}
fmt.Printf("\nhistory holds %d\n\nundo:\n", h.Len())
for {
it, ok := h.Pop()
if !ok {
break
}
fmt.Printf(" ← %s\n", it.Title)
}
fmt.Printf("\nhistory holds %d\n", h.Len())
return nil
}
