1 /* Roy Keene 2 CS 2314 3 Section 04 4 Lab 07 5 22 Oct 02 6 lab9.cpp 7 */ 8 9 #include <stdlib.h> 10 #include <time.h> 11 #include <iostream> 12 #include <fstream> 13 #include <string> 14 15 using namespace std; 16 //#define _CS2314_LAB7_DUPLICATES 17 #include "sortedtype.h" 18 19 #ifndef _CS2314_LAB7_NUM_ITEMS 20 #define _CS2314_LAB7_NUM_ITEMS 500 21 #endif 22 23 #ifndef _CS2314_LAB7_OFILE 24 #define _CS2314_LAB7_OFILE "outFile" 25 #endif 26 27 int old_main(void); 28 int main(void) { 29 SortedType<int> m; 30 ofstream out(_CS2314_LAB7_OFILE); 31 int i, n, x, max, *tree, l, ol, f; 32 33 for (f=0;f<10;f++) { 34 srand(time(NULL)+max+rand()); 35 n=1+(int) (_CS2314_LAB7_NUM_ITEMS*(rand()/(RAND_MAX+1.0))); 36 n*=2; 37 max=n+(int) ((_CS2314_LAB7_NUM_ITEMS*3)*(rand()/(RAND_MAX+1.0))); 38 tree=new int[n]; 39 for (i=0;i<n;i++) { 40 ol=l=m.LengthIs(); 41 x=(int) (max*1.0*(rand()/(RAND_MAX+1.0))); 42 #ifndef _CS2314_LAB7_DUPLICATES 43 if (m.RetrieveItem(x)) { i--; continue; } 44 #endif 45 out << "Inserting " << x << "\n"; 46 m.InsertItem(x); 47 tree[i]=x; 48 if (!m.RetrieveItem(x)) { 49 out << "Error! Was unable to retrieve an item I just inserted: " << tree[i] << "\n"; 50 cerr << "Error! Was unable to retrieve an item I just inserted: " << tree[i] << "\n"; 51 } 52 l=m.LengthIs(); 53 if ((l-ol)!=1) cerr << "Error! Inserting caused an odd difference! [l-ol]=" << (l-ol) << "\n"; 54 } 55 out << "[" << (l=m.LengthIs()) << "] "; m.PrintList(out); 56 if (l!=n) { 57 out << "Error! Inserted " << n << " items, but only have " << l << " items there now!\n"; 58 cerr << "Error! Inserted " << n << " items, but only have " << l << " items there now!\n"; 59 } 60 for (i=0;i<n;i+=2) { 61 ol=l=m.LengthIs(); 62 out << "Removing " << tree[i] << "\n"; 63 m.DeleteItem(tree[i]); 64 l=m.LengthIs(); 65 if ((ol-l)!=1) { 66 out << "Error! Deleting caused an odd difference! [l-ol]=" << (l-ol) << "\n"; 67 cerr << "Error! Deleting caused an odd difference! [l-ol]=" << (l-ol) << "\n"; 68 } 69 #ifndef _CS2314_LAB7_DUPLICATES 70 if (m.RetrieveItem(tree[i])) { 71 out << "Error! I was able to retrieve an item I just deleted: " << tree[i] << "\n"; 72 cerr << "Error! I was able to retrieve an item I just deleted: " << tree[i] << "\n"; 73 } 74 #endif 75 } 76 out << "[" << (l=m.LengthIs()) << "] "; m.PrintList(out); 77 if (l!=(n/2)) { 78 out << "Error! Inserted " << (n/2) << " items, but only have " << l << " items there now!\n"; 79 cerr << "Error! Inserted " << (n/2) << " items, but only have " << l << " items there now!\n"; 80 } 81 for (i=0;i<n;i+=2) { 82 ol=l=m.LengthIs(); 83 x=(int) (max*1.0*(rand()/(RAND_MAX+1.0))); 84 #ifndef _CS2314_LAB7_DUPLICATES 85 if (m.RetrieveItem(x)) { i-=2; continue; } 86 #endif 87 out << "Inserting " << x << "\n"; 88 m.InsertItem(x); 89 tree[i]=x; 90 if (!m.RetrieveItem(x)) { 91 out << "Error! Was unable to retrieve an item I just inserted: " << tree[i] << "\n"; 92 cerr << "Error! Was unable to retrieve an item I just inserted: " << tree[i] << "\n"; 93 } 94 l=m.LengthIs(); 95 if ((l-ol)!=1) { 96 out << "Error! Inserting caused an odd difference! [l-ol]=" << (l-ol) << "\n"; 97 cerr << "Error! Inserting caused an odd difference! [l-ol]=" << (l-ol) << "\n"; 98 } 99 } 100 out << "[" << (l=m.LengthIs()) << "] "; m.PrintList(out); 101 if (l!=n) { 102 out << "Error! Inserted " << n << " items, but only have " << l << " items there now!\n"; 103 cerr << "Error! Inserted " << n << " items, but only have " << l << " items there now!\n"; 104 } 105 for (i=1;i<n;i+=2) { 106 ol=l=m.LengthIs(); 107 out << "Removing " << tree[i] << "\n"; 108 m.DeleteItem(tree[i]); 109 l=m.LengthIs(); 110 if ((ol-l)!=1) { 111 out << "Error! Deleting caused an odd difference! [l-ol]=" << (l-ol) << "\n"; 112 cerr << "Error! Deleting caused an odd difference! [l-ol]=" << (l-ol) << "\n"; 113 } 114 #ifndef _CS2314_LAB7_DUPLICATES 115 if (m.RetrieveItem(tree[i])) { 116 out << "Error! I was able to retrieve an item I just deleted: " << tree[i] << "\n"; 117 cerr << "Error! I was able to retrieve an item I just deleted: " << tree[i] << "\n"; 118 } 119 #endif 120 } 121 out << "[" << (l=m.LengthIs()) << "] "; m.PrintList(out); 122 if (l!=(n/2)) { 123 out << "Error! Inserted " << (n/2) << " items, but only have " << l << " items there now!\n"; 124 cerr << "Error! Inserted " << (n/2) << " items, but only have " << l << " items there now!\n"; 125 } 126 127 m.MakeEmpty(); 128 if (m.LengthIs()) { 129 out << "Error! MakeEmpty() did not make empty?! LengthIs()=" << m.LengthIs() << "\n"; 130 cerr << "Error! MakeEmpty() did not make empty?! LengthIs()=" << m.LengthIs() << "\n"; 131 } 132 133 delete tree; 134 } 135 136 out << "----------------\n"; 137 138 out.close(); 139 140 return(old_main()); 141 } 142 143 int old_main(void) { 144 SortedType<int> m1, m3; 145 SortedType<string> m2; 146 ofstream out(_CS2314_LAB7_OFILE, ios::app); 147 int tree1[]={5,1,10,-1,2,8,13,-2,0,3,7,9,11,12},dtree1[]={1,-2,5}; 148 string tree2[]={"test","joe","bob","a","sally","END"}, dtree2[]={"test"}; 149 int tree3[]={50,25,75,12,37,63,87,6,18,29,43,57,69,81,93}, dtree3[]={25,50,12,75,87}; 150 int a=3, ol, l; 151 unsigned int i; 152 153 154 for (i=0;i<(sizeof(tree1)/sizeof(int));i++) { 155 out << "Inserting " << tree1[i] << "\n"; 156 m1.InsertItem(tree1[i]); 157 } 158 159 if (m1.RetrieveItem(a)) { out << "Found "<< a <<"\n"; } else { out << "Did not find "<<a<<"\n"; } 160 a++; 161 if (m1.RetrieveItem(a)) { out << "Found "<< a <<"\n"; } else { out << "Did not find "<<a<<"\n"; } 162 a++; 163 if (m1.RetrieveItem(a)) { out << "Found "<< a <<"\n"; } else { out << "Did not find "<<a<<"\n"; } 164 165 166 out << "Current list is:\n"; 167 m1.PrintList(out); 168 out << "Length is : " << m1.LengthIs() << "\n"; 169 for (i=0;i<(sizeof(dtree1)/sizeof(int));i++) { 170 out << "Deleteing "<< dtree1[i] <<":\n"; 171 m1.DeleteItem(dtree1[i]); 172 m1.PrintList(out); 173 out << "Length is : " << m1.LengthIs() << "\n"; 174 } 175 out << "Making empty:\n"; 176 m1.MakeEmpty(); 177 m1.PrintList(out); 178 out << "Length is : " << m1.LengthIs() << "\n"; 179 out << "Inserting " << 3 << "\n"; 180 m1.InsertItem(3); 181 m1.PrintList(out); 182 out << "Length is : " << m1.LengthIs() << "\n"; 183 out << "Making empty:\n"; 184 m1.MakeEmpty(); 185 m1.PrintList(out); 186 out << "Length is : " << m1.LengthIs() << "\n"; 187 out << "----------------\n"; 188 189 for (i=0;i<(sizeof(tree3)/sizeof(int));i++) { 190 out << "Inserting " << tree3[i] << "\n"; 191 m3.InsertItem(tree3[i]); 192 } 193 m3.PrintList(out); 194 out << "Length is : " << (ol=m3.LengthIs()) << "\n"; 195 for (i=0;i<(sizeof(dtree3)/sizeof(int));i++) { 196 out << "Deleteing "<< dtree3[i] <<":\n"; 197 m3.DeleteItem(dtree3[i]); 198 m3.PrintList(out); 199 out << "Length is : " << (l=m3.LengthIs()) << "\n"; 200 ol--; 201 if (ol!=l) { 202 out << "Error! Length is " << l << " -- should be: " << ol << "\n"; 203 cerr << "Error! Length is " << l << " -- should be: " << ol << "\n"; 204 } 205 } 206 207 out << "----------------\n"; 208 209 for (i=0;i<(sizeof(tree2)/sizeof(string));i++) { 210 out << "Inserting " << tree2[i] << "\n"; 211 m2.InsertItem(tree2[i]); 212 } 213 m2.PrintList(out); 214 out << "Length is : " << (ol=m2.LengthIs()) << "\n"; 215 for (i=0;i<(sizeof(dtree2)/sizeof(int));i++) { 216 out << "Deleteing "<< dtree2[i] <<":\n"; 217 m2.DeleteItem(dtree2[i]); 218 m2.PrintList(out); 219 out << "Length is : " << (l=m2.LengthIs()) << "\n"; 220 ol--; 221 if (ol!=l) { 222 out << "Error! Length is " << l << " -- should be: " << ol << "\n"; 223 cerr << "Error! Length is " << l << " -- should be: " << ol << "\n"; 224 } 225 } 226 227 out << "----------------\n"; 228 229 out.close(); 230 231 return(0); 232 } |