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 */ 91 public static int binarySearch(T)(T[] a, int fromIndex, int toIndex, T key) 92 { 93 // rangeCheck(a.length, fromIndex, toIndex); 94 return binarySearch0!T(a, fromIndex, toIndex, key); 95 } 96 97 // Like public version, but without range checks. 98 private static int binarySearch0(T)(T[] a, int fromIndex, int toIndex, T key) 99 { 100 int low = fromIndex; 101 int high = toIndex - 1; 102 103 while (low <= high) 104 { 105 int mid = (low + high) >>> 1; 106 auto midVal = a[mid]; 107 108 int cmp = compare(midVal,key); 109 110 if (cmp < 0) 111 low = mid + 1; 112 else if (cmp > 0) 113 high = mid - 1; 114 else 115 return mid; // key found 116 } 117 return -(low + 1); // key not found. 118 } 119 120 /** 121 * Searches the specified array for the specified object using the binary 122 * search algorithm. The array must be sorted into ascending order 123 * according to the specified comparator (as by the 124 * {@link #sort(Object[], Comparator) sort(T[], Comparator)} 125 * method) prior to making this call. If it is 126 * not sorted, the results are undefined. 127 * If the array contains multiple 128 * elements equal to the specified object, there is no guarantee which one 129 * will be found. 130 * 131 * @param <T> the class of the objects in the array 132 * @param a the array to be searched 133 * @param key the value to be searched for 134 * @param c the comparator by which the array is ordered. A 135 * {@code null} value indicates that the elements' 136 * {@linkplain Comparable natural ordering} should be used. 137 * @return index of the search key, if it is contained in the array; 138 * otherwise, <code>(-(<i>insertion point</i>) - 1)</code>. The 139 * <i>insertion point</i> is defined as the point at which the 140 * key would be inserted into the array: the index of the first 141 * element greater than the key, or {@code a.length} if all 142 * elements in the array are less than the specified key. Note 143 * that this guarantees that the return value will be >= 0 if 144 * and only if the key is found. 145 * @throws ClassCastException if the array contains elements that are not 146 * <i>mutually comparable</i> using the specified comparator, 147 * or the search key is not comparable to the 148 * elements of the array using this comparator. 149 */ 150 public static int binarySearch(T)(T[] a, T key, Comparator!T c) 151 { 152 return binarySearch0!T(a, 0, cast(int)(a.length), key, c); 153 } 154 155 /** 156 * Searches a range of 157 * the specified array for the specified object using the binary 158 * search algorithm. 159 * The range must be sorted into ascending order 160 * according to the specified comparator (as by the 161 * {@link #sort(Object[], int, int, Comparator) 162 * sort(T[], int, int, Comparator)} 163 * method) prior to making this call. 164 * If it is not sorted, the results are undefined. 165 * If the range contains multiple elements equal to the specified object, 166 * there is no guarantee which one will be found. 167 * 168 * @param <T> the class of the objects in the array 169 * @param a the array to be searched 170 * @param fromIndex the index of the first element (inclusive) to be 171 * searched 172 * @param toIndex the index of the last element (exclusive) to be searched 173 * @param key the value to be searched for 174 * @param c the comparator by which the array is ordered. A 175 * {@code null} value indicates that the elements' 176 * {@linkplain Comparable natural ordering} should be used. 177 * @return index of the search key, if it is contained in the array 178 * within the specified range; 179 * otherwise, <code>(-(<i>insertion point</i>) - 1)</code>. The 180 * <i>insertion point</i> is defined as the point at which the 181 * key would be inserted into the array: the index of the first 182 * element in the range greater than the key, 183 * or {@code toIndex} if all 184 * elements in the range are less than the specified key. Note 185 * that this guarantees that the return value will be >= 0 if 186 * and only if the key is found. 187 * @throws ClassCastException if the range contains elements that are not 188 * <i>mutually comparable</i> using the specified comparator, 189 * or the search key is not comparable to the 190 * elements in the range using this comparator. 191 * @throws IllegalArgumentException 192 * if {@code fromIndex > toIndex} 193 * @throws ArrayIndexOutOfBoundsException 194 * if {@code fromIndex < 0 or toIndex > a.length} 195 */ 196 // public static int binarySearch(T)(T[] a, int fromIndex, int toIndex, T key, 197 // Comparator < ? super T > c) 198 // { 199 // rangeCheck(a.length, fromIndex, toIndex); 200 // return binarySearch0(a, fromIndex, toIndex, key, c); 201 // } 202 203 // Like public version, but without range checks. 204 private static int binarySearch0(T)(T[] a, int fromIndex, int toIndex, 205 T key, Comparator!T c) 206 { 207 if (c is null) 208 { 209 return binarySearch0!T(a, fromIndex, toIndex, key); 210 } 211 int low = fromIndex; 212 int high = toIndex - 1; 213 214 while (low <= high) 215 { 216 int mid = (low + high) >>> 1; 217 T midVal = a[mid]; 218 int cmp = c.compare(midVal, key); 219 if (cmp < 0) 220 low = mid + 1; 221 else if (cmp > 0) 222 high = mid - 1; 223 else 224 return mid; // key found 225 } 226 return - (low + 1); // key not found. 227 } 228 229 }