source: src/tests/searchsort.c@ 69efef81

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors deferred_resn demangler enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr no_list persistent-indexer pthread-emulation qualifiedEnum
Last change on this file since 69efef81 was 93cdd5c, checked in by Peter A. Buhr <pabuhr@…>, 8 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.