// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package ring implements operations on circular lists.
package ring // A Ring is an element of a circular list, or ring. // Rings do not have a beginning or end; a pointer to any ring element // serves as reference to the entire ring. Empty rings are represented // as nil Ring pointers. The zero value for a Ring is a one-element // ring with a nil Value. type Ring struct { next, prev *Ring Value any // for use by client; untouched by this library } func ( *Ring) () *Ring { .next = .prev = return } // Next returns the next ring element. r must not be empty. func ( *Ring) () *Ring { if .next == nil { return .init() } return .next } // Prev returns the previous ring element. r must not be empty. func ( *Ring) () *Ring { if .next == nil { return .init() } return .prev } // Move moves n % r.Len() elements backward (n < 0) or forward (n >= 0) // in the ring and returns that ring element. r must not be empty. func ( *Ring) ( int) *Ring { if .next == nil { return .init() } switch { case < 0: for ; < 0; ++ { = .prev } case > 0: for ; > 0; -- { = .next } } return } // New creates a ring of n elements. func ( int) *Ring { if <= 0 { return nil } := new(Ring) := for := 1; < ; ++ { .next = &Ring{prev: } = .next } .next = .prev = return } // Link connects ring r with ring s such that r.Next() // becomes s and returns the original value for r.Next(). // r must not be empty. // // If r and s point to the same ring, linking // them removes the elements between r and s from the ring. // The removed elements form a subring and the result is a // reference to that subring (if no elements were removed, // the result is still the original value for r.Next(), // and not nil). // // If r and s point to different rings, linking // them creates a single ring with the elements of s inserted // after r. The result points to the element following the // last element of s after insertion. func ( *Ring) ( *Ring) *Ring { := .Next() if != nil { := .Prev() // Note: Cannot use multiple assignment because // evaluation order of LHS is not specified. .next = .prev = .prev = .next = } return } // Unlink removes n % r.Len() elements from the ring r, starting // at r.Next(). If n % r.Len() == 0, r remains unchanged. // The result is the removed subring. r must not be empty. func ( *Ring) ( int) *Ring { if <= 0 { return nil } return .Link(.Move( + 1)) } // Len computes the number of elements in ring r. // It executes in time proportional to the number of elements. func ( *Ring) () int { := 0 if != nil { = 1 for := .Next(); != ; = .next { ++ } } return } // Do calls function f on each element of the ring, in forward order. // The behavior of Do is undefined if f changes *r. func ( *Ring) ( func(any)) { if != nil { (.Value) for := .Next(); != ; = .next { (.Value) } } }