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