import {
    Block, Comparator, Dictionary, PairPredicate, Positional, Predicate, Sequence, SequenceIterator,
    Transform,
    Falsy
} from "../types"
import { identity, negate } from "../../functions/static/function"
import { is } from "../../functions/static/equality"
import { isGreaterThan, isLessThan, ErrorMessage } from "../../shared"
import { OmniSequence, OutDestination } from "./omni-sequence"
import { range } from "../../functions/static/sequence"

/**
 * @hidden
 */
export type PipeConstructor = { new (sequence: Sequence<any>): OmniSequence<any> }

let Pipe = null as any as PipeConstructor

/**
 * @hidden
 */
export function injectPipeConstructor(constructor: PipeConstructor) {
    Pipe = constructor
}

/**
 * An omni-sequence that is iterable more than once and supports random access.
 */
export class Span<T> implements OmniSequence<T> {

    constructor(positional: Positional<T>)

    constructor(positional: Positional<T>, start: number)

    constructor(positional: Positional<T>, start: number, end: number)

    constructor(positional: Positional<T>, start?: number, end?: number) {
        this._array = positional
        this._start = start === undefined ? 0 : start
        this._end = end === undefined ? positional.length : end
    }

    /**
     * The underlying array or string of the span.
     */
    private _array: Positional<T>

    /**
     * The underlying array or string of the span.
     */
    get array(): Positional<T> {
        return this._array
    }

    /**
     * The start index of the span.
     */
    private _start: number

    /**
     * The start index of the span.
     */
    get start(): number {
        return this._start
    }

    /**
     * The non-inclusive end index of the span.
     */
    private _end: number

    /**
     * The non-inclusive end index of the span.
     */
    get end(): number {
        return this._end
    }

    [Symbol.iterator](): Iterator<T> {
        return this._iterate(false)
    }

    toString(): string {
        return "Span::{" + this.start + ":" + this.end + "}"
    }

    all(predicate: Predicate<T>): boolean {
        const {array, start, end} = this
        for (let i = start; i < end; i++) {
            if (!predicate(array[i])) {
                return false
            }
        }
        return true
    }

    as<O extends T>(this: Span<T>): OmniSequence<O> {
        return this as any
    }

    concat(elements: Sequence<T>): OmniSequence<T> {
        return new Pipe(generateAppend(this, elements))
    }

    append(...elements: T[]): OmniSequence<T> {
        return new Pipe(generateAppend(this, elements))
    }

    associate<K>(transform: Transform<T, K>): OmniSequence<[K, T]> {
        return this.map((element) => [transform(element), element] as [K, T])
    }

    at(index: number): T {
        index = this._sanitizeIndex(index)

        const {array, start, end} = this
        if (index < start || index >= end) {
            throw new Error(ErrorMessage.indexOutOfBoundsAt)
        }
        return array[index]
    }

    cleave(index: number): [T[], T[]] {
        index = this._sanitizeIndex(index)

        const {array, start, end} = this
        if (index < start || index > end) {
            throw new Error(ErrorMessage.indexOutOfBoundsCleave)
        }
        const before = array.slice(start, index)
        const after = array.slice(index, end)
        return [before, after] as [T[], T[]]
    }

    count(): number
    count(predicate: Predicate<T>): number
    count(predicate?: Predicate<T>): number {
        if (predicate === undefined) {
            return this.end - this.start
        }
        let count = 0
        const {array, start, end} = this
        for (let i = start; i < end; i++) {
            if (predicate(array[i])) {
                count++
            }
        }
        return count
    }

    cut(index: number): OmniSequence<T>
    cut(index: number, count: number): OmniSequence<T>
    cut(index: number, count: number = 1): OmniSequence<T> {
        index = this._sanitizeIndex(index)
        count = this._sanitizeCount(count)

        const {array, start, end} = this
        if (index < start || index >= end) {
            throw new Error(ErrorMessage.indexOutOfBoundsCut)
        }
        return new Pipe(generateCut(this, index, count))
    }

    chunk(count: number): OmniSequence<T[]> {
        count = this._sanitizeCount(count)

        if (count < 1) {
            throw new Error(ErrorMessage.invalidChunkSize)
        }
        return new Pipe(generateChunk(this, count))
    }

