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