shufflequeue

Documentation

Index

• Variables
• type FisherYatesQueue
  • func CreateShuffledFrom[T any](rng *rand.Rand, ts []T) *FisherYatesQueue[T]
  • func Empty[T any](rng *rand.Rand) *FisherYatesQueue[T]
  • func (r *FisherYatesQueue[T]) All(yield func(*T) bool)
  • func (r *FisherYatesQueue[T]) Dequeue() (*T, error)
  • func (r *FisherYatesQueue[T]) Enqueue(t T)
  • func (r *FisherYatesQueue[T]) EnqueueSlice(ts []T)
  • func (r *FisherYatesQueue[T]) Len() int
  • func (r *FisherYatesQueue[T]) RequeueAll()
  • func (r *FisherYatesQueue[T]) RequeueLast()
  • func (r *FisherYatesQueue[T]) RequeueLastN(n int)
  • func (r *FisherYatesQueue[T]) ShuffleRemaining()

Variables

var ErrEmptyQueue = errors.New("empty queue")

Types

type FisherYatesQueue

type FisherYatesQueue[T any] struct {
	// contains filtered or unexported fields
}

A "queue" that dequeues elements via incremental Fisher-Yates shuffling. Unlike most Fisher Yates implementations, this queue swaps items to _beginning_ of the slice. This allows the queue to grow after some items have been dequeued. Additionally data is never discarded which provides a convenient and fast dequeue and requeue methods.

func CreateShuffledFrom

func CreateShuffledFrom[T any](rng *rand.Rand, ts []T) *FisherYatesQueue[T]

Creates a new shuffle queue from the passed slice. The slice is immediately shuffled.

func Empty

func Empty[T any](rng *rand.Rand) *FisherYatesQueue[T]

FISO first in shrug out queue -- items are dequeued when RNGesus sees fit uses Fisher-Yates and underlying data is never discarded instead the slice is "sorted" in place. Unlike most in place FY implementations, this structure moves swapped elements to the front of the slice rather than the end. this allows new items to be added after dequeues have happened

func (*FisherYatesQueue[T]) All

func (r *FisherYatesQueue[T]) All(yield func(*T) bool)

Convenience iterator that repeatedly randomly dequeues until all items are dequeued. Items can be requeued as normal, however care must be taken to avoid accidentally creating infinite loops:

```golang
q := RandomQueueFrom(rng, theSlice)
for something := range q.All {
    if !predicate(something) {
        q.RequeueLast()
    }
}
```

Depending on how `predicate` determines something should be requeued it may be possible to end up in a situation where the predicate _always_ rejects the item, placing it back into the queue and eventually the queue consists exclusively of items the predicate will reject.

func (*FisherYatesQueue[T]) Dequeue

func (r *FisherYatesQueue[T]) Dequeue() (*T, error)

func (*FisherYatesQueue[T]) Enqueue

func (r *FisherYatesQueue[T]) Enqueue(t T)

func (*FisherYatesQueue[T]) EnqueueSlice

func (r *FisherYatesQueue[T]) EnqueueSlice(ts []T)

func (*FisherYatesQueue[T]) Len

func (r *FisherYatesQueue[T]) Len() int

func (*FisherYatesQueue[T]) RequeueAll

func (r *FisherYatesQueue[T]) RequeueAll()

Requeues every item in the pool. Unlike calling `r.RequeueLastN(math.IntMax)` this will additionally re-shuffle the pool to remove any incidental sorting due to previous usage of the queue.

func (*FisherYatesQueue[T]) RequeueLast

func (r *FisherYatesQueue[T]) RequeueLast()

func (*FisherYatesQueue[T]) RequeueLastN

func (r *FisherYatesQueue[T]) RequeueLastN(n int)

func (*FisherYatesQueue[T]) ShuffleRemaining

func (r *FisherYatesQueue[T]) ShuffleRemaining()

Shuffles only indexes eligble for dequeuing.