Go implementation of C++ STL iterators and algorithms

# 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: [简体中文](README_ZH.md)

[![GoDoc](https://godoc.org/github.com/disksing/iter?status.svg)](https://godoc.org/github.com/disksing/iter)
[![Build Status](https://travis-ci.com/disksing/iter.svg?branch=master)](https://travis-ci.com/disksing/iter)
[![codecov](https://codecov.io/gh/disksing/iter/branch/master/graph/badge.svg)](https://codecov.io/gh/disksing/iter)
[![Go Report Card](https://goreportcard.com/badge/github.com/disksing/iter)](https://goreportcard.com/report/github.com/disksing/iter)

## 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](https://godoc.org/github.com/disksing/iter#AllOf), [FindIf](https://godoc.org/github.com/disksing/iter#FindIf), [Accumulate](https://godoc.org/github.com/disksing/iter#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](https://godoc.org/github.com/disksing/iter#Shuffle), [Sample](https://godoc.org/github.com/disksing/iter#Sample), [Partition](https://godoc.org/github.com/disksing/iter#Partition).

- STL also includes some complicated algorithms that may take hours to make it correct. **Implementing it manually is impractical**. Such as [NthElement](https://godoc.org/github.com/disksing/iter#NthElement), [StablePartition](https://godoc.org/github.com/disksing/iter#StablePartition), [NextPermutation](https://godoc.org/github.com/disksing/iter#NextPermutation).

- The implementation in the library contains some **imperceptible performance optimizations**. For instance, [MinmaxElement](https://godoc.org/github.com/disksing/iter#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](https://github.com/liyue201/gostl), [gods](https://github.com/emirpasic/gods) and [go-stp](https://github.com/itrabbit/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](https://github.com/disksing/iter/wiki/Algorithms).

## Examples

> The examples are run with some function alias to make it simple. See [example_test.go](https://github.com/disksing/iter/blob/master/examples_test.go) for the detail.

<table>
<thead><tr><th colspan="2">Print a list.List</th></tr></thead>
<tbody><td>

```go
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
```

</td><td>

```go
l := list.New()
GenerateN(ListBackInserter(l), 5, IotaGenerator(1))
Copy(lBegin(l), lEnd(l), IOWriter(os.Stdout, "->"))
// Output:
// 1->2->3->4->5
```

</td></tr></tbody>

<thead><tr><th colspan="2">Reverse a string</th></tr></thead>
<tbody><tr><td>

```go
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!
```

</td><td>

```go
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!
```

</td></tr></tbody>

<thead><tr><th colspan="2">In-place deduplicate (from <a href="https://github.com/golang/go/wiki/SliceTricks#in-place-deduplicate-comparable">SliceTricks</a>, with minor change)</th></tr></thead>
<tbody><tr><td>

```go
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]
```

</td><td>

```go
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]
```

</td></tr></tbody>

<thead><tr><th colspan="2">Sum all integers received from a channel</th></tr></thead>
<tbody><tr><td>

```go
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
```

</td><td>

```go
ch := make(chan int)
go func() {
  CopyN(IotaReader(1), 100, ChanWriter(ch))
  close(ch)
}()
fmt.Println(Accumulate(ChanReader(ch), ChanEOF, 0))
// Output:
// 5050
```

</td></tr></tbody>

<thead><tr><th colspan="2">Remove consecutive spaces in a string</th></tr></thead>
<tbody><tr><td>

```go
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
```

</td><td>

```go
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
```

</td></tr></tbody>

<thead><tr><th colspan="2">Collect N maximum elements from a channel</th></tr></thead>
<tbody><tr><td>

```go
// Need to manually mantain a min-heap.
```

</td><td>

```go
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, ", "))
```

</td></tr></tbody>

<thead><tr><th colspan="2">Print all permutations of ["a", "b", "c"]</th></tr></thead>
<tbody><tr><td>

```go
// Usually requires some sort of recursion
```

</td><td>

```go
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]
```

</td></tr></tbody>
</table>

## Thanks

- [cppreference.com](https://en.cppreference.com/)
- [LLVM libc++](https://libcxx.llvm.org/)

## License

BSD 3-Clause


iter

Iterator implementation to provide map and reduce functionalities

# Goterator

[![Test and Build](https://github.com/yaa110/goterator/actions/workflows/ci.yml/badge.svg)](https://github.com/yaa110/goterator/actions/workflows/ci.yml) [![PkgGoDev](https://pkg.go.dev/badge/github.com/yaa110/goterator)](https://pkg.go.dev/github.com/yaa110/goterator)

Iterator implementation for Golang to provide map and reduce functionalities.

## Package

```go
import (
    "github.com/yaa110/goterator"
    "github.com/yaa110/goterator/generator"
)
```

## Getting Started

- Create a generator from slices

```go
words := []interface{}{"an", "example", "of", "goterator"}

gen := generator.NewSlice(words)
```

- Create a generator from channels

```go
chn := make(chan interface{}, 4)
chn <- "an"
chn <- "example"
chn <- "of"
chn <- "goterator"
close(chn)

gen := generator.NewChannel(chn)
```

- Create custom generators

```go
type TestGenerator struct {
    words []string
    i     int
    value string
}

func (g *TestGenerator) Next() bool {
    if g.i == len(g.words) {
        return false
    }
    g.value = g.words[g.i]
    g.i++
    return true
}

func (g *TestGenerator) Value() interface{} {
    return g.value
}

gen := &TestGenerator{
    words: []string{"an", "example", "of", "goterator"},
    i: 0,
    value: "",
}
```

- Iterate over generators

```go
lengths := goterator.New(gen).Map(func(word interface{}) interface{} {
    return len(word.(string))
}).Collect()

assert.Equal([]interface{}{2, 7, 2, 9}, lengths)
```

Please for more information about mappers and reducers (consumers) check the [documentation](https://godoc.org/github.com/yaa110/goterator).


goterator

Convenient looping using Go's range-over-func feature

[![Genocide Watch](https://hinds-banner.vercel.app/genocide-watch?variant=plum)](https://www.pcrf.net/)

<p align="center">
    <img alt="gloop logo" src="img/logo.svg" width=500 />
</p>

<p align="center">
    <strong><i>gloop</i></strong> is a Go utility library for convenient looping using Go's <a href="https://go.dev/blog/range-functions">range-over-func</a> feature.
</p>

<div align="center">

[![Go Reference](https://pkg.go.dev/badge/github.com/alvii147/gloop.svg)](https://pkg.go.dev/github.com/alvii147/gloop) [![Tests](https://img.shields.io/github/actions/workflow/status/alvii147/gloop/github-ci.yml?branch=main&label=tests&logo=github)](https://github.com/alvii147/gloop/actions) ![Coverage](https://img.shields.io/badge/coverage-100%25-brightgreen) [![Go Report Card](https://goreportcard.com/badge/github.com/alvii147/gloop)](https://goreportcard.com/report/github.com/alvii147/gloop) [![License](https://img.shields.io/github/license/alvii147/gloop)](https://github.com/alvii147/gloop/blob/main/LICENSE)

</div>

# Installation

Install `gloop` using the `go get` command:

```bash
go get -u github.com/alvii147/gloop
```

> [!NOTE]
> Go version 1.23+ required as older versions don't offer the range-over-func feature.

# Usage

Once installed, `gloop` can be imported and used directly in your project:

```go
package main

import (
	"fmt"

	"github.com/alvii147/gloop"
)

func main() {
	for seq := range gloop.Permutations(gloop.String("CAT"), 3) {
		perm := gloop.ToString(seq)
		fmt.Println(perm)
	}
}
```

This ranges over and outputs all permutations of `CAT`:

```
CAT
CTA
ACT
ATC
TCA
TAC
```

See more specific documentation and examples in the [features section](#features) below.

# Features

## Generators

* [`Interval`](https://pkg.go.dev/github.com/alvii147/gloop#Interval) allows looping over values in a given interval of a given step size. 
* [`Linspace`](https://pkg.go.dev/github.com/alvii147/gloop#Linspace) allows looping over evenly spaced values within a given interval. n must be greater than 1. 
* [`RandomNormal`](https://pkg.go.dev/github.com/alvii147/gloop#RandomNormal) allows looping over a given number of random values drawn from a Gaussian distribution. The size must not be negative and the standard deviation must be positive. 
* [`RandomUniform`](https://pkg.go.dev/github.com/alvii147/gloop#RandomUniform) allows looping over a given number of random values drawn from a uniform distribution. The size must not be negative. 

## Scalar Iterators

* [`Chain`](https://pkg.go.dev/github.com/alvii147/gloop#Chain) allows looping over multiple [iter.Seq] sequences.
* [`Chain2`](https://pkg.go.dev/github.com/alvii147/gloop#Chain2) allows looping over multiple [iter.Seq2] sequences.
* [`Channel`](https://pkg.go.dev/github.com/alvii147/gloop#Channel) allows looping over values from a given channel. The values are consumed from the channel.
* [`Collect`](https://pkg.go.dev/github.com/alvii147/gloop#Collect) allows looping over a given set of values.
* [`Enumerate`](https://pkg.go.dev/github.com/alvii147/gloop#Enumerate) allows looping over an [iter.Seq] sequence with an index, converting it to an [iter.Seq2] sequence.
* [`Filter`](https://pkg.go.dev/github.com/alvii147/gloop#Filter) runs a given function on each value from an [iter.Seq] sequence and allows looping over values for which the function returns true.
* [`Filter2`](https://pkg.go.dev/github.com/alvii147/gloop#Filter2) runs a given function on each value from an [iter.Seq2] sequence and allows looping over values for which the function returns true.
* [`Keys`](https://pkg.go.dev/github.com/alvii147/gloop#Keys) allows looping over an [iter.Seq2], converting it to an [iter.Seq] sequence by discarding the value.
* [`KeyValue`](https://pkg.go.dev/github.com/alvii147/gloop#KeyValue) converts an [iter.Seq] sequence of [KeyValuePair] values to an [iter.Seq2] sequence.
* [`KeyValue2`](https://pkg.go.dev/github.com/alvii147/gloop#KeyValue2) converts an [iter.Seq2] sequence to an [iter.Seq] sequence of [KeyValuePair] values.
* [`List`](https://pkg.go.dev/github.com/alvii147/gloop#List) allows looping over a given [container/list.List].
* [`Map`](https://pkg.go.dev/github.com/alvii147/gloop#Map) allows looping over keys and values in a map.
* [`Reverse`](https://pkg.go.dev/github.com/alvii147/gloop#Reverse) allows looping over an [iter.Seq] sequence in order of descending index.
* [`Reverse2`](https://pkg.go.dev/github.com/alvii147/gloop#Reverse2) allows looping over an [iter.Seq2] sequence in order of descending index.
* [`Slice`](https://pkg.go.dev/github.com/alvii147/gloop#Slice) allows looping over a given slice.
* [`Sort`](https://pkg.go.dev/github.com/alvii147/gloop#Sort) allows looping over an [iter.Seq] sequence in sorted order.
* [`SortByComparison`](https://pkg.go.dev/github.com/alvii147/gloop#SortByComparison) allows looping over an [iter.Seq] sequence in sorted order using a comparison function.
* [`SortByComparison2`](https://pkg.go.dev/github.com/alvii147/gloop#SortByComparison2) allows looping over an [iter.Seq2] sequence in sorted order using a comparison function.
* [`SortByRank`](https://pkg.go.dev/github.com/alvii147/gloop#SortByRank) allows looping over an [iter.Seq] sequence in sorted order using a ranking function.
* [`SortByRank2`](https://pkg.go.dev/github.com/alvii147/gloop#SortByRank2) allows looping over an [iter.Seq2] sequence in sorted order using a ranking function.
* [`String`](https://pkg.go.dev/github.com/alvii147/gloop#String) allows looping over the runes in a given string.
* [`Transform`](https://pkg.go.dev/github.com/alvii147/gloop#Transform) runs a given function on each value over an [iter.Seq] sequence and allows looping over the returned values.
* [`Transform2`](https://pkg.go.dev/github.com/alvii147/gloop#Transform2) runs a given function on each key and value over an [iter.Seq2] sequence and allows looping over the returned values.
* [`Unique`](https://pkg.go.dev/github.com/alvii147/gloop#Unique) allows looping over unique values in an [iter.Seq] sequence.
* [`Unique2`](https://pkg.go.dev/github.com/alvii147/gloop#Unique2) allows looping over unique key value pairs in an [iter.Seq2] sequence.
* [`Values`](https://pkg.go.dev/github.com/alvii147/gloop#Values) allows looping over an [iter.Seq2] and converting it to an [iter.Seq] sequence by discarding the key.
* [`Zip`](https://pkg.go.dev/github.com/alvii147/gloop#Zip) allows looping over two [iter.Seq] sequences in pairs.
* [`Zip2`](https://pkg.go.dev/github.com/alvii147/gloop#Zip2) allows looping over two [iter.Seq2] sequences in pairs.

## Vector Iterators

* [`Batch`](https://pkg.go.dev/github.com/alvii147/gloop#Batch) allows looping over an [iter.Seq] sequence in batches of a given size. The batch size must be positive.
* [`Batch2`](https://pkg.go.dev/github.com/alvii147/gloop#Batch2) allows looping over an [iter.Seq2] sequence in batches of a given size. The batch size must be positive.
* [`CartesianProduct`](https://pkg.go.dev/github.com/alvii147/gloop#CartesianProduct) allows looping over the Cartesian product of a given size for an [iter.Seq] sequence. The size must be positive.
* [`CartesianProduct2`](https://pkg.go.dev/github.com/alvii147/gloop#CartesianProduct2) allows looping over the Cartesian product of a given size for an [iter.Seq2] sequence. The size must be positive.
* [`Combinations`](https://pkg.go.dev/github.com/alvii147/gloop#Combinations) allows looping over all combinations of a given size for an [iter.Seq] sequence. The size must be positive.
* [`Combinations2`](https://pkg.go.dev/github.com/alvii147/gloop#Combinations2) allows looping over all combinations of a given size for an [iter.Seq2] sequence. The size must be positive.
* [`Permutations`](https://pkg.go.dev/github.com/alvii147/gloop#Permutations) allows looping over all permutations of a given size for an [iter.Seq] sequence. The size must be positive.
* [`Permutations2`](https://pkg.go.dev/github.com/alvii147/gloop#Permutations2) allows looping over all permutations of a given size for an [iter.Seq2] sequence. The size must be positive.
* [`Window`](https://pkg.go.dev/github.com/alvii147/gloop#Window) allows looping over an [iter.Seq] sequence in sliding windows of a given size.
* [`Window2`](https://pkg.go.dev/github.com/alvii147/gloop#Window2) allows looping over an [iter.Seq2] sequence in sliding windows of a given size.
* [`ZipN`](https://pkg.go.dev/github.com/alvii147/gloop#ZipN) allows looping over multiple [iter.Seq] sequences simultaneously.
* [`ZipN2`](https://pkg.go.dev/github.com/alvii147/gloop#ZipN2) allows looping over multiple [iter.Seq2] sequences simultaneously.

## Aggregators

* [`All`](https://pkg.go.dev/github.com/alvii147/gloop#All) computes whether or not all values in an [iter.Seq] sequence are true.
* [`Any`](https://pkg.go.dev/github.com/alvii147/gloop#Any) computes whether or not any value in an [iter.Seq] sequence is true.
* [`Equal`](https://pkg.go.dev/github.com/alvii147/gloop#Equal) checks if two given [iter.Seq] sequences are exactly equal in contents and order.
* [`Equal2`](https://pkg.go.dev/github.com/alvii147/gloop#Equal2) checks if two given [iter.Seq2] sequences are exactly equal in contents and order.
* [`Equivalent`](https://pkg.go.dev/github.com/alvii147/gloop#Equivalent) checks if two given [iter.Seq] sequences are equal in contents, ignoring order.
* [`Equivalent2`](https://pkg.go.dev/github.com/alvii147/gloop#Equivalent2) checks if two given [iter.Seq2] sequences are equal in contents, ignoring order.
* [`Fold`](https://pkg.go.dev/github.com/alvii147/gloop#Fold) runs a given function on each value from an [iter.Seq] sequence and accumulates the result into a single value.
* [`Fold2`](https://pkg.go.dev/github.com/alvii147/gloop#Fold2) runs a given function on each value from an [iter.Seq2] sequence and accumulates the result into a single value.
* [`Max`](https://pkg.go.dev/github.com/alvii147/gloop#Max) computes the maximum value over an [iter.Seq] sequence.
* [`MaxByComparison`](https://pkg.go.dev/github.com/alvii147/gloop#MaxByComparison) computes the maximum value over an [iter.Seq] sequence using a comparison function.
* [`MaxByComparison2`](https://pkg.go.dev/github.com/alvii147/gloop#MaxByComparison2) computes the maximum key and value over an [iter.Seq2] sequence using a comparison function.
* [`MaxByRank`](https://pkg.go.dev/github.com/alvii147/gloop#MaxByRank) computes the maximum value over an [iter.Seq] sequence using a ranking function.
* [`MaxByRank2`](https://pkg.go.dev/github.com/alvii147/gloop#MaxByRank2) computes the maximum value over an [iter.Seq2] sequence using a ranking function.
* [`Mean`](https://pkg.go.dev/github.com/alvii147/gloop#Mean) computes the mean value over an [iter.Seq] sequence.
* [`Min`](https://pkg.go.dev/github.com/alvii147/gloop#Min) computes the minimum value over an [iter.Seq] sequence.
* [`MinByComparison`](https://pkg.go.dev/github.com/alvii147/gloop#MinByComparison) computes the minimum value over an [iter.Seq] sequence using a comparison function.
* [`MinByComparison2`](https://pkg.go.dev/github.com/alvii147/gloop#MinByComparison2) computes the minimum key and value over an [iter.Seq2] sequence using a comparison function.
* [`MinByRank`](https://pkg.go.dev/github.com/alvii147/gloop#MinByRank) computes the minimum value over an [iter.Seq] sequence using a ranking function.
* [`MinByRank2`](https://pkg.go.dev/github.com/alvii147/gloop#MinByRank2) computes the minimum value over an [iter.Seq2] sequence using a ranking function.
* [`Product`](https://pkg.go.dev/github.com/alvii147/gloop#Product) computes the product of values over an [iter.Seq] sequence.
* [`Reduce`](https://pkg.go.dev/github.com/alvii147/gloop#Reduce) runs a given function on each adjacent pair in an [iter.Seq] sequence and accumulates the result into a single value.
* [`Reduce2`](https://pkg.go.dev/github.com/alvii147/gloop#Reduce2) runs a given function on each adjacent pair of keys and values in an [iter.Seq2] sequence and accumulates the result into a single key and value pair.
* [`Sum`](https://pkg.go.dev/github.com/alvii147/gloop#Sum) computes summation over an [iter.Seq] sequence.
* [`ToList`](https://pkg.go.dev/github.com/alvii147/gloop#ToList) converts an [iter.Seq] sequence to a [container/list.List].
* [`ToList2`](https://pkg.go.dev/github.com/alvii147/gloop#ToList2) converts an [iter.Seq2] sequence to [container/list.List] of keys and values.
* [`ToSlice`](https://pkg.go.dev/github.com/alvii147/gloop#ToSlice) converts an [iter.Seq] sequence to a slice.
* [`ToSlice2`](https://pkg.go.dev/github.com/alvii147/gloop#ToSlice2) converts an [iter.Seq2] sequence to slices of keys and values.
* [`ToString`](https://pkg.go.dev/github.com/alvii147/gloop#ToString) converts an [iter.Seq] sequence of runes to a string.

## Miscellaneous

* [`DeferLoop`](https://pkg.go.dev/github.com/alvii147/gloop#DeferLoop) allows looping over an [iter.Seq] sequence, yielding a defer function that can register another function to be executed at the end of the currently running loop. If multiple functions are registered, they are executed in FIFO order.
* [`Parallelize`](https://pkg.go.dev/github.com/alvii147/gloop#Parallelize) runs a function on each value in an [iter.Seq] sequence on separate goroutines.
* [`Parallelize2`](https://pkg.go.dev/github.com/alvii147/gloop#Parallelize2) runs a function on each value in an [iter.Seq2] sequence on separate goroutines.

[iter.Seq]: https://pkg.go.dev/iter#Seq
[iter.Seq2]: https://pkg.go.dev/iter#Seq2
[container/list.List]: https://pkg.go.dev/container/list#List

# Contributing

All contributions are welcome! Please see [CONTRIBUTING.md](.github/CONTRIBUTING.md) for contribution guidelines.


The Best Go Libraries For Data Structures and Algorithms - Iterators (3)

iter

goterator

gloop