Ready to transform that code for concurrency? OK, here we go:
//
// Created by Pierre Lebeaupin on 17/01/2021.
// Copyright © 2021 Pierre Lebeaupin. All rights reserved.
//
// Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
//
// 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
import Foundation;
@Sendable func exploreAdditionOfFloorAsync(_ l: inout [ReadyValueNonGCD],
_ composedCount: inout Int,
_ otherComposedCount: inout Int,
_ dispatcher: DispatcherAsync,
kind: Op) async {
guard otherComposedCount == 0 else {
return;
}
otherComposedCount = composedCount;
composedCount = 0;
await exploreAdditionOfRightNodeAsync(&l,
&composedCount,
&otherComposedCount,
dispatcher,
kind: kind,
skip: 0);
composedCount = otherComposedCount;
otherComposedCount = 0;
}
@Sendable func exploreAdditionOfRightNodeAsync(_ l: inout [ReadyValueNonGCD],
_ composedCount: inout Int,
_ otherComposedCount: inout Int,
_ dispatcher: DispatcherAsync,
kind: Op,
skip: Int) async {
var referenceDecomposedValue = [false: kind.neutralValue(), true: kind.neutralValue()];
// Siblings are the other right nodes on the same floor
// Downstream ones are those created while this one is active
var downstreamSiblingsRecruitmentSkip = Int(0); // placeholder
await dispatcher(&l,
&composedCount,
&otherComposedCount,
&referenceDecomposedValue,
&downstreamSiblingsRecruitmentSkip,
kind,
/* startingFrom: */ skip,
{ _ in return nil;});
}
/*
The point of iterate_possible_left_nodes() is to enumerate all the possible ways
to recruit candidates into the current operation, out of the pool of possible
candidates; that pool has been determined by explore_addition_of_right_node().
Obviously, the number of possibilities to pick a non-strict subset out of N
elements is 2 to the Nth power: each candidate in the pool can either be
recruited (1) or not (0) by this composition. Some of these possibilities are
invalid, of course, but we will explore the solution space that way.
By counting the possibilities from 00...0 to 11...1, we would in fact enumerate
all the possible recruitments for this composition. For practical reasons, we
will go backwards, from 11...1 to 00...0.
What we will do in practice is evaluating the first candidate, first recruting
it, which means we start with:
- 1x...x
then adjust the recruitment location, and delegate to ourselves. That way,
assuming this function performs it job for N-1, it will perform the job from
11...1 to 10...0; in other words, half the job for N. Then, we remove that
candidate from the composition, and ihnibit it from any future recruitment for
this composition; then we start over the loop.
The result is that the next candidate will be evaluated and hired at first and
recursive delegation will occur, resulting in these possibilities being
explored:
- 01...x
That is, from 011...1 to 010...0.
At the next loop iteration, the possibilities explored will start with 001, etc.
up until we realize we excluded all candidates; at which point the only
combination left is 00...0, which we don't need to explore at all. Unless, of
course, there were only one or two candidates in the pool, in which case that
test triggers even earlier.
There is additional accounting to avoid a downstream sibling (a composition on
the same floor) recovering candidates in a way that results in a composition
that we ourselves explored earlier, but that is the basic principle.
*/
@Sendable func iteratePossibleLeftNodesAsync(_ l: inout [ReadyValueNonGCD],
_ composedCount: inout Int,
_ otherComposedCount: inout Int,
_ decomposedValue: inout [Bool:UInt32],
_ downstreamSiblingsRecruitmentSkip: inout Int,
_ resultReceiver: @escaping @Sendable (_ result: String) -> Void,
_ startGoal: UInt32,
_ kind: Op,
_ startingFrom: Int,
_ walkOperands: @escaping @Sendable (_ action: (_ value: ReadyValueNonGCD, _ reverse: Bool) -> Void?) -> Void?,
_ dispatcher: DispatcherAsync) async {
let emptyComposition = (walkOperands({_,_ in return ();}) == nil)
/* Why that odd upper bound? If that conditional is true, emptyComposition is
true, which means we are recruiting the senior contribution. If by doing so we'd
end up skipping a composed contribution (the other part of the conditional means
there is at least one left) as a result of the initial if, otherComposedCount
would never reach 0 no matter how many siblings we'd add, and so we'd never be
able to close the floor anyway. So it'd be pointless to keep going. */
for candidateReverseOffset in
startingFrom ..< ((emptyComposition && (otherComposedCount > 0)) ? startingFrom+1 : (l.count - composedCount) ) {
if emptyComposition {
downstreamSiblingsRecruitmentSkip = candidateReverseOffset;
}
/* Note: new compositions are added at the end of the array, i.e. at the high offsets,
while primitives (if any left) will be at the low offsets. As a result, the candidates
to be recruited as a first priority are found at the high offsets first, though not so
high that we would end up recruiting from the same floor (forbidden). */
let rightChild = l.remove(at: (l.count - composedCount - 1) - candidateReverseOffset);
if let _ = rightChild.op {
otherComposedCount -= 1;
}
defer {
if let _ = rightChild.op {
otherComposedCount += 1;
}
l.insert(rightChild, at: ((l.count+1) - composedCount - 1) - candidateReverseOffset);
}
for phase in 0...1 {
let reverse = (phase == 1);
{ (_ valueComponent: inout UInt32) in
valueComponent = kind.combine(valueComponent, rightChild.value);
}(&decomposedValue[reverse]!);
defer {
{ (_ valueComponent: inout UInt32) in
valueComponent = kind.uncombine(valueComponent, rightChild.value);
}(&decomposedValue[reverse]!);
}
let selfNode = {@Sendable (_ action: (_ value: ReadyValueNonGCD, _ reverse: Bool) -> Void?) -> Void? in
return action(rightChild, reverse) ?? walkOperands(action);
};
await dispatcher(&l,
&composedCount,
&otherComposedCount,
&decomposedValue,
&downstreamSiblingsRecruitmentSkip,
kind,
/* startingFrom: */ candidateReverseOffset,
selfNode);
// close current composition
var num = 0;
guard (selfNode({_,_ in guard num == 0 else {return ();}; num += 1; return nil;}) != nil)
&& ( (kind == .additive) ? decomposedValue[false]! > decomposedValue[true]! :
((decomposedValue[false]! % decomposedValue[true]!) == 0) ) else {
continue;
}
let realizedValue = kind.uncombine(decomposedValue[false]!, decomposedValue[true]!);
let description = { @Sendable () -> String in
var current = "(";
var isFirst = true;
var numRev = 0;
selfNode({(_ value: ReadyValueNonGCD, _ freverse: Bool) -> Void? in
guard !freverse else {
numRev += 1;
return nil;
}
if !isFirst {
current += " ";
current += kind.rawValue;
current += " ";
}
isFirst = false;
current += value.description();
return nil; // keep going;
});
if numRev > 0 {
isFirst = true;
current += " ";
current += ((kind == .additive) ? "-" : "/");
current += " ";
if numRev > 1 {
current += "(";
}
selfNode({(_ value: ReadyValueNonGCD,
_ freverse: Bool) -> Void? in
guard freverse else {
return nil;
}
if !isFirst {
current += " ";
current += kind.rawValue;
current += " ";
}
isFirst = false;
current += value.description();
return nil;
});
if numRev > 1 {
current += ")";
}
}
current += ")";
return current;
};
guard l.count > 0 else {
if realizedValue == startGoal {
resultReceiver(description());
}
continue;
}
composedCount += 1;
l.append(.init(value: realizedValue, op: kind, description: description));
defer {
l.remove(at: l.count - 1);
composedCount -= 1;
}
await exploreAdditionOfRightNodeAsync(&l,
&composedCount,
&otherComposedCount,
dispatcher,
kind: kind,
skip: downstreamSiblingsRecruitmentSkip);
await exploreAdditionOfFloorAsync(&l,
&composedCount,
&otherComposedCount,
dispatcher,
kind: ((kind == .additive) ? .multiplicative : .additive));
}
}
}