    difference<K>(sequence: Sequence<T>): OmniSequence<T>
    difference<K>(sequence: Sequence<T>, transform: Transform<T, K>): OmniSequence<T>
    difference<K>(sequence: Sequence<T>, transform: Transform<T, K> = identity): OmniSequence<T> {
        return new Pipe(generateDifference(this, sequence, transform as Transform<T, K>))
    }

    done(): T[] {
        const {array, start, end} = this

        if (Array.isArray(array)) {
            return array.slice(start, end) as T[]
        }
        return Array.from(array.slice(start, end) as any) as T[]
    }

    drop(): OmniSequence<T>
    drop(count: number): OmniSequence<T>
    drop(predicate: Predicate<T>): OmniSequence<T>
    drop(argument?: number | Predicate<T>): OmniSequence<T> {
        if (argument === undefined) {
            argument = 1
        } else if (typeof argument === "function") {
            const predicate = argument
            const index = this._indexNot(predicate)
            if (index < 0) {
                return new Span(this.array, this.end, this.end)
            }
            return this._after(index)
        }

        const count = this._sanitizeCount(argument)
        return this._after(Math.min(this.start + count, this.end))
    }

    dropLast(): OmniSequence<T>
    dropLast(count: number): OmniSequence<T>
    dropLast(predicate: Predicate<T>): OmniSequence<T>
    dropLast(argument?: number | Predicate<T>): OmniSequence<T> {
        if (argument === undefined) {
            argument = 1
        } else if (typeof argument === "function") {
            const predicate = argument
            const index = this._indexNot(predicate, true)
            if (index < 0) {
                return new Span(this.array, this.start, this.start)
            }
            return this._before(index + 1)
        }
        const count = this._sanitizeCount(argument)
        return this._before(Math.max(this.end - count, this.start))
    }

    each(action: (element: T, index: number, end: Block) => void): OmniSequence<T> {
        const {array, start, end} = this
        let exited = false
        const exit = () => {
            exited = true
        }
        for (let i = start; i < end; i++) {
            action(array[i], i, exit)
            if (exited) {
                break
            }
        }
        return this
    }

    endsWith(suffix: Positional<T>): boolean
    endsWith(suffix: Positional<T>, equals: PairPredicate<T>): boolean
    endsWith(suffix: Positional<T>, equals: PairPredicate<T> = is): boolean {
        if (suffix.length > this.count()) {
            return false
        }

        const array = this.array
        const start = this.end - suffix.length
        for (let i = 0; i < suffix.length; i++) {
            if (!equals(suffix[i], array[start + i])) {
                return false
            }
        }
        return true
    }

    entries(): OmniSequence<[number, T]> {
        return new Pipe(generateEntries(this))
    }

    entriesReversed(): OmniSequence<[number, T]> {
        return new Pipe(generateEntriesReversed(this))
    }

    filter(): OmniSequence<T>
    filter(predicate: Predicate<T>): OmniSequence<T>
    filter(predicate: Predicate<T> = identity): OmniSequence<T> {
        return new Pipe(generateFilter(this, predicate))
    }

    find(predicate: Predicate<T>): T | null
    find<O>(predicate: Predicate<T>, instead: O): T | O
    find<O>(predicate: Predicate<T>, instead?: O): T | O | null {
        const {array, start, end} = this
        for (let i = start; i < end; i++) {
            if (predicate(array[i])) {
                return array[i]
            }
        }
        if (instead === undefined) {
            return null
        }
        return instead
    }

    findLast(predicate: Predicate<T>): T | null
    findLast<O>(predicate: Predicate<T>, instead: O): T | O
    findLast<O>(predicate: Predicate<T>, instead?: O): T | O | null {
        const {array, start, end} = this
        for (let i = end - 1; i >= start; i--) {
            if (predicate(array[i])) {
                return array[i]
            }
        }
        if (instead === undefined) {
            return null
        }
        return instead
    }

    first<O>(): T
    first<O>(instead: O): T | O
    first<O>(instead?: O): T | O {
        const array = this.array
        if (array.length === 0) {
            if (instead === undefined) {
                throw new Error(ErrorMessage.noFirstElement)
            }
            return instead
        }
        return array[0]
    }

    flat<T>(this: Span<Sequence<T>>): OmniSequence<T> {
        return new Pipe(generateFlat(this))
    }

    fold<R>(initial: R, reducer: (accumulator: R, current: T) => R): R {
        const {array, start, end} = this
        let value = initial
        for (let i = start; i < end; i++) {
            value = reducer(value, array[i])
        }
        return value
    }

    index(predicate: Predicate<T>): number {
        return this._index(predicate, false) - this.start
    }

    indices(): OmniSequence<number>
    indices(predicate: Predicate<T>): OmniSequence<number>
    indices(predicate?: Predicate<T>): OmniSequence<number> {
        if (predicate === undefined) {
            return range(this.count())
        }
        return new Pipe(generateIndices(this, predicate))
    }

    indicesReversed(): OmniSequence<number>
    indicesReversed(predicate: Predicate<T>): OmniSequence<number>
    indicesReversed(predicate?: Predicate<T>): OmniSequence<number> {
        if (predicate === undefined) {
            return range(this.start, this.end, -1)
        }
        return new Pipe(generateIndicesReversed(this, predicate))
    }

    inject(index: number, elements: Sequence<T>): OmniSequence<T> {
        index = this._sanitizeIndex(index)

        const {start, end} = this
        if (index < start || index > end) {
            throw new Error(ErrorMessage.indexOutOfBoundsInject)
        }
        return new Pipe(generateInject(this, index, elements))
    }

    intersect<K>(sequence: Sequence<T>): OmniSequence<T>
    intersect<K>(sequence: Sequence<T>, transform: Transform<T, K>): OmniSequence<T>
    intersect<K>(sequence: Sequence<T>, transform: Transform<T, K> = identity): OmniSequence<T> {
        return new Pipe(generateIntersect(this, sequence, transform))
    }

    insert(index: number, ...elements: T[]): OmniSequence<T> {
        index = this._sanitizeIndex(index)

        const {start, end} = this
        if (index < start || index > end) {
            throw new Error(ErrorMessage.indexOutOfBoundsInsert)
        }
        return new Pipe(generateInject(this, index, elements))
    }

    invert<K, V>(this: Span<[K, V]>): OmniSequence<[V, K]> {
        return new Pipe(generateInvert(this))
    }

    join(): string
    join(separator: string): string
    join(separator = ""): string {
        return this.yank().toArray().join(separator)
    }

    last<O>(): T
    last<O>(instead: O): T | O
    last<O>(instead?: O): T | O {
        if (this.count() > 0) {
            return this.array[this.end - 1]
        }
        if (instead === undefined) {
            throw new Error(ErrorMessage.noLastElement)
        }
        return instead
    }

    lastIndex(): number
    lastIndex(predicate: Predicate<T>): number
    lastIndex(predicate?: Predicate<T>): number {
        if (predicate === undefined) {
            return this.count() - 1
        }
        return this._index(predicate, true) - this.start
    }

    map<OK, OV>(this: Span<T>, transform: Transform<T, [OK, OV]>): OmniSequence<[OK, OV]>
    map<O>(this: Span<T>, transform: Transform<T, O>): OmniSequence<O>
    map<O>(this: Span<T>, transform: Transform<T, O>): OmniSequence<O> {
        return new Pipe(generateMap(this, transform))
    }

    max(this: Span<number>): number
    max(transform: Transform<T, number>): T
    max(transform?: Transform<T, number>): T | number {
        return findExtreme(this, transform || identity, -Infinity, isGreaterThan, ErrorMessage.noMaxElement)
    }

    mean(this: Span<number>): number {
        const {array, start, end} = this
        let sum = 0
        if (this.count() === 0) {
            return 0
        }
        for (let i = start; i < end; i++) {
            sum += array[i]
        }
        return sum / array.length
    }

    min(this: Span<number>): number
    min(transform: Transform<T, number>): T
    min(transform?: Transform<T, number>): T | number {
        return findExtreme(this, transform || identity, Infinity, isLessThan, ErrorMessage.noMinElement)
    }

    none(): boolean
    none(predicate: Predicate<T>): boolean
    none(predicate?: Predicate<T>): boolean {
        return !this.some(predicate as Predicate<T>)
    }

    partition(predicate: Predicate<T>): [T[], T[]] {
        const {array, start, end} = this
        const positive: T[] = []
        const negative: T[] = []
        for (let i = start; i < end; i++) {
            const element = array[i]
            if (predicate(element)) {
                positive.push(element)
            } else {
                negative.push(element)
            }
        }
        return [positive, negative]
    }

    permute<T>(): OmniSequence<T[]> {
        return new Pipe(generatePermute(this))
    }

    prepend(...elements: T[]): OmniSequence<T> {
        return new Pipe(generatePrepend(this, elements))
    }

    rank(transform: Transform<T, number>): OmniSequence<T> {
        return this.sort((a: T, b: T) => transform(a) - transform(b))
    }

    remove(predicate: Predicate<T>): OmniSequence<T>
    remove(predicate: Predicate<T>, count: number): OmniSequence<T>
    remove(predicate: Predicate<T>, count: number = Infinity): OmniSequence<T> {
        return new Pipe(generateRemove(this, predicate, this._sanitizeCount(count)))
    }

    removeLast(predicate: Predicate<T>, count: number): OmniSequence<T> {
        return new Pipe(generateRemoveLast(this, predicate, this._sanitizeCount(count)))
    }

    repeat(): OmniSequence<T>
    repeat(count: number): OmniSequence<T>
    repeat(count?: number): OmniSequence<T> {
        return new Pipe(generateRepeat(this, count ? this._sanitizeCount(count) : count))
    }

    replace<R>(predicate: Predicate<T>, replacement: R): OmniSequence<T | R>
    replace<R>(predicate: Predicate<T>, replacement: R, count: number): OmniSequence<T | R>
    replace<R>(predicate: Predicate<T>, replacement: R, count = Infinity): OmniSequence<T | R> {
        return new Pipe(generateReplace(this, predicate, replacement, this._sanitizeCount(count)))
    }

    replaceLast<R>(predicate: Predicate<T>, replacement: R, count: number): OmniSequence<T | R> {
        return new Pipe(generateReplaceLast(this, predicate, replacement, this._sanitizeCount(count)))
    }

    reversed(): OmniSequence<T> {
        return new Pipe(this._iterate(true))
    }

    set(index: number, element: T): OmniSequence<T> {
        index = this._sanitizeIndex(index)

        const {start, end} = this
        if (index < start || index >= end) {
            throw new Error(ErrorMessage.indexOutOfBoundsSet)
        }

        const copy = this.yank()
        const inner = copy.array as T[]
        inner[index] = element
        return copy
    }

    slice(start: number, end: number): OmniSequence<T> {
        start = this._sanitizeIndex(start)
        end = this._sanitizeIndex(end)

        if (start < this.start || start > this.end || end < start) {
            throw new Error(ErrorMessage.invalidSliceBounds)
        }
        return this._slice(start, end)
    }

    solid(): Span<T> {
        return this
    }

    some(): boolean
    some(predicate: Predicate<T>): boolean
    some(predicate?: Predicate<T>): boolean {
        if (predicate === undefined) {
            return this.end > this.start
        }
        return this.index(predicate) >= 0
    }

    sort(this: Span<number>): OmniSequence<number>
    sort(this: Span<number>, descending: boolean): OmniSequence<number>
    sort(this: Span<string>): OmniSequence<string>
    sort(this: Span<string>, descending: boolean): OmniSequence<string>
    sort(comparator: Comparator<T>): OmniSequence<T>
    sort(this: Span<T | number | string>, second: Comparator<T> | boolean = false): OmniSequence<T | number | string> {
        const {array, start, end} = this
        let segment = array.slice(start, end)
        if (typeof segment === "string") {
            segment = Array.from(segment)
        }
        if (segment.length === 0) {
            return new Span(segment)
        }

        let comparator: Comparator<T>
        if (typeof second === "function") {
            comparator = second
        } else {
            const descending = second
            if (typeof segment[0] === "string") {
                comparator = ((a: string, b: string) => a.localeCompare(b)) as any
            } else {
                comparator = ((a: number, b: number) => a - b) as any
            }
            if (descending) {
                comparator = negate(comparator)
            }
        }

        return new Span(segment.sort(comparator as any))
    }

    startsWith(prefix: Sequence<T>): boolean
    startsWith(prefix: Sequence<T>, equals: PairPredicate<T>): boolean
    startsWith(prefix: Sequence<T>, equals: PairPredicate<T> = is): boolean {
        const iterator = this[Symbol.iterator]()
        const prefixIterator = prefix[Symbol.iterator]()

        while (true) {
            const current = iterator.next()
            const prefixResult = prefixIterator.next()
            if (prefixResult.done) {
                break
            }
            if (current.done) {
                return false
            }
            if (!equals(current.value, prefixResult.value)) {
                return false
            }
        }

        return true
    }

    sum(this: Span<number>): number {
        const {array, start, end} = this

        let sum = 0
        for (let i = start; i < end; i++) {
            sum += array[i]
        }
        return sum
    }

    swap(first: number, second: number): OmniSequence<T> {
        first = this._sanitizeIndex(first)
        second = this._sanitizeIndex(second)

        const {start, end} = this
        if (first < start || first >= end) {
            throw new Error(ErrorMessage.indexOutOfBoundsSwap)
        }
        if (second < start || second >= end) {
            throw new Error(ErrorMessage.indexOutOfBoundsSwap)
        }
        const copy = this.yank()
        const array = copy.array as T[]

        const temporary = array[first]
        array[first] = array[second]
        array[second] = temporary

        return copy
    }

    take(): OmniSequence<T>
    take(count: number): OmniSequence<T>
    take(predicate: Predicate<T>): OmniSequence<T>
    take(argument?: number | Predicate<T>): OmniSequence<T> {
        if (argument === undefined) {
            return this._copy()
        }

        if (typeof argument === "function") {
            const predicate = argument
            const index = this._indexNot(predicate)
            if (index < 0) {
                return this._copy()
            }
            return this._before(index)
        }

        const count = argument === undefined ? this.count() : this._sanitizeCount(argument)
        return this._before(Math.min(count + this.start, this.end))
    }

    takeLast(count: number): OmniSequence<T>
    takeLast(predicate: Predicate<T>): OmniSequence<T>
    takeLast(argument: number | Predicate<T>): OmniSequence<T> {
        if (typeof argument === "function") {
            const predicate = argument
            const index = this._indexNot(predicate, true)
            return this._after(index + 1)
        }

        const count = argument === undefined ? this.count() : this._sanitizeCount(argument)
        return this._after(Math.max(0, this.end - count))
    }

    toArray(): T[]
    toArray(destination: T[]): T[]
    toArray(destination: T[], clear: boolean): T[]
    toArray(destination?: T[], clear: boolean = false): T[] {
        if (destination === undefined) {
            return this.done()
        }

        const {array, start, end} = this

        if (clear) {
            destination.length = 0
        }
        for (let i = start; i < end; i++) {
            destination.push(array[i])
        }
        return destination
    }

    toMap<K, V>(this: Span<[K, V]>): Map<K, V>
    toMap<K, V>(this: Span<[K, V]>, destination: Map<K, V>): Map<K, V>
    toMap<K, V>(this: Span<[K, V]>, destination: Map<K, V>, clear: boolean): Map<K, V>
    toMap<K, V>(this: Span<[K, V]>, destination?: Map<K, V>, clear: boolean = false): Map<K, V> {
        const {array, start, end} = this

        destination = destination || new Map()

        if (clear) {
            destination.clear()
        }
        for (let i = start; i < end; i++) {
            const [key, value] = array[i]
            destination.set(key, value)
        }
        return destination
    }

    toObject<V>(this: Span<[string, V]>): Dictionary<V>
    toObject<V>(this: Span<[string, V]>, destination: Dictionary<V>): Dictionary<V>
    toObject<V>(this: Span<[string, V]>, destination: Dictionary<V>, clear: boolean): Dictionary<V>
    toObject<V>(this: Span<[string, V]>, destination?: Dictionary<V>, clear: boolean = false): Dictionary<V> {
        const {array, start, end} = this

        if (destination) {
            if (clear) {
                for (const key in destination) {
                    if (destination.hasOwnProperty(key)) {
                        delete destination[key]
                    }
                }
            }
        } else {
            destination = {}
        }

        for (let i = start; i < end; i++) {
            const [key, value] = array[i]
            destination[key] = value
        }
        return destination
    }

    toSet(): Set<T>
    toSet(destination: Set<T>): Set<T>
    toSet(destination: Set<T>, clear: boolean): Set<T>
    toSet(destination?: Set<T>, clear: boolean = false): Set<T> {
        const {array, start, end} = this

        destination = destination || new Set()
        if (clear) {
            destination.clear()
        }
        for (let i = start; i < end; i++) {
            destination.add(array[i])
        }
        return destination
    }

    union<K>(sequence: Sequence<T>): OmniSequence<T>
    union<K>(sequence: Sequence<T>, transform: Transform<T, K>): OmniSequence<T>
    union<K>(sequence: Sequence<T>, transform: Transform<T, K> = identity): OmniSequence<T> {
        return new Pipe(generateUnion(this, sequence, transform))
    }

    unique<K>(): OmniSequence<T>
    unique<K>(transform: Transform<T, K>): OmniSequence<T>
    unique<K>(transform: Transform<T, K> = identity): OmniSequence<T> {
        return new Pipe(generateUnique(this, transform))
    }

    use<R>(transform: Transform<Span<T>, R>): R {
        return transform(this)
    }

    yank(): Span<T> {
        return new Span(this.toArray()) as Span<T>
    }

    zip<V>(elements: Sequence<V>): OmniSequence<[T, V]> {
        return new Pipe(generateZip(this, elements))
    }

    private _index(predicate: Predicate<T>, reverse = false): number {
        const {array, start, end} = this
        if (reverse) {
            for (let i = end - 1; i >= start; i--) {
                if (predicate(array[i])) {
                    return i
                }
            }
        } else {
            for (let i = start; i < end; i++) {
                if (predicate(array[i])) {
                    return i
                }
            }
        }
        return -1
    }

    private _indexNot(predicate: Predicate<T>, reverse = false): number {
        const {array, start, end} = this
        if (reverse) {
            for (let i = end - 1; i >= start; i--) {
                if (!predicate(array[i])) {
                    return i
                }
            }
        } else {
            for (let i = start; i < end; i++) {
                if (!predicate(array[i])) {
                    return i
                }
            }
        }
        return -1
    }

    private * _iterate(reverse: boolean): SequenceIterator<T> {
        const {array, start, end} = this
        if (reverse) {
            for (let i = end - 1; i >= start; i--) {
                yield array[i]
            }
        } else {
            for (let i = start; i < end; i++) {
                yield array[i]
            }
        }
    }

    private _after(start: number) {
        return this._slice(start, this.end)
    }

    private _before(end: number) {
        return this._slice(this.start, end)
    }

    private _copy() {
        return this._slice(this.start, this.end)
    }

    private _empty() {
        return this._slice(this.start, this.start)
    }

    private _sanitizeIndex(index: number) {
        return this._start + Math.floor(index)
    }

    private _sanitizeCount(count: number) {
        return Math.max(Math.floor(count), 0)
    }

    private _seat(positional: Positional<T>) {
        this._array = positional
        this._start = 0
        this._end = positional.length
    }

    private _slice(start: number, end: number) {
        return new Span(this.array, start, end)
    }
}

function* generateAppend<T>(span: Span<T>, elements: Sequence<T>): SequenceIterator<T> {
    yield* span
    yield* elements
}

function* generateCut<T>(span: Span<T>, index: number, count: number): SequenceIterator<T> {
    const {array, start, end} = span
    const first = index + start
    const last = Math.min(first + Math.max(count, 0), end) - 1
    for (let i = start; i < first; i++) {
        yield array[i]
    }
    for (let i = last + 1; i < end; i++) {
        yield array[i]
    }
}

function* generateChunk<T>(span: Span<T>, count: number): SequenceIterator<T[]> {
    const {array, start, end} = span

    let current: T[] = []
    for (let i = start; i < end; i++) {
        current.push(array[i])
        if (current.length === count) {
            yield current
            current = []
        }
    }
    if (current.length !== 0) {
        yield current
    }
}

function* generateDifference<T, K>(span: Span<T>, sequence: Sequence<T>, 
                                   transform: Transform<T, K>): SequenceIterator<T> {

    sequence = Array.isArray(sequence) ? sequence : Array.from(sequence)

    const {array, start, end} = span
    const keys = new Set<K>() 
    const otherKeys = new Set<K>()

    for (const element of sequence) {
        otherKeys.add(transform(element))
    }

    for (let i = start; i < end; i++) {
        const element = array[i]
        const key = transform(element)
        if (keys.has(key)) {
            continue
        }
        keys.add(key)
        if (otherKeys.has(key)) {
            continue
        }
        yield element
    }

    otherKeys.clear()

    for (const element of sequence) {
        const key = transform(element)
        if (otherKeys.has(key)) {
            continue
        }
        otherKeys.add(key)
        if (keys.has(key)) {
            continue
        }
        yield element
    }
}

function* generateEntries<T>(span: Span<T>): SequenceIterator<[number, T]> {
    const {array, start, end} = span
    for (let i = start; i < end; i++) {
        yield [i, array[i]]
    }
}

function* generateEntriesReversed<T>(span: Span<T>): SequenceIterator<[number, T]> {
    const {array, start, end} = span
    for (let i = end - 1; i >= start; i--) {
        yield [i, array[i]]
    }
}

function* generateFilter<T>(span: Span<T>, predicate: Predicate<T>): SequenceIterator<T> {
    const {array, start, end} = span
    for (let i = start; i < end; i++) {
        const element = array[i]
        if (predicate(element)) {
            yield element
        }
    }
}

function* generateFlat<T>(span: Span<Sequence<T>>): SequenceIterator<T> {
    const {array, start, end} = span
    for (let i = start; i < end; i++) {
        yield* array[i]
    }
}

function* generateIndices<T>(span: Span<T>, predicate: Predicate<T>): SequenceIterator<number> {
    const {array, start, end} = span
    for (let i = start; i < end; i++) {
        const element = array[i]
        if (predicate(element)) {
            yield i
        }
    }
}

function* generateIndicesReversed<T>(span: Span<T>, predicate: Predicate<T>): SequenceIterator<number> {
    const {array, start, end} = span
    for (let i = end - 1; i >= start; i--) {
        const element = array[i]
        if (predicate(element)) {
            yield i
        }
    }
}

function* generateInject<T>(span: Span<T>, index: number, elements: Sequence<T>): SequenceIterator<T> {
    const {array, start, end} = span
    for (let i = start; i < index; i++) {
        yield array[i]
    }
    yield* elements
    for (let i = index; i < end; i++) {
        yield array[i]
    }
}

function* generateIntersect<T, K>(span: Span<T>, sequence: Sequence<T>, 
                                  transform: Transform<T, K>): SequenceIterator<T> {
    const {array, start, end} = span

    const keys = new Set<K>()
    const other = new Set<K>()

    for (const element of sequence) {
        other.add(transform(element))
    }

    for (let i = start; i < end; i++) {
        const element = array[i]
        const key = transform(element)
        if (keys.has(key)) {
            continue
        }
        keys.add(key)
        if (other.has(key)) {
            yield element
        }
    }

}

function* generateInvert<K, V>(span: Span<[K, V]>): SequenceIterator<[V, K]> {
    const {array, start, end} = span
    for (let i = start; i < end; i++) {
        const pair = array[i]
        yield [pair[1], pair[0]]
    }
}

function* generateMap<T, O>(span: Span<T>, transform: Transform<T, O>): SequenceIterator<O> {
    const {array, start, end} = span
    for (let i = start; i < end; i++) {
        yield transform(array[i])
    }
}

function* generatePrepend<T>(span: Span<T>, elements: Sequence<T>): SequenceIterator<T> {
    yield* elements
    yield* span
}

function* generatePermute<T>(span: Span<T>): SequenceIterator<T[]> {
    const length = span.count()
    const counts = new Array(length).fill(0)

    const permutation = span.toArray()

    let i = 0

    yield span.toArray()

    while (i < length) {
        if (counts[i] >= i) {
            counts[i++] = 0
            continue
        }

        const j = i % 2 && counts[i]

        const temporary = permutation[i]
        permutation[i] = permutation[j]
        permutation[j] = temporary

        yield permutation.slice()

        ++counts[i]

        i = 1
    }
}

function* generateRemove<T>(span: Span<T>, predicate: Predicate<T>, count: number): SequenceIterator<T> {
    const {array, start, end} = span

    let removed = 0
    let i = start

    if (count > 0) {
        while (i < end) {
            const element = array[i++]
            if (predicate(element)) {
                if (++removed >= count) {
                    break
                }
            } else {
                yield element
            }
        }
    }

    while (i < end) {
        yield array[i++]
    }
}

function* generateRemoveLast<T>(span: Span<T>, predicate: Predicate<T>, count: number): SequenceIterator<T> {
    const {array, start, end} = span
    const back = []

    let removed = 0
    let i

    for (i = end - 1; i >= start && removed < count; i--) {
        const element = array[i]
        if (predicate(element)) {
            removed++
        } else {
            back.push(element)
        }
    }

    for (let j = start; j <= i; j++) {
        yield array[j]
    }

    for (let j = back.length - 1; j >= 0; j--) {
        yield back[j]
    }
}

function* generateRepeat<T>(span: Span<T>, count: number | undefined): SequenceIterator<T> {
    if (count === undefined) {
        while (true) {
            yield* span
        }
    }
    count = Math.max(count, 0)
    for (let i = 0; i < count; i++) {
        yield* span
    }
}

function* generateReplace<T, R>(span: Span<T>, predicate: Predicate<T>, replacement: R,
                                count: number): SequenceIterator<T | R> {
    const {array, start, end} = span

    let i
    let replaced = 0

    for (i = start; i < end && replaced < count; i++) {
        const element = array[i]
        if (predicate(element)) {
            yield replacement
            replaced++
        } else {
            yield element
        }
    }

    while (i < end) {
        yield array[i++]
    }
}

function* generateReplaceLast<T, R>(span: Span<T>, predicate: Predicate<T>, replacement: R,
                                    count: number): SequenceIterator<T | R> {
    const {array, start, end} = span
    const back = []

    let replaced = 0
    let i

    for (i = end - 1; i >= start && replaced < count; i--) {
        const element = array[i]
        if (predicate(element)) {
            back.push(replacement)
            replaced++
        } else {
            back.push(element)
        }
    }

    for (let j = start; j <= i; j++) {
        yield array[j]
    }

    for (let j = back.length - 1; j >= 0; j--) {
        yield back[j]
    }
}

function* generateUnion<T, K>(span: Span<T>, sequence: Sequence<T>,  
                              transform: Transform<T, K>): SequenceIterator<T> {
    const {array, start, end} = span
    const seen = new Set<K>()

    for (let i = start; i < end; i++) {
        const element = array[i]
        const key = transform(element)
        if (seen.has(key)) {
            continue
        }
        yield element
        seen.add(key)
    }

    for (const element of sequence) {
        const key = transform(element)
        if (seen.has(key)) {
            continue
        }
        yield element
        seen.add(key)
    }
}

function* generateUnique<T, K>(span: Span<T>, transform: Transform<T, K>): SequenceIterator<T> {
    const {array, start, end} = span
    const seen = new Set<K>()
    for (let i = start; i < end; i++) {
        const element = array[i]
        const key = transform(element)
        if (seen.has(key)) {
            continue
        }
        yield element
        seen.add(key)
    }
}

function* generateZip<T, V>(span: Span<T>, values: Sequence<V>): SequenceIterator<[T, V]> {
    const {array, start, end} = span
    let i = start
    for (const value of values) {
        if (i >= end) {
            break
        }
        yield [array[i++], value]
    }
}

function findExtreme<T>(span: Span<T>, transform: Transform<T, number>, opposite: number,
                        comparator: PairPredicate<number>, errorMessage: string): T {
    if (span.none()) {
        throw new Error(errorMessage)
    }

    const {array, start, end} = span

    let extreme = opposite
    let result: T
    let found = false
    for (let i = start; i < end; i++) {
        const element = array[i]
        const value = transform(element)
        if (comparator(value, extreme)) {
            extreme = value
            result = element
            found = true
        }
    }

    return result!!
}