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((int)array.size() > hole);
149  array[hole] = array[ hole / 2 ];
150  }
151  assert((int)array.size() > 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((int)array.size() > 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((int)array.size() > hole);
221  array[hole] = array[child];
222  } else {
223  break;
224  }
225  }
226  assert((int)array.size() > 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
int size() const
Returns the size of the container.
VehicleHeap array
The vehicle vector heap.
void remove(SUMOVehicle *veh)
Removes a single vehicle.
void percolateDown(int hole)
Moves the elements down.
DepartFinder(SUMOTime time)
constructor
SUMOTime DELTA_T
Definition: SUMOTime.cpp:39
bool isEmpty() const
Returns the information whether the container is empty.
bool anyWaitingBefore(SUMOTime time) const
Returns the information whether any vehicles want to depart before the given time.
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.
void showArray() const
Prints the container (the departure times)
const VehicleVector & top()
Returns the uppermost vehicle vector.
SUMOTime myTime
the searched departure time
MSVehicleContainer(int capacity=10)
Constructor.
virtual const SUMOVehicleParameter & getParameter() const =0
Returns the vehicle&#39;s parameter (including departure definition)
SUMOTime topTime() const
Returns the time the uppermost vehicle vector is assigned to.
std::pair< SUMOTime, VehicleVector > VehicleDepartureVector
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.