package main
import (
"container/list"
"flag"
"fmt"
"algo/metrics"
)
// Node is one entry in the playlist. Unlike a slice, the entries are NOT
// stored next to each other: each one knows only its two neighbours.
type Node struct {
Item Item
Prev *Node
Next *Node
}
// Playlist is a doubly-linked list with a head and a tail.
type Playlist struct {
Head *Node
Tail *Node
Len int
}
// Append adds an item to the end. O(1) — we already hold the tail.
func (p *Playlist) Append(it Item) *Node {
n := &Node{Item: it, Prev: p.Tail}
if p.Tail != nil {
p.Tail.Next = n
} else {
p.Head = n
}
p.Tail = n
p.Len++
return n
}
// NodeAt walks to position i and returns the node there. This is the LOSS:
// it is O(n), and it is what the list has to pay before any of its O(1)
// operations can happen. Every hop is counted.
func (p *Playlist) NodeAt(i int, c *metrics.Counter) *Node {
if i < 0 || i >= p.Len {
return nil
}
n := p.Head
for k := 0; k < i; k++ {
c.Hit()
n = n.Next
}
return n
}
// unlink detaches n from the list without touching anything else. O(1).
func (p *Playlist) unlink(n *Node) {
if n.Prev != nil {
n.Prev.Next = n.Next
} else {
p.Head = n.Next
}
if n.Next != nil {
n.Next.Prev = n.Prev
} else {
p.Tail = n.Prev
}
n.Prev, n.Next = nil, nil
}
// insertBefore splices n in ahead of at. O(1).
func (p *Playlist) insertBefore(n, at *Node) {
n.Prev = at.Prev
n.Next = at
if at.Prev != nil {
at.Prev.Next = n
} else {
p.Head = n
}
at.Prev = n
}
// Splice moves the node at `from` to position `to`. The MOVE itself is O(1) —
// four pointer writes, counted below. Getting hold of the two nodes is not.
func (p *Playlist) Splice(from, to int, walk, ptr *metrics.Counter) bool {
n := p.NodeAt(from, walk)
if n == nil {
return false
}
target := p.NodeAt(to, walk)
if target == nil || target == n {
return false
}
p.unlink(n)
// Four pointer writes, whatever n and target are and however big the list is.
for i := 0; i < 4; i++ {
ptr.Hit()
}
p.insertBefore(n, target)
return true
}
// MoveInSlice does the same job on a []Item: remove at `from`, insert at `to`.
// Every element between the two positions has to SHIFT, and each shift is
// counted. This is what the list is competing against.
func MoveInSlice(items []Item, from, to int, c *metrics.Counter) []Item {
if from < 0 || from >= len(items) || to < 0 || to >= len(items) || from == to {
return items
}
it := items[from]
if from < to {
for i := from; i < to; i++ {
c.Hit()
items[i] = items[i+1]
}
} else {
for i := from; i > to; i-- {
c.Hit()
items[i] = items[i-1]
}
}
items[to] = it
return items
}
// MoveInStdList is the same move using container/list — the standard library's
// doubly-linked list. Its MoveBefore is O(1) like ours; reaching the elements
// is the same O(n) walk.
func MoveInStdList(l *list.List, from, to int, walk *metrics.Counter) bool {
at := func(i int) *list.Element {
e := l.Front()
for k := 0; k < i && e != nil; k++ {
walk.Hit()
e = e.Next()
}
return e
}
a, b := at(from), at(to)
if a == nil || b == nil || a == b {
return false
}
l.MoveBefore(a, b)
return true
}
func cmdPlaylist(args []string) error {
fs := flag.NewFlagSet("playlist", flag.ContinueOnError)
in := fs.String("in", "library.jsonl", "library file")
from := fs.Int("from", 0, "position to move from")
to := fs.Int("to", 0, "position to move to")
if err := fs.Parse(args); err != nil {
return err
}
items, err := load(*in)
if err != nil {
return err
}
n := len(items)
// 1. Our doubly-linked playlist.
var pl Playlist
for _, it := range items {
pl.Append(it)
}
var walk, ptr metrics.Counter
pl.Splice(*from, *to, &walk, &ptr)
// 2. The slice.
slice := append([]Item(nil), items...)
var shift metrics.Counter
MoveInSlice(slice, *from, *to, &shift)
// 3. container/list.
sl := list.New()
for _, it := range items {
sl.PushBack(it)
}
var stdWalk metrics.Counter
MoveInStdList(sl, *from, *to, &stdWalk)
fmt.Printf("move %d -> %d in a library of %d\n\n", *from, *to, n)
fmt.Printf("%-24s %14s %14s\n", "", "walk/shift", "pointer writes")
fmt.Printf("%-24s %14d %14d\n", "slice (shift)", shift.N(), 0)
fmt.Printf("%-24s %14d %14d\n", "Playlist (ours)", walk.N(), ptr.N())
fmt.Printf("%-24s %14d %14s\n", "container/list", stdWalk.N(), "(hidden)")
// THE OTHER HALF. Above, every structure had to FIND the node first. Now
// assume you already hold it — a drag-and-drop UI does, because the thing
// being moved is the thing you grabbed. The walk disappears and only the
// move is left.
var uncounted metrics.Counter
node := pl.NodeAt(*from, &uncounted)
target := pl.NodeAt(*to, &uncounted)
var held metrics.Counter
if node != nil && target != nil && node != target {
pl.unlink(node)
for i := 0; i < 4; i++ {
held.Hit()
}
pl.insertBefore(node, target)
}
var heldShift metrics.Counter
MoveInSlice(slice, *from, *to, &heldShift)
fmt.Printf("\nand if you ALREADY HOLD the node (a drag-and-drop UI does):\n")
fmt.Printf("%-24s %14d %14d\n", "slice (shift)", heldShift.N(), 0)
fmt.Printf("%-24s %14d %14d\n", "Playlist (ours)", 0, held.N())
return nil
}
