iter

package module
v2.0.0-...-1f204b1 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Mar 16, 2022 License: BSD-3-Clause Imports: 3 Imported by: 0

README

iter

Note: I'm currently working on making it work with Go generics. For previous version, please check v1 branch.

Go implementation of C++ STL iterators and algorithms.

Less hand-written loops, more expressive code.

README translations: 简体中文

GoDoc Build Status codecov Go Report Card

Motivation

Although Go doesn't have generics, we deserve to have reuseable general algorithms. iter helps improving Go code in several ways:

  • Some simple loops are unlikely to be wrong or inefficient, but calling algorithm instead will make the code more concise and easier to comprehend. Such as AllOf, FindIf, Accumulate.

  • Some algorithms are not complicated, but it is not easy to write them correctly. Reusing code makes them easier to reason for correctness. Such as Shuffle, Sample, Partition.

  • STL also includes some complicated algorithms that may take hours to make it correct. Implementing it manually is impractical. Such as NthElement, StablePartition, NextPermutation.

  • The implementation in the library contains some imperceptible performance optimizations. For instance, MinmaxElement is done by taking two elements at a time. In this way, the overall number of comparisons is significantly reduced.

There are alternative libraries have similar goals, such as gostl, gods and go-stp. What makes iter unique is:

  • Non-intrusive. Instead of introducing new containers, iter tends to reuse existed containers in Go (slice, string, list.List, etc.) and use iterators to adapt them to algorithms.

  • Full algorithms (>100). It includes almost all algorithms come before C++17. Check the Full List.

Examples

The examples are run with some function alias to make it simple. See example_test.go for the detail.

Print a list.List
l := list.New()
for i := 1; i <= 5; i++ {
  l.PushBack(i)
}
for e := l.Front(); e != nil; e = e.Next() {
  fmt.Print(e.Value)
  if e.Next() != nil {
    fmt.Print("->")
  }
}
// Output:
// 1->2->3->4->5
l := list.New()
GenerateN(ListBackInserter(l), 5, IotaGenerator(1))
Copy(lBegin(l), lEnd(l), IOWriter(os.Stdout, "->"))
// Output:
// 1->2->3->4->5
Reverse a string
s := "!dlrow olleH"
var sb strings.Builder
for i := len(s) - 1; i >= 0; i-- {
  sb.WriteByte(s[i])
}
fmt.Println(sb.String())

b := []byte(s)
for i := len(s)/2 - 1; i >= 0; i-- {
  j := len(s) - 1 - i
  b[i], b[j] = b[j], b[i]
}
fmt.Println(string(b))
// Output:
// Hello world!
// Hello world!
s := "!dlrow olleH"
fmt.Println(MakeString(StringRBegin(s), StringREnd(s)))

b := []byte(s)
Reverse(begin(b), end(b))
fmt.Println(string(b))
// Output:
// Hello world!
// Hello world!
In-place deduplicate (from SliceTricks, with minor change)
in := []int{3, 2, 1, 4, 3, 2, 1, 4, 1}
sort.Ints(in)
j := 0
for i := 1; i < len(in); i++ {
  if in[j] == in[i] {
    continue
  }
  j++
  in[j] = in[i]
}
in = in[:j+1]
fmt.Println(in)
// Output:
// [1 2 3 4]
in := []int{3, 2, 1, 4, 3, 2, 1, 4, 1}
Sort(begin(in), end(in))
Erase(&in, Unique(begin(in), end(in)))
fmt.Println(in)
// Output:
// [1 2 3 4]
Sum all integers received from a channel
ch := make(chan int)
go func() {
  for _, x := range rand.Perm(100) {
    ch <- x + 1
  }
  close(ch)
}()
var sum int
for x := range ch {
  sum += x
}
fmt.Println(sum)
// Output:
// 5050
ch := make(chan int)
go func() {
  CopyN(IotaReader(1), 100, ChanWriter(ch))
  close(ch)
}()
fmt.Println(Accumulate(ChanReader(ch), ChanEOF, 0))
// Output:
// 5050
Remove consecutive spaces in a string
str := "  a  quick   brown  fox  "
var sb strings.Builder
var prevIsSpace bool
for i := 0; i < len(str); i++ {
  if str[i] != ' ' || !prevIsSpace {
    sb.WriteByte(str[i])
  }
  prevIsSpace = str[i] == ' '
}
fmt.Println(sb.String())
// Output:
// a quick brown fox
str := "  a  quick   brown  fox  "
var sb StringBuilderInserter
UniqueCopyIf(sBegin(str), sEnd(str), &sb,
  func(x, y Any) bool { return x.(byte) == ' ' && y.(byte) == ' ' })
