source: src/tests/searchsort.c @ 3205495

new-envwith_gc
Last change on this file since 3205495 was 93cdd5c, checked in by Peter A. Buhr <pabuhr@…>, 7 years ago

add lower/upper bound bsearch, and update bsearch and its test

  • Property mode set to 100644
File size: 4.2 KB
Line 
1//
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.
6//
7// searchsort.c --
8//
9// Author           : Peter A. Buhr
10// Created On       : Thu Feb  4 18:17:50 2016
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Tue Jan  2 08:01:17 2018
13// Update Count     : 100
14//
15
16#include <fstream>
17#include <stdlib>                                                                               // bsearch, qsort
18#include <stdlib.h>                                                                             // C version of bsearch
19
20int comp( const void * t1, const void * t2 ) { return *(int *)t1 < *(int *)t2 ? -1 : *(int *)t2 < *(int *)t1 ? 1 : 0; }
21
22int main( void ) {
23        const unsigned int size = 10;
24        int iarr[size];
25
26        for ( unsigned int i = 0; i < size; i += 1 ) {
27                iarr[i] = size - i;
28                sout | iarr[i] | ", ";
29        } // for
30        sout | endl | endl;
31
32        // ascending sort/search by changing < to >
33        qsort( iarr, size );
34        for ( unsigned int i = 0; i < size; i += 1 ) {
35                sout | iarr[i] | ", ";
36        } // for
37        sout | endl;
38        for ( unsigned int i = 0; i < size; i += 1 ) {          // C version
39                int key = size - i;
40                int * v = bsearch( &key, iarr, size, sizeof( iarr[0] ), comp );
41                sout | key | ':' | *v | ", ";
42        } // for
43        sout | endl;
44
45        for ( unsigned int i = 0; i < size; i += 1 ) {
46                int * v = bsearch( size - i, iarr, size );
47                sout | size - i | ':' | *v | ", ";
48        } // for
49        sout | endl;
50        for ( unsigned int i = 0; i < size; i += 1 ) {
51                unsigned int posn = bsearch( size - i, iarr, size );
52                sout | size - i | ':' | iarr[posn] | ", ";
53        } // for
54        sout | endl | endl;
55
56        // descending sort/search by changing < to >
57        for ( unsigned int i = 0; i < size; i += 1 ) {
58                iarr[i] = i + 1;
59                sout | iarr[i] | ", ";
60        } // for
61        sout | endl;
62        {
63                int ?<?( int x, int y ) { return x > y; }
64                qsort( iarr, size );
65                for ( unsigned int i = 0; i < size; i += 1 ) {
66                        sout | iarr[i] | ", ";
67                } // for
68                sout | endl;
69                for ( unsigned int i = 0; i < size; i += 1 ) {
70                        int * v = bsearch( size - i, iarr, size );
71                        sout | size - i | ':' | *v | ", ";
72                } // for
73                sout | endl;
74                for ( unsigned int i = 0; i < size; i += 1 ) {
75                        unsigned int posn = bsearch( size - i, iarr, size );
76                        sout | size - i | ':' | iarr[posn] | ", ";
77                } // for
78        }
79        sout | endl | endl;
80
81        double darr[size];
82        for ( unsigned int i = 0; i < size; i += 1 ) {
83                darr[i] = size - i + 0.5;
84                sout | darr[i] | ", ";
85        } // for
86        sout | endl;
87        qsort( darr, size );
88        for ( unsigned int i = 0; i < size; i += 1 ) {
89                sout | darr[i] | ", ";
90        } // for
91        sout | endl;
92        for ( unsigned int i = 0; i < size; i += 1 ) {
93                double * v = bsearch( size - i + 0.5, darr, size );
94                sout | size - i + 0.5 | ':' | *v | ", ";
95        } // for
96        sout | endl;
97        for ( unsigned int i = 0; i < size; i += 1 ) {
98                unsigned int posn = bsearch( size - i + 0.5, darr, size );
99                sout | size - i + 0.5 | ':' | darr[posn] | ", ";
100        } // for
101        sout | endl | endl;
102
103        struct S { int i, j; } sarr[size];
104        int ?<?( S t1, S t2 ) { return t1.i < t2.i && t1.j < t2.j; }
105        ofstream & ?|?( ofstream & os, S v ) { return os | v.i | ' ' | v.j; }
106        for ( unsigned int i = 0; i < size; i += 1 ) {
107                sarr[i].i = size - i;
108                sarr[i].j = size - i + 1;
109                sout | sarr[i] | ", ";
110        } // for
111        sout | endl;
112        qsort( sarr, size );
113        for ( unsigned int i = 0; i < size; i += 1 ) {
114                sout | sarr[i] | ", ";
115        } // for
116        sout | endl;
117        for ( unsigned int i = 0; i < size; i += 1 ) {
118                S temp = { size - i, size - i + 1 };
119                S * v = bsearch( temp, sarr, size );
120                sout | temp | ':' | *v | ", ";
121        } // for
122        sout | endl;
123        for ( unsigned int i = 0; i < size; i += 1 ) {
124                S temp = { size - i, size - i + 1 };
125                unsigned int posn = bsearch( temp, sarr, size );
126                sout | temp | ':' | sarr[posn] | ", ";
127        } // for
128        sout | endl | endl;
129        {
130                unsigned int getKey( const S & s ) { return s.j; }
131                for ( unsigned int i = 0; i < size; i += 1 ) {
132                        sout | sarr[i] | ", ";
133                } // for
134                sout | endl;
135                for ( unsigned int i = 0; i < size; i += 1 ) {
136                        S * v = bsearch( size - i + 1, sarr, size );
137                        sout | size - i + 1 | ':' | *v | ", ";
138                } // for
139                sout | endl;
140                for ( unsigned int i = 0; i < size; i += 1 ) {
141                        unsigned int posn = bsearch( size - i + 1, sarr, size );
142                        sout | size - i + 1 | ':' | sarr[posn] | ", ";
143                } // for
144                sout | endl | endl;
145        }
146} // main
147
148// Local Variables: //
149// tab-width: 4 //
150// compile-command: "cfa searchsort.c" //
151// End: //
Note: See TracBrowser for help on using the repository browser.