type DoubleNode struct {
  Key  int     //鍵
  Value interface{} //值
  Prev *DoubleNode //上一個節(jié)點指針
  Next *DoubleNode //下一個節(jié)點指針
  Freq int     //頻率次數(shù).為了給LFU使用的
}

//定義一個雙鏈表的結(jié)構(gòu)
type DoubleList struct {
  lock   *sync.RWMutex //鎖
  Capacity uint     //最大容量
  Size   uint     //當(dāng)前容量
  Head   *DoubleNode  //頭節(jié)點
  Tail   *DoubleNode  //尾部節(jié)點
}

//初使雙鏈表
func New(capacity uint) *DoubleList {
  list := new(DoubleList)
  list.Capacity = capacity
  list.lock = new(sync.RWMutex)
  list.Size = 0
  list.Head = nil
  list.Tail = nil
  return list
}

func (list *DoubleList) AddHead(node *DoubleNode) bool {
  //判斷容量是否為0
  if list.Capacity == 0 {
    return false
  }
  list.lock.Lock()
  defer list.lock.Unlock()
  //判斷頭部節(jié)點是否為nil
  if list.Head == nil {
    list.Head = node
    list.Tail = node
  } else { //存在頭部節(jié)點
    list.Head.Prev = node //將舊頭部節(jié)點上一個節(jié)點指向新節(jié)點
    node.Next = list.Head //新頭部節(jié)點下一個節(jié)點指向舊頭部節(jié)點
    list.Head = node   //設(shè)置新的頭部節(jié)點
    list.Head.Prev = nil //將新的頭部節(jié)點上一個節(jié)點設(shè)置NIL
  }
  list.Size++
  return true
}

func (list *DoubleList) AddTail(node *DoubleNode) bool {
  //判斷是否有容量,
  if list.Capacity == 0 {
    return false
  }
  list.lock.Lock()
  defer list.lock.Unlock()
  //判斷尾部是否為空
  if list.Tail == nil {
    list.Tail = node
    list.Head = node
  } else {
    //舊的尾部下個節(jié)點指向新節(jié)點
    list.Tail.Next = node
    //追加新節(jié)點時,先將node的上節(jié)點指向舊的尾部節(jié)點
    node.Prev = list.Tail
    //設(shè)置新的尾部節(jié)點
    list.Tail = node
    //新的尾部下個節(jié)點設(shè)置為空
    list.Tail.Next = nil
  }
  //雙鏈表大小+1
  list.Size++
  return true
}

//添加任意位置元素
func (list *DoubleList) Insert(index uint, node *DoubleNode) bool {
  //容量滿了
  if list.Size == list.Capacity {
    return false
  }
  //如果沒有節(jié)點
  if list.Size == 0 {
    return list.Append(node)
  }
  //如果插入的位置大于當(dāng)前長度則尾部添加
  if index > list.Size {
    return list.AddTail(node)
  }
  //如果插入的位置等于0則,頭部添加
  if index == 0 {
    return list.AddHead(node)
  }
  //取出要插入位置的節(jié)點
  nextNode := list.Get(index)
  list.lock.Lock()
  defer list.lock.Unlock()
  //中間插入:
  //假設(shè)已有A, C節(jié)點, 現(xiàn)在要插入B節(jié)點
  // nextNode即是C節(jié)點,
  //A的下節(jié)點應(yīng)該是B, 即C的上節(jié)點的下節(jié)點是B
  nextNode.Prev.Next = node
  //B的上節(jié)點是C的上節(jié)點
  node.Prev = nextNode.Prev
  //B的下節(jié)點是C
  node.Next = nextNode
  //C的上節(jié)點是B
  nextNode.Prev = node
  list.Size++
  return true
}

//刪除頭部節(jié)點
func (list *DoubleList) RemoveHead() *DoubleNode {
  //判斷頭部節(jié)點是否為空
  if list.Head == nil {
    return nil
  }
  list.lock.Lock()
  defer list.lock.Unlock()
  //將頭部節(jié)點取出來
  node := list.Head
  //判斷頭部是否有下一個節(jié)點
  if node.Next != nil {
    list.Head = node.Next
    list.Head.Prev = nil
  } else { //如果沒有下一個節(jié)點, 說明只有一個節(jié)點
    list.Head, list.Tail = nil, nil
  }
  list.Size--
  return node
}

//刪除尾部節(jié)點
func (list *DoubleList) RemoveTail() *DoubleNode {
  //判斷尾部節(jié)點是否為空
  if list.Tail == nil {
    return nil
  }
  list.lock.Lock()
  defer list.lock.Unlock()
  //取出尾部節(jié)點
  node := list.Tail
  //判斷尾部節(jié)點的上一個是否存在
  if node.Prev != nil {
    list.Tail = node.Prev
    list.Tail.Next = nil
  }
  list.Size--
  return node
}

//刪除任意元素
func (list *DoubleList) Remove(node *DoubleNode) *DoubleNode {
  //判斷是否是頭部節(jié)點
  if node == list.Head {
    return list.RemoveHead()
  }
  //判斷是否是尾部節(jié)點
  if node == list.Tail {
    return list.RemoveTail()
  }
  list.lock.Lock()
  defer list.lock.Unlock()
  //節(jié)點為中間節(jié)點
  //則需要:
  //將上一個節(jié)點的下一節(jié)點指針指向下節(jié)點
  //將下一個節(jié)點的上一節(jié)點指針指向上節(jié)點
  node.Prev.Next = node.Next
  node.Next.Prev = node.Prev
  list.Size--
  return node
}