fmt.Println(sb.String())
// Output:
// a quick brown fox
Collect N maximum elements from a channel
// Need to manually mantain a min-heap.
top := make([]int, 5)
PartialSortCopyBy(ChanReader(ch), ChanEOF, begin(top), end(top),
  func(x, y Any) bool { return x.(int) > y.(int) })
Copy(begin(top), end(top), IOWriter(os.Stdout, ", "))
Print all permutations of ["a", "b", "c"]
// Usually requires some sort of recursion
s := []string{"a", "b", "c"}
for ok := true; ok; ok = NextPermutation(begin(s), end(s)) {
  fmt.Println(s)
}
// Output:
// [a b c]
// [a c b]
// [b a c]
// [b c a]
// [c a b]
// [c b a]

Thanks

License

BSD 3-Clause

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func AdvanceN

func AdvanceN[T any, It Iter[T]](it It, n int) It

AdvanceN moves an iterator by step N.

func ChanReader

func ChanReader[T any](c chan T) *chanReader[T]

ChanReader returns an InputIter that reads from a channel.

func ChanWriter

func ChanWriter[T any](c chan T) *chanWriter[T]

ChanWriter returns an OutIter that writes to a channel.

func Distance

func Distance[T any, It Iter[T]](first, last It) int

Distance returns the distance of two iterators.

func IOWriter

func IOWriter(w io.Writer, delimiter string) *ioWriter

IOWriter returns an OutputIter that writes values to an io.Writer. It panics if meet any error.

func IotaGenerator

func IotaGenerator[T Numeric](x T) func() T

IotaGenerator creates a Generator that returns [x, x+1, x+2...).

func IotaReader

func IotaReader[T Numeric, It iotaReader[T]](x T) It

IotaReader creates an InputIter that returns [x, x+1, x+2...).

func RandomGenerator

func RandomGenerator[T any](s []T, r *rand.Rand) func() T

RandomGenerator creates a generator that returns random item of a slice.

func RepeatGenerator

func RepeatGenerator[T any](x T) func() T

RepeatGenerator creates an Generator that returns [x, x, x...).

func RepeatReader

func RepeatReader[T any](x T) repeatReader[T]

RepeatReader creates an InputIter that returns [x, x, x...).

Types

type BackwardMovable

type BackwardMovable[It Iter[any]] interface {
	Prev() It
}

BackwardMovable represents iterators that can move backward.

type BidiIter

type BidiIter[T any, It Iter[T]] interface {
	ForwardIter[T, It]
	BackwardMovable[It]
}

BidiIter is an iterator that moves both forward or backward.

type BidiReadWriter

type BidiReadWriter[T any, It Iter[T]] interface {
	BidiIter[T, It]
	ReadWriter[T]
}

BidiReadWriter is an interface that groups BidiIter and ReadWriter.

type BidiReader

type BidiReader[T any, It Iter[T]] interface {
	BidiIter[T, It]
	Reader[T]
}

BidiReader is an interface that groups BidiIter and Reader.

type BidiWriter

type BidiWriter[T any, It Iter[T]] interface {
	BidiIter[T, It]
	Writer[T]
}

BidiWriter is an interface that groups BidiIter and Writer.

type Chan

type Chan[Elem any] interface {
	~chan Elem
}

Chan is a constraint that matches channels of any element type.

type Comparable

type Comparable[It Iter[any]] interface {
	Eq(It) bool
}

Comparable represents an iterator that can be compared.

type Complex

type Complex interface {
	~complex64 | ~complex128
}

