feiyu
Bug?
容器Ring笔记
06/27
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
// 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
// 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 main
import (
package main
import (
"container/ring"
"fmt"
"strconv")
func main() {
RingFunc()}
/**
func (r Ring) Next() Ring // 下一个元素
func (r Ring) Prev() Ring // 上一个元素
func (r Ring) Move(n int) Ring // 返回从当前元素移动n(向前或向后)步指向的元素
func New(n int) *Ring //
// 合并或者移除， 并返回r原本的后继元素r.Next()。
// 若r与s是不同环，则连接r和s。设n为r的后继，p为s的前驱，则：r的后继是s,s的前驱是r. p的后继变为n，n的前驱变为p
// 如果r和s指向同一个环形链表，则会删除掉r和s之间的元素，删掉的元素构成一个子链表，返回指向该子链表的指针（r的原后继元素）；
func (r Ring) Link(s Ring) *Ring
func (r Ring) Unlink(n int) Ring // 删除链表中n % r.Len()个元素，从r.Next()开始删除。注意它的返回值，返回的是删除的链表
func (r *Ring) Len() int // 求Ring的长度
func (r *Ring) Do(f func(interface{})) // 对Ring中元素执行 f 操作
*/
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 (
