1 /** 2 * This implement a search algorihm with heuristic. 3 * The algorithm first does a linear scan near the 4 * provided location. If nothing is found, then 5 * it switches to a binary search. 6 */ 7 module source.util.lookup; 8 9 uint lookup(alias f, uint N, T)(T[] items, uint needle, uint pivot) in { 10 assert(items.length > 0, "items must not be empty"); 11 assert(pivot < items.length); 12 } do { 13 return (needle > f(items[pivot])) 14 ? forwardLinearLookup!(f, N, binaryLookup)(items, needle, pivot) 15 : backwardLinearLookup!(f, N, binaryLookup)(items, needle, pivot); 16 } 17 18 unittest { 19 alias bl5 = lookup!(i => i, 5, uint); 20 21 uint[] items = [1, 3, 5, 7, 11, 13, 17, 23]; 22 23 assert(bl5(items, 5, 6) == 2); 24 assert(bl5(items, 16, 6) == 5); 25 assert(bl5(items, 4, 3) == 1); 26 assert(bl5(items, 2, 3) == 0); 27 assert(bl5(items, 1, 6) == 0); 28 assert(bl5(items, 1, 1) == 0); 29 assert(bl5(items, 5, 7) == 2); 30 assert(bl5(items, 3, 7) == 1); 31 assert(bl5(items, 22, 4) == 6); 32 assert(bl5(items, 23, 6) == 7); 33 assert(bl5(items, 42, 0) == 7); 34 } 35 36 private: 37 38 uint forwardLinearLookup(alias f, uint N, alias fallback, T)(T[] items, uint needle, uint first) in { 39 assert(items.length > 0, "items must not be empty"); 40 assert(first < items.length - 1, "first is out of bound"); 41 assert(needle >= f(items[first + 1]), "needle is before first"); 42 } do { 43 auto l = cast(uint) items.length; 44 45 uint stop = first + N + 2; 46 if (stop > l) { 47 stop = l; 48 } 49 50 auto i = first + 2; 51 if (i < l) do { 52 if (f(items[i]) > needle) { 53 return i - 1; 54 } 55 } while(++i != stop); 56 57 return fallback!f(items, needle, stop - 1, l); 58 } 59 60 unittest { 61 static uint testFallback(alias f, T)(T[], uint, uint, uint) { 62 return -1; 63 } 64 65 alias fll5 = forwardLinearLookup!(i => i, 5, testFallback, uint); 66 alias fll8 = forwardLinearLookup!(i => i, 8, testFallback, uint); 67 68 uint[] items = [1, 3, 5, 7, 11, 13, 17, 23]; 69 70 assert(fll5(items, 5, 0) == 2); 71 assert(fll5(items, 16, 0) == 5); 72 assert(fll5(items, 17, 0) == -1); 73 assert(fll5(items, 17, 1) == 6); 74 assert(fll8(items, 17, 0) == 6); 75 assert(fll8(items, 22, 0) == 6); 76 assert(fll5(items, 6, 1) == 2); 77 assert(fll5(items, 5, 1) == 2); 78 } 79 80 uint backwardLinearLookup(alias f, uint N, alias fallback, T)(T[] items, uint needle, uint last) in { 81 assert(items.length > 0, "items must not be empty"); 82 assert(last > 0 && last < items.length, "last is out of bound"); 83 assert(needle >= f(items[0]), "needle is before first"); 84 assert(needle < f(items[last]), "needle is past last"); 85 } do { 86 auto stop = (last < N) ? 0 : last - N; 87 88 auto i = last - 1; 89 do { 90 if (f(items[i]) <= needle) { 91 return i; 92 } 93 } while(i-- != stop); 94 95 return fallback!f(items, needle, 0, stop); 96 } 97 98 unittest { 99 static uint testFallback(alias f, T)(T[], uint, uint, uint) { 100 return -1; 101 } 102 103 alias bll5 = backwardLinearLookup!(i => i, 5, testFallback, uint); 104 alias bll8 = backwardLinearLookup!(i => i, 8, testFallback, uint); 105 106 uint[] items = [1, 3, 5, 7, 11, 13, 17, 23]; 107 108 assert(bll5(items, 5, 6) == 2); 109 assert(bll5(items, 16, 6) == 5); 110 assert(bll5(items, 4, 3) == 1); 111 assert(bll5(items, 2, 3) == 0); 112 assert(bll5(items, 1, 5) == 0); 113 assert(bll5(items, 2, 6) == -1); 114 assert(bll5(items, 5, 7) == 2); 115 assert(bll5(items, 4, 7) == -1); 116 assert(bll8(items, 3, 7) == 1); 117 } 118 119 uint binaryLookup(alias f, T)(T[] items, uint needle, uint min, uint max) in { 120 assert(items.length > 0, "items must not be empty"); 121 assert(needle >= f(items[min]), "needle is before first"); 122 assert(max == items.length || needle < f(items[max]), "needle is past last"); 123 } do { 124 min++; 125 while(min < max) { 126 auto i = (min + max - 1) / 2; 127 auto c = f(items[i]); 128 if (c == needle) { 129 return i; 130 } 131 132 if (c < needle) { 133 min = i + 1; 134 } else { 135 max = i; 136 } 137 } 138 139 return min - 1; 140 } 141 142 unittest { 143 alias bl = binaryLookup!(i => i, uint); 144 145 uint[] items = [1, 3, 5, 7, 11, 13, 17, 23]; 146 147 assert(bl(items, 5, 0, 6) == 2); 148 assert(bl(items, 16, 0, 6) == 5); 149 assert(bl(items, 4, 0, 3) == 1); 150 assert(bl(items, 2, 0, 3) == 0); 151 assert(bl(items, 1, 0, 6) == 0); 152 assert(bl(items, 5, 0, 7) == 2); 153 assert(bl(items, 3, 0, 7) == 1); 154 assert(bl(items, 22, 0, 7) == 6); 155 assert(bl(items, 23, 0, 8) == 7); 156 assert(bl(items, 42, 0, 8) == 7); 157 }