Complex is a constraint that permits any complex numeric type. If future releases of Go add new predeclared complex numeric types, this constraint will be modified to include them.

type Float

type Float interface {
	~float32 | ~float64
}

Float is a constraint that permits any floating-point type. If future releases of Go add new predeclared floating-point types, this constraint will be modified to include them.

type ForwardIter

type ForwardIter[T any, It Iter[T]] interface {
	ForwardMovable[It]
	Comparable[It]
	AllowMultiplePass() // a marker indicates it can be multiple passed.
}

ForwardIter is an iterator that moves forward.

type ForwardMovable

type ForwardMovable[It Iter[any]] interface {
	Next() It
}

ForwardMovable represents iterators that can move forward.

type ForwardReadWriter

type ForwardReadWriter[T any, It Iter[T]] interface {
	ForwardIter[T, It]
	ReadWriter[T]
}

ForwardReadWriter is an interface that groups ForwardIter and ReadWriter.

type ForwardReader

type ForwardReader[T any, It Iter[T]] interface {
	ForwardIter[T, It]
	Reader[T]
}

ForwardReader is an interface that groups ForwardIter and Reader.

type ForwardWriter

type ForwardWriter[T any, It Iter[T]] interface {
	ForwardIter[T, It]
	Writer[T]
}

ForwardWriter is an interface that groups ForwardIter and Writer.

type InputIter

type InputIter[T any, It Iter[T]] interface {
	Reader[T]
	ForwardMovable[It]
	Comparable[It]
}

InputIter is a readable and forward movable iterator.

type Integer

type Integer interface {
	Signed | Unsigned
}

Integer is a constraint that permits any integer type. If future releases of Go add new predeclared integer types, this constraint will be modified to include them.

type Iter

type Iter[T any] interface{}

Iter represents an iterator, just an alias of any.

type Map

type Map[Key comparable, Val any] interface {
	~map[Key]Val
}

Map is a constraint that matches maps of any element and value type.

type Numeric

type Numeric interface {
	Integer | Float
}

Numeric is a constraint that permits any numeric type.

type Ordered

type Ordered interface {
	Integer | Float | ~string
}

Ordered is a constraint that permits any ordered type: any type that supports the operators < <= >= >. If future releases of Go add new ordered types, this constraint will be modified to include them.

type OutputIter

type OutputIter[T any] interface {
	Writer[T]
}

OutputIter is a writable and ForwardMovable iterator.

It may not implement the incremental interface, in which case the increment logic is done in Write().

type RandomIter

type RandomIter[T any, It Iter[T]] interface {
	BidiIter[T, It]
	AdvanceN(n int) It
	Distance(It) int
	Less(It) bool
}

RandomIter is a random access iterator.

type RandomReadWriter

type RandomReadWriter[T any, It Iter[T]] interface {
	RandomIter[T, It]
	ReadWriter[T]
}

RandomReadWriter is an interface that groups RandomIter and ReadWriter.

type RandomReader

type RandomReader[T any, It Iter[T]] interface {
	RandomIter[T, It]
	Reader[T]
}

RandomReader is an interface that groups RandomIter and Reader.

type RandomWriter

type RandomWriter[T any, It Iter[T]] interface {
	RandomIter[T, It]
	Writer[T]
}

RandomWriter is an interface that groups RandomIter and Writer.

type ReadWriter

type ReadWriter[T any] interface {
	Reader[T]
	Writer[T]
}

ReadWriter is an interface that groups Reader and Writer.

type Reader

type Reader[T any] interface {
	Read() T
}

Reader is a readable iterator.

type Signed

type Signed interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64
}

Signed is a constraint that permits any signed integer type. If future releases of Go add new predeclared signed integer types, this constraint will be modified to include them.

type Slice

type Slice[Elem any] interface {
	~[]Elem
}

Slice is a constraint that matches slices of any element type.

type Unsigned

type Unsigned interface {
	~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
}

Unsigned is a constraint that permits any unsigned integer type. If future releases of Go add new predeclared unsigned integer types, this constraint will be modified to include them.

type Writer

type Writer[T any] interface {
	Write(T)
}

Writer is a writable iterator.

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL