libgo/go/container/ring/ring.go

   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 }