// Week 9 – A simple model of dynamic memory management: memory is an array of records, a pointer is an index.
// Run: 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 // head of the free list
)

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

// reserve (Reserve): a slot from the front of the free list; Nil if there is none.
func reserve() int {
	if free == Nil {
		return Nil
	}
	p := free
	free = mem[p].Next
	return p
}

// release (Free): back to the front of the free list.
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"} { // insertion at the beginning
		p := reserve()
		mem[p].Value = s
		mem[p].Next = head
		head = p
	}
	fmt.Println("after 4 insertions:")
	printMemory(head)

	p := head // deleting A from the beginning
	head = mem[p].Next
	release(p)
	q := head // deleting C after B
	p = mem[q].Next
	mem[q].Next = mem[p].Next
	release(p)
	fmt.Println("\nafter deleting A and C:")
	printMemory(head)
}