Changeset 788
- Timestamp:
- 07/07/08 23:12:47 (5 months ago)
- Files:
-
- trunk/phobos/std/algorithm.d (modified) (67 diffs)
Legend:
- Unmodified
- Added
- Removed
- Modified
- Copied
- Moved
trunk/phobos/std/algorithm.d
r743 r788 332 332 } 333 333 334 version (wyda)unittest334 unittest 335 335 { 336 336 int[] a = [ 3, 4 ]; … … 376 376 } 377 377 378 version(wyda)unittest378 unittest 379 379 { 380 380 int[] a = [ 10, 11, 12, 13, 14 ]; … … 421 421 Ranges[0] filter(alias pred, Ranges...)(Ranges rs) 422 422 { 423 alias unaryFun!(pred) fun; 423 424 typeof(return) result; 424 425 // Accumulate … … 427 428 foreach (it; begin(range) .. end(range)) // current input 428 429 { 429 if ( pred(*it)) result ~= *it;430 if (fun(*it)) result ~= *it; 430 431 } 431 432 } … … 433 434 } 434 435 435 Ranges[0] filter(string pred, Ranges...)(Ranges rs) 436 { 437 return .filter!(unaryFun!(pred), Ranges)(rs); 438 } 439 440 version (wyda) unittest 436 unittest 441 437 { 442 438 int[] a = [ 3, 4 ]; … … 471 467 // void inPlace(alias fun, Ranges...)(Ranges rs) 472 468 { 473 alias unaryFun!(fun ) f;474 foreach (j; begin(r) .. end(r)) f(*j);469 alias unaryFun!(fun, true) todo; 470 foreach (j; begin(r) .. end(r)) todo(*j); 475 471 foreach (i, x; rs) 476 472 { 477 foreach (j; begin(x) .. end(x)) f(*j);478 } 479 } 480 481 version (wyda)unittest473 foreach (j; begin(x) .. end(x)) todo(*j); 474 } 475 } 476 477 unittest 482 478 { 483 479 // fill with 42 … … 528 524 } 529 525 530 version (wyda)unittest526 unittest 531 527 { 532 528 Object obj1 = new Object; … … 622 618 } 623 619 624 version (wyda)unittest620 unittest 625 621 { 626 622 int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ]; … … 656 652 ---- 657 653 */ 658 Iterator!(Range) find(alias pred, Range, E)(Range haystack, E needle) 659 { 654 Iterator!(Range) find(alias pred = "a == b", Range, E)(Range haystack, E needle) 655 { 656 alias binaryFun!(pred) test; 657 // @@@BUG@@@ 660 658 //foreach (i; begin(haystack) .. end(haystack)) 661 659 for (auto i = begin(haystack); i != end(haystack); ++i) 662 660 { 663 if ( pred(*i, needle)) return i;661 if (test(*i, needle)) return i; 664 662 } 665 663 return end(haystack); 666 664 } 667 665 668 /// Ditto 669 Iterator!(Range) find(string pred = "a == b", Range, E)( 670 Range haystack, E needle) 671 { 672 return .find!(binaryFun!(pred), Range, E)(haystack, needle); 673 } 674 675 version (wyda) unittest 666 unittest 676 667 { 677 668 int[] a = [ 1, 2, 3 ]; … … 691 682 string[] s = [ "Hello", "world", "!" ]; 692 683 assert(find!("toupper(a) == toupper(b)")(s, "hello") == begin(s)); 693 } 694 695 version (wyda) unittest 684 685 static bool f(string a, string b) { return toupper(a) == toupper(b); } 686 assert(find!(f)(s, "hello") == begin(s)); 687 } 688 689 unittest 696 690 { 697 691 int[] a = [ 1, 2, 3, 2, 6 ]; … … 730 724 Iterator!(Range) find(alias pred, Range)(Range haystack) 731 725 { 726 alias unaryFun!(pred) predFun; 732 727 foreach (i; begin(haystack) .. end(haystack)) 733 728 { 734 if (pred (*i)) return i;729 if (predFun(*i)) return i; 735 730 } 736 731 return end(haystack); 737 732 } 738 733 739 /// Ditto 740 Iterator!(Range) find(string pred, Range)(Range haystack) 741 { 742 return find!(unaryFun!(pred), Range)(haystack); 743 } 744 745 version (wyda) unittest 734 unittest 746 735 { 747 736 auto a = [ 1, 2, 3 ]; … … 768 757 ---- 769 758 */ 770 Iterator!(Range1) findRange(alias pred , Range1, Range2)(771 Range1 seq, Range2 subseq)759 Iterator!(Range1) findRange(alias pred = "a == b", Range1, Range2) 760 (Range1 seq, Range2 subseq) 772 761 { 773 762 auto e1 = end(seq); … … 783 772 } 784 773 785 /// Ditto 786 Iterator!(Range1) findRange( 787 string pred = q{a == b}, Range1, Range2)(Range1 seq, Range2 subseq) 788 { 789 return .findRange!(binaryFun!(pred), Range1, Range2)(seq, subseq); 790 } 791 792 version (wyda) unittest 774 unittest 793 775 { 794 776 int[] a = [ -1, 0, 1, 2, 3, 4, 5 ]; … … 913 895 thread-safe storage so it is not rebuilt repeatedly. 914 896 */ 915 Iterator!(Range) findBoyerMoore(alias pred, Range)(Range seq, 916 Range subseq) 917 { 918 return BoyerMooreFinder!(pred, Range)(subseq).inspect(seq); 919 } 920 921 /// Ditto 922 Iterator!(Range) findBoyerMoore(string pred = q{a == b}, Range)( 923 Range seq, Range subseq) 924 { 925 return .findBoyerMoore!(binaryFun!(pred), Range)(seq, subseq); 926 } 927 928 version (wyda) unittest 929 { 930 debug(string) writefln("Boyer-Moore implementation version (wyda) unittest\n"); 897 Iterator!(Range) findBoyerMoore(alias pred = "a == b", Range) 898 (Range seq, Range subseq) 899 { 900 return BoyerMooreFinder!(binaryFun!(pred), Range)(subseq).inspect(seq); 901 } 902 903 unittest 904 { 931 905 string h = "/homes/aalexand/d/dmd/bin/../lib/libphobos.a(dmain2.o)" 932 906 "(.gnu.linkonce.tmain+0x74): In function `main' undefined reference" … … 960 934 ---- 961 935 */ 962 Iterator!(Range) findAdjacent(alias pred , Range)(Range r)936 Iterator!(Range) findAdjacent(alias pred = "a == b", Range)(Range r) 963 937 { 964 938 auto first = begin(r), last = end(r); … … 967 941 { 968 942 for (++next; next != last; ++first, ++next) 969 if ( pred(*first, *next)) return first;943 if (binaryFun!(pred)(*first, *next)) return first; 970 944 } 971 945 return last; 972 946 } 973 947 974 /// Ditto 975 Iterator!(Range) findAdjacent(string pred = q{a == b}, Range)(Range r) 976 { 977 return .findAdjacent!(binaryFun!(pred), Range)(r); 978 } 979 980 version (wyda) unittest 948 unittest 981 949 { 982 950 int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ]; … … 1003 971 ---- 1004 972 */ 1005 Iterator!(Range1) findAmong(alias pred , Range1, Range2)(973 Iterator!(Range1) findAmong(alias pred = "a == b", Range1, Range2)( 1006 974 Range1 seq, Range2 choices) 1007 975 { … … 1013 981 } 1014 982 1015 /// Ditto 1016 Iterator!(Range1) findAmong( 1017 string pred = q{a == b}, Range1, Range2)(Range1 seq, Range2 choices) 1018 { 1019 return .findAmong!(binaryFun!(pred), Range1, Range2)(seq, choices); 1020 } 1021 1022 version (wyda) unittest 983 unittest 1023 984 { 1024 985 int[] a = [ -1, 0, 2, 1, 2, 3, 4, 5 ]; … … 1026 987 assert(findAmong(a, b) == begin(a) + 2); 1027 988 assert(findAmong(b, [ 4, 6, 7 ]) == end(b)); 989 assert(findAmong!("a==b")(a, b) == begin(a) + 2); 990 assert(findAmong!("a==b")(b, [ 4, 6, 7 ]) == end(b)); 1028 991 } 1029 992 … … 1049 1012 ---- 1050 1013 */ 1051 Iterator!(Range1) findAmongSorted(alias less , Range1, Range2)(1014 Iterator!(Range1) findAmongSorted(alias less = "a < b", Range1, Range2)( 1052 1015 Range1 seq, in Range2 choices) 1053 1016 { 1054 assert(isSorted!(less)(choices)); 1017 alias binaryFun!(less) lessFun; // pun not intended 1018 assert(isSorted!(lessFun)(choices)); 1055 1019 foreach (i, e; seq) 1056 1020 { 1057 if (canFindSorted!(less )(choices, e)) return begin(seq) + i;1021 if (canFindSorted!(lessFun)(choices, e)) return begin(seq) + i; 1058 1022 } 1059 1023 return end(seq); 1060 1024 } 1061 1025 1062 /// Ditto 1063 Iterator!(Range1) findAmongSorted( 1064 string less = q{a < b}, Range1, Range2)(Range1 seq, in Range2 subseq) 1065 { 1066 return .findAmongSorted!(binaryFun!(less), Range1, Range2)(seq, subseq); 1067 } 1068 1069 version (wyda) unittest 1026 unittest 1070 1027 { 1071 1028 int[] a = [ -1, 0, 2, 1, 2, 3, 4, 5 ]; … … 1092 1049 ---- 1093 1050 */ 1094 bool canFind(alias pred , Range, E)(Range haystack, E needle)1051 bool canFind(alias pred = "a == b", Range, E)(Range haystack, E needle) 1095 1052 { 1096 1053 return find!(pred)(haystack, needle) != end(haystack); 1097 }1098 1099 /// Ditto1100 bool canFind(string pred = q{a == b}, Range, E)(Range haystack, E needle)1101 {1102 return find!(binaryFun!(pred), Range, E)(haystack, needle) != end(haystack);1103 1054 } 1104 1055 … … 1110 1061 1111 1062 /// Ditto 1112 bool canFind(string pred, Range)(Range haystack)1113 {1114 return find!(unaryFun!(pred))(haystack) != end(haystack);1115 }1116 1117 /// Ditto1118 1063 bool canFindAmong(alias pred, Range1, Range2)(Range1 seq, Range2 choices) 1119 1064 { 1120 1065 return findAmong!(pred)(seq, choices) != end(seq); 1121 }1122 1123 /// Ditto1124 bool canFindAmong(string pred, Range1, Range2)(Range1 seq, Range2 choices)1125 {1126 return findAmong!(binaryFun!(pred))(seq, choices) != end(seq);1127 1066 } 1128 1067 … … 1130 1069 bool canFindAmongSorted(alias pred, Range1, Range2)(Range1 seq, Range2 choices) 1131 1070 { 1132 return canFindAmongSorted!(pred)(seq, choices) != end(seq); 1133 } 1134 1135 /// Ditto 1136 bool canFindAmongSorted(string pred, Range1, Range2)( 1137 Range1 seq, Range2 choices) 1138 { 1139 return canFindAmongSorted!(pred)(seq, choices) != end(seq); 1071 return findAmongSorted!(pred)(seq, choices) != end(seq); 1140 1072 } 1141 1073 … … 1154 1086 */ 1155 1087 1156 size_t count(alias pred , Range, E)(Range r, E value)1157 { 1158 bool pred2(typeof(*begin(r)) a) { return pred(a, value); }1088 size_t count(alias pred = "a == b", Range, E)(Range r, E value) 1089 { 1090 bool pred2(typeof(*begin(r)) a) { return binaryFun!(pred)(a, value); } 1159 1091 return count!(pred2)(r); 1160 1092 } 1161 1093 1162 /// Ditto 1163 size_t count(string pred = "a == b", Range, E)( 1164 Range r, E value) 1165 { 1166 return count!(binaryFun!(pred), Range, E)(r, value); 1167 } 1168 1169 version (wyda) unittest 1094 unittest 1170 1095 { 1171 1096 int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ]; … … 1189 1114 foreach (i; begin(r) .. end(r)) 1190 1115 { 1191 if ( pred(*i)) ++result;1116 if (unaryFun!(pred)(*i)) ++result; 1192 1117 } 1193 1118 return result; 1194 1119 } 1195 1120 1196 /// Ditto 1197 size_t count(string pred, Range)(Range r) 1198 { 1199 return count!(unaryFun!(pred), Range)(r); 1200 } 1201 1202 version (wyda) unittest 1121 unittest 1203 1122 { 1204 1123 int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ]; … … 1231 1150 ---- 1232 1151 */ 1233 bool equal(alias pred , Range1, Range2)(Range1 r1, Range2 r2)1152 bool equal(alias pred = "a == b", Range1, Range2)(Range1 r1, Range2 r2) 1234 1153 { 1235 1154 if (r1.length != r2.length) return false; … … 1238 1157 } 1239 1158 1240 /// Ditto 1241 bool equal(string pred = q{a == b}, Range1, Range2)(Range1 r1, Range2 r2) 1242 { 1243 return equal!(binaryFun!(pred), Range1, Range2)(r1, r2); 1244 } 1245 1246 version (wyda) unittest 1159 unittest 1247 1160 { 1248 1161 int[] a = [ 1, 2, 4, 3]; … … 1307 1220 } 1308 1221 1309 version (wyda)unittest1222 unittest 1310 1223 { 1311 1224 int a = 5; … … 1382 1295 } 1383 1296 1384 version (wyda)unittest1297 unittest 1385 1298 { 1386 1299 int a = 5; … … 1420 1333 1421 1334 Tuple!(Iterator!(Range1), Iterator!(Range2)) 1422 mismatch(alias pred , Range1, Range2)(Range1 r1, Range2 r2)1335 mismatch(alias pred = "a == b", Range1, Range2)(Range1 r1, Range2 r2) 1423 1336 { 1424 1337 auto i1 = begin(r1), i2 = begin(r2), e1 = end(r1), e2 = end(r2); 1425 1338 for (; i1 != e1 && i2 != e2; ++i1, ++i2) 1426 1339 { 1427 if (! pred(*i1, *i2)) break;1340 if (!binaryFun!(pred)(*i1, *i2)) break; 1428 1341 } 1429 1342 return tuple(i1, i2); 1430 1343 } 1431 1344 1432 /// Ditto 1433 Tuple!(Iterator!(Range1), Iterator!(Range2)) 1434 mismatch(string pred = q{a == b}, Range1, Range2)(Range1 r1, Range2 r2) 1435 { 1436 return .mismatch!(binaryFun!(pred), Range1, Range2)(r1, r2); 1437 } 1438 1439 version (wyda) unittest 1345 unittest 1440 1346 { 1441 1347 // doc example … … 1660 1566 } 1661 1567 1662 version (wyda)unittest1568 unittest 1663 1569 { 1664 1570 assert(levenshteinDistance("a", "a") == 0); … … 1720 1626 } 1721 1627 1722 version (wyda)unittest1628 unittest 1723 1629 { 1724 1630 int[] a = [ 1, 5 ]; … … 1763 1669 foreach (s; begin(source) .. end(source)) 1764 1670 { 1765 if (! pred(*s)) continue;1671 if (!unaryFun!(pred)(*s)) continue; 1766 1672 if (t == te) enforce(false, 1767 1673 "copyIf: insufficient space in target range"); … … 1772 1678 } 1773 1679 1774 Range2 copyIf(string pred, Range1, Range2)(Range1 source, Range2 target) 1775 { 1776 return .copyIf!(unaryFun!(pred), Range1, Range2)(source, target); 1777 } 1778 1779 version (wyda) unittest 1680 unittest 1780 1681 { 1781 1682 int[] a = [ 1, 5 ]; … … 1853 1754 } 1854 1755 1855 version (wyda)unittest1756 unittest 1856 1757 { 1857 1758 int[] range = null; … … 1926 1827 } 1927 1828 1928 version (wyda)unittest1829 unittest 1929 1830 { 1930 1831 // doc example … … 2033 1934 } 2034 1935 2035 version (wyda)unittest1936 unittest 2036 1937 { 2037 1938 int[] arr = [ 1, 2, 3, 4, 5 ]; … … 2054 1955 ---- 2055 1956 */ 2056 Range eliminate(alias pred ,1957 Range eliminate(alias pred = "a == b", 2057 1958 SwapStrategy ss = SwapStrategy.semistable, 2058 1959 Range, Value)(Range r, Value v) 2059 1960 { 2060 1961 alias Iterator!(Range) It; 2061 bool comp(typeof(*It) a) { return ! pred(a, v); }1962 bool comp(typeof(*It) a) { return !binaryFun!(pred)(a, v); } 2062 1963 static void assignIterB(It a, It b) { *a = *b; } 2063 1964 return range(begin(r), 2064 partition!(comp, 2065 ss, assignIterB, Range)(r)); 2066 } 2067 2068 /// Ditto 2069 Range eliminate(string pred = "a == b", 2070 SwapStrategy ss = SwapStrategy.semistable, 2071 Range, Value)(Range r, Value v) 2072 { 2073 return .eliminate!(binaryFun!(pred), ss, Range, Value)(r, v); 2074 } 2075 2076 version (wyda) unittest 1965 partition!(comp, 1966 ss, assignIterB, Range)(r)); 1967 } 1968 1969 unittest 2077 1970 { 2078 1971 int[] arr = [ 1, 2, 3, 2, 4, 5, 2 ]; … … 2229 2122 } 2230 2123 2231 version (wyda)unittest // partition2124 unittest // partition 2232 2125 { 2233 2126 auto Arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; … … 2408 2301 BUGS: 2409 2302 2410 stable topN has not been implemented yet.2411 */ 2412 void topN(alias less ,2303 Stable topN has not been implemented yet. 2304 */ 2305 void topN(alias less = "a < b", 2413 2306 SwapStrategy ss = SwapStrategy.unstable, 2414 2307 alias iterSwap = .iterSwap, Range, It)(Range r, It nth) … … 2423 2316 auto pivot = b + (e - b) / 2; 2424 2317 auto pivotVal = *pivot; 2425 bool pred(ElementType!(Range) a) { return a < pivotVal; } 2318 bool pred(ElementType!(Range) a) 2319 { 2320 return binaryFun!(less)(a, pivotVal); 2321 } 2426 2322 iterSwap(pivot, e - 1); 2427 2323 pivot = partition!(pred, ss, iterSwap)(range(b, e)); … … 2433 2329 } 2434 2330 2435 /// Ditto 2436 void topN(string less = q{a < b}, 2437 SwapStrategy ss = SwapStrategy.unstable, 2438 alias iterSwap = .iterSwap, Range, It)(Range r, It nth) 2439 { 2440 return .topN!(binaryFun!(less), ss, iterSwap, Range, It)(r, nth); 2441 } 2442 2443 version (wyda) unittest 2331 unittest 2444 2332 { 2445 2333 scope(failure) writeln(stderr, "Failure testing algorithm"); … … 2500 2388 */ 2501 2389 2502 void sort(alias less , SwapStrategy ss = SwapStrategy.unstable,2390 void sort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, 2503 2391 alias iterSwap = .iterSwap, Range)(Range r) 2504 2392 { 2505 static if (is(typeof(less(*begin(r), *end(r))) == bool)) 2506 { 2507 sortImpl!(less, ss, iterSwap)(r); 2508 assert(isSorted!(less)(r)); 2393 alias binaryFun!(less) lessFun; 2394 static if (is(typeof(lessFun(*begin(r), *end(r))) == bool)) 2395 { 2396 sortImpl!(lessFun, ss, iterSwap)(r); 2397 assert(isSorted!(lessFun)(r)); 2509 2398 } 2510 2399 else 2511 2400 { 2512 static assert(false, typeof(&less).stringof); 2513 } 2514 } 2515 2516 /// Ditto 2517 void sort(string less = q{a < b}, SwapStrategy ss = SwapStrategy.unstable, 2518 alias iterSwap = .iterSwap, Range)(Range r) 2519 { 2520 return .sort!(binaryFun!(less), ss, iterSwap, Range)(r); 2521 } 2522 2523 version (wyda) unittest 2401 static assert(false, "Invalid predicate passed to sort"); 2402 } 2403 } 2404 2405 unittest 2524 2406 { 2525 2407 // sort using delegate … … 2699 2581 created. 2700 2582 */ 2701 void schwartzSort(alias transform, alias less ,2583 void schwartzSort(alias transform, alias less = "a < b", 2702 2584 SwapStrategy ss = SwapStrategy.unstable, Range)(Range r) 2703 2585 { … … 2720 2602 } 2721 2603 2722 /// Ditto 2723 void schwartzSort(alias transform, string less = q{a < b}, 2724 SwapStrategy ss = SwapStrategy.unstable, Range)(Range r) 2725 { 2726 return .schwartzSort!(transform, binaryFun!(less), ss, Range)(r); 2727 } 2728 2729 version (wyda) unittest 2604 unittest 2730 2605 { 2731 2606 static double entropy(double[] probs) { … … 2776 2651 ---- 2777 2652 */ 2778 void partialSort(alias less , SwapStrategy ss = SwapStrategy.unstable,2653 void partialSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, 2779 2654 alias iterSwap = .iterSwap, Range, It)(Range r, It mid) 2780 2655 { … … 2783 2658 } 2784 2659 2785 /// Ditto 2786 void partialSort(string less = "a < b", 2787 SwapStrategy ss = SwapStrategy.unstable, 2788 alias iterSwap = .iterSwap, Range, It)(Range r, It mid) 2789 { 2790 return .partialSort!(binaryFun!(less), ss, iterSwap, Range, It)(r, mid); 2791 } 2792 2793 version (wyda) unittest 2660 unittest 2794 2661 { 2795 2662 int[] a = [ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 ]; … … 2894 2761 SRange, TRange)(SRange source, TRange target) 2895 2762 { 2763 alias binaryFun!(less) lessFun; 2896 2764 static assert(ss == SwapStrategy.unstable, 2897 2765 "Stable indexing not yet implemented"); … … 2916 2784 bool indirectLess(TElem a, TElem b) 2917 2785 { 2918 return less (*index2iter(a), *index2iter(b));2786 return lessFun(*index2iter(a), *index2iter(b)); 2919 2787 } 2920 2788 void indirectCopy(SIter from, ref TElem to) … … 2952 2820 for (; sb != se; ++sb) 2953 2821 { 2954 if (!less (*sb, *index2iter(*tb))) continue;2822 if (!lessFun(*sb, *index2iter(*tb))) continue; 2955 2823 // copy the source over the smallest 2956 2824 indirectCopy(sb, *tb); … … 3027 2895 } 3028 2896 3029 /// Ditto 3030 void partialIndex( 3031 string less, 3032 SwapStrategy ss = SwapStrategy.unstable, 3033 alias iterSwap = .iterSwap, 3034 SRange, TRange)(SRange source, TRange target) 3035 { 3036 return .topNIndexImpl!(binaryFun!(less), true, ss, iterSwap)(source, target); 3037 } 3038 3039 version (wyda) unittest 2897 unittest 3040 2898 { 3041 2899 invariant arr = [ 2, 3, 1 ]; … … 3046 2904 } 3047 2905 3048 version (wyda)unittest2906 unittest 3049 2907 { 3050 2908 static bool less(int a, int b) { return a < b; } … … 3224 3082 ---- 3225 3083 */ 3226 Iterator!(Range) lowerBound(alias less, Range, V)(Range r, V value) 3227 { 3228 //assert(isSorted!(less)(r)); 3084 Iterator!(Range) lowerBound(alias less = "a < b", Range, V)(Range r, V value) 3085 { 3229 3086 auto first = begin(r); 3230 3087 auto count = end(r) - first; … … 3233 3090 invariant step = count / 2; 3234 3091 auto it = first + step; 3235 if ( less(*it, value))3092 if (binaryFun!(less)(*it, value)) 3236 3093 { 3237 3094 first = it + 1; … … 3246 3103 } 3247 3104 3248 /// Ditto 3249 Iterator!(Range) lowerBound(string less = q{a < b}, Range, V)(Range r, V value) 3250 { 3251 return .lowerBound!(binaryFun!(less), Range, V)(r, value); 3252 } 3253 3254 version (wyda) unittest 3105 unittest 3255 3106 { 3256 3107 int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]; … … 3283 3134 ---- 3284 3135 */ 3285 Iterator!(Range) upperBound(alias less, Range, V)(Range r, V value) 3286 { 3287 //assert(isSorted!(less)(r)); 3136 Iterator!(Range) upperBound(alias less = "a < b", Range, V)(Range r, V value) 3137 { 3288 3138 auto first = begin(r); 3289 3139 size_t count = end(r) - first; … … 3292 3142 auto step = count / 2; 3293 3143 auto it = first + step; 3294 if (! less(value,*it))3144 if (!binaryFun!(less)(value,*it)) 3295 3145 { 3296 3146 first = it + 1; … … 3302 3152 } 3303 3153 3304 /// Ditto 3305 Iterator!(Range) upperBound(string less = q{a < b}, Range, V)(Range r, V value) 3306 { 3307 return .upperBound!(binaryFun!(less), Range, V)(r, value); 3308 } 3309 3310 version (wyda) unittest 3154 unittest 3311 3155 { 3312 3156 auto a = [ 1, 2, 3, 3, 3, 4, 4, 5, 6 ]; … … 3338 3182 ---- 3339 3183 */ 3340 Range equalRange(alias less , Range, V)(Range r, V value)3341 { 3342 //assert(isSorted!(less)(r));3184 Range equalRange(alias less = "a < b", Range, V)(Range r, V value) 3185 { 3186 alias binaryFun!(less) lessFun; 3343 3187 auto first = begin(r), last = end(r); 3344 3188 for (size_t count = last - first; count > 0; ) … … 3346 3190 auto step = count / 2; 3347 3191 auto middle = first + step; 3348 if (less (*middle, value))3192 if (lessFun(*middle, value)) 3349 3193 { 3350 3194 first = middle + 1; 3351 3195 count -= step + 1; 3352 3196 } 3353 else if (less (value, *middle))3197 else if (lessFun(value, *middle)) 3354 3198 { 3355 3199 count = step; … … 3367 3211 } 3368 3212 3369 /// Ditto 3370 Range equalRange(string less = q{a < b}, Range, V)(Range r, V value) 3371 { 3372 return .equalRange!(binaryFun!(less), Range, V)(r, value); 3373 } 3374 3375 version (wyda) unittest 3213 unittest 3376 3214 { 3377 3215 int[] a = [ 1, 2, 3, 3, 3, 4, 4, 5, 6 ]; … … 3392 3230 */ 3393 3231 3394 bool canFindSorted(alias less , T, V)(T range, V value)3232 bool canFindSorted(alias less = "a < b", T, V)(T range, V value) 3395 3233 { 3396 3234 auto p = lowerBound!(less)(range, value); 3397 return p != end(range) && !less(value, *p); 3398 } 3399 3400 bool canFindSorted(string less = q{a < b}, T, V)(T range, V value) 3401 { 3402 return .canFindSorted!(binaryFun!(less), T, V)(range, value); 3403 } 3404 3405 version (wyda) unittest 3235 return p != end(range) && !binaryFun!(less)(value, *p); 3236 } 3237 3238 unittest 3406 3239 { 3407 3240 auto a = rndstuff!(int); … … 3419 3252 */ 3420 3253 3421 void makeHeap(alias less , alias iterSwap = .iterSwap, Range)(Range r)3254 void makeHeap(alias less = "a < b", alias iterSwap = .iterSwap, Range)(Range r) 3422 3255 { 3423 3256 if (r.length < 2) return; … … 3430 3263 } 3431 3264 3432 version (wyda)unittest3265 unittest 3433 3266 { 3434 3267 // example from "Introduction to Algorithms" Cormen et al., p 146 … … 3461 3294 } 3462 3295 3463 version (wyda)unittest3296 unittest 3464 3297 { 3465 3298 // example from "Introduction to Algorithms" Cormen et al., p 143 … … 3529 3362 } 3530 3363 3531 version (wyda)unittest3364 unittest 3532 3365 { 3533 3366 auto r = Random(unpredictableSeed); … … 3542 3375 // Internal random array generators 3543 3376 3544 version (wyda) version(unittest)3377 version(unittest) 3545 3378 { 3546 3379 private enum size_t maxArraySize = 50;