Array

`Array`

Canonical source: protos/lib/collections/Array.protos at locked revision e99b712ecf658a527b1fe82c8beba2c1286d8dc9.
// THE LICENSED WORK IS PROVIDED UNDER THE TERMS OF THE ADAPTIVE PUBLIC LICENSE
// ("LICENSE") AS FIRST COMPLETED BY: Guillermo Adrián Molina. ANY USE, PUBLIC
// DISPLAY, PUBLIC PERFORMANCE, REPRODUCTION OR DISTRIBUTION OF, OR PREPARATION OF
// DERIVATIVE WORKS BASED ON, THE LICENSED WORK CONSTITUTES RECIPIENT'S ACCEPTANCE
// OF THIS LICENSE AND ITS TERMS, WHETHER OR NOT SUCH RECIPIENT READS THE TERMS OF
// THE LICENSE. "LICENSED WORK" AND "RECIPIENT" ARE DEFINED IN THE LICENSE. A COPY
// OF THE LICENSE IS LOCATED IN THE TEXT FILE ENTITLED "LICENSE.TXT" ACCOMPANYING
// THE CONTENTS OF THIS FILE. IF A COPY OF THE LICENSE DOES NOT ACCOMPANY THIS
// FILE, A COPY OF THE LICENSE MAY ALSO BE OBTAINED AT THE FOLLOWING WEB SITE:
// https://github.com/guillermomolina/protos
//
// Software distributed under the License is distributed on an "AS IS" basis,
// WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License for
// the specific language governing rights and limitations under the License.

//! Sequential and isolated-parallel algorithms over ordinary Arrays.

/// Answers a fresh Array whose element `i` is `transform(array[i])`, applied to a
/// snapshot of `array` in ascending index order.
map: (array, transform) => {
    snapshot: Array(...array)
    result: Array(...snapshot)
    index: 0
    snapshot.each((element) => {
        result[index] = transform(element)
        index = index + 1
    })
    result
}

/// Answers a fresh Array of the elements of a snapshot of `array` for which
/// `predicate(element)` answers `true`, keeping source order. A result other
/// than canonical `true` or `false` signals `InvalidPredicateResult`.
filter: (array, predicate) => {
    snapshot: Array(...array)

    filterRange: (start, end) => {
        length: end - start
        result: null

        (length == 0).ifTrue(() => {
            result = Array()
        })

        (length == 1).ifTrue(() => {
            element: snapshot[start]
            decision: predicate(element)

            (decision === true).ifTrue(() => {
                result = Array(element)
            })
            (decision === true).ifFalse(() => {
                (decision === false).ifTrue(() => {
                    result = Array()
                })
                (decision === false).ifFalse(() => {
                    InvalidPredicateResult().signal()
                })
            })
        })

        (length > 1).ifTrue(() => {
            middle: start + length.div(2)
            left: filterRange(start, middle)
            right: filterRange(middle, end)
            result = Array(...left, ...right)
        })

        result
    }

    filterRange(0, snapshot.size())
}

/// Answers the lowest index of a snapshot of `array` whose element satisfies
/// `predicate(element)`, or `null` when none does. Elements are tested in
/// ascending order; a result other than canonical `true` or `false` signals
/// `InvalidPredicateResult`.
findIndex: (array, predicate) => {
    snapshot: Array(...array)
    index: 0

    snapshot.each((element) => {
        decision: predicate(element)

        (decision === true).ifTrue(() => {
            ^index
        })
        (decision === false).ifFalse(() => {
            InvalidPredicateResult().signal()
        })

        index = index + 1
    })

    null
}

/// Folds a snapshot of `array` left to right with `reducer(accumulator, element)`.
/// An optional single `initial` value seeds the fold; without one, the first
/// element does, and an empty Array answers `null`. More than one initial
/// value signals an Error.
reduce: (array, reducer, ...initial) => {
    snapshot: Array(...array)
    initialSize: initial.size()

    (initialSize > 1).ifTrue(() => {
        Error().signal()
    })

    snapshotSize: snapshot.size()
    accumulator: null

    (initialSize == 1).ifTrue(() => {
        accumulator = initial[0]
    })

    (initialSize == 0).ifTrue(() => {
        (snapshotSize == 0).ifTrue(() => {
            ^null
        })
        accumulator = snapshot[0]
    })

    foldRange: (start, end) => {
        length: end - start

        (length == 1).ifTrue(() => {
            accumulator = reducer(accumulator, snapshot[start])
        })

        (length > 1).ifTrue(() => {
            middle: start + length.div(2)
            foldRange(start, middle)
            foldRange(middle, end)
        })
    }

    foldRange(1 - initialSize, snapshotSize)
    accumulator
}

/// Answers a fresh Array with the elements of a snapshot of `array` stably sorted
/// by `less(left, right)`. A comparator result other than canonical `true` or
/// `false` signals `InvalidComparatorResult`, and two elements each less than
/// the other signal `InvalidComparatorOrder`. The source is not mutated.
sort: (array, less) => {
    snapshot: Array(...array)

    merge: (left, right) => {
        result: Array(...left, ...right)
        leftSize: left.size()
        rightSize: right.size()
        leftIndex: 0
        rightIndex: 0
        mergeRange: (start, end) => {
            length: end - start

            (length == 1).ifTrue(() => {
                leftDone: leftIndex == leftSize
                rightDone: rightIndex == rightSize

                leftDone.ifTrue(() => {
                    result[start] = right[rightIndex]
                    rightIndex = rightIndex + 1
                })

                leftDone.ifFalse(() => {
                    rightDone.ifTrue(() => {
                        result[start] = left[leftIndex]
                        leftIndex = leftIndex + 1
                    })

                    rightDone.ifFalse(() => {
                        leftValue: left[leftIndex]
                        rightValue: right[rightIndex]
                        lr: less(leftValue, rightValue)

                        (lr === true).ifFalse(() => {
                            (lr === false).ifFalse(() => {
                                InvalidComparatorResult().signal()
                            })
                        })

                        rl: less(rightValue, leftValue)

                        (rl === true).ifFalse(() => {
                            (rl === false).ifFalse(() => {
                                InvalidComparatorResult().signal()
                            })
                        })

                        (lr === true).ifTrue(() => {
                            (rl === true).ifTrue(() => {
                                InvalidComparatorOrder().signal()
                            })
                            result[start] = leftValue
                            leftIndex = leftIndex + 1
                        })

                        (lr === false).ifTrue(() => {
                            (rl === true).ifTrue(() => {
                                result[start] = rightValue
                                rightIndex = rightIndex + 1
                            })
                            (rl === false).ifTrue(() => {
                                result[start] = leftValue
                                leftIndex = leftIndex + 1
                            })
                        })
                    })
                })
            })

            (length > 1).ifTrue(() => {
                middle: start + length.div(2)
                mergeRange(start, middle)
                mergeRange(middle, end)
            })

            null
        }

        mergeRange(0, result.size())
        result
    }

    sortRange: (start, end) => {
        length: end - start
        result: null

        (length == 0).ifTrue(() => {
            result = Array()
        })

        (length == 1).ifTrue(() => {
            result = Array(snapshot[start])
        })

        (length > 1).ifTrue(() => {
            middle: start + length.div(2)
            left: sortRange(start, middle)
            right: sortRange(middle, end)
            result = merge(left, right)
        })

        result
    }

    sortRange(0, snapshot.size())
}

// Parallel algorithms (D160): Standard Library policy composed only from the
// public isolated-parallel substrate (`Closure.parallel`, `Future`,
// `Future.all`, `ensure`). Every callback runs in isolated P, so it cannot
// capture caller state; explicit trailing `arguments` are the supported way to
// pass data to it, and they cross P exactly like the elements do.
//
// A non-empty call first submits P snapshots of the source elements, the
// callback, and the arguments. That synchronous submission is the input
// snapshot point and signals `NonParallelValue` before any Future is returned.
// Each logical callback invocation then runs in its own isolated P child owned
// by the operation's result Future. Cancelling the result Future cancels
// unfinished children. Failure selection never depends on worker timing.
//
// Arrays, Errors, and other results are always assembled in the caller domain
// and only cross P: P children run nothing but the user callback, and their
// raw outcomes are validated in the caller in ascending index order.

/// Answers a Future of a fresh Array whose element `i` is
/// `worker(array[i], arguments...)`, evaluated in isolated parallel execution.
/// Results keep source order; the lowest failing index supplies the failure.
parallelMap: (array, worker, ...arguments) => {
    snapshot: Array(...array)

    (snapshot.size() == 0).ifTrue(() => {
        ^(() => { Array() }).future()
    })

    input: ((bundle) => {
        bundle
    }).parallel(Array(snapshot, worker, arguments))

    apply: (element, callback, extra) => {
        callback(element, ...extra)
    }

    (() => {
        children: Array()

        (() => {
            parts: input.value()
            children = map(parts[0], (element) => {
                apply.parallel(element, parts[1], parts[2])
            })
            Future.all(...children).value()
        }).ensure(() => {
            input.cancel()
            children.each((child) => {
                child.cancel()
            })
        })
    }).future()
}

/// Answers a Future of a fresh Array of the elements for which
/// `predicate(element, arguments...)`, evaluated in isolated parallel
/// execution, answers `true`. Selection keeps source order. Outcomes are
/// examined in ascending index order, so the lowest index whose predicate
/// fails or answers something other than canonical `true` or `false`
/// (`InvalidPredicateResult`) supplies the failure.
parallelFilter: (array, predicate, ...arguments) => {
    snapshot: Array(...array)

    (snapshot.size() == 0).ifTrue(() => {
        ^(() => { Array() }).future()
    })

    input: ((bundle) => {
        bundle
    }).parallel(Array(snapshot, predicate, arguments))

    apply: (element, callback, extra) => {
        callback(element, ...extra)
    }

    (() => {
        children: Array()

        (() => {
            parts: input.value()
            children = map(parts[0], (element) => {
                apply.parallel(element, parts[1], parts[2])
            })
            index: 0
            filter(parts[0], (element) => {
                decision: children[index].value()
                index = index + 1
                decision
            })
        }).ensure(() => {
            input.cancel()
            children.each((child) => {
                child.cancel()
            })
        })
    }).future()
}

/// Answers a Future of the lowest index whose element satisfies
/// `predicate(element, arguments...)`, evaluated in isolated parallel
/// execution, or `null` when none does. Indexes are decided in ascending
/// logical order: a failure or non-Boolean result (`InvalidPredicateResult`)
/// at a lower index defeats a later match, and work at higher indexes is
/// cancelled once the outcome is decided.
parallelFindIndex: (array, predicate, ...arguments) => {
    snapshot: Array(...array)

    (snapshot.size() == 0).ifTrue(() => {
        ^(() => { null }).future()
    })

    input: ((bundle) => {
        bundle
    }).parallel(Array(snapshot, predicate, arguments))

    apply: (element, callback, extra) => {
        callback(element, ...extra)
    }

    (() => {
        children: Array()

        (() => {
            parts: input.value()
            children = map(parts[0], (element) => {
                apply.parallel(element, parts[1], parts[2])
            })
            findIndex(children, (child) => {
                child.value()
            })
        }).ensure(() => {
            input.cancel()
            children.each((child) => {
                child.cancel()
            })
        })
    }).future()
}

/// Answers a Future of the reduction of the elements with
/// `reducer(left, right, arguments...)`, or `null` for an empty Array. Each
/// round combines adjacent pairs (0,1), (2,3), ... left to right in isolated
/// parallel execution and carries an odd final value unchanged, so the
/// parenthesization is fixed and a non-associative reducer stays
/// deterministic. Within a round the leftmost failing pair supplies the
/// failure, and no later round starts after a failure.
parallelReduce: (array, reducer, ...arguments) => {
    snapshot: Array(...array)

    (snapshot.size() == 0).ifTrue(() => {
        ^(() => { null }).future()
    })

    // Groups one round's values into adjacent pairs, ending with a singleton
    // when the round has an odd final value.
    pairs: (values) => {
        size: values.size()

        pairRange: (start, end) => {
            length: end - start
            result: null

            (length == 1).ifTrue(() => {
                position: start * 2
                result = Array(Array(values[position]))
                (position + 1 < size).ifTrue(() => {
                    result = Array(Array(values[position], values[position + 1]))
                })
            })

            (length > 1).ifTrue(() => {
                middle: start + length.div(2)
                result = Array(...pairRange(start, middle), ...pairRange(middle, end))
            })

            result
        }

        pairRange(0, size.div(2) + size.mod(2))
    }

    combine: (pair, callback, ...extra) => {
        result: pair[0]

        (pair.size() == 2).ifTrue(() => {
            result = callback(pair[0], pair[1], ...extra)
        })

        result
    }

    round: parallelMap(pairs(snapshot), combine, reducer, ...arguments)

    (() => {
        (() => {
            values: round.value()

            (() => { values.size() > 1 }).whileTrue() {
                round = parallelMap(pairs(values), combine, reducer, ...arguments)
                values = round.value()
            }

            values[0]
        }).ensure(() => {
            round.cancel()
        })
    }).future()
}

/// Answers a Future of a fresh Array with the elements stably sorted by
/// `less(left, right, arguments...)`. The result, comparator invocation order,
/// and failures are exactly those of `sort` with the comparator
/// `(left, right) => less(left, right, arguments...)`, except that every
/// comparator invocation runs in its own isolated parallel execution. The
/// source Array is not mutated.
parallelSort: (array, less, ...arguments) => {
    snapshot: Array(...array)

    (snapshot.size() == 0).ifTrue(() => {
        ^(() => { Array() }).future()
    })

    input: ((bundle) => {
        bundle
    }).parallel(Array(snapshot, less, arguments))

    compare: (left, right, comparator, extra) => {
        comparator(left, right, ...extra)
    }

    (() => {
        parts: input.value()
        sort(parts[0], (left, right) => {
            compare.parallel(left, right, parts[1], parts[2]).value()
        })
    }).future()
}
← collections family · Standard-library source