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