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-2017 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 
40 // ===========================================================================
41 // method definitions
42 // ===========================================================================
43 /* -------------------------------------------------------------------------
44  * methods from MSVehicleContainer::VehicleDepartureVectorSortCrit
45  * ----------------------------------------------------------------------- */
46 bool
47 MSVehicleContainer::VehicleDepartureVectorSortCrit::operator()
48 (const VehicleDepartureVector& e1, const VehicleDepartureVector& e2) const {
49  return e1.first < e2.first;
50 }
51 
52 
53 
54 /* -------------------------------------------------------------------------
55  * methods from MSVehicleContainer::DepartFinder
56  * ----------------------------------------------------------------------- */
58  : myTime(time) {}
59 
60 
61 bool
62 MSVehicleContainer::DepartFinder::operator()
63 (const VehicleDepartureVector& e) const {
64  return myTime + DELTA_T > e.first && myTime <= e.first;
65 }
66 
67 
68 
69 /* -------------------------------------------------------------------------
70  * methods from MSVehicleContainer
71  * ----------------------------------------------------------------------- */
73  : currentSize(0), array(capacity + 1, VehicleDepartureVector()) {}
74 
75 
77  // !!! vehicles are deleted in MSVehicle
78 }
79 
80 
81 void
83  // check whether a new item shall be added or the vehicle may be
84  // added to an existing list
85  VehicleHeap::iterator i =
86  find_if(array.begin() + 1, array.begin() + currentSize + 1, DepartFinder(veh->getParameter().depart));
87  if (currentSize == 0 || i == array.begin() + currentSize + 1) {
88  // a new heap-item is necessary
90  newElem.second.push_back(veh);
91  addReplacing(newElem);
92  } else {
93  // add vehicle to an existing heap-item
94  (*i).second.push_back(veh);
95  }
96 }
97 
98 
99 void
101  // check whether a new item shall be added or the vehicle may be
102  // added to an existing list
103  VehicleHeap::iterator i =
104  find_if(array.begin() + 1, array.begin() + currentSize + 1, DepartFinder(veh->getParameter().depart));
105  if (!(currentSize == 0 || i == array.begin() + currentSize + 1)) {
106  // remove vehicle from an existing heap-item
107  (*i).second.erase(std::remove((*i).second.begin(), (*i).second.end(), veh), (*i).second.end());
108  }
109 }
110 
111 
112 void
114  VehicleHeap::iterator j =
115  find_if(array.begin() + 1, array.begin() + currentSize + 1,
116  DepartFinder(time));
117  if (currentSize == 0 || j == array.begin() + currentSize + 1) {
118  VehicleDepartureVector newElem(time,
119  VehicleVector(cont));
120  addReplacing(newElem);
121  } else {
122  VehicleVector& stored = (*j).second;
123  stored.reserve(stored.size() + cont.size());
124  copy(cont.begin(), cont.end(), back_inserter(stored));
125  }
126 }
127 
128 
129 
130 void
132  if (isFull()) {
133  std::vector<VehicleDepartureVector> array2((array.size() - 1) * 2 + 1, VehicleDepartureVector());
134  for (int i = (int)array.size(); i-- > 0;) {
135  assert(i < (int)array2.size());
136  array2[i] = array[i];
137  }
138  array = array2;
139  }
140 
141  // Percolate up
142  int hole = ++currentSize;
143  for (; hole > 1 && (x.first < array[ hole / 2 ].first); hole /= 2) {
144  assert((int)array.size() > hole);
145  array[hole] = array[ hole / 2 ];
146  }
147  assert((int)array.size() > hole);
148  array[hole] = x;
149 }
150 
151 
152 bool
154  return !isEmpty() && topTime() < time;
155 }
156 
157 
160  if (isEmpty()) {
161  throw 1;
162  }
163  assert(array.size() > 1);
164  return array[ 1 ].second;
165 }
166 
167 
168 SUMOTime
170  if (isEmpty()) {
171  throw 1;
172  }
173  assert(array.size() > 1);
174  return array[ 1 ].first;
175 }
176 
177 
178 void
180 
181 {
182  if (isEmpty()) {
183  throw 1;
184  }
185 
186  assert(array.size() > 1);
187  array[ 1 ] = array[ currentSize-- ];
188  percolateDown(1);
189 }
190 
191 
192 bool
194  return currentSize == 0;
195 }
196 
197 
198 bool
200  return currentSize >= ((int) array.size()) - 1;
201 }
202 
203 
204 void
206  int child;
207  assert((int)array.size() > hole);
208  VehicleDepartureVector tmp = array[ hole ];
209 
210  for (; hole * 2 <= currentSize; hole = child) {
211  child = hole * 2;
212  if (child != currentSize && (array[child + 1].first < array[child].first)) {
213  child++;
214  }
215  if ((array[ child ].first < tmp.first)) {
216  assert((int)array.size() > hole);
217  array[hole] = array[child];
218  } else {
219  break;
220  }
221  }
222  assert((int)array.size() > hole);
223  array[hole] = tmp;
224 }
225 
226 
227 int
229  return currentSize;
230 }
231 
232 
233 void
235  for (VehicleHeap::const_iterator i = array.begin() + 1; i != array.begin() + currentSize + 1; ++i) {
236  if (i != array.begin() + 1) {
237  std::cout << ", ";
238  }
239  std::cout << (*i).first;
240  }
241  std::cout << std::endl << "-------------------------" << std::endl;
242 }
243 
244 
245 std::ostream& operator << (std::ostream& strm, MSVehicleContainer& cont) {
246  strm << "------------------------------------" << std::endl;
247  while (!cont.isEmpty()) {
248  const MSVehicleContainer::VehicleVector& v = cont.top();
249  for (MSVehicleContainer::VehicleVector::const_iterator i = v.begin(); i != v.end(); ++i) {
250  strm << (*i)->getParameter().depart << std::endl;
251  }
252  cont.pop();
253  }
254  return strm;
255 }
256 
257 
258 
259 /****************************************************************************/
260 
friend std::ostream & operator<<(std::ostream &strm, MSVehicleContainer &cont)
Prints the contents of the container.
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:40
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:67
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
long long int SUMOTime
Definition: TraCIDefs.h:52
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.