GTK+ IOStream  Beta
<< GTK+ >> add C++ IOStream operators to GTK+. Now with extra abilities ... like network serialisation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
HeapTreeSort.C
Go to the documentation of this file.
1 /* Copyright 2000-2013 Matt Flax <flatmax@flatmax.org>
2  This file is part of GTK+ IOStream class set
3 
4  GTK+ IOStream is free software; you can redistribute it and/or modify
5  it under the terms of the GNU General Public License as published by
6  the Free Software Foundation; either version 2 of the License, or
7  (at your option) any later version.
8 
9  GTK+ IOStream is distributed in the hope that it will be useful,
10  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  GNU General Public License for more details.
13 
14  You have received a copy of the GNU General Public License
15  along with GTK+ IOStream
16  */
17 #include "HeapTreeType.H"
18 #include "HeapTree.H"
19 #include <math.h>
20 #include <time.h>
21 
22 // random string generation function
23 string randomStrGen(int length) {
24  static string charset = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
25  string result;
26  result.resize(length);
27 
28  for (int i = 0; i < length; i++)
29  result[i] = charset[rand() % charset.length()];
30 
31  return result;
32 }
33 
34 // random number generation function
35 int findRand(int cnt){
36  int r=(int)round((float)(rand()-RAND_MAX/2)*2.0/(float)RAND_MAX*(float)cnt);
37  return r;
38 }
39 
40 int main(int argc, char *argv[]){
41 
42  int cnt=12; // the number of elements to sort
43 
44  HeapTreeType<int> ht; // the heap tree which will sort int types
45  ht.resize(cnt); // resize the heaptree (not necessary but more efficient)
46 
47  srand(time(NULL)); // generate a random seed
48 
49  // generate random numbers to sort
50  cout<<'\n'<<endl;
51  cout<<"sorting ints example\ninput : ";
52  for (int i=0;i<cnt;i++)
53  ht.add(findRand(cnt));
54  ht.dump(); // display the numbers
55  cout<<endl;
56 
57  ht.sort(); // sort the numbers
58 
59  cout<<"output : "; // display the sorted numbers
60  ht.dump();
61 
62  cout<<'\n'<<endl;
63  cout<<"sorting strings example\ninput : ";
64  HeapTree<string> hts; // create the HeapTree for string type
65  for (int i=0;i<cnt;i++){ // generate some random strings
66  string *tempS=new string(randomStrGen(4));
67  cout<<*tempS<<'\t';
68  hts.add(tempS, &string::compare); // add the string to the HeapTree
69  }
70  cout<<endl;
71 
72  hts.sort(&string::compare); // do the sorting
73 
74  cout<<"output : "; // dump the sorted strings to std output
75  hts.dumpDereference();
76  cout<<'\n'<<endl;
77 
78  hts.deleteElements();//cleanup
79 
80  // an example sorting a LinkList.
81  cout<<"sorting strings LinkList example\ninput : ";
83  for (int i=0;i<cnt;i++){ // generate some random strings
84  string *tempS=new string(randomStrGen(4));
85  cout<<*tempS<<'\t';
86  ll.add(tempS); // add the string to the LinkList.
87  }
88  cout<<endl;
89 
90  hts.sort(ll, &string::compare);
91 
92  cout<<"output : "; // dump the sorted strings to std output
93  ll.grab(1); ll.prev();
94  for (int i=0;i<ll.getCount(); i++)
95  cout<<*ll.next()<<'\t';
96  cout<<endl;
97 
98  //cleanup
99  while (ll.getCount())
100  delete ll.remove();
101 
102  return 0;
103 }