| /* |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you under the Apache License, Version 2.0 (the |
| * "License"); you may not use this file except in compliance |
| * with the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package accord.primitives; |
| |
| import accord.api.RoutingKey; |
| import accord.primitives.Routable.Domain; |
| import accord.utils.IndexedFold; |
| import accord.utils.IndexedFoldToLong; |
| import accord.utils.IndexedRangeFoldToLong; |
| import accord.utils.SortedArrays; |
| import net.nicoulaj.compilecommand.annotations.Inline; |
| |
| import static accord.utils.SortedArrays.Search.FLOOR; |
| |
| /** |
| * A collection of either Seekable or Unseekable |
| */ |
| public interface Routables<K extends Routable, U extends Routables<K, ?>> extends Iterable<K> |
| { |
| enum Slice |
| { |
| /** (Default) Overlapping ranges are returned unmodified */ |
| Overlapping, |
| /** Overlapping ranges are split/shrunk to the intersection of the overlaps */ |
| Minimal, |
| /** Overlapping ranges are extended to the union of the overlaps */ |
| Maximal |
| } |
| |
| int indexOf(K item); |
| K get(int i); |
| int size(); |
| |
| boolean isEmpty(); |
| boolean intersects(AbstractRanges<?> ranges); |
| boolean intersects(AbstractKeys<?, ?> keys); |
| default boolean intersects(Routables<?, ?> routables) |
| { |
| switch (routables.domain()) |
| { |
| default: throw new AssertionError(); |
| case Key: return intersects((AbstractKeys<?, ?>) routables); |
| case Range: return intersects((AbstractRanges<?>) routables); |
| } |
| } |
| boolean contains(RoutableKey key); |
| boolean containsAll(Routables<?, ?> keysOrRanges); |
| |
| U slice(Ranges ranges); |
| Routables<K, ?> slice(Ranges ranges, Slice slice); |
| |
| /** |
| * Search forwards from {code thisIndex} and {@code withIndex} to find the first entries in each collection |
| * that intersect with each other. Return their position packed in a long, with low bits representing |
| * the resultant {@code thisIndex} and high bits {@code withIndex}. |
| */ |
| long findNextIntersection(int thisIndex, AbstractRanges<?> with, int withIndex); |
| |
| /** |
| * Search forwards from {code thisIndex} and {@code withIndex} to find the first entries in each collection |
| * that intersect with each other. Return their position packed in a long, with low bits representing |
| * the resultant {@code thisIndex} and high bits {@code withIndex}. |
| */ |
| long findNextIntersection(int thisIndex, AbstractKeys<?, ?> with, int withIndex); |
| |
| /** |
| * Search forwards from {code thisIndex} and {@code withIndex} to find the first entries in each collection |
| * that intersect with each other. Return their position packed in a long, with low bits representing |
| * the resultant {@code thisIndex} and high bits {@code withIndex}. |
| */ |
| long findNextIntersection(int thisIndex, Routables<K, ?> with, int withIndex); |
| |
| /** |
| * Perform {@link SortedArrays#exponentialSearch} from {@code thisIndex} looking for {@code find} with behaviour of {@code search} |
| */ |
| int findNext(int thisIndex, Range find, SortedArrays.Search search); |
| |
| /** |
| * Perform {@link SortedArrays#exponentialSearch} from {@code thisIndex} looking for {@code find} with behaviour of {@code search} |
| */ |
| int findNext(int thisIndex, RoutableKey find, SortedArrays.Search search); |
| |
| Domain domain(); |
| |
| /** |
| * Fold-left over the {@code inputs} that intersect with {@code matching} in ascending order. |
| * Terminate once we hit {@code terminalValue}. |
| */ |
| @Inline |
| static <Input extends Routable, T> T foldl(Routables<Input, ?> inputs, AbstractRanges<?> matching, IndexedFold<? super Input, T> fold, T initialValue) |
| { |
| return Helper.foldl(Routables::findNextIntersection, Helper::findLimit, inputs, matching, fold, initialValue); |
| } |
| |
| /** |
| * Fold-left over the {@code inputs} that intersect with {@code matching} in ascending order. |
| * If the inputs are ranges, narrow them to the parts the intersect with {@code matching}, so that we never visit |
| * any portion of a {@code Range} that is not in {@code matching} (See {@link Slice#Minimal}). |
| * Terminate once we hit {@code terminalValue}. |
| */ |
| @Inline |
| static <T> T foldlMinimal(Seekables<?, ?> inputs, AbstractRanges<?> matching, IndexedFold<? super Seekable, T> fold, T initialValue) |
| { |
| return Helper.foldlMinimal(inputs, matching, fold, initialValue); |
| } |
| |
| /** |
| * Fold-left over the {@code inputs} that intersect with {@code matching} in ascending order. |
| * Terminate once we hit {@code terminalValue}. |
| */ |
| @Inline |
| static <Input extends RoutableKey, T> T foldl(AbstractKeys<Input, ?> inputs, AbstractRanges<?> matching, IndexedFold<? super Input, T> fold, T initialValue) |
| { |
| return Helper.foldl(AbstractKeys::findNextIntersection, Helper::findLimit, inputs, matching, fold, initialValue); |
| } |
| |
| /** |
| * Fold-left over the {@code inputs} that intersect with {@code matching} in ascending order. |
| * Terminate once we hit {@code terminalValue}. |
| */ |
| @Inline |
| static <T> T foldl(AbstractRanges<?> inputs, Routables<?, ?> matching, IndexedFold<? super Range, T> fold, T initialValue) |
| { |
| switch (matching.domain()) |
| { |
| default: throw new AssertionError(); |
| case Key: return Helper.foldl(AbstractRanges::findNextIntersection, Helper::findLimit, inputs, (AbstractKeys<?,?>)matching, fold, initialValue); |
| case Range: return Helper.foldl(AbstractRanges::findNextIntersection, Helper::findLimit, inputs, (AbstractRanges<?>)matching, fold, initialValue); |
| } |
| } |
| |
| /** |
| * Fold-left over the {@code inputs} that intersect with {@code matching} in ascending order. |
| * Terminate once we hit {@code terminalValue}. |
| */ |
| @Inline |
| static <Input extends RoutableKey> long foldl(AbstractKeys<Input, ?> inputs, AbstractRanges<?> matching, IndexedFoldToLong<? super Input> fold, long param, long initialValue, long terminalValue) |
| { |
| return Helper.foldl(AbstractKeys::findNextIntersection, Helper::findLimit, inputs, matching, fold, param, initialValue, terminalValue); |
| } |
| |
| /** |
| * Fold-left over the {@code inputs} that intersect with {@code matching} in ascending order. |
| * Terminate once we hit {@code terminalValue}. |
| */ |
| @Inline |
| static <Input extends Routable> long foldl(Routables<Input, ?> inputs, AbstractRanges<?> matching, IndexedFoldToLong<? super Input> fold, long param, long initialValue, long terminalValue) |
| { |
| return Helper.foldl(Routables::findNextIntersection, Helper::findLimit, inputs, matching, fold, param, initialValue, terminalValue); |
| } |
| |
| /** |
| * Fold-left over the {@code inputs} that intersect with {@code matching} in ascending order. |
| * Terminate once we hit {@code terminalValue}. |
| */ |
| @Inline |
| static <Input extends Routable> long foldl(Routables<Input, ?> inputs, AbstractKeys<?, ?> matching, IndexedFoldToLong<? super Input> fold, long param, long initialValue, long terminalValue) |
| { |
| return Helper.foldl(Routables::findNextIntersection, (ls, li, rs, ri) -> li + 1, |
| inputs, matching, fold, param, initialValue, terminalValue); |
| } |
| |
| /** |
| * Fold-left over the {@code inputs} that intersect with {@code matching} in ascending order. |
| * Terminate once we hit {@code terminalValue}. |
| */ |
| @Inline |
| static <Input extends RoutingKey, Matching extends Routable> long foldl(AbstractKeys<Input, ?> inputs, Routables<Matching, ?> matching, IndexedFoldToLong<? super Input> fold, long param, long initialValue, long terminalValue) |
| { |
| return Helper.foldl((ls, li, rs, ri) -> SortedArrays.swapHighLow32b(rs.findNextIntersection(ri, ls, li)), (ls, li, rs, ri) -> li + 1, |
| inputs, matching, fold, param, initialValue, terminalValue); |
| } |
| |
| /** |
| * Fold-left over the {@code inputs} that intersect with {@code matching} in ascending order, passing the contiguous ranges that intersect to the IndexedRangeFold function. |
| * Terminate once we hit {@code terminalValue}. |
| */ |
| @Inline |
| static <Input extends Routable> long rangeFoldl(Routables<Input, ?> inputs, AbstractRanges<?> matching, IndexedRangeFoldToLong fold, long param, long initialValue, long terminalValue) |
| { |
| return Helper.rangeFoldl(Routables::findNextIntersection, (ls, li, rs, ri) -> li + 1, |
| inputs, matching, fold, param, initialValue, terminalValue); |
| } |
| |
| /** |
| * Fold-left over the {@code inputs} that intersect with {@code matching} in ascending order, passing the contiguous ranges that intersect to the IndexedRangeFold function. |
| * Terminate once we hit {@code terminalValue}. |
| */ |
| @Inline |
| static <Input extends Routable> long rangeFoldl(Routables<Input, ?> inputs, AbstractKeys<?, ?> matching, IndexedRangeFoldToLong fold, long param, long initialValue, long terminalValue) |
| { |
| return Helper.rangeFoldl(Routables::findNextIntersection, (ls, li, rs, ri) -> li + 1, |
| inputs, matching, fold, param, initialValue, terminalValue); |
| } |
| |
| /** |
| * Fold-left over the {@code inputs} that <b>do not</b> intersect with {@code matching} in ascending order. |
| * Terminate once we hit {@code terminalValue}. |
| */ |
| @Inline |
| static <Input extends Routable> long foldlMissing(Routables<Input, ?> inputs, Routables<Input, ?> notMatching, IndexedFoldToLong<? super Input> fold, long param, long initialValue, long terminalValue) |
| { |
| return Helper.foldlMissing((ls, li, rs, ri) -> rs.findNextIntersection(ri, ls, li), (ls, li, rs, ri) -> li + 1, |
| inputs, notMatching, fold, param, initialValue, terminalValue); |
| } |
| |
| class Helper |
| { |
| interface SetIntersections<L extends Routables<?, ?>, R extends Routables<?, ?>> |
| { |
| long findNext(L left, int li, R right, int ri); |
| } |
| |
| interface ValueIntersections<L extends Routables<?, ?>, R extends Routables<?, ?>> |
| { |
| int findLimit(L left, int li, R right, int ri); |
| } |
| |
| @Inline |
| static <T> T foldlMinimal(Seekables<?, ?> is, AbstractRanges<?> ms, IndexedFold<? super Seekable, T> fold, T initialValue) |
| { |
| int i = 0, m = 0; |
| while (true) |
| { |
| long im = is.findNextIntersection(i, ms, m); |
| if (im < 0) |
| break; |
| |
| i = (int)(im); |
| m = (int)(im >>> 32); |
| |
| Range mv = ms.get(m); |
| int nexti = Helper.findLimit(is, i, ms, m); |
| while (i < nexti) |
| { |
| initialValue = fold.apply(is.get(i).slice(mv), initialValue, i); |
| ++i; |
| } |
| } |
| |
| return initialValue; |
| } |
| |
| @Inline |
| static <Input extends Routable, Inputs extends Routables<Input, ?>, Matches extends Routables<?, ?>, T> |
| T foldl(SetIntersections<Inputs, Matches> setIntersections, ValueIntersections<Inputs, Matches> valueIntersections, |
| Inputs is, Matches ms, IndexedFold<? super Input, T> fold, T initialValue) |
| { |
| int i = 0, m = 0; |
| while (true) |
| { |
| long im = setIntersections.findNext(is, i, ms, m); |
| if (im < 0) |
| break; |
| |
| i = (int)(im); |
| m = (int)(im >>> 32); |
| |
| int nexti = valueIntersections.findLimit(is, i, ms, m); |
| while (i < nexti) |
| { |
| initialValue = fold.apply(is.get(i), initialValue, i); |
| ++i; |
| } |
| } |
| |
| return initialValue; |
| } |
| |
| @Inline |
| static <Input extends Routable, Inputs extends Routables<Input, ?>, Matches extends Routables<?, ?>> |
| long foldl(SetIntersections<Inputs, Matches> setIntersections, ValueIntersections<Inputs, Matches> valueIntersections, |
| Inputs is, Matches ms, IndexedFoldToLong<? super Input> fold, long param, long initialValue, long terminalValue) |
| { |
| int i = 0, m = 0; |
| done: while (true) |
| { |
| long im = setIntersections.findNext(is, i, ms, m); |
| if (im < 0) |
| break; |
| |
| i = (int)(im); |
| m = (int)(im >>> 32); |
| |
| int nexti = valueIntersections.findLimit(is, i, ms, m); |
| while (i < nexti) |
| { |
| initialValue = fold.apply(is.get(i), param, initialValue, i); |
| if (initialValue == terminalValue) |
| break done; |
| ++i; |
| } |
| } |
| |
| return initialValue; |
| } |
| |
| @Inline |
| static <Input extends Routable, Inputs extends Routables<Input, ?>, Matches extends Routables<?, ?>> |
| long foldlMissing(SetIntersections<Inputs, Matches> setIntersections, ValueIntersections<Inputs, Matches> valueIntersections, |
| Inputs is, Matches ms, IndexedFoldToLong<? super Input> fold, long param, long initialValue, long terminalValue) |
| { |
| int i = 0, m = 0; |
| done: while (true) |
| { |
| long im = setIntersections.findNext(is, i, ms, m); |
| if (im < 0) |
| break; |
| |
| int nexti = (int)(im); |
| while (i < nexti) |
| { |
| initialValue = fold.apply(is.get(i), param, initialValue, i); |
| if (initialValue == terminalValue) |
| break done; |
| ++i; |
| } |
| |
| m = (int)(im >>> 32); |
| i = 1 + valueIntersections.findLimit(is, nexti, ms, m); |
| } |
| |
| return initialValue; |
| } |
| |
| static <Input extends Routable, Inputs extends Routables<Input, ?>, Matches extends Routables<?, ?>> |
| long rangeFoldl(SetIntersections<Inputs, Matches> setIntersections, ValueIntersections<Inputs, Matches> valueIntersections, |
| Inputs is, Matches ms, IndexedRangeFoldToLong fold, long param, long initialValue, long terminalValue) |
| { |
| int i = 0, m = 0; |
| while (true) |
| { |
| long kri = setIntersections.findNext(is, i, ms, m); |
| if (kri < 0) |
| break; |
| |
| i = (int)(kri); |
| m = (int)(kri >>> 32); |
| |
| int nexti = valueIntersections.findLimit(is, i, ms, m); |
| initialValue = fold.apply(param, initialValue, i, nexti); |
| if (initialValue == terminalValue) |
| break; |
| i = nexti; |
| } |
| |
| return initialValue; |
| } |
| |
| static <L extends Routable> int findLimit(Routables<L, ?> ls, int li, AbstractRanges<?> rs, int ri) |
| { |
| Range range = rs.get(ri); |
| |
| int nextl = ls.findNext(li + 1, range, FLOOR); |
| if (nextl < 0) nextl = -1 - nextl; |
| else nextl++; |
| return nextl; |
| } |
| |
| static int findLimit(AbstractRanges<?> ls, int li, AbstractKeys<?, ?> rs, int ri) |
| { |
| RoutableKey r = rs.get(ri); |
| |
| int nextl = ls.findNext(li + 1, r, FLOOR); |
| if (nextl < 0) nextl = -1 - nextl; |
| else nextl++; |
| return nextl; |
| } |
| } |
| } |