X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fintervalstore%2Fimpl%2FBinarySearcher.java;fp=src%2Fintervalstore%2Fimpl%2FBinarySearcher.java;h=1086e9149b472b5fe3d1697dcc3b1d9a43480d8a;hb=a83adb45bdf9554e270921b4baad94defd314b36;hp=0000000000000000000000000000000000000000;hpb=d4ec118f86b5c9dee801e743c46aaacc7bb521d1;p=jalview.git diff --git a/src/intervalstore/impl/BinarySearcher.java b/src/intervalstore/impl/BinarySearcher.java new file mode 100644 index 0000000..1086e91 --- /dev/null +++ b/src/intervalstore/impl/BinarySearcher.java @@ -0,0 +1,91 @@ +/* +BSD 3-Clause License + +Copyright (c) 2018, Mungo Carstairs +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + +* Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + +* 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. + +* 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. +*/ +package intervalstore.impl; + +import java.util.List; +import java.util.function.Function; + +/** + * Provides a method to perform binary search of an ordered list for the first + * entry that satisfies a supplied condition + * + * @author gmcarstairs + */ +public final class BinarySearcher +{ + private BinarySearcher() + { + } + + /** + * Performs a binary search of the list to find the index of the first entry + * for which the test returns true. Answers the length of the list if there is + * no such entry. + *

+ * For correct behaviour, the provided list must be ordered consistent with + * the test, that is, any entries returning false must precede any entries + * returning true. Note that this means that this method is not + * usable to search for equality (to find a specific entry), as all unequal + * entries will answer false to the test. To do that, use + * Collections.binarySearch instead. + * + * @param list + * @param test + * @return + * @see java.util.Collections#binarySearch(List, Object) + */ + public static int findFirst(List list, + Function test) + { + int start = 0; + int end = list.size() - 1; + int matched = list.size(); + + while (start <= end) + { + int mid = (start + end) / 2; + T entry = list.get(mid); + boolean itsTrue = test.apply(entry); + if (itsTrue) + { + matched = mid; + end = mid - 1; + } + else + { + start = mid + 1; + } + } + + return matched; + } +}