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.offheapstruct; 018 019import java.io.Serializable; 020 021/** 022 * 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} 023 * and adapted to {@link com.alexkasko.unsafe.offheapstruct.OffHeapStructCollection} 024 * 025 * @author alexkasko 026 * Date: 7/4/13 027 * @see com.alexkasko.unsafe.offheaplong.OffHeapLongSorter 028 * @see com.alexkasko.unsafe.offheapstruct.OffHeapStructSorter 029 */ 030public class OffHeapStructBinarySearch { 031 032 033 // long key part 034 035 /** 036 * Performs a binary search for {@code value} in the ascending sorted off-heap struct collection using long struct key. 037 * Searching in an unsorted collection has an undefined result. It's also undefined which element 038 * is found if there are multiple occurrences of the same element. 039 * 040 * @param collection the sorted array to search. 041 * @param value the element to find. 042 * @param keyOffset long key field offset within stuct bounds 043 * @return the non-negative index of the element, or a negative index which 044 * is {@code -index - 1} where the element would be inserted. 045 */ 046 public static long binarySearchByLongKey(OffHeapStructCollection collection, long value, int keyOffset) { 047 return binarySearchByLongKey(collection, 0, collection.size(), value, keyOffset); 048 } 049 050 /** 051 * Performs a binary search for {@code value} in the ascending sorted off-heap struct collection using long struct key. 052 * in the range specified by fromIndex (inclusive) and toIndex (exclusive). 053 * Searching in an unsorted collection has an undefined result. It's also undefined which element 054 * is found if there are multiple occurrences of the same element. 055 * 056 * @param collection the sorted collection to search. 057 * @param startIndex the inclusive start index. 058 * @param endIndex the exclusive end index. 059 * @param value the element to find. 060 * @param keyOffset long key field offset within stuct bounds 061 * @return the non-negative index of the element, or a negative index which 062 * is {@code -index - 1} where the element would be inserted. 063 * @throws IllegalArgumentException {@code if (startIndex < 0 || startIndex > endIndex || endIndex > collection.size()} 064 */ 065 public static long binarySearchByLongKey(OffHeapStructCollection collection, long startIndex, long endIndex, long value, int keyOffset) { 066 if (startIndex < 0 || startIndex > endIndex || endIndex > collection.size()) { 067 throw new IllegalArgumentException("Illegal input, collection size: [" + collection.size() + "], " + 068 "startIndex: [" + startIndex + "], endIndex: [" + endIndex + "]"); 069 } 070 long lo = startIndex; 071 long hi = endIndex - 1; 072 while (lo <= hi) { 073 long mid = (lo + hi) >>> 1; 074 long midVal = collection.getLong(mid, keyOffset); 075 076 if (midVal < value) { 077 lo = mid + 1; 078 } else if (midVal > value) { 079 hi = mid - 1; 080 } else { 081 return mid; // value found 082 } 083 } 084 return ~lo; // value not present 085 } 086 087 /** 088 * Performs a binary search for {@code value} in the ascending sorted off-heap struct collection using long struct key. 089 * Returns range of indices having given value or empty range. 090 * Searching in an unsorted collection has an undefined result. It's also undefined which element 091 * is found if there are multiple occurrences of the same element. 092 * 093 * @param collection the sorted array to search. 094 * @param value the element to find. 095 * @param keyOffset long key field offset within stuct bounds 096 * @param out range instance, will be set with start/end indices having given value or with empty value 097 */ 098 public static void binarySearchRangeByLongKey(OffHeapStructCollection collection, long value, int keyOffset, IndexRange out) { 099 binarySearchRangeByLongKey(collection, 0, collection.size(), value, keyOffset, out); 100 } 101 102 /** 103 * Performs a binary search for {@code value} in the ascending sorted off-heap struct collection using long struct key. 104 * Returns range of indices having given value or empty range. 105 * Searching in an unsorted collection has an undefined result. It's also undefined which element 106 * is found if there are multiple occurrences of the same element. 107 * 108 * @param collection the sorted array to search. 109 * @param startIndex the inclusive start index. 110 * @param endIndex the exclusive end index. 111 * @param value the element to find. 112 * @param keyOffset long key field offset within stuct bounds 113 * @param out range instance, will be set with start/end indices having given value or with empty value 114 */ 115 public static void binarySearchRangeByLongKey(OffHeapStructCollection collection, long startIndex, long endIndex, 116 long value, int keyOffset, IndexRange out) { 117 long ind = binarySearchByLongKey(collection, startIndex, endIndex, value, keyOffset); 118 if(ind < 0) { 119 out.setEmpty(ind); 120 return; 121 } 122 long from = ind; 123 while (from >= startIndex && value == collection.getLong(from, keyOffset)) { 124 from -= 1; 125 } 126 from += 1; 127 long to = ind; 128 while (to < endIndex && value == collection.getLong(to, keyOffset)) { 129 to += 1; 130 } 131 to -= 1; 132 out.set(from, to); 133 } 134 135 136 // int key part 137 138 /** 139 * Performs a binary search for {@code value} in the ascending sorted off-heap struct collection using int struct key. 140 * Searching in an unsorted collection has an undefined result. It's also undefined which element 141 * is found if there are multiple occurrences of the same element. 142 * 143 * @param collection the sorted array to search. 144 * @param value the element to find. 145 * @param keyOffset int key field offset within stuct bounds 146 * @return the non-negative index of the element, or a negative index which 147 * is {@code -index - 1} where the element would be inserted. 148 */ 149 public static long binarySearchByIntKey(OffHeapStructCollection collection, long value, int keyOffset) { 150 return binarySearchByIntKey(collection, 0, collection.size(), value, keyOffset); 151 } 152 153 /** 154 * Performs a binary search for {@code value} in the ascending sorted off-heap struct collection using int struct key. 155 * in the range specified by fromIndex (inclusive) and toIndex (exclusive). 156 * Searching in an unsorted collection has an undefined result. It's also undefined which element 157 * is found if there are multiple occurrences of the same element. 158 * 159 * @param collection the sorted collection to search. 160 * @param startIndex the inclusive start index. 161 * @param endIndex the exclusive end index. 162 * @param value the element to find. 163 * @param keyOffset int key field offset within stuct bounds 164 * @return the non-negative index of the element, or a negative index which 165 * is {@code -index - 1} where the element would be inserted. 166 * @throws IllegalArgumentException {@code if (startIndex < 0 || startIndex > endIndex || endIndex > collection.size()} 167 */ 168 public static long binarySearchByIntKey(OffHeapStructCollection collection, long startIndex, long endIndex, long value, int keyOffset) { 169 if (startIndex < 0 || startIndex > endIndex || endIndex > collection.size()) { 170 throw new IllegalArgumentException("Illegal input, collection size: [" + collection.size() + "], " + 171 "startIndex: [" + startIndex + "], endIndex: [" + endIndex + "]"); 172 } 173 long lo = startIndex; 174 long hi = endIndex - 1; 175 while (lo <= hi) { 176 long mid = (lo + hi) >>> 1; 177 long midVal = collection.getInt(mid, keyOffset); 178 179 if (midVal < value) { 180 lo = mid + 1; 181 } else if (midVal > value) { 182 hi = mid - 1; 183 } else { 184 return mid; // value found 185 } 186 } 187 return ~lo; // value not present 188 } 189 190 /** 191 * Performs a binary search for {@code value} in the ascending sorted off-heap struct collection using int struct key. 192 * Returns range of indices having given value or empty range. 193 * Searching in an unsorted collection has an undefined result. It's also undefined which element 194 * is found if there are multiple occurrences of the same element. 195 * 196 * @param collection the sorted array to search. 197 * @param value the element to find. 198 * @param keyOffset int key field offset within stuct bounds 199 * @param out range instance, will be set with start/end indices having given value or with empty value 200 */ 201 public static void binarySearchRangeByIntKey(OffHeapStructCollection collection, long value, int keyOffset, IndexRange out) { 202 binarySearchRangeByIntKey(collection, 0, collection.size(), value, keyOffset, out); 203 } 204 205 /** 206 * Performs a binary search for {@code value} in the ascending sorted off-heap struct collection using int struct key. 207 * Returns range of indices having given value or empty range. 208 * Searching in an unsorted collection has an undefined result. It's also undefined which element 209 * is found if there are multiple occurrences of the same element. 210 * 211 * @param collection the sorted array to search. 212 * @param startIndex the inclusive start index. 213 * @param endIndex the exclusive end index. 214 * @param value the element to find. 215 * @param keyOffset int key field offset within stuct bounds 216 * @param out range instance, will be set with start/end indices having given value or with empty value 217 */ 218 public static void binarySearchRangeByIntKey(OffHeapStructCollection collection, long startIndex, long endIndex, 219 long value, int keyOffset, IndexRange out) { 220 long ind = binarySearchByIntKey(collection, startIndex, endIndex, value, keyOffset); 221 if(ind < 0) { 222 out.setEmpty(ind); 223 return; 224 } 225 long from = ind; 226 while (from >= startIndex && value == collection.getInt(from, keyOffset)) { 227 from -= 1; 228 } 229 from += 1; 230 long to = ind; 231 while (to < endIndex && value == collection.getInt(to, keyOffset)) { 232 to += 1; 233 } 234 to -= 1; 235 out.set(from, to); 236 } 237 238 /** 239 * {@link OffHeapStructCollection} index range representation. 240 * Was made mutable to prevent new object instantiation for each search. 241 * {@link #isEmpty()} method should be checked before accessing indices. 242 * Empty range will contain negative equal indices which values are 243 * {@code -index - 1} where the element would be inserted. 244 * Range with size {@code 1} will contain equal indices. 245 */ 246 public static class IndexRange implements Serializable { 247 private static final long serialVersionUID = 879348143026038919L; 248 private boolean empty; 249 private long fromIndex; 250 private long toIndex; 251 252 public IndexRange() { 253 this.empty = false; 254 this.fromIndex = -1; 255 this.toIndex = -1; 256 } 257 258 /** 259 * Sets value for empty range 260 * 261 * @param value negative value for empty range returned by search 262 */ 263 void setEmpty(long value) { 264 this.empty = true; 265 this.fromIndex = value; 266 this.toIndex = value; 267 } 268 269 /** 270 * Sets boundaries for non-empty range 271 * 272 * @param from start index 273 * @param to end index 274 */ 275 void set(long from, long to) { 276 this.empty = false; 277 this.fromIndex = from; 278 this.toIndex = to; 279 } 280 281 /** 282 * Whether this range is empty 283 * 284 * @return whether this range is empty 285 */ 286 public boolean isEmpty() { 287 return empty; 288 } 289 290 /** 291 * Whether this range is not empty 292 * 293 * @return whether this range is not empty 294 */ 295 public boolean isNotEmpty() { 296 return !empty; 297 } 298 299 /** 300 * Start index or {@code -index - 1} 301 * where the element would be inserted for empty range 302 * 303 * @return start index value or {@code -index - 1} 304 * where the element would be inserted for empty range 305 */ 306 public long getFromIndex() { 307 return fromIndex; 308 } 309 310 /** 311 * End index or {@code -index - 1} 312 * where the element would be inserted for empty range 313 * 314 * @return end index value, {@code -index - 1} 315 * where the element would be inserted for empty range 316 */ 317 public long getToIndex() { 318 return toIndex; 319 } 320 321 /** 322 * {@inheritDoc} 323 */ 324 @Override 325 public boolean equals(Object o) { 326 if (this == o) return true; 327 if (o == null || getClass() != o.getClass()) return false; 328 IndexRange that = (IndexRange) o; 329 if (empty != that.empty) return false; 330 if (fromIndex != that.fromIndex) return false; 331 if (toIndex != that.toIndex) return false; 332 return true; 333 } 334 335 /** 336 * {@inheritDoc} 337 */ 338 @Override 339 public int hashCode() { 340 int result = (empty ? 1 : 0); 341 result = 31 * result + (int) (fromIndex ^ (fromIndex >>> 32)); 342 result = 31 * result + (int) (toIndex ^ (toIndex >>> 32)); 343 return result; 344 } 345 346 /** 347 * {@inheritDoc} 348 */ 349 @Override 350 public String toString() { 351 final StringBuilder sb = new StringBuilder(); 352 sb.append("IndexRange"); 353 sb.append("{empty=").append(empty); 354 sb.append(", fromIndex=").append(fromIndex); 355 sb.append(", toIndex=").append(toIndex); 356 sb.append('}'); 357 return sb.toString(); 358 } 359 } 360}