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  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 (int i = (int)array.size(); i-- > 0;) {
126  assert(i < (int)array2.size());
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  return !isEmpty() && topTime() < time;
146 }
147 
148 
151  if (isEmpty()) {
152  throw 1;
153  }
154  assert(array.size() > 1);
155  return array[ 1 ].second;
156 }
157 
158 
159 SUMOTime
161  if (isEmpty()) {
162  throw 1;
163  }
164  assert(array.size() > 1);
165  return array[ 1 ].first;
166 }
167 
168 
169 void
171 
172 {
173  if (isEmpty()) {
174  throw 1;
175  }
176 
177  assert(array.size() > 1);
178  array[ 1 ] = array[ currentSize-- ];
179  percolateDown(1);
180 }
181 
182 
183 bool
185  return currentSize == 0;
186 }
187 
188 
189 bool
191  return currentSize >= ((int) array.size()) - 1;
192 }
193 
194 
195 void
197  int child;
198  assert(array.size() > (size_t)hole);
199  VehicleDepartureVector tmp = array[ hole ];
200 
201  for (; hole * 2 <= currentSize; hole = child) {
202  child = hole * 2;
203  if (child != currentSize && (array[ child + 1 ].first < array[ child ].first)) {
204  child++;
205  }
206  if ((array[ child ].first < tmp.first)) {
207  assert(array.size() > (size_t) hole);
208  array[ hole ] = array[ child ];
209  } else {
210  break;
211  }
212  }
213  assert(array.size() > (size_t) hole);
214  array[ hole ] = tmp;
215 }
216 
217 
218 size_t
220  return currentSize;
221 }
222 
223 
224 void
226  for (VehicleHeap::const_iterator i = array.begin() + 1; i != array.begin() + currentSize + 1; ++i) {
227  if (i != array.begin() + 1) {
228  std::cout << ", ";
229  }
230  std::cout << (*i).first;
231  }
232  std::cout << std::endl << "-------------------------" << std::endl;
233 }
234 
235 
236 std::ostream& operator << (std::ostream& strm, MSVehicleContainer& cont) {
237  strm << "------------------------------------" << std::endl;
238  while (!cont.isEmpty()) {
239  const MSVehicleContainer::VehicleVector& v = cont.top();
240  for (MSVehicleContainer::VehicleVector::const_iterator i = v.begin(); i != v.end(); ++i) {
241  strm << (*i)->getParameter().depart << std::endl;
242  }
243  cont.pop();
244  }
245  return strm;
246 }
247 
248 
249 
250 /****************************************************************************/
251 
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.
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:65
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.
SUMOTime myTime
the searched departure time
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.