Eclipse SUMO - Simulation of Urban MObility
MSVehicleContainer.cpp
Go to the documentation of this file.
1 /****************************************************************************/
2 // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3 // Copyright (C) 2001-2019 German Aerospace Center (DLR) and others.
4 // This program and the accompanying materials
5 // are made available under the terms of the Eclipse Public License v2.0
6 // which accompanies this distribution, and is available at
7 // http://www.eclipse.org/legal/epl-v20.html
8 // SPDX-License-Identifier: EPL-2.0
9 /****************************************************************************/
17 // vehicles sorted by their departures
18 /****************************************************************************/
19 
20 
21 // ===========================================================================
22 // included modules
23 // ===========================================================================
24 #include <config.h>
25 
26 #include <algorithm>
27 #include <cassert>
28 #include <iterator>
29 #include "MSVehicle.h"
30 #include "MSVehicleContainer.h"
31 
32 
33 // ===========================================================================
34 // method definitions
35 // ===========================================================================
36 /* -------------------------------------------------------------------------
37  * methods from MSVehicleContainer::VehicleDepartureVectorSortCrit
38  * ----------------------------------------------------------------------- */
39 bool
40 MSVehicleContainer::VehicleDepartureVectorSortCrit::operator()
41 (const VehicleDepartureVector& e1, const VehicleDepartureVector& e2) const {
42  return e1.first < e2.first;
43 }
44 
45 
46 
47 /* -------------------------------------------------------------------------
48  * methods from MSVehicleContainer::DepartFinder
49  * ----------------------------------------------------------------------- */
51  : myTime(time) {}
52 
53 
54 bool
55 MSVehicleContainer::DepartFinder::operator()
56 (const VehicleDepartureVector& e) const {
57  return myTime + DELTA_T > e.first && myTime <= e.first;
58 }
59 
60 
61 
62 /* -------------------------------------------------------------------------
63  * methods from MSVehicleContainer
64  * ----------------------------------------------------------------------- */
66  : currentSize(0), array(capacity + 1, VehicleDepartureVector()) {}
67 
68 
70  // !!! vehicles are deleted in MSVehicle
71 }
72 
73 
74 void
76  // check whether a new item shall be added or the vehicle may be
77  // added to an existing list
78  VehicleHeap::iterator i =
79  find_if(array.begin() + 1, array.begin() + currentSize + 1, DepartFinder(veh->getParameter().depart));
80  if (currentSize == 0 || i == array.begin() + currentSize + 1) {
81  // a new heap-item is necessary
83  newElem.second.push_back(veh);
84  addReplacing(newElem);
85  } else {
86  // add vehicle to an existing heap-item
87  (*i).second.push_back(veh);
88  }
89 }
90 
91 
92 void
94  // check whether a new item shall be added or the vehicle may be
95  // added to an existing list
96  VehicleHeap::iterator i =
97  find_if(array.begin() + 1, array.begin() + currentSize + 1, DepartFinder(veh->getParameter().depart));
98  if (!(currentSize == 0 || i == array.begin() + currentSize + 1)) {
99  // remove vehicle from an existing heap-item
100  (*i).second.erase(std::remove((*i).second.begin(), (*i).second.end(), veh), (*i).second.end());
101  }
102 }
103 
104 
105 void
107  VehicleHeap::iterator j =
108  find_if(array.begin() + 1, array.begin() + currentSize + 1,
109  DepartFinder(time));
110  if (currentSize == 0 || j == array.begin() + currentSize + 1) {
111  VehicleDepartureVector newElem(time,
112  VehicleVector(cont));
113  addReplacing(newElem);
114  } else {
115  VehicleVector& stored = (*j).second;
116  stored.reserve(stored.size() + cont.size());
117  copy(cont.begin(), cont.end(), back_inserter(stored));
118  }
119 }
120 
121 
122 
123 void
125  if (isFull()) {
126  std::vector<VehicleDepartureVector> array2((array.size() - 1) * 2 + 1, VehicleDepartureVector());
127  for (int i = (int)array.size(); i-- > 0;) {
128  assert(i < (int)array2.size());
129  array2[i] = array[i];
130  }
131  array = array2;
132  }
133 
134  // Percolate up
135  int hole = ++currentSize;
136  for (; hole > 1 && (x.first < array[ hole / 2 ].first); hole /= 2) {
137  assert((int)array.size() > hole);
138  array[hole] = array[ hole / 2 ];
139  }
140  assert((int)array.size() > hole);
141  array[hole] = x;
142 }
143 
144 
145 bool
147  return !isEmpty() && topTime() < time;
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((int)array.size() > 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((int)array.size() > hole);
210  array[hole] = array[child];
211  } else {
212  break;
213  }
214  }
215  assert((int)array.size() > hole);
216  array[hole] = tmp;
217 }
218 
219 
220 int
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 
friend std::ostream & operator<<(std::ostream &strm, MSVehicleContainer &cont)
Prints the contents of the container.
long long int SUMOTime
Definition: SUMOTime.h:35
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:35
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:61
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.