1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4 5 // Package ring implements operations on circular lists.
6 package ring
7 8 // A Ring is an element of a circular list, or ring.
9 // Rings do not have a beginning or end; a pointer to any ring element
10 // serves as reference to the entire ring. Empty rings are represented
11 // as nil Ring pointers. The zero value for a Ring is a one-element
12 // ring with a nil Value.
13 type Ring struct {
14 next, prev *Ring
15 Value any // for use by client; untouched by this library
16 }
17 18 func (r *Ring) init() *Ring {
19 r.next = r
20 r.prev = r
21 return r
22 }
23 24 // Next returns the next ring element. r must not be empty.
25 func (r *Ring) Next() *Ring {
26 if r.next == nil {
27 return r.init()
28 }
29 return r.next
30 }
31 32 // Prev returns the previous ring element. r must not be empty.
33 func (r *Ring) Prev() *Ring {
34 if r.next == nil {
35 return r.init()
36 }
37 return r.prev
38 }
39 40 // Move moves n % r.Len() elements backward (n < 0) or forward (n >= 0)
41 // in the ring and returns that ring element. r must not be empty.
42 func (r *Ring) Move(n int) *Ring {
43 if r.next == nil {
44 return r.init()
45 }
46 switch {
47 case n < 0:
48 for ; n < 0; n++ {
49 r = r.prev
50 }
51 case n > 0:
52 for ; n > 0; n-- {
53 r = r.next
54 }
55 }
56 return r
57 }
58 59 // New creates a ring of n elements.
60 func New(n int) *Ring {
61 if n <= 0 {
62 return nil
63 }
64 r := &Ring{}
65 p := r
66 for i := 1; i < n; i++ {
67 p.next = &Ring{prev: p}
68 p = p.next
69 }
70 p.next = r
71 r.prev = p
72 return r
73 }
74 75 // Link connects ring r with ring s such that r.Next()
76 // becomes s and returns the original value for r.Next().
77 // r must not be empty.
78 //
79 // If r and s point to the same ring, linking
80 // them removes the elements between r and s from the ring.
81 // The removed elements form a subring and the result is a
82 // reference to that subring (if no elements were removed,
83 // the result is still the original value for r.Next(),
84 // and not nil).
85 //
86 // If r and s point to different rings, linking
87 // them creates a single ring with the elements of s inserted
88 // after r. The result points to the element following the
89 // last element of s after insertion.
90 func (r *Ring) Link(s *Ring) *Ring {
91 n := r.Next()
92 if s != nil {
93 p := s.Prev()
94 // Note: Cannot use multiple assignment because
95 // evaluation order of LHS is not specified.
96 r.next = s
97 s.prev = r
98 n.prev = p
99 p.next = n
100 }
101 return n
102 }
103 104 // Unlink removes n % r.Len() elements from the ring r, starting
105 // at r.Next(). If n % r.Len() == 0, r remains unchanged.
106 // The result is the removed subring. r must not be empty.
107 func (r *Ring) Unlink(n int) *Ring {
108 if n <= 0 {
109 return nil
110 }
111 return r.Link(r.Move(n + 1))
112 }
113 114 // Len computes the number of elements in ring r.
115 // It executes in time proportional to the number of elements.
116 func (r *Ring) Len() int {
117 n := 0
118 if r != nil {
119 n = 1
120 for p := r.Next(); p != r; p = p.next {
121 n++
122 }
123 }
124 return n
125 }
126 127 // Do calls function f on each element of the ring, in forward order.
128 // The behavior of Do is undefined if f changes *r.
129 func (r *Ring) Do(f func(any)) {
130 if r != nil {
131 f(r.Value)
132 for p := r.Next(); p != r; p = p.next {
133 f(p.Value)
134 }
135 }
136 }
137