SUMO - Simulation of Urban MObility
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.dlr.de/
12 // Copyright (C) 2001-2016 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  // check whether a new item shall be added or the vehicle may be
106  // added to an existing list
107  VehicleHeap::iterator i =
108  find_if(array.begin() + 1, array.begin() + currentSize + 1, DepartFinder(veh->getParameter().depart));
109  if (!(currentSize == 0 || i == array.begin() + currentSize + 1)) {
110  // remove vehicle from an existing heap-item
111  (*i).second.erase(std::remove((*i).second.begin(), (*i).second.end(), veh), (*i).second.end());
112  }
113 }
114 
115 
116 void
118  VehicleHeap::iterator j =
119  find_if(array.begin() + 1, array.begin() + currentSize + 1,
120  DepartFinder(time));
121  if (currentSize == 0 || j == array.begin() + currentSize + 1) {
122  VehicleDepartureVector newElem(time,
123  VehicleVector(cont));
124  addReplacing(newElem);
125  } else {
126  VehicleVector& stored = (*j).second;
127  stored.reserve(stored.size() + cont.size());
128  copy(cont.begin(), cont.end(), back_inserter(stored));
129  }
130 }
131 
132 
133 
134 void
136  if (isFull()) {
137  std::vector<VehicleDepartureVector> array2((array.size() - 1) * 2 + 1, VehicleDepartureVector());
138  for (int i = (int)array.size(); i-- > 0;) {
139  assert(i < (int)array2.size());
140  array2[i] = array[i];
141  }
142  array = array2;
143  }
144 
145  // Percolate up
146  int hole = ++currentSize;
147  for (; hole > 1 && (x.first < array[ hole / 2 ].first); hole /= 2) {
148  assert(array.size() > (int) hole);
149  array[ hole ] = array[ hole / 2 ];
150  }
151  assert(array.size() > (int) hole);
152  array[ hole ] = x;
153 }
154 
155 
156 bool
158  return !isEmpty() && topTime() < time;
159 }
160 
161 
164  if (isEmpty()) {
165  throw 1;
166  }
167  assert(array.size() > 1);
168  return array[ 1 ].second;
169 }
170 
171 
172 SUMOTime
174  if (isEmpty()) {
175  throw 1;
176  }
177  assert(array.size() > 1);
178  return array[ 1 ].first;
179 }
180 
181 
182 void
184 
185 {
186  if (isEmpty()) {
187  throw 1;
188  }
189 
190  assert(array.size() > 1);
191  array[ 1 ] = array[ currentSize-- ];
192  percolateDown(1);
193 }
194 
195 
196 bool
198  return currentSize == 0;
199 }
200 
201 
202 bool
204  return currentSize >= ((int) array.size()) - 1;
205 }
206 
207 
208 void
210  int child;
211  assert(array.size() > (int)hole);
212  VehicleDepartureVector tmp = array[ hole ];
213 
214  for (; hole * 2 <= currentSize; hole = child) {
215  child = hole * 2;
216  if (child != currentSize && (array[ child + 1 ].first < array[ child ].first)) {
217  child++;
218  }
219  if ((array[ child ].first < tmp.first)) {
220  assert(array.size() > (int) hole);
221  array[ hole ] = array[ child ];
222  } else {
223  break;
224  }
225  }
226  assert(array.size() > (int) hole);
227  array[ hole ] = tmp;
228 }
229 
230 
231 int
233  return currentSize;
234 }
235 
236 
237 void
239  for (VehicleHeap::const_iterator i = array.begin() + 1; i != array.begin() + currentSize + 1; ++i) {
240  if (i != array.begin() + 1) {
241  std::cout << ", ";
242  }
243  std::cout << (*i).first;
244  }
245  std::cout << std::endl << "-------------------------" << std::endl;
246 }
247 
248 
249 std::ostream& operator << (std::ostream& strm, MSVehicleContainer& cont) {
250  strm << "------------------------------------" << std::endl;
251  while (!cont.isEmpty()) {
252  const MSVehicleContainer::VehicleVector& v = cont.top();
253  for (MSVehicleContainer::VehicleVector::const_iterator i = v.begin(); i != v.end(); ++i) {
254  strm << (*i)->getParameter().depart << std::endl;
255  }
256  cont.pop();
257  }
258  return strm;
259 }
260 
261 
262 
263 /****************************************************************************/
264 
friend std::ostream & operator<<(std::ostream &strm, MSVehicleContainer &cont)
Prints the contents of the container.
long long int SUMOTime
Definition: SUMOTime.h:43
VehicleHeap array
The vehicle vector heap.
void remove(SUMOVehicle *veh)
Removes a single vehicle.
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.
SUMOTime DELTA_T
Definition: SUMOTime.cpp:39
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:66
SUMOTime depart
The vehicle&#39;s departure time.
void add(SUMOVehicle *veh)
Adds a single vehicle.
const VehicleVector & top()
Returns the uppermost vehicle vector.
SUMOTime myTime
the searched departure time
MSVehicleContainer(int capacity=10)
Constructor.
int size() const
Returns the size of the container.
virtual const SUMOVehicleParameter & getParameter() const =0
Returns the vehicle&#39;s parameter (including departure definition)
std::pair< SUMOTime, VehicleVector > VehicleDepartureVector
bool anyWaitingBefore(SUMOTime time) const
Returns the information whether any vehicles want to depart before the given time.
void showArray() const
Prints the container (the departure times)
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.