// 第 9 周 – 动态内存管理的简单模型：内存是记录数组，指针是下标。
// 运行：go run ./w09/memorymodel
package main

import "fmt"

const (
	Nil  = -1
	Size = 8
)

type Elem struct {
	Value string
	Next  int
}

var (
	mem  [Size]Elem
	free int // 空闲链表的头
)

func initMemory() {
	for i := 0; i < Size-1; i++ {
		mem[i].Next = i + 1
	}
	mem[Size-1].Next = Nil
	free = 0
}

// 分配（Reserve）：从空闲链表的前端取一个位置；没有时为 Nil。
func reserve() int {
	if free == Nil {
		return Nil
	}
	p := free
	free = mem[p].Next
	return p
}

// 释放（Free）：放回空闲链表的前端。
func release(p int) {
	mem[p] = Elem{Next: free}
	free = p
}

func printMemory(head int) {
	fmt.Println("  index | value | next")
	for i, e := range mem {
		next := fmt.Sprint(e.Next)
		if e.Next == Nil {
			next = "Nil"
		}
		fmt.Printf("  %5d | %5s | %4s\n", i, e.Value, next)
	}
	fmt.Print("  list: ")
	for p := head; p != Nil; p = mem[p].Next {
		fmt.Printf("%s(%d) ", mem[p].Value, p)
	}
	fmt.Print("\n  free: ")
	for p := free; p != Nil; p = mem[p].Next {
		fmt.Print(p, " ")
	}
	fmt.Println()
}

func main() {
	initMemory()
	head := Nil
	for _, s := range []string{"D", "C", "B", "A"} { // 在表头插入
		p := reserve()
		mem[p].Value = s
		mem[p].Next = head
		head = p
	}
	fmt.Println("after 4 insertions:")
	printMemory(head)

	p := head // 从表头删除 A
	head = mem[p].Next
	release(p)
	q := head // 删除 B 之后的 C
	p = mem[q].Next
	mem[q].Next = mem[p].Next
	release(p)
	fmt.Println("\nafter deleting A and C:")
	printMemory(head)
}