1 /* 2 * Hunt - A refined core library for D programming language. 3 * 4 * Copyright (C) 2018-2019 HuntLabs 5 * 6 * Website: https://www.huntlabs.net/ 7 * 8 * Licensed under the Apache-2.0 License. 9 * 10 */ 11 12 module hunt.util.ArrayHelper; 13 14 import hunt.util.Comparator; 15 16 17 class ArrayHelper 18 { 19 /** 20 * Searches the specified array for the specified object using the binary 21 * search algorithm. The array must be sorted into ascending order 22 * according to the 23 * {@linkplain Comparable natural ordering} 24 * of its elements (as by the 25 * {@link #sort(Object[])} method) prior to making this call. 26 * If it is not sorted, the results are undefined. 27 * (If the array contains elements that are not mutually comparable (for 28 * example, strings and integers), it <i>cannot</i> be sorted according 29 * to the natural ordering of its elements, hence results are undefined.) 30 * If the array contains multiple 31 * elements equal to the specified object, there is no guarantee which 32 * one will be found. 33 * 34 * @param a the array to be searched 35 * @param key the value to be searched for 36 * @return index of the search key, if it is contained in the array; 37 * otherwise, <code>(-(<i>insertion point</i>) - 1)</code>. The 38 * <i>insertion point</i> is defined as the point at which the 39 * key would be inserted into the array: the index of the first 40 * element greater than the key, or {@code a.length} if all 41 * elements in the array are less than the specified key. Note 42 * that this guarantees that the return value will be >= 0 if 43 * and only if the key is found. 44 * @throws ClassCastException if the search key is not comparable to the 45 * elements of the array. 46 */ 47 public static int binarySearch(T)(T[] a, T key) 48 { 49 return binarySearch0!T(a, 0, cast(int)(a.length), key); 50 } 51 52 /** 53 * Searches a range of 54 * the specified array for the specified object using the binary 55 * search algorithm. 56 * The range must be sorted into ascending order 57 * according to the 58 * {@linkplain Comparable natural ordering} 59 * of its elements (as by the 60 * {@link #sort(Object[], int, int)} method) prior to making this 61 * call. If it is not sorted, the results are undefined. 62 * (If the range contains elements that are not mutually comparable (for 63 * example, strings and integers), it <i>cannot</i> be sorted according 64 * to the natural ordering of its elements, hence results are undefined.) 65 * If the range contains multiple 66 * elements equal to the specified object, there is no guarantee which 67 * one will be found. 68 * 69 * @param a the array to be searched 70 * @param fromIndex the index of the first element (inclusive) to be 71 * searched 72 * @param toIndex the index of the last element (exclusive) to be searched 73 * @param key the value to be searched for 74 * @return index of the search key, if it is contained in the array 75 * within the specified range; 76 * otherwise, <code>(-(<i>insertion point</i>) - 1)</code>. The 77 * <i>insertion point</i> is defined as the point at which the 78 * key would be inserted into the array: the index of the first 79 * element in the range greater than the key, 80 * or {@code toIndex} if all 81 * elements in the range are less than the specified key. Note 82 * that this guarantees that the return value will be >= 0 if 83 * and only if the key is found. 84 * @throws ClassCastException if the search key is not comparable to the 85 * elements of the array within the specified range. 86 * @throws IllegalArgumentException 87 * if {@code fromIndex > toIndex} 88 * @throws ArrayIndexOutOfBoundsException 89 * if {@code fromIndex < 0 or toIndex > a.length} 90 * @since 1.6 91 */ 92 public static int binarySearch(T)(T[] a, int fromIndex, int toIndex, T key) 93 { 94 // rangeCheck(a.length, fromIndex, toIndex); 95 return binarySearch0!T(a, fromIndex, toIndex, key); 96 } 97 98 // Like public version, but without range checks. 99 private static int binarySearch0(T)(T[] a, int fromIndex, int toIndex, T key) 100 { 101 int low = fromIndex; 102 int high = toIndex - 1; 103 104 while (low <= high) 105 { 106 int mid = (low + high) >>> 1; 107 auto midVal = a[mid]; 108 109 int cmp = compare(midVal,key); 110 111 if (cmp < 0) 112 low = mid + 1; 113 else if (cmp > 0) 114 high = mid - 1; 115 else 116 return mid; // key found 117 } 118 return -(low + 1); // key not found. 119 } 120 121 /** 122 * Searches the specified array for the specified object using the binary 123 * search algorithm. The array must be sorted into ascending order 124 * according to the specified comparator (as by the 125 * {@link #sort(Object[], Comparator) sort(T[], Comparator)} 126 * method) prior to making this call. If it is 127 * not sorted, the results are undefined. 128 * If the array contains multiple 129 * elements equal to the specified object, there is no guarantee which one 130 * will be found. 131 * 132 * @param <T> the class of the objects in the array 133 * @param a the array to be searched 134 * @param key the value to be searched for 135 * @param c the comparator by which the array is ordered. A 136 * {@code null} value indicates that the elements' 137 * {@linkplain Comparable natural ordering} should be used. 138 * @return index of the search key, if it is contained in the array; 139 * otherwise, <code>(-(<i>insertion point</i>) - 1)</code>. The 140 * <i>insertion point</i> is defined as the point at which the 141 * key would be inserted into the array: the index of the first 142 * element greater than the key, or {@code a.length} if all 143 * elements in the array are less than the specified key. Note 144 * that this guarantees that the return value will be >= 0 if 145 * and only if the key is found. 146 * @throws ClassCastException if the array contains elements that are not 147 * <i>mutually comparable</i> using the specified comparator, 148 * or the search key is not comparable to the 149 * elements of the array using this comparator. 150 */ 151 public static int binarySearch(T)(T[] a, T key, Comparator!T c) 152 { 153 return binarySearch0!T(a, 0, cast(int)(a.length), key, c); 154 } 155 156 /** 157 * Searches a range of 158 * the specified array for the specified object using the binary 159 * search algorithm. 160 * The range must be sorted into ascending order 161 * according to the specified comparator (as by the 162 * {@link #sort(Object[], int, int, Comparator) 163 * sort(T[], int, int, Comparator)} 164 * method) prior to making this call. 165 * If it is not sorted, the results are undefined. 166 * If the range contains multiple elements equal to the specified object, 167 * there is no guarantee which one will be found. 168 * 169 * @param <T> the class of the objects in the array 170 * @param a the array to be searched 171 * @param fromIndex the index of the first element (inclusive) to be 172 * searched 173 * @param toIndex the index of the last element (exclusive) to be searched 174 * @param key the value to be searched for 175 * @param c the comparator by which the array is ordered. A 176 * {@code null} value indicates that the elements' 177 * {@linkplain Comparable natural ordering} should be used. 178 * @return index of the search key, if it is contained in the array 179 * within the specified range; 180 * otherwise, <code>(-(<i>insertion point</i>) - 1)</code>. The 181 * <i>insertion point</i> is defined as the point at which the 182 * key would be inserted into the array: the index of the first 183 * element in the range greater than the key, 184 * or {@code toIndex} if all 185 * elements in the range are less than the specified key. Note 186 * that this guarantees that the return value will be >= 0 if 187 * and only if the key is found. 188 * @throws ClassCastException if the range contains elements that are not 189 * <i>mutually comparable</i> using the specified comparator, 190 * or the search key is not comparable to the 191 * elements in the range using this comparator. 192 * @throws IllegalArgumentException 193 * if {@code fromIndex > toIndex} 194 * @throws ArrayIndexOutOfBoundsException 195 * if {@code fromIndex < 0 or toIndex > a.length} 196 * @since 1.6 197 */ 198 // public static int binarySearch(T)(T[] a, int fromIndex, int toIndex, T key, 199 // Comparator < ? super T > c) 200 // { 201 // rangeCheck(a.length, fromIndex, toIndex); 202 // return binarySearch0(a, fromIndex, toIndex, key, c); 203 // } 204 205 // Like public version, but without range checks. 206 private static int binarySearch0(T)(T[] a, int fromIndex, int toIndex, 207 T key, Comparator!T c) 208 { 209 if (c is null) 210 { 211 return binarySearch0!T(a, fromIndex, toIndex, key); 212 } 213 int low = fromIndex; 214 int high = toIndex - 1; 215 216 while (low <= high) 217 { 218 int mid = (low + high) >>> 1; 219 T midVal = a[mid]; 220 int cmp = c.compare(midVal, key); 221 if (cmp < 0) 222 low = mid + 1; 223 else if (cmp > 0) 224 high = mid - 1; 225 else 226 return mid; // key found 227 } 228 return - (low + 1); // key not found. 229 } 230 231 }