[73abe95] | 1 | // |
---|
[658f6de0] | 2 | // Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo |
---|
| 3 | // |
---|
| 4 | // The contents of this file are covered under the licence agreement in the |
---|
| 5 | // file "LICENCE" distributed with Cforall. |
---|
[73abe95] | 6 | // |
---|
[dc8511c] | 7 | // searchsort.cfa -- |
---|
[73abe95] | 8 | // |
---|
[658f6de0] | 9 | // Author : Peter A. Buhr |
---|
| 10 | // Created On : Thu Feb 4 18:17:50 2016 |
---|
| 11 | // Last Modified By : Peter A. Buhr |
---|
[5ea5b28] | 12 | // Last Modified On : Thu Dec 20 22:49:46 2018 |
---|
| 13 | // Update Count : 108 |
---|
[73abe95] | 14 | // |
---|
[658f6de0] | 15 | |
---|
[73abe95] | 16 | #include <fstream.hfa> |
---|
[200fcb3] | 17 | #include <stdlib.hfa> // bsearch, qsort |
---|
[f2cdc44] | 18 | #include <stdlib.h> // C version of bsearch |
---|
| 19 | |
---|
| 20 | int comp( const void * t1, const void * t2 ) { return *(int *)t1 < *(int *)t2 ? -1 : *(int *)t2 < *(int *)t1 ? 1 : 0; } |
---|
[658f6de0] | 21 | |
---|
| 22 | int main( void ) { |
---|
[73ac10e] | 23 | const int size = 10; |
---|
[658f6de0] | 24 | int iarr[size]; |
---|
| 25 | |
---|
[200fcb3] | 26 | sout | nlOff; // turn off auto newline |
---|
| 27 | |
---|
[73ac10e] | 28 | for ( i; 0 ~ size ) { |
---|
[658f6de0] | 29 | iarr[i] = size - i; |
---|
| 30 | sout | iarr[i] | ", "; |
---|
| 31 | } // for |
---|
[5ea5b28] | 32 | sout | nl | nl; |
---|
[f2cdc44] | 33 | |
---|
| 34 | // ascending sort/search by changing < to > |
---|
[658f6de0] | 35 | qsort( iarr, size ); |
---|
[73ac10e] | 36 | for ( i; 0 ~ size ) { |
---|
[658f6de0] | 37 | sout | iarr[i] | ", "; |
---|
| 38 | } // for |
---|
[200fcb3] | 39 | sout | nl; |
---|
[b81fd95] | 40 | for ( i; 0 ~ size ) { // C version, returns void* |
---|
[f2cdc44] | 41 | int key = size - i; |
---|
[b81fd95] | 42 | int * v = ( int * ) bsearch( &key, iarr, size, sizeof( iarr[0] ), comp ); |
---|
[9c47a47] | 43 | sout | key | ':' | *v | ", "; |
---|
[f2cdc44] | 44 | } // for |
---|
[200fcb3] | 45 | sout | nl; |
---|
[9c47a47] | 46 | |
---|
[73ac10e] | 47 | for ( i; 0 ~ size ) { |
---|
[9c47a47] | 48 | int * v = bsearch( size - i, iarr, size ); |
---|
| 49 | sout | size - i | ':' | *v | ", "; |
---|
[658f6de0] | 50 | } // for |
---|
[200fcb3] | 51 | sout | nl; |
---|
[73ac10e] | 52 | for ( i; 0 ~ size ) { |
---|
[707446a] | 53 | unsigned int posn = bsearch( size - i, iarr, size ); |
---|
[9c47a47] | 54 | sout | size - i | ':' | iarr[posn] | ", "; |
---|
[707446a] | 55 | } // for |
---|
[5ea5b28] | 56 | sout | nl | nl; |
---|
[658f6de0] | 57 | |
---|
[94980502] | 58 | // descending sort/search by changing < to > |
---|
[73ac10e] | 59 | for ( i; 0 ~ size ) { |
---|
[94980502] | 60 | iarr[i] = i + 1; |
---|
| 61 | sout | iarr[i] | ", "; |
---|
| 62 | } // for |
---|
[200fcb3] | 63 | sout | nl; |
---|
[94980502] | 64 | { |
---|
[73ac10e] | 65 | // redefinition of ?<? can't overlap the loop controls: |
---|
| 66 | { |
---|
| 67 | int (*?<?)(int, int) = ?>?; |
---|
| 68 | qsort( iarr, size ); |
---|
| 69 | } |
---|
| 70 | for ( i; 0 ~ size ) { |
---|
[94980502] | 71 | sout | iarr[i] | ", "; |
---|
| 72 | } // for |
---|
[200fcb3] | 73 | sout | nl; |
---|
[73ac10e] | 74 | for ( i; 0 ~ size ) { |
---|
| 75 | int (*?<?)(int, int) = ?>?; |
---|
[9c47a47] | 76 | int * v = bsearch( size - i, iarr, size ); |
---|
| 77 | sout | size - i | ':' | *v | ", "; |
---|
[94980502] | 78 | } // for |
---|
[200fcb3] | 79 | sout | nl; |
---|
[73ac10e] | 80 | for ( i; 0 ~ size ) { |
---|
| 81 | int (*?<?)(int, int) = ?>?; |
---|
[707446a] | 82 | unsigned int posn = bsearch( size - i, iarr, size ); |
---|
[9c47a47] | 83 | sout | size - i | ':' | iarr[posn] | ", "; |
---|
[707446a] | 84 | } // for |
---|
[94980502] | 85 | } |
---|
[5ea5b28] | 86 | sout | nl | nl; |
---|
[94980502] | 87 | |
---|
[658f6de0] | 88 | double darr[size]; |
---|
[73ac10e] | 89 | for ( i; 0 ~ size ) { |
---|
[658f6de0] | 90 | darr[i] = size - i + 0.5; |
---|
| 91 | sout | darr[i] | ", "; |
---|
| 92 | } // for |
---|
[200fcb3] | 93 | sout | nl; |
---|
[658f6de0] | 94 | qsort( darr, size ); |
---|
[73ac10e] | 95 | for ( i; 0 ~ size ) { |
---|
[658f6de0] | 96 | sout | darr[i] | ", "; |
---|
| 97 | } // for |
---|
[200fcb3] | 98 | sout | nl; |
---|
[73ac10e] | 99 | for ( i; 0 ~ size ) { |
---|
[9c47a47] | 100 | double * v = bsearch( size - i + 0.5, darr, size ); |
---|
| 101 | sout | size - i + 0.5 | ':' | *v | ", "; |
---|
[658f6de0] | 102 | } // for |
---|
[200fcb3] | 103 | sout | nl; |
---|
[73ac10e] | 104 | for ( i; 0 ~ size ) { |
---|
[707446a] | 105 | unsigned int posn = bsearch( size - i + 0.5, darr, size ); |
---|
[9c47a47] | 106 | sout | size - i + 0.5 | ':' | darr[posn] | ", "; |
---|
[707446a] | 107 | } // for |
---|
[5ea5b28] | 108 | sout | nl | nl; |
---|
[658f6de0] | 109 | |
---|
| 110 | struct S { int i, j; } sarr[size]; |
---|
| 111 | int ?<?( S t1, S t2 ) { return t1.i < t2.i && t1.j < t2.j; } |
---|
[09687aa] | 112 | ofstream & ?|?( ofstream & os, S v ) { return os | v.i | ' ' | v.j; } |
---|
[73ac10e] | 113 | for ( i; 0 ~ size ) { |
---|
[658f6de0] | 114 | sarr[i].i = size - i; |
---|
| 115 | sarr[i].j = size - i + 1; |
---|
| 116 | sout | sarr[i] | ", "; |
---|
| 117 | } // for |
---|
[200fcb3] | 118 | sout | nl; |
---|
[658f6de0] | 119 | qsort( sarr, size ); |
---|
[73ac10e] | 120 | for ( i; 0 ~ size ) { |
---|
[658f6de0] | 121 | sout | sarr[i] | ", "; |
---|
| 122 | } // for |
---|
[200fcb3] | 123 | sout | nl; |
---|
[73ac10e] | 124 | for ( i; 0 ~ size ) { |
---|
[658f6de0] | 125 | S temp = { size - i, size - i + 1 }; |
---|
[9c47a47] | 126 | S * v = bsearch( temp, sarr, size ); |
---|
| 127 | sout | temp | ':' | *v | ", "; |
---|
[658f6de0] | 128 | } // for |
---|
[200fcb3] | 129 | sout | nl; |
---|
[73ac10e] | 130 | for ( i; 0 ~ size ) { |
---|
[707446a] | 131 | S temp = { size - i, size - i + 1 }; |
---|
| 132 | unsigned int posn = bsearch( temp, sarr, size ); |
---|
[9c47a47] | 133 | sout | temp | ':' | sarr[posn] | ", "; |
---|
[707446a] | 134 | } // for |
---|
[5ea5b28] | 135 | sout | nl | nl; |
---|
[9c47a47] | 136 | { |
---|
[73ac10e] | 137 | int getKey( const S & s ) { return s.j; } |
---|
| 138 | for ( i; 0 ~ size ) { |
---|
[9c47a47] | 139 | sout | sarr[i] | ", "; |
---|
| 140 | } // for |
---|
[200fcb3] | 141 | sout | nl; |
---|
[73ac10e] | 142 | for ( i; 0 ~ size ) { |
---|
[9c47a47] | 143 | S * v = bsearch( size - i + 1, sarr, size ); |
---|
| 144 | sout | size - i + 1 | ':' | *v | ", "; |
---|
| 145 | } // for |
---|
[200fcb3] | 146 | sout | nl; |
---|
[73ac10e] | 147 | for ( i; 0 ~ size ) { |
---|
[9c47a47] | 148 | unsigned int posn = bsearch( size - i + 1, sarr, size ); |
---|
| 149 | sout | size - i + 1 | ':' | sarr[posn] | ", "; |
---|
| 150 | } // for |
---|
[5ea5b28] | 151 | sout | nl | nl; |
---|
[9c47a47] | 152 | } |
---|
[658f6de0] | 153 | } // main |
---|
| 154 | |
---|
| 155 | // Local Variables: // |
---|
| 156 | // tab-width: 4 // |
---|
[dc8511c] | 157 | // compile-command: "cfa searchsort.cfa" // |
---|
[658f6de0] | 158 | // End: // |
---|