## std.iterators: The Iter interface and associated functions.
## This module is imported by default.
# reference: https://doc.rust-lang.org/std/iter/
# reference: https://docs.rs/itertools/latest/itertools/

use std.queue.ring

## The Iter interface. Any type implementing `next()` is iterable.
pub type Iter[T] = interface
  next(mut Self): T? # should T be lent?

## The IntoIter interface.
## Any type implementing `iter()` may be converted to an iterable type.
pub type IntoIter[T] = interface
  iter(Self): Iter[T]

## The Peek interface.
## Any type implementing `Iter`, `peek`, and `peek_nth` is peekable.
pub type Peek[T] = interface
  next(mut Self): T?
  peek(mut Self): T?
  peek_nth(mut Self, int): T?

## A concrete Peekable structure formed from a generic Iter type.
## Implements the Peek interface. Can be formed with `.peekable()`
type PeekImpl = struct
  iter: ref Iter[T] # this is probably bad... heap allocated...
  buf: Queue[T]

## Convert any Iter into a peekable equivalent.
# https://github.com/LukeMathWalker/multipeek/blob/main/src/lib.rs
pub func peekable[T](iter: owned Iter[T]): PeekImpl[T] =
  { iter, buf: ... } # todo: implement Queue, somewhere

pub func next[T](self: mut PeekImpl[T]): T? =
  match self.buf.pop()
  of None:
    self.iter.next()
  of Some(val):
    val
pub func peek[T](self: mut PeekImpl[T]): T? =
  match self.buf.peek()
  of None:
    self.buf.push(self.iter.next())
    self.buf.peek()
  of Some(val):
    val
pub func peek_nth[T](self: mut PeekImpl[T], i: uint): T? =
  if self.buf.len > i:
    self.buf.get(i)!
  else:
    for _ in self.buf.len .. i: # fixme
      match self.buf.next()
      of None:
        return None
      of Some(val):
        self.buf.push(val)
    self.buf.peek()

# todo: useful functions for an iterator
# https://doc.rust-lang.org/std/iter/trait.Iterator.html#provided-methods

func advance_by[T](self: Iter[T], n: uint) =
  for i in 0 .. n:
    if self.next().is_none():
      return

pub func get[T](self: Iter[T], at: uint): Option[T]
  self.advance_by(at-1).ok? # fixme
  self.next()

## Returns true if every element in an Iter fulfills the conditional.
pub func all[T](self: Iter[T], cond: T -> bool): bool =
  for elem in self:
    if not cond(elem):
      return false
  true

## Returns true if any element in an Iter fulfills the conditional.
pub func any[T](self: Iter[T], cond: T -> bool): bool =
  for elem in self:
    if cond(elem):
      return true
  false

## Returns true if an Iter contains the given element.
pub func contains[T](self: Iter[T], val: T): bool =
  self.any(elem => elem == val)

## Returns the first element matching a condition, if it exists.
pub func find[T](self: Iter[T], cond: T -> bool): T? =
  for elem in self:
    if cond(elem):
      return Some(elem)
  None

## Returns the position of the first element matching a condition, if it exists.
pub func position[T](self: Iter[T], cond: T -> bool): T? =
  var i = 0
  for elem in self:
    if cond(elem):
      return Some(i)
    i += 1
  None

pub func fold[T, U](self: Iter[T], init: U, op: (U, T) -> U) =
  var res = init
  for elem in self:
    res = res.op(elem)
  res

pub func reduce[T, U](self: Iter[T], op: (U, T) -> U): U? =
  match self.next()
  of None:
    None
  of Some(val):
    var res = val
    for elem in self:
      res = op(res, elem)
    Some(res)

pub func count[T](self: Iter[T], element: T): uint =
  self.fold(0, (elem, acc) => if elem == element: acc + 1 else: acc)

pub func count[T](self: Iter[T]): uint =
  self.fold(0, (elem, acc) => acc + 1)

pub func last[T](self: Iter[T]): T =
  var res = None
  for elem in self:
    res = elem
  res

pub func ==[T](first: Iter[T], second: Iter[T]): bool =
  for (a, b) in :
    if a != b:
      return false
  true

type LazyIter = struct
  ...

pub func apply[T](self: mut LazyIter[T], fn: T -> T)
pub func map[T, S](self: Iter[T], fn: T -> S): LazyIter[S]
pub func foreach[T, S](self: Iter[T], fn: T -> S): LazyIter[T]

pub func enumerate[T](self: LazyIter[T]): LazyIter[T] # todo: impl with map or similar

pub func dedup[T](self: Iter[T], sorted = false): LazyIter[T]
pub func filter[T](self: Iter[T], cond: T -> bool): LazyIter[T]

## Takes (at most) the first `n` elements of an iterator.
pub func take[T](self: Iter[T], n: uint): LazyIter[T]
## Skips (at most) the first `n` elements of an iterator.
pub func skip[T](self: Iter[T], n: uint): LazyIter[T]

pub func repeat[T](self: Iter[T], n: uint): LazyIter[T] # cycle??
pub func intersperse[T](self: Iter[T], item: T): LazyIter[T]
pub func step[T](self: Iter[T], step: uint): LazyIter[T]
pub func flatten[T](self: Iter[Iter[T]]): LazyIter[T]

pub func chain[T](first: Iter[T], second: Iter[T]): LazyIter[T]

pub func zip[T, U](first: Iter[T], second: Iter[U]): Iter[(T, U)]
pub func unzip[T, U](self: Iter[(T, U)]): (Iter[T], Iter[U])

# equivalent of collect. useful for type conversion
pub func from[T](self: LazyIter[T]): list[T]
pub func from(self: LazyIter[chr]): str

pub type BoundIter[T] = interface
  next(mut Self): T?
  pop(mut Self): T?

pub func rev[T](self: BoundIter[T]): BoundIter[T]

pub type SizedIter[T] = interface
  next(mut Self): T?
  pop(mut Self): T?
  len(Self): uint
  get(mut Self): T?

pub func max(self: Iter[Comparable[T]]): T
pub func min(self: Iter[Comparable[T]]): T
pub func sorted(self: Iter[Comparable[T]]): bool