容器Ring笔记

Ring源码

package ring

// Ring代表环形链表的一个元素，也代表本身。一个指向任意一个元素的指针都代表整个链表的引用。
type Ring struct {
next, prev *Ring
Value interface{} // for use by client; untouched by this library
}

func (r Ring) init() Ring {
r.next = r
r.prev = r
return r
}

// Next returns the next ring element. r must not be empty.
func (r Ring) Next() Ring {
if r.next == nil {

  return r.init()

}
return r.next
}

// Prev returns the previous ring element. r must not be empty.
func (r Ring) Prev() Ring {
if r.next == nil {

  return r.init()

}
return r.prev
}

// n可以是正数，也可以是负数。正数表示往后移动 n 步，负数表示往前移动 n 步
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 creates a ring of n elements.
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
}

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
}

// 首先定位到 n+1 位置，设为p，然后 r.Next() 到 p 之间的元素从原来的环上断开，从外界来看，相当于r移除了 r.Next() 到 p 之间所有元素。注意返回值是p, 它实际上是一个subring。
func (r Ring) Unlink(n int) Ring {
if n <= 0 {

  return nil

}
return r.Link(r.Move(n + 1))
}

// 计算环形链表长度，时间复杂度为 n. 这点跟list是有区别的
func (r *Ring) Len() int {
n := 0
if r != nil {

  n = 1
  for p := r.Next(); p != r; p = p.next {
     n++
  }

}
return n
}

// 按照向后的顺序对每个元素调用 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)
  }

}
}

package ring

func (r Ring) init() Ring {
r.next = r
r.prev = r
return r
}

// Next returns the next ring element. r must not be empty.
func (r Ring) Next() Ring {
if r.next == nil {

  return r.init()

}
return r.next
}

// Prev returns the previous ring element. r must not be empty.
func (r Ring) Prev() Ring {
if r.next == nil {

  return r.init()

}
return r.prev
}

// n可以是正数，也可以是负数。正数表示往后移动 n 步，负数表示往前移动 n 步
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 creates a ring of n elements.
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
}

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
}

  return nil

}
return r.Link(r.Move(n + 1))
}

// 计算环形链表长度，时间复杂度为 n. 这点跟list是有区别的
func (r *Ring) Len() int {
n := 0
if r != nil {

  n = 1
  for p := r.Next(); p != r; p = p.next {
     n++
  }

}
return n
}

// 按照向后的顺序对每个元素调用 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)
  }

}
}
package ring

func (r Ring) init() Ring {
r.next = r
r.prev = r
return r
}

// Next returns the next ring element. r must not be empty.
func (r Ring) Next() Ring {
if r.next == nil {

  return r.init()

}
return r.next
}

// Prev returns the previous ring element. r must not be empty.
func (r Ring) Prev() Ring {
if r.next == nil {

  return r.init()

}
return r.prev
}

// n可以是正数，也可以是负数。正数表示往后移动 n 步，负数表示往前移动 n 步
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 creates a ring of n elements.
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
}

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
}

  return nil

}
return r.Link(r.Move(n + 1))
}

// 计算环形链表长度，时间复杂度为 n. 这点跟list是有区别的
func (r *Ring) Len() int {
n := 0
if r != nil {

  n = 1
  for p := r.Next(); p != r; p = p.next {
     n++
  }

}
return n
}

// 按照向后的顺序对每个元素调用 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)
  }

}
}

测试

package main

import (

package main

import (

"container/ring"
"fmt"
"strconv"

)

func main() {

RingFunc()

}

func RingFunc() {

q := ring.New(3) //初始长度10
for i := 0; i < q.Len(); i++ {
    q.Value = i + 10
    q = q.Next()
}

r := ring.New(10) //初始长度10
rLen := r.Len()
for i := 0; i < rLen; i++ {
    r.Value = i  //需要自己赋值，Ring没有提供可以赋值的方法
    r = r.Next()
}

printRing(r) // 0 1 2 3 4 5 6 7 8 9


r = r.Move(6)
fmt.Println("向后移动6步,值为：" + strconv.Itoa(r.Value.(int))) //6

r = r.Move(-3)
fmt.Println("向前移动3步,值为：" + strconv.Itoa(r.Value.(int))) //3


r = r.Link(q)
printRing(r) // 4 5 6 7 8 9 0 1 2 3 10 11 12


r1 := r.Unlink(19)   //移除19%13=6个元素
printRing(r)  // 4 1 2 3 10 11 12
printRing(r1) // 5 6 7 8 9 0

}

func printRing(r *ring.Ring) {

rLen := r.Len()
for i := 0; i < rLen; i++ {
    fmt.Print(r.Value)
    fmt.Print(" ")
    r = r.Next()
}
fmt.Println()

}
package main

import (

Ring源码

测试

发表评论