/**
* @since 1.0.0
*/
import type { Either } from "@effect/data/Either"
import * as Equal from "@effect/data/Equal"
import * as Equivalence from "@effect/data/Equivalence"
import { dual, identity, pipe } from "@effect/data/Function"
import * as Hash from "@effect/data/Hash"
import type { TypeLambda } from "@effect/data/HKT"
import { type Inspectable, NodeInspectSymbol, toJSON, toString } from "@effect/data/Inspectable"
import type { NonEmptyIterable } from "@effect/data/NonEmptyIterable"
import type { Option } from "@effect/data/Option"
import * as O from "@effect/data/Option"
import * as Order from "@effect/data/Order"
import type { Pipeable } from "@effect/data/Pipeable"
import { pipeArguments } from "@effect/data/Pipeable"
import type { Predicate, Refinement } from "@effect/data/Predicate"
import { isObject } from "@effect/data/Predicate"
import * as RA from "@effect/data/ReadonlyArray"
import type { NonEmptyReadonlyArray } from "@effect/data/ReadonlyArray"
const TypeId: unique symbol = Symbol.for("@effect/data/Chunk") as TypeId
/**
* @category symbol
* @since 1.0.0
*/
export type TypeId = typeof TypeId
/**
* @category models
* @since 1.0.0
*/
export interface Chunk extends Iterable, Equal.Equal, Pipeable, Inspectable {
readonly [TypeId]: {
readonly _A: (_: never) => A
}
readonly length: number
/** @internal */
right: Chunk
/** @internal */
left: Chunk
/** @internal */
backing: Backing
/** @internal */
depth: number
}
/**
* @category model
* @since 1.0.0
*/
export interface NonEmptyChunk extends Chunk, NonEmptyIterable {}
/**
* @category type lambdas
* @since 1.0.0
*/
export interface ChunkTypeLambda extends TypeLambda {
readonly type: Chunk
}
type Backing =
| IArray
| IConcat
| ISingleton
| IEmpty
| ISlice
interface IArray {
readonly _tag: "IArray"
readonly array: ReadonlyArray
}
interface IConcat {
readonly _tag: "IConcat"
readonly left: Chunk
readonly right: Chunk
}
interface ISingleton {
readonly _tag: "ISingleton"
readonly a: A
}
interface IEmpty {
readonly _tag: "IEmpty"
}
interface ISlice {
readonly _tag: "ISlice"
readonly chunk: Chunk
readonly offset: number
readonly length: number
}
function copy(
src: ReadonlyArray,
srcPos: number,
dest: Array,
destPos: number,
len: number
) {
for (let i = srcPos; i < Math.min(src.length, srcPos + len); i++) {
dest[destPos + i - srcPos] = src[i]!
}
return dest
}
const emptyArray: ReadonlyArray = []
/**
* Compares the two chunks of equal length using the specified function
*
* @category equivalence
* @since 1.0.0
*/
export const getEquivalence = (isEquivalent: Equivalence.Equivalence): Equivalence.Equivalence> =>
Equivalence.make((self, that) => toReadonlyArray(self).every((value, i) => isEquivalent(value, unsafeGet(that, i))))
const _equivalence = getEquivalence(Equal.equals)
const ChunkProto: Omit, "backing" | "depth" | "left" | "length" | "right"> = {
[TypeId]: {
_A: (_: never) => _
},
toString(this: Chunk) {
return toString(this.toJSON())
},
toJSON(this: Chunk) {
return {
_id: "Chunk",
values: toReadonlyArray(this).map(toJSON)
}
},
[NodeInspectSymbol](this: Chunk) {
return this.toJSON()
},
[Equal.symbol](this: Chunk, that: unknown): boolean {
return isChunk(that) && _equivalence(this, that)
},
[Hash.symbol](this: Chunk): number {
return Hash.array(toReadonlyArray(this))
},
[Symbol.iterator](this: Chunk): Iterator {
switch (this.backing._tag) {
case "IArray": {
return this.backing.array[Symbol.iterator]()
}
case "IEmpty": {
return emptyArray[Symbol.iterator]()
}
default: {
return toReadonlyArray(this)[Symbol.iterator]()
}
}
},
pipe(this: Chunk) {
return pipeArguments(this, arguments)
}
}
const makeChunk = (backing: Backing): Chunk => {
const chunk = Object.create(ChunkProto)
chunk.backing = backing
switch (backing._tag) {
case "IEmpty": {
chunk.length = 0
chunk.depth = 0
chunk.left = this
chunk.right = this
break
}
case "IConcat": {
chunk.length = backing.left.length + backing.right.length
chunk.depth = 1 + Math.max(backing.left.depth, backing.right.depth)
chunk.left = backing.left
chunk.right = backing.right
break
}
case "IArray": {
chunk.length = backing.array.length
chunk.depth = 0
chunk.left = _empty
chunk.right = _empty
break
}
case "ISingleton": {
chunk.length = 1
chunk.depth = 0
chunk.left = _empty
chunk.right = _empty
break
}
case "ISlice": {
chunk.length = backing.length
chunk.depth = backing.chunk.depth + 1
chunk.left = _empty
chunk.right = _empty
break
}
}
return chunk
}
/**
* Checks if `u` is a `Chunk`
*
* @category constructors
* @since 1.0.0
*/
export const isChunk: {
(u: Iterable): u is Chunk
(u: unknown): u is Chunk
} = (u: unknown): u is Chunk => isObject(u) && TypeId in u
const _empty = makeChunk({ _tag: "IEmpty" })
/**
* @category constructors
* @since 1.0.0
*/
export const empty: () => Chunk = () => _empty
/**
* Builds a `NonEmptyChunk` from an non-empty collection of elements.
*
* @category constructors
* @since 1.0.0
*/
export const make = ]>(
...as: As
): NonEmptyChunk => as.length === 1 ? of(as[0]) : unsafeFromNonEmptyArray(as)
/**
* Builds a `NonEmptyChunk` from a single element.
*
* @category constructors
* @since 1.0.0
*/
export const of = (a: A): NonEmptyChunk => makeChunk({ _tag: "ISingleton", a }) as any
/**
* Converts from an `Iterable`
*
* @category conversions
* @since 1.0.0
*/
export const fromIterable = (self: Iterable): Chunk =>
isChunk(self) ? self : makeChunk({ _tag: "IArray", array: RA.fromIterable(self) })
const copyToArray = (self: Chunk, array: Array, initial: number): void => {
switch (self.backing._tag) {
case "IArray": {
copy(self.backing.array, 0, array, initial, self.length)
break
}
case "IConcat": {
copyToArray(self.left, array, initial)
copyToArray(self.right, array, initial + self.left.length)
break
}
case "ISingleton": {
array[initial] = self.backing.a
break
}
case "ISlice": {
let i = 0
let j = initial
while (i < self.length) {
array[j] = unsafeGet(self, i)
i += 1
j += 1
}
break
}
}
}
/**
* Converts the specified `Chunk` to a `ReadonlyArray`.
*
* @category conversions
* @since 1.0.0
*/
export const toReadonlyArray = (self: Chunk): ReadonlyArray => {
switch (self.backing._tag) {
case "IEmpty": {
return emptyArray
}
case "IArray": {
return self.backing.array
}
default: {
const arr = new Array(self.length)
copyToArray(self, arr, 0)
self.backing = {
_tag: "IArray",
array: arr
}
self.left = _empty
self.right = _empty
self.depth = 0
return arr
}
}
}
/**
* @since 1.0.0
* @category elements
*/
export const reverse = (self: Chunk): Chunk => {
switch (self.backing._tag) {
case "IEmpty":
case "ISingleton":
return self
case "IArray": {
return makeChunk({ _tag: "IArray", array: RA.reverse(self.backing.array) })
}
case "IConcat": {
return makeChunk({ _tag: "IConcat", left: reverse(self.backing.right), right: reverse(self.backing.left) })
}
case "ISlice":
return unsafeFromArray(RA.reverse(toReadonlyArray(self)))
}
}
/**
* This function provides a safe way to read a value at a particular index from a `Chunk`.
*
* @category elements
* @since 1.0.0
*/
export const get: {
(index: number): (self: Chunk) => Option
(self: Chunk, index: number): Option
} = dual(
2,
(self: Chunk, index: number): Option =>
index < 0 || index >= self.length ? O.none() : O.some(unsafeGet(self, index))
)
/**
* Wraps an array into a chunk without copying, unsafe on mutable arrays
*
* @since 1.0.0
* @category unsafe
*/
export const unsafeFromArray = (self: ReadonlyArray): Chunk => makeChunk({ _tag: "IArray", array: self })
/**
* Wraps an array into a chunk without copying, unsafe on mutable arrays
*
* @since 1.0.0
* @category unsafe
*/
export const unsafeFromNonEmptyArray = (self: NonEmptyReadonlyArray): NonEmptyChunk =>
unsafeFromArray(self) as any
/**
* Gets an element unsafely, will throw on out of bounds
*
* @since 1.0.0
* @category unsafe
*/
export const unsafeGet: {
(index: number): (self: Chunk) => A
(self: Chunk, index: number): A
} = dual(2, (self: Chunk, index: number): A => {
switch (self.backing._tag) {
case "IEmpty": {
throw new Error(`Index out of bounds`)
}
case "ISingleton": {
if (index !== 0) {
throw new Error(`Index out of bounds`)
}
return self.backing.a
}
case "IArray": {
if (index >= self.length || index < 0) {
throw new Error(`Index out of bounds`)
}
return self.backing.array[index]!
}
case "IConcat": {
return index < self.left.length
? unsafeGet(self.left, index)
: unsafeGet(self.right, index - self.left.length)
}
case "ISlice": {
return unsafeGet(self.backing.chunk, index + self.backing.offset)
}
}
})
/**
* Appends the specified element to the end of the `Chunk`.
*
* @category concatenating
* @since 1.0.0
*/
export const append: {
(a: A2): (self: Chunk) => NonEmptyChunk
(self: Chunk, a: A2): NonEmptyChunk
} = dual(2, (self: Chunk, a: A2): NonEmptyChunk => appendAllNonEmpty(self, of(a)))
/**
* Prepend an element to the front of a `Chunk`, creating a new `NonEmptyChunk`.
*
* @category concatenating
* @since 1.0.0
*/
export const prepend: {
(elem: B): (self: Chunk) => NonEmptyChunk
(self: Chunk, elem: B): NonEmptyChunk
} = dual(2, (self: Chunk, elem: B): NonEmptyChunk => appendAllNonEmpty(of(elem), self))
/**
* Takes the first up to `n` elements from the chunk
*
* @since 1.0.0
*/
export const take: {
(n: number): (self: Chunk) => Chunk
(self: Chunk, n: number): Chunk
} = dual(2, (self: Chunk, n: number): Chunk => {
if (n <= 0) {
return _empty
} else if (n >= self.length) {
return self
} else {
switch (self.backing._tag) {
case "ISlice": {
return makeChunk({
_tag: "ISlice",
chunk: self.backing.chunk,
length: n,
offset: self.backing.offset
})
}
case "IConcat": {
if (n > self.left.length) {
return makeChunk({
_tag: "IConcat",
left: self.left,
right: take(self.right, n - self.left.length)
})
}
return take(self.left, n)
}
default: {
return makeChunk({
_tag: "ISlice",
chunk: self,
offset: 0,
length: n
})
}
}
}
})
/**
* Drops the first up to `n` elements from the chunk
*
* @since 1.0.0
*/
export const drop: {
(n: number): (self: Chunk) => Chunk
(self: Chunk, n: number): Chunk
} = dual(2, (self: Chunk, n: number): Chunk => {
if (n <= 0) {
return self
} else if (n >= self.length) {
return _empty
} else {
switch (self.backing._tag) {
case "ISlice": {
return makeChunk({
_tag: "ISlice",
chunk: self.backing.chunk,
offset: self.backing.offset + n,
length: self.backing.length - n
})
}
case "IConcat": {
if (n > self.left.length) {
return drop(self.right, n - self.left.length)
}
return makeChunk({
_tag: "IConcat",
left: drop(self.left, n),
right: self.right
})
}
default: {
return makeChunk({
_tag: "ISlice",
chunk: self,
offset: n,
length: self.length - n
})
}
}
}
})
/**
* Drops the last `n` elements.
*
* @since 1.0.0
*/
export const dropRight: {
(n: number): (self: Chunk) => Chunk
(self: Chunk, n: number): Chunk
} = dual(2, (self: Chunk, n: number): Chunk => take(self, Math.max(0, self.length - n)))
/**
* Drops all elements so long as the predicate returns true.
*
* @since 1.0.0
*/
export const dropWhile: {
(f: (a: A) => boolean): (self: Chunk) => Chunk
(self: Chunk, f: (a: A) => boolean): Chunk
} = dual(2, (self: Chunk, f: (a: A) => boolean): Chunk => {
const arr = toReadonlyArray(self)
const len = arr.length
let i = 0
while (i < len && f(arr[i]!)) {
i++
}
return drop(self, i)
})
/**
* @category concatenating
* @since 1.0.0
*/
export const prependAll: {
(that: Chunk): (self: Chunk) => Chunk
(self: Chunk, that: Chunk): Chunk
} = dual(2, (self: NonEmptyChunk, that: Chunk): Chunk => appendAll(that, self))
/**
* @category concatenating
* @since 1.0.0
*/
export const prependAllNonEmpty: {
(that: NonEmptyChunk): (self: Chunk) => NonEmptyChunk
(that: Chunk): (self: NonEmptyChunk) => NonEmptyChunk
(self: Chunk, that: NonEmptyChunk): NonEmptyChunk
(self: NonEmptyChunk, that: Chunk): NonEmptyChunk
} = dual(2, (self: NonEmptyChunk, that: Chunk): NonEmptyChunk => prependAll(self, that) as any)
/**
* Concatenates the two chunks
*
* @category concatenating
* @since 1.0.0
*/
export const appendAll: {
(that: Chunk): (self: Chunk) => Chunk
(self: Chunk, that: Chunk): Chunk
} = dual(2, (self: Chunk, that: Chunk): Chunk => {
if (self.backing._tag === "IEmpty") {
return that
}
if (that.backing._tag === "IEmpty") {
return self
}
const diff = that.depth - self.depth
if (Math.abs(diff) <= 1) {
return makeChunk({ _tag: "IConcat", left: self, right: that })
} else if (diff < -1) {
if (self.left.depth >= self.right.depth) {
const nr = appendAll(self.right, that)
return makeChunk({ _tag: "IConcat", left: self.left, right: nr })
} else {
const nrr = appendAll(self.right.right, that)
if (nrr.depth === self.depth - 3) {
const nr = makeChunk({ _tag: "IConcat", left: self.right.left, right: nrr })
return makeChunk({ _tag: "IConcat", left: self.left, right: nr })
} else {
const nl = makeChunk({ _tag: "IConcat", left: self.left, right: self.right.left })
return makeChunk({ _tag: "IConcat", left: nl, right: nrr })
}
}
} else {
if (that.right.depth >= that.left.depth) {
const nl = appendAll(self, that.left)
return makeChunk({ _tag: "IConcat", left: nl, right: that.right })
} else {
const nll = appendAll(self, that.left.left)
if (nll.depth === that.depth - 3) {
const nl = makeChunk({ _tag: "IConcat", left: nll, right: that.left.right })
return makeChunk({ _tag: "IConcat", left: nl, right: that.right })
} else {
const nr = makeChunk({ _tag: "IConcat", left: that.left.right, right: that.right })
return makeChunk({ _tag: "IConcat", left: nll, right: nr })
}
}
}
})
/**
* @category concatenating
* @since 1.0.0
*/
export const appendAllNonEmpty: {
(that: NonEmptyChunk): (self: Chunk) => NonEmptyChunk
(that: Chunk): (self: NonEmptyChunk) => NonEmptyChunk
(self: Chunk, that: NonEmptyChunk): NonEmptyChunk
(self: NonEmptyChunk, that: Chunk): NonEmptyChunk
} = dual(2, (self: NonEmptyChunk, that: Chunk): NonEmptyChunk => appendAll(self, that) as any)
/**
* Returns a filtered and mapped subset of the elements.
*
* @since 1.0.0
* @category filtering
*/
export const filterMap: {
(f: (a: A, i: number) => Option): (self: Chunk) => Chunk
(self: Chunk, f: (a: A, i: number) => Option): Chunk
} = dual(
2,
(self: Chunk, f: (a: A, i: number) => Option): Chunk => unsafeFromArray(RA.filterMap(self, f))
)
/**
* Returns a filtered and mapped subset of the elements.
*
* @since 1.0.0
* @category filtering
*/
export const filter: {
(refinement: Refinement): (self: Chunk) => Chunk
(predicate: Predicate): (self: Chunk) => Chunk
(self: Chunk, refinement: Refinement): Chunk
(self: Chunk, predicate: Predicate): Chunk
} = dual(
2,
(self: Chunk, predicate: Predicate) =>
unsafeFromArray(RA.filterMap(self, O.liftPredicate(predicate)))
)
/**
* Transforms all elements of the chunk for as long as the specified function returns some value
*
* @since 1.0.0
* @category filtering
*/
export const filterMapWhile: {
(f: (a: A) => Option): (self: Chunk) => Chunk
(self: Chunk, f: (a: A) => Option): Chunk
} = dual(2, (self: Chunk, f: (a: A) => Option) => unsafeFromArray(RA.filterMapWhile(self, f)))
/**
* Filter out optional values
*
* @since 1.0.0
* @category filtering
*/
export const compact = (self: Chunk>): Chunk => filterMap(self, identity)
/**
* Returns a chunk with the elements mapped by the specified function.
*
* @since 1.0.0
* @category sequencing
*/
export const flatMap: {
(f: (a: A, i: number) => Chunk): (self: Chunk) => Chunk
(self: Chunk, f: (a: A, i: number) => Chunk): Chunk
} = dual(2, (self: Chunk, f: (a: A, i: number) => Chunk) => {
if (self.backing._tag === "ISingleton") {
return f(self.backing.a, 0)
}
let out: Chunk = _empty
let i = 0
for (const k of self) {
out = appendAll(out, f(k, i++))
}
return out
})
/**
* @category sequencing
* @since 1.0.0
*/
export const flatMapNonEmpty: {
(f: (a: A, i: number) => NonEmptyChunk): (self: NonEmptyChunk) => NonEmptyChunk
(self: NonEmptyChunk, f: (a: A, i: number) => NonEmptyChunk): NonEmptyChunk
} = flatMap as any
/**
* Applies the specified function to each element of the `List`.
*
* @since 1.0.0
* @category combinators
*/
export const forEach: {
(f: (a: A) => B): (self: Chunk) => void
(self: Chunk, f: (a: A) => B): void
} = dual(2, (self: Chunk, f: (a: A) => B): void => toReadonlyArray(self).forEach(f))
/**
* Flattens a chunk of chunks into a single chunk by concatenating all chunks.
*
* @since 1.0.0
* @category sequencing
*/
export const flatten: (self: Chunk>) => Chunk = flatMap(identity)
/**
* @category sequencing
* @since 1.0.0
*/
export const flattenNonEmpty: (
self: NonEmptyChunk>
) => NonEmptyChunk = flatMapNonEmpty(identity)
/**
* Groups elements in chunks of up to `n` elements.
*
* @since 1.0.0
* @category elements
*/
export const chunksOf: {
(n: number): (self: Chunk) => Chunk>
(self: Chunk, n: number): Chunk>
} = dual(2, (self: Chunk, n: number) => {
const gr: Array> = []
let current: Array = []
toReadonlyArray(self).forEach((a) => {
current.push(a)
if (current.length >= n) {
gr.push(unsafeFromArray(current))
current = []
}
})
if (current.length > 0) {
gr.push(unsafeFromArray(current))
}
return unsafeFromArray(gr)
})
/**
* Creates a Chunk of unique values that are included in all given Chunks.
*
* The order and references of result values are determined by the Chunk.
*
* @since 1.0.0
* @category elements
*/
export const intersection: {
(that: Chunk): (self: Chunk) => Chunk
(self: Chunk, that: Chunk): Chunk
} = dual(
2,
(self: Chunk, that: Chunk): Chunk =>
unsafeFromArray(RA.intersection(toReadonlyArray(self), toReadonlyArray(that)))
)
/**
* Determines if the chunk is empty.
*
* @since 1.0.0
* @category elements
*/
export const isEmpty = (self: Chunk): boolean => self.length === 0
/**
* Determines if the chunk is not empty.
*
* @since 1.0.0
* @category elements
*/
export const isNonEmpty = (self: Chunk): self is NonEmptyChunk => self.length > 0
/**
* Returns the first element of this chunk if it exists.
*
* @since 1.0.0
* @category elements
*/
export const head: (self: Chunk) => Option = get(0)
/**
* Returns the first element of this chunk.
*
* @since 1.0.0
* @category unsafe
*/
export const unsafeHead = (self: Chunk): A => unsafeGet(self, 0)
/**
* Returns the first element of this non empty chunk.
*
* @since 1.0.0
* @category elements
*/
export const headNonEmpty: (self: NonEmptyChunk) => A = unsafeHead
/**
* Returns the last element of this chunk if it exists.
*
* @since 1.0.0
* @category elements
*/
export const last = (self: Chunk): Option => get(self, self.length - 1)
/**
* Returns the last element of this chunk.
*
* @since 1.0.0
* @category unsafe
*/
export const unsafeLast = (self: Chunk): A => unsafeGet(self, self.length - 1)
/**
* Returns an effect whose success is mapped by the specified f function.
*
* @since 1.0.0
* @category mapping
*/
export const map: {
(f: (a: A, i: number) => B): (self: Chunk) => Chunk
(self: Chunk, f: (a: A, i: number) => B): Chunk
} = dual(2, (self: Chunk, f: (a: A, i: number) => B): Chunk =>
self.backing._tag === "ISingleton" ?
of(f(self.backing.a, 0)) :
unsafeFromArray(pipe(toReadonlyArray(self), RA.map((a, i) => f(a, i)))))
/**
* Statefully maps over the chunk, producing new elements of type `B`.
*
* @since 1.0.0
* @category folding
*/
export const mapAccum: {
(s: S, f: (s: S, a: A) => readonly [S, B]): (self: Chunk) => [S, Chunk]
(self: Chunk, s: S, f: (s: S, a: A) => readonly [S, B]): [S, Chunk]
} = dual(3, (self: Chunk, s: S, f: (s: S, a: A) => readonly [S, B]): [S, Chunk] => {
const [s1, as] = RA.mapAccum(self, s, f)
return [s1, unsafeFromArray(as)]
})
/**
* Separate elements based on a predicate that also exposes the index of the element.
*
* @category filtering
* @since 1.0.0
*/
export const partition: {
(refinement: Refinement): (self: Chunk) => [Chunk>, Chunk]
(predicate: (a: A) => boolean): (self: Chunk) => [Chunk, Chunk]
(self: Chunk, refinement: Refinement): [Chunk>, Chunk]
(self: Chunk, predicate: (a: A) => boolean): [Chunk, Chunk]
} = dual(
2,
(self: Chunk, predicate: (a: A) => boolean): [Chunk, Chunk] =>
pipe(
RA.partition(toReadonlyArray(self), predicate),
([l, r]) => [unsafeFromArray(l), unsafeFromArray(r)]
)
)
/**
* Partitions the elements of this chunk into two chunks using f.
*
* @category filtering
* @since 1.0.0
*/
export const partitionMap: {
(f: (a: A) => Either): (self: Chunk) => [Chunk, Chunk]
(self: Chunk, f: (a: A) => Either): [Chunk, Chunk]
} = dual(2, (self: Chunk, f: (a: A) => Either): [Chunk, Chunk] =>
pipe(
RA.partitionMap(toReadonlyArray(self), f),
([l, r]) => [unsafeFromArray(l), unsafeFromArray(r)]
))
/**
* Partitions the elements of this chunk into two chunks.
*
* @category filtering
* @since 1.0.0
*/
export const separate = (self: Chunk>): [Chunk, Chunk] =>
pipe(
RA.separate(toReadonlyArray(self)),
([l, r]) => [unsafeFromArray(l), unsafeFromArray(r)]
)
/**
* Retireves the size of the chunk
*
* @since 1.0.0
* @category elements
*/
export const size = (self: Chunk): number => self.length
/**
* Sort the elements of a Chunk in increasing order, creating a new Chunk.
*
* @since 1.0.0
* @category elements
*/
export const sort: {
(O: Order.Order): (self: Chunk) => Chunk
(self: Chunk, O: Order.Order): Chunk