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
HeapTree.H
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 #ifndef HEAP_TREE_H_
18 #define HEAP_TREE_H_
19 
20 #include "HeapTreeType.H"
21 #include "LinkList.H"
22 
35 template<class HT_TYPE>
36 class HeapTree : public HeapTreeType<HT_TYPE*> {
40  typedef int(HT_TYPE::*HTCompareMethod)(const HT_TYPE&)const;
41 
48  void swapIfBigger(unsigned int index, HTCompareMethod compare){
49  HeapTreeCell childL, childR;
50  HeapTreeType<HT_TYPE*>::findChildren(index, childL, childR);
51  unsigned int indexL=HeapTreeType<HT_TYPE*>::findIndex(childL);
52  unsigned int indexR=HeapTreeType<HT_TYPE*>::findIndex(childR);
53  //cout<<"indexL "<<indexL<<"indexR "<<indexR<<endl;
54  int useIndexL=0, useIndexR=0;
55  int res;
57  // cout<<"indexL "<<(*(*this)[index])<<'\t'<<(*(*this)[indexL])<<'\t'<<(*(*this)[index].*compare)(*(*this)[indexL])<<endl;
58  if (((*(*this)[index]).*compare)(*(*this)[indexL])<0)
59  useIndexL=1;
60  }
62  // cout<<"indexR "<<*(*this)[index]<<'\t'<<*(*this)[indexR]<<'\t'<<(*(*this)[index].*compare)(*(*this)[indexR])<<endl;
63  if (((*(*this)[index]).*compare)(*(*this)[indexR])<0)
64  useIndexR=1;
65  }
66  if (useIndexR && useIndexL){
67  // cout<<"indexLR "<<*(*this)[indexL]<<'\t'<<*(*this)[indexR]<<'\t'<<(*(*this)[indexL].*compare)(*(*this)[indexR])<<endl;
68  if (((*(*this)[indexL]).*compare)(*(*this)[indexR])<0)
69  useIndexL=0;
70  else
71  useIndexR=0;
72  }
73  if (useIndexL){
74 // cout<<"before index indexL "<<*(*this)[index]<<'\t'<<*(*this)[indexL]<<'\t'<<(*(*this)[index].*compare)(*(*this)[indexL])<<endl;
75  HeapTreeType<HT_TYPE*>::swap(index,indexL);
76  // cout<<"after index indexL "<<*(*this)[index]<<'\t'<<*(*this)[indexL]<<'\t'<<(*(*this)[index].*compare)(*(*this)[indexL])<<endl;
77  swapIfBigger(indexL, compare);
78  }
79  if (useIndexR){
80  // cout<<"before index indexR "<<*(*this)[index]<<'\t'<<*(*this)[indexR]<<'\t'<<(*(*this)[index].*compare)(*(*this)[indexR])<<endl;
81  HeapTreeType<HT_TYPE*>::swap(index,indexR);
82  // cout<<"after index indexR "<<*(*this)[index]<<'\t'<<*(*this)[indexR]<<'\t'<<(*(*this)[index].*compare)(*(*this)[indexR])<<endl;
83  swapIfBigger(indexR, compare);
84  }
85  }
86 public:
87 
89  HeapTree(int baseIn=2) : HeapTreeType<HT_TYPE*>(baseIn) {
90  }
91 
92 
97  void add(HT_TYPE *value, HTCompareMethod compare){
99  if (HeapTreeType<HT_TYPE*>::unsortedCount+1>vector<HT_TYPE*>::size())
100  vector<HT_TYPE*>::resize(HeapTreeType<HT_TYPE*>::unsortedCount+1);
102  // bubble up
104  //this->dump(); cout<<endl;
105  while (index>0){
106  int parent=HeapTreeType<HT_TYPE*>::findParent(index);
107  if ((*(*this)[parent].*compare)(*(*this)[index])<0){
108  HeapTreeType<HT_TYPE*>::swap(parent, index);
109  index=parent;
110  //this->dump(); cout<<endl;
111  } else
112  break;
113  }
114  //this->dump(); cout<<endl;
115  }
116 
120  void sort(HTCompareMethod compare){
121  // store first and bubble up
122  unsigned int sizeOrig=HeapTreeType<HT_TYPE*>::unsortedCount;
124  unsigned int index=0;
126  swapIfBigger(index, compare);
128  //this->dump();
129 // cout<<"\tunsortedCount="<<HeapTreeType<HT_TYPE*>::unsortedCount<<endl;
130  }
131  }
132 
139  if (vector<HT_TYPE*>::size()!=ll.getCount()) // ensure the vector size matches
140  resize(ll.getCount());
141  while (ll.getCount()) // load the vector
142  add(ll.remove(),compare);
143  sort(compare); // sort
144  for (int i=0; i<vector<HT_TYPE*>::size(); i++) // unload the vector
145  ll.add((*this)[i]);
147  }
148 
151  void deleteElements(void){
152  for (int i=0;i<HeapTreeType<HT_TYPE*>::unsortedCount; i++){
153  delete (*this)[i];
154  (*this)[i]=NULL;
155  }
157  }
158 // /** Run through the vector and output (to cout) the HT_TYPE tree element.
159 // */
160 // void dump(){
161 // for (int i=0;i<(HeapTreeType<HT_TYPE*>::vector<HT_TYPE>::size());i++)
162 // cout<<*(HeapTreeType<HT_TYPE*>::vector<HT_TYPE>::operator[](i))<<'\t';
163 // }
164 
165 // HT_TYPE operator[](int i){
166 // return HeapTreeType<HT_TYPE*>::operator[](i);
167 // }
168 };
169 #endif //HEAP_TREE_H_
170