Geant4  10.03.p03
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
G4KDMap.cc
Go to the documentation of this file.
1 //
2 // ********************************************************************
3 // * License and Disclaimer *
4 // * *
5 // * The Geant4 software is copyright of the Copyright Holders of *
6 // * the Geant4 Collaboration. It is provided under the terms and *
7 // * conditions of the Geant4 Software License, included in the file *
8 // * LICENSE and available at http://cern.ch/geant4/license . These *
9 // * include a list of copyright holders. *
10 // * *
11 // * Neither the authors of this software system, nor their employing *
12 // * institutes,nor the agencies providing financial support for this *
13 // * work make any representation or warranty, express or implied, *
14 // * regarding this software system or assume any liability for its *
15 // * use. Please see the license in the file LICENSE and URL above *
16 // * for the full disclaimer and the limitation of liability. *
17 // * *
18 // * This code implementation is the result of the scientific and *
19 // * technical work of the GEANT4 collaboration. *
20 // * By using, copying, modifying or distributing the software (or *
21 // * any work based on the software) you agree to acknowledge its *
22 // * use in resulting scientific publications, and indicate your *
23 // * acceptance of all terms of the Geant4 Software license. *
24 // ********************************************************************
25 //
26 #include "G4KDMap.hh"
27 #include "globals.hh"
28 #include "G4KDNode.hh"
29 #include <algorithm>
30 
31 using namespace std;
32 
33 typedef std::deque<G4KDNode_Base*>::iterator _deq_iterator;
34 
36  G4KDNode_Base* const & rhs) //const
37 {
38  return (*lhs)[fDimension] < (*rhs)[fDimension];
39 }
40 
41 __1DSortOut::__1DSortOut(size_t dimension) :
42  fSortOutNDim(dimension)
43 {
44 }
45 
47  fContainer(right.fContainer), fSortOutNDim(right.fSortOutNDim)
48 {
49 }
50 
52 {
53  return fSortOutNDim.fDimension;
54 }
55 
56 G4KDNode_Base* __1DSortOut::GetMidle(size_t& main_middle)
57 {
58  size_t contSize = fContainer.size();
59  main_middle = (size_t) ceil(contSize / 2.); // ceil = round up
60  return fContainer[main_middle];
61 }
62 
64 {
65  return fContainer.insert(fContainer.end(), pos);
66 }
67 
69 {
70  size_t middle;
71  G4KDNode_Base* pos = GetMidle(middle);
72  _deq_iterator deq_pos = fContainer.begin() + middle;
73 
74  if(deq_pos == fContainer.end()) return 0; // this is a double check
75 
76  fContainer.erase(deq_pos);
77  return pos;
78 }
79 
81 {
82  sort(fContainer.begin(), fContainer.end(), fSortOutNDim);
83 }
84 
86 {
87  fContainer.erase(deq_pos);
88 }
89 
91 {
92  vector<_deq_iterator>& vit = fMap[pos];
93 
94  size_t maxSize = fSortOut.size();
95 
96  G4cout << "G4KDMap::Insert : " << maxSize << G4endl;
97 
98 
99  vit.reserve(maxSize);
100 
101  for (size_t i = 0; i < fSortOut.size(); ++i)
102  {
103  vit[i] = fSortOut[i].Insert(pos);
104 
105 // if(*(vit[i]) != pos)
106 // {
107 // G4cout << "insert wrong iterator" << G4endl;
108 // abort();
109 // }
110  }
111  /*
112  std::map<G4KDNode*, std::vector<_deq_iterator> >::iterator fMap_it
113  = fMap.begin();
114 
115  for( ; fMap_it != fMap.end() ; fMap_it++)
116  {
117  std::vector<_deq_iterator>& vit = fMap_it->second;
118 
119  G4KDNode* tmpNode = fMap_it->first;
120 
121  for(size_t i = 0 ; i < fSortOut.size() ; i++)
122  {
123  G4cout << "i = " << i << G4endl;
124  G4cout << "vit[i] = " << *(vit[i]) << G4endl;
125  if(*(vit[i]) != tmpNode)
126  {
127  G4cout << "!!!! Wrong iterator" << G4endl;
128  abort();
129  }
130  }
131 
132  }
133  */
134 
135  fIsSorted = false;
136 }
137 
139 {
140  G4cout << "_____________" << G4endl;
141  G4cout << "G4KDMap::PopOutMiddle ( "<< dimension << " )" << G4endl;
142 
143  if(fIsSorted == false) Sort();
144  G4KDNode_Base* output_node = fSortOut[dimension].PopOutMiddle();
145 
146  if(output_node == 0) return 0;
147 
148  G4cout << "output_node : " << output_node << G4endl;
149  G4cout << "output_node : " << output_node->GetAxis() << G4endl;
150 
151  std::map<G4KDNode_Base*, std::vector<_deq_iterator> >::iterator fMap_it
152  = fMap.find(output_node);
153 
154 
155  if(fMap_it == fMap.end())
156  {
157  G4cout << "fMap_it == fMap.end()" << G4endl;
158  G4cout << "output_node = " << output_node << G4endl;
159  return output_node;
160  }
161 
162  std::vector<_deq_iterator>& vit = fMap_it->second;
163 
164  /*
165  if(fMap_it->first != output_node)
166  {
167  G4cout << "fMap_it->first ! output_node"<< G4endl;
168  G4cout << "fMap_it->first = " << fMap_it->first << G4endl;
169  abort();
170  }
171  */
172 
173  for(size_t i = 0; i < fSortOut.size(); i++)
174  {
175  if(i != dimension)
176  {
177  G4cout << "i = " << i << G4endl;
178 
179  /*
180  // G4cout << "i = " << i << G4endl;
181  // G4cout << "vit[i] = " << *(vit[i]) << G4endl;
182  if(*(vit[i]) != output_node)
183  {
184  G4cout << "deleting wrong iterator" << G4endl;
185  abort();
186  }
187  */
188  fSortOut[i].Erase(vit[i]);
189  }
190  }
191 
192  fMap.erase(fMap_it);
193 
194  return output_node;
195 }
196 
198 {
199  for (size_t i = 0; i < fSortOut.size(); ++i)
200  {
201  fSortOut[i].Sort();
202  }
203 
204  fIsSorted = true;
205 }
std::deque< G4KDNode_Base * > fContainer
Definition: G4KDMap.hh:85
std::deque< G4KDNode_Base * >::iterator _deq_iterator
Definition: G4KDMap.cc:33
int GetAxis() const
Definition: G4KDNode.hh:83
G4KDNode_Base * PopOutMiddle(size_t dimension)
Definition: G4KDMap.cc:138
void Sort()
Definition: G4KDMap.cc:197
G4KDNode_Base * PopOutMiddle()
Definition: G4KDMap.cc:68
bool operator()(G4KDNode_Base *const &lhs, G4KDNode_Base *const &rhs)
Definition: G4KDMap.cc:35
G4GLOB_DLL std::ostream G4cout
void Erase(std::deque< G4KDNode_Base * >::iterator &)
Definition: G4KDMap.cc:85
__1DSortOut(size_t dimension)
Definition: G4KDMap.cc:41
sortOutNDim fSortOutNDim
Definition: G4KDMap.hh:86
std::deque< G4KDNode_Base * >::iterator Insert(G4KDNode_Base *)
Definition: G4KDMap.cc:63
int GetDimension()
Definition: G4KDMap.cc:51
G4KDNode_Base * GetMidle(size_t &)
Definition: G4KDMap.cc:56
#define G4endl
Definition: G4ios.hh:61
void Insert(G4KDNode_Base *pos)
Definition: G4KDMap.cc:90
void Sort()
Definition: G4KDMap.cc:80
static const G4double pos