cycle

Documentation

Overview

Package cycle implements a total cyclic order relation for transforming linear orders of the form 0..N into cyclic orders. Beyond what a modulo provides, this allows for the cycling of a projection and an index independently.

Example

package main

import (
	"bytes"
	"fmt"
	"log"

	"dasa.cc/x/cycle"
)

func main() {
	// ids of entire set, held in memory.
	ids := []int{0, 1, 2, 3, 4}

	// load data by id; don't want entire set's data in memory.
	load := func(id int) ([]byte, error) {
		if id < 0 || id > 4 {
			return nil, fmt.Errorf("Unknown id %v", id)
		}
		return []byte{uint8(id)}, nil
	}

	// pool holds data loaded by id for a given number of items held in memory.
	pool := make([][]byte, 3)

	// initial index of zero, also keep one item to the left and to the right loaded.
	r, err := cycle.New(-1, 0, len(pool), len(ids))
	if err != nil {
		log.Fatal(err)
	}

	// mustLoad populates pool with data; argument i is an absolute position
	// in entire set to load data for; r.Map(i) maps to a relative position
	// in pool to store data.
	mustLoad := func(i int) {
		var err error
		if pool[r.Map(i)], err = load(i); err != nil {
			panic(err)
		}
	}

	// load data from left to right.
	r.Do(r.Left(), 1, mustLoad)

	// or, load data from index to right and index-1 to left; could ran in parallel.
	r.Do(r.Index(), 1, mustLoad)
	r.Do(r.Index()-1, -1, mustLoad)

	// print data from left to right.
	buf := new(bytes.Buffer)
	r.Do(r.Left(), 1, func(i int) {
		fmt.Fprintf(buf, "%+v", pool[r.Map(i)])
	})
	fmt.Println("index", r.Index())
	fmt.Println("start", buf.String())
	fmt.Println()

	// cycle the projection and index to right.
	wi, ws, err := r.Cycle(1, 1)
	if err != nil {
		log.Fatal(err)
	}

	// update stale entries in p.
	r.Do(wi, ws, mustLoad)

	// print values after cycle.
	buf.Reset()
	r.Do(r.Left(), 1, func(i int) {
		fmt.Fprintf(buf, "%+v", pool[r.Map(i)])
	})
	fmt.Println("index", r.Index())
	fmt.Println("cycle", buf.String())
}

Output:

index 0
start [4][0][1]

index 1
cycle [0][1][2]

Index

• type R
  • func New(z, i, nsubset, nset int) (*R, error)
  • func (r *R) Cycle(sp, si int) (i, s int, err error)
  • func (r *R) Diff(i int) (dl, dr int)
  • func (r *R) Do(i, s int, fn func(i int))
  • func (r *R) Index() int
  • func (r *R) Left() int
  • func (r *R) Map(i int) int
  • func (r *R) Right() int

Examples

• Package

Types

type R

type R struct {
	// contains filtered or unexported fields
}

R is a total cyclic order relation, maintaining a left,right projection and a tracked index, both of which may cycle independent of each other.

func New

func New(z, i, nsubset, nset int) (*R, error)

New instance of R with displacement, index, subset length, and parent set length.

func (*R) Cycle

func (r *R) Cycle(sp, si int) (i, s int, err error)

Cycle projection and index, return offset index along stride.

func (*R) Diff

func (r *R) Diff(i int) (dl, dr int)

Diff returns absolute difference of index to left and right projections.

func (*R) Do

func (r *R) Do(i, s int, fn func(i int))

Do executes fn for each index along stride to projection end. If stride is zero, fn(index) is called once.

func (*R) Index

func (r *R) Index() int

Index returns absolute index of parent set.

func (*R) Left

func (r *R) Left() int

Left returns left projection index of parent set. Due to totality, left > right is possible.

func (*R) Map

func (r *R) Map(i int) int

Map an index for parent set to subset.

func (*R) Right

func (r *R) Right() int

Right returns right projection index of parent set. Due to totality, right < left is possible.