LRU caching example

lru.go

package main

import (
    "fmt"
    "bufio"
    "os"
    "errors"
)

//practice LRU cache
//input - n size line one, space delimited cache item values line two, query line three
func main() {
    var n int
    var v int
    var k int
    var c Node
    scanner := bufio.NewReader(os.Stdin)
    _, err := fmt.Fscanf(scanner, "%d\n", &n)
    if err != nil {
	    panic(err.Error())
    }

    //build cache mgt
    q := Queue {Count: 0}
    m := make(map[int]Node, n)
    for i :=0; i <n-1; i++ {
	    _, _ = fmt.Fscanf(scanner, "%d ", &v)
	    c = Node {ID: i, Data: v}
	    q.Push(c)
	    m[i] = c
    }
    _, _ = fmt.Fscanf(scanner, "%d\n", &v)
    c = Node {ID: n-1, Data: v}
    q.Push(c)
    m[n-1] = c

    fmt.Printf("m built %v\n", m)
    fmt.Printf("q built %v\n", q)

    //query
    _, _ = fmt.Fscanf(scanner, "%d\n", &k)
    if c, ok := m[k]; !ok {
	    //not currently in-cache
	    addCacheItem(c, m, q)
	    fmt.Printf("uncached:")
    } else {
	    fmt.Printf("cached:")
    }
    //verify item is available from cache now
    fmt.Printf(" %v\n", m[c.ID])
}

func addCacheItem(c Node, m map[int]Node, q Queue) {
	//first, remove node to make room
	t, err := q.Pop()
	if err != nil {
		panic(err.Error())
	}
	fmt.Printf("popped %v\n", t)
	delete(m, t.ID)
	//add the new item to cache
	m[c.ID] = c
	q.Push(c)
}

type Node struct {
	ID int
	Data int
  Prev *Node
	Next *Node
}

type Queue struct {
	Head *Node
	Tail *Node
	Count int
}

func (q *Queue) Pop() (Node, error) {
	if q.Count >0 {
      if q.Tail == q.Head {
        q.Tail = nil
      }

      t := Node{ID: q.Head.ID, Data: q.Head.Data}
      q.Head.Prev = nil
      q.Head = q.Head.Next
      q.Count = q.Count -1
      return t, nil
  } else {
      t := Node{ID: -1, Data: -1}
      return t, errors.New("empty queue")
	}
}

func (q *Queue) Push(n Node) {
	t := Node {ID: n.ID, Data: n.Data}
	if q.Head == nil {
		q.Tail = &t
		q.Head = &t
	} else {
		q.Tail.Next = &t
		t.Prev = q.Tail
		q.Tail = &t
	}

	q.Count = q.Count +1
}