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-sim.org/
12 // Copyright (C) 2001-2013 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 
VehicleHeap array
The vehicle vector heap.
SUMOTime topTime() const
Returns the time the uppermost vehicle vector is assigned to.
void percolateDown(int hole)
Moves the elements down.
DepartFinder(SUMOTime time)
constructor
bool isEmpty() const
Returns the information whether the container is empty.
std::vector< SUMOVehicle * > VehicleVector
definition of a list of vehicles which have the same departure time
int currentSize
Number of elements in heap.
void pop()
Removes the uppermost vehicle vector.
Representation of a vehicle.
Definition: SUMOVehicle.h:63
MSVehicleContainer(size_t capacity=10)
Constructor.
SUMOTime depart
The vehicle&#39;s departure time.
size_t size() const
Returns the size of the container.
void add(SUMOVehicle *veh)
Adds a single vehicle.
const VehicleVector & top()
Returns the uppermost vehicle vector.
bool anyWaitingFor(SUMOTime time) const
Returns the information whether any vehicles want to depart at the given time.
virtual const SUMOVehicleParameter & getParameter() const =0
Returns the vehicle&#39;s parameter (including departure definition)
int SUMOTime
Definition: SUMOTime.h:43
std::pair< SUMOTime, VehicleVector > VehicleDepartureVector
void showArray() const
Prints the container (the departure times)
#define DELTA_T
Definition: SUMOTime.h:50
std::ostream & operator<<(std::ostream &os, const MTRand &mtrand)
void addReplacing(const VehicleDepartureVector &cont)
Replaces the existing single departure time vector by the one given.
Searches for the VehicleDepartureVector with the wished depart.
~MSVehicleContainer()
Destructor.