Golang标准库学习—container/ring

container包中有三个数据结构：heap(堆)、list(链表)、ring(环)

Package ring

import "container/ring"

ring实现了环形链表的操作。环的尾部就是头部，所以每个元素实际上就可以代表自身的这个环。不需要像list一样保持list和element两个结构，只需要保持一个结构就可以。

type Ring

环形链表没有头尾；指向环形链表任一元素的指针都可以作为整个环形链表看待。Ring零值是具有一个（Value字段为nil的）元素的链表。
type Ring struct {
 next, prev *Ring
 Value      interface{} // for use by client; untouched by this library
}

ring包中除了init初始化，其他都是对外调用的包

init()方法 初始化ring
func (r *Ring) init() *Ring {
 r.next = r
 r.prev = r
 return r
}
Next方法 返回r的后一个元素，r不能为空。
func (r *Ring) Next() *Ring {
 if r.next == nil {
  return r.init()
 }
 return r.next
}
Prev方法 返回r的前一个元素，r不能为空。
func (r *Ring) Prev() *Ring {
 if r.next == nil {
  return r.init()
 }
 return r.prev
}
Move方法 返回r移动n%r.Len()个位置（n>=0向前移动，n<0向后移动）后的元素，r不能为空。
源码倒是没有通过n%r.Len()来减少for循环次数。难道这样做效率会更低？还是说很少有n远大于r.Len()的情况。
func (r *Ring) Move(n int) *Ring {
 if r.next == nil {
  return r.init()
 }
 switch {
 case n < 0:
  for ; n < 0; n++ {
   r = r.prev
  }
 case n > 0:
  for ; n > 0; n-- {
   r = r.next
  }
 }
 return r
}
New方法 创建一个具有n个元素的环形链表
func New(n int) *Ring {
 if n <= 0 {
  return nil
 }
 r := new(Ring)
 p := r
 for i := 1; i < n; i++ {
  p.next = &Ring{prev: p}
  p = p.next
 }
 p.next = r
 r.prev = p
 return r
}
Link方法 Link连接r和s，并返回r原本的后继元素r.Next()。r不能为空。
如果r和s指向同一个环形链表，则会删除掉r和s之间的元素，删掉的元素构成一个子链表，返回指向该子链表的指针（r的原后继元素）；如果没有删除元素，则仍然返回r的原后继元素，而不是nil。

如果r和s指向不同的链表，将创建一个单独的链表，将s指向的链表插入r后面，返回s原最后一个元素后面的元素（即r的原后继元素）。
func (r *Ring) Link(s *Ring) *Ring {
 n := r.Next()
 if s != nil {
  p := s.Prev()
  // Note: Cannot use multiple assignment because
  // evaluation order of LHS is not specified.
  r.next = s
  s.prev = r
  n.prev = p
  p.next = n
 }
 return n
}
Unlink方法 删除链表中n % r.Len()个元素，从r.Next()开始删除。如果n % r.Len() == 0，不修改r。返回删除的元素构成的链表，r不能为空。
func (r *Ring) Unlink(n int) *Ring {
 if n <= 0 {
  return nil
 }
 return r.Link(r.Move(n + 1))
}
Len方法 返回环形链表中的元素个数，复杂度O(n)。
func (r *Ring) Len() int {
 n := 0
 if r != nil {
  n = 1
  for p := r.Next(); p != r; p = p.next {
   n++
  }
 }
 return n
}
Do方法对链表的每一个元素都执行f（正向顺序）注意如果f改变了*r，Do的行为是未定义的。
func (r *Ring) Do(f func(interface{})) {
 if r != nil {
  f(r.Value)
  for p := r.Next(); p != r; p = p.next {
   f(p.Value)
  }
 }
}

下面简单的使用了ring包，查看相关功能

Do方法的用处很多，这里只是实现了打印

package main

import (
 "fmt"
 "container/ring"
)

func main() {
 // 生成3个节点的循环链表
 r := ring.New(3)
 for i := 1; i<=3; i++ {
  r.Value = i
  r = r.Next()
 }

 // 通过Do传入方法，对ring执行
 s := 0
 r.Do(func (p interface{}) {
  s += p.(int)
 })
 fmt.Println("s sum is ", s)

 // 遍历ring
 r.Do(func (p interface{}) {
  fmt.Println(p)
 }) 

 // 向后移动两个位置
 r = r.Move(2)
 r.Do(func (p interface{}) {
  fmt.Println(p)
 }) 
 
 // r2为再向后移动两个位置后的r
 // r3使用Link方法 将r与r2连接
 r2 := r.Move(2)
 r3 := r.Link(r2)

 r3.Do(func (p interface{}) {
  fmt.Println(p)
 })
}

记录每天解决的一点小问题，积累起来就能解决大问题。