Source file src/pkg/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 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	}