001/* 002 * Copyright 2013 Alex Kasko (alexkasko.com) 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package com.alexkasko.unsafe.offheaplong; 018 019import com.alexkasko.unsafe.offheap.OffHeapAddressable; 020 021import java.io.Serializable; 022 023/** 024 * Binary search implementation borrowed from {@code https://android.googlesource.com/platform/libcore/+/android-4.2.2_r1/luni/src/main/java/java/util/Arrays.java} 025 * and adapted to {@link com.alexkasko.unsafe.offheap.OffHeapAddressable} 026 * 027 * @author alexkasko 028 * Date: 3/5/13 029 * @see com.alexkasko.unsafe.offheaplong.OffHeapLongSorter 030 */ 031public class OffHeapLongBinarySearch { 032 /** 033 * Performs a binary search for {@code value} in the ascending sorted off-heap collection. 034 * Searching in an unsorted collection has an undefined result. It's also undefined which element 035 * is found if there are multiple occurrences of the same element. 036 * 037 * @param collection the sorted array to search. 038 * @param value the element to find. 039 * @return the non-negative index of the element, or a negative index which 040 * is {@code -index - 1} where the element would be inserted. 041 */ 042 public static long binarySearch(OffHeapAddressable collection, long value) { 043 return binarySearch(collection, 0, collection.size(), value); 044 } 045 046 /** 047 * Performs a binary search for {@code value} in the ascending sorted off-heap collection, 048 * in the range specified by fromIndex (inclusive) and toIndex (exclusive). 049 * Searching in an unsorted collection has an undefined result. It's also undefined which element 050 * is found if there are multiple occurrences of the same element. 051 * 052 * @param collection the sorted collection to search. 053 * @param startIndex the inclusive start index. 054 * @param endIndex the exclusive end index. 055 * @param value the element to find. 056 * @return the non-negative index of the element, or a negative index which 057 * is {@code -index - 1} where the element would be inserted. 058 * @throws IllegalArgumentException {@code if (startIndex < 0 || startIndex > endIndex || endIndex > collection.size()} 059 */ 060 public static long binarySearch(OffHeapAddressable collection, long startIndex, long endIndex, long value) { 061 if (startIndex < 0 || startIndex > endIndex || endIndex > collection.size()) { 062 throw new IllegalArgumentException("Illegal input, collection size: [" + collection.size() + "], " + 063 "startIndex: [" + startIndex + "], endIndex: [" + endIndex + "]"); 064 } 065 long lo = startIndex; 066 long hi = endIndex - 1; 067 while (lo <= hi) { 068 long mid = (lo + hi) >>> 1; 069 long midVal = collection.get(mid); 070 071 if (midVal < value) { 072 lo = mid + 1; 073 } else if (midVal > value) { 074 hi = mid - 1; 075 } else { 076 return mid; // value found 077 } 078 } 079 return ~lo; // value not present 080 } 081 082 /** 083 * Performs a binary search for {@code value} in the ascending sorted off-heap collection. 084 * Returns range of indices having given value or empty range. 085 * Searching in an unsorted collection has an undefined result. It's also undefined which element 086 * is found if there are multiple occurrences of the same element. 087 * 088 * @param collection the sorted array to search. 089 * @param value the element to find. 090 * @param out range instance, will be set with start/end indices having given value or with empty value 091 */ 092 public static void binarySearchRange(OffHeapAddressable collection, long value, IndexRange out) { 093 binarySearchRange(collection, 0, collection.size(), value, out); 094 } 095 096 /** 097 * Performs a binary search for {@code value} in the ascending sorted off-heap collection. 098 * Returns range of indices having given value or empty range. 099 * Searching in an unsorted collection has an undefined result. It's also undefined which element 100 * is found if there are multiple occurrences of the same element. 101 * 102 * @param collection the sorted array to search. 103 * @param startIndex the inclusive start index. 104 * @param endIndex the exclusive end index. 105 * @param value the element to find. 106 * @param out range instance, will be set with start/end indices having given value or with empty value 107 */ 108 public static void binarySearchRange(OffHeapAddressable collection, long startIndex, long endIndex, 109 long value, IndexRange out) { 110 long ind = binarySearch(collection, startIndex, endIndex, value); 111 if(ind < 0) { 112 out.setEmpty(ind); 113 return; 114 } 115 long from = ind; 116 while (from >= startIndex && value == collection.get(from)) from -= 1; 117 from += 1; 118 long to = ind; 119 while (to < endIndex && value == collection.get(to)) to += 1; 120 to -= 1; 121 out.set(from, to); 122 } 123 124 /** 125 * {@link OffHeapAddressable} index range representation. 126 * Was made mutable to prevent new object instantiation for each search. 127 * {@link #isEmpty()} method should be checked before accessing indices. 128 * Empty range will contain negative equal indices which values are 129 * {@code -index - 1} where the element would be inserted. 130 * Range with size {@code 1} will contain equal indices. 131 */ 132 public static class IndexRange implements Serializable { 133 private static final long serialVersionUID = 879348143026038919L; 134 private boolean empty; 135 private long fromIndex; 136 private long toIndex; 137 138 public IndexRange() { 139 this.empty = false; 140 this.fromIndex = -1; 141 this.toIndex = -1; 142 } 143 144 /** 145 * Sets value for empty range 146 * 147 * @param value negative value for empty range returned by search 148 */ 149 private void setEmpty(long value) { 150 this.empty = true; 151 this.fromIndex = value; 152 this.toIndex = value; 153 } 154 155 /** 156 * Sets boundaries for non-empty range 157 * 158 * @param from start index 159 * @param to end index 160 */ 161 private void set(long from, long to) { 162 this.empty = false; 163 this.fromIndex = from; 164 this.toIndex = to; 165 } 166 167 /** 168 * Whether this range is empty 169 * 170 * @return whether this range is empty 171 */ 172 public boolean isEmpty() { 173 return empty; 174 } 175 176 /** 177 * Whether this range is not empty 178 * 179 * @return whether this range is not empty 180 */ 181 public boolean isNotEmpty() { 182 return !empty; 183 } 184 185 /** 186 * Start index or {@code -index - 1} 187 * where the element would be inserted for empty range 188 * 189 * @return start index value or {@code -index - 1} 190 * where the element would be inserted for empty range 191 */ 192 public long getFromIndex() { 193 return fromIndex; 194 } 195 196 /** 197 * End index or {@code -index - 1} 198 * where the element would be inserted for empty range 199 * 200 * @return end index value, {@code -index - 1} 201 * where the element would be inserted for empty range 202 */ 203 public long getToIndex() { 204 return toIndex; 205 } 206 207 /** 208 * {@inheritDoc} 209 */ 210 @Override 211 public boolean equals(Object o) { 212 if (this == o) return true; 213 if (o == null || getClass() != o.getClass()) return false; 214 IndexRange that = (IndexRange) o; 215 if (empty != that.empty) return false; 216 if (fromIndex != that.fromIndex) return false; 217 if (toIndex != that.toIndex) return false; 218 return true; 219 } 220 221 /** 222 * {@inheritDoc} 223 */ 224 @Override 225 public int hashCode() { 226 int result = (empty ? 1 : 0); 227 result = 31 * result + (int) (fromIndex ^ (fromIndex >>> 32)); 228 result = 31 * result + (int) (toIndex ^ (toIndex >>> 32)); 229 return result; 230 } 231 232 /** 233 * {@inheritDoc} 234 */ 235 @Override 236 public String toString() { 237 final StringBuilder sb = new StringBuilder(); 238 sb.append("IndexRange"); 239 sb.append("{empty=").append(empty); 240 sb.append(", fromIndex=").append(fromIndex); 241 sb.append(", toIndex=").append(toIndex); 242 sb.append('}'); 243 return sb.toString(); 244 } 245 } 246}