SUMO - Simulation of Urban MObility
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
MSVehicleContainer.cpp
Go to the documentation of this file.
1 /****************************************************************************/
9 // vehicles sorted by their departures
10 /****************************************************************************/
11 // SUMO, Simulation of Urban MObility; see http://sumo.sourceforge.net/
12 // Copyright (C) 2001-2012 DLR (http://www.dlr.de/) and contributors
13 /****************************************************************************/
14 //
15 // This file is part of SUMO.
16 // SUMO is free software: you can redistribute it and/or modify
17 // it under the terms of the GNU General Public License as published by
18 // the Free Software Foundation, either version 3 of the License, or
19 // (at your option) any later version.
20 //
21 /****************************************************************************/
22 
23 
24 // ===========================================================================
25 // included modules
26 // ===========================================================================
27 #ifdef _MSC_VER
28 #include <windows_config.h>
29 #else
30 #include <config.h>
31 #endif
32 
33 #include <algorithm>
34 #include <cassert>
35 #include <iterator>
36 #include "MSVehicle.h"
37 #include "MSVehicleContainer.h"
38 
39 #ifdef CHECK_MEMORY_LEAKS
40 #include <foreign/nvwa/debug_new.h>
41 #endif // CHECK_MEMORY_LEAKS
42 
43 
44 // ===========================================================================
45 // method definitions
46 // ===========================================================================
47 /* -------------------------------------------------------------------------
48  * methods from MSVehicleContainer::VehicleDepartureVectorSortCrit
49  * ----------------------------------------------------------------------- */
50 bool
51 MSVehicleContainer::VehicleDepartureVectorSortCrit::operator()
52 (const VehicleDepartureVector& e1, const VehicleDepartureVector& e2) const {
53  return e1.first < e2.first;
54 }
55 
56 
57 
58 /* -------------------------------------------------------------------------
59  * methods from MSVehicleContainer::DepartFinder
60  * ----------------------------------------------------------------------- */
62  : myTime(time) {}
63 
64 
65 bool
66 MSVehicleContainer::DepartFinder::operator()
67 (const VehicleDepartureVector& e) const {
68  return myTime + DELTA_T > e.first && myTime <= e.first;
69 }
70 
71 
72 
73 /* -------------------------------------------------------------------------
74  * methods from MSVehicleContainer
75  * ----------------------------------------------------------------------- */
77  : currentSize(0), array(capacity + 1, VehicleDepartureVector()) {}
78 
79 
81  // !!! vehicles are deleted in MSVehicle
82 }
83 
84 
85 void
87  // check whether a new item shall be added or the vehicle may be
88  // added to an existing list
89  VehicleHeap::iterator i =
90  find_if(array.begin() + 1, array.begin() + currentSize + 1, DepartFinder(veh->getParameter().depart));
91  if (currentSize == 0 || i == array.begin() + currentSize + 1) {
92  // a new heap-item is necessary
94  newElem.second.push_back(veh);
95  addReplacing(newElem);
96  } else {
97  // add vehicle to an existing heap-item
98  (*i).second.push_back(veh);
99  }
100 }
101 
102 
103 void
105  VehicleHeap::iterator j =
106  find_if(array.begin() + 1, array.begin() + currentSize + 1,
107  DepartFinder(time));
108  if (currentSize == 0 || j == array.begin() + currentSize + 1) {
109  VehicleDepartureVector newElem(time,
110  VehicleVector(cont));
111  addReplacing(newElem);
112  } else {
113  VehicleVector& stored = (*j).second;
114  stored.reserve(stored.size() + cont.size());
115  copy(cont.begin(), cont.end(), back_inserter(stored));
116  }
117 }
118 
119 
120 
121 void
123  if (isFull()) {
124  std::vector<VehicleDepartureVector> array2((array.size() - 1) * 2 + 1, VehicleDepartureVector());
125  for (size_t i = array.size(); i-- > 0;) {
126  assert(array2.size() > i);
127  array2[i] = array[i];
128  }
129  array = array2;
130  }
131 
132  // Percolate up
133  int hole = ++currentSize;
134  for (; hole > 1 && (x.first < array[ hole / 2 ].first); hole /= 2) {
135  assert(array.size() > (size_t) hole);
136  array[ hole ] = array[ hole / 2 ];
137  }
138  assert(array.size() > (size_t) hole);
139  array[ hole ] = x;
140 }
141 
142 
143 bool
145  VehicleHeap::const_iterator j =
146  find_if(array.begin() + 1, array.begin() + currentSize + 1, DepartFinder(time));
147  return j != array.begin() + currentSize + 1;
148 }
149 
150 
153  if (isEmpty()) {
154  throw 1;
155  }
156  assert(array.size() > 1);
157  return array[ 1 ].second;
158 }
159 
160 
161 SUMOTime
163  if (isEmpty()) {
164  throw 1;
165  }
166  assert(array.size() > 1);
167  return array[ 1 ].first;
168 }
169 
170 
171 void
173 
174 {
175  if (isEmpty()) {
176  throw 1;
177  }
178 
179  assert(array.size() > 1);
180  array[ 1 ] = array[ currentSize-- ];
181  percolateDown(1);
182 }
183 
184 
185 bool
187  return currentSize == 0;
188 }
189 
190 
191 bool
193  return currentSize >= ((int) array.size()) - 1;
194 }
195 
196 
197 void
199  int child;
200  assert(array.size() > (size_t)hole);
201  VehicleDepartureVector tmp = array[ hole ];
202 
203  for (; hole * 2 <= currentSize; hole = child) {
204  child = hole * 2;
205  if (child != currentSize && (array[ child + 1 ].first < array[ child ].first)) {
206  child++;
207  }
208  if ((array[ child ].first < tmp.first)) {
209  assert(array.size() > (size_t) hole);
210  array[ hole ] = array[ child ];
211  } else {
212  break;
213  }
214  }
215  assert(array.size() > (size_t) hole);
216  array[ hole ] = tmp;
217 }
218 
219 
220 size_t
222  return currentSize;
223 }
224 
225 
226 void
228  for (VehicleHeap::const_iterator i = array.begin() + 1; i != array.begin() + currentSize + 1; ++i) {
229  if (i != array.begin() + 1) {
230  std::cout << ", ";
231  }
232  std::cout << (*i).first;
233  }
234  std::cout << std::endl << "-------------------------" << std::endl;
235 }
236 
237 
238 std::ostream& operator << (std::ostream& strm, MSVehicleContainer& cont) {
239  strm << "------------------------------------" << std::endl;
240  while (!cont.isEmpty()) {
241  const MSVehicleContainer::VehicleVector& v = cont.top();
242  for (MSVehicleContainer::VehicleVector::const_iterator i = v.begin(); i != v.end(); ++i) {
243  strm << (*i)->getParameter().depart << std::endl;
244  }
245  cont.pop();
246  }
247  return strm;
248 }
249 
250 
251 
252 /****************************************************************************/
253