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 /****************************************************************************/
16 // vehicles sorted by their departures
17 /****************************************************************************/
18 
19 
20 // ===========================================================================
21 // included modules
22 // ===========================================================================
23 #include <config.h>
24 
25 #include <algorithm>
26 #include <cassert>
27 #include <iterator>
28 #include "MSVehicle.h"
29 #include "MSVehicleContainer.h"
30 
31 
32 // ===========================================================================
33 // method definitions
34 // ===========================================================================
35 /* -------------------------------------------------------------------------
36  * methods from MSVehicleContainer::VehicleDepartureVectorSortCrit
37  * ----------------------------------------------------------------------- */
38 bool
39 MSVehicleContainer::VehicleDepartureVectorSortCrit::operator()
40 (const VehicleDepartureVector& e1, const VehicleDepartureVector& e2) const {
41  return e1.first < e2.first;
42 }
43 
44 
45 
46 /* -------------------------------------------------------------------------
47  * methods from MSVehicleContainer::DepartFinder
48  * ----------------------------------------------------------------------- */
50  : myTime(time) {}
51 
52 
53 bool
54 MSVehicleContainer::DepartFinder::operator()
55 (const VehicleDepartureVector& e) const {
56  return myTime + DELTA_T > e.first && myTime <= e.first;
57 }
58 
59 
60 
61 /* -------------------------------------------------------------------------
62  * methods from MSVehicleContainer
63  * ----------------------------------------------------------------------- */
65  : currentSize(0), array(capacity + 1, VehicleDepartureVector()) {}
66 
67 
69  // !!! vehicles are deleted in MSVehicle
70 }
71 
72 
73 void
75  // check whether a new item shall be added or the vehicle may be
76  // added to an existing list
77  VehicleHeap::iterator i =
78  find_if(array.begin() + 1, array.begin() + currentSize + 1, DepartFinder(veh->getParameter().depart));
79  if (currentSize == 0 || i == array.begin() + currentSize + 1) {
80  // a new heap-item is necessary
82  newElem.second.push_back(veh);
83  addReplacing(newElem);
84  } else {
85  // add vehicle to an existing heap-item
86  (*i).second.push_back(veh);
87  }
88 }
89 
90 
91 void
93  // check whether a new item shall be added or the vehicle may be
94  // added to an existing list
95  VehicleHeap::iterator i =
96  find_if(array.begin() + 1, array.begin() + currentSize + 1, DepartFinder(veh->getParameter().depart));
97  if (!(currentSize == 0 || i == array.begin() + currentSize + 1)) {
98  // remove vehicle from an existing heap-item
99  (*i).second.erase(std::remove((*i).second.begin(), (*i).second.end(), veh), (*i).second.end());
100  }
101 }
102 
103 
104 void
106  VehicleHeap::iterator j =
107  find_if(array.begin() + 1, array.begin() + currentSize + 1,
108  DepartFinder(time));
109  if (currentSize == 0 || j == array.begin() + currentSize + 1) {
110  VehicleDepartureVector newElem(time,
111  VehicleVector(cont));
112  addReplacing(newElem);
113  } else {
114  VehicleVector& stored = (*j).second;
115  stored.reserve(stored.size() + cont.size());
116  copy(cont.begin(), cont.end(), back_inserter(stored));
117  }
118 }
119 
120 
121 
122 void
124  if (isFull()) {
125  std::vector<VehicleDepartureVector> array2((array.size() - 1) * 2 + 1, VehicleDepartureVector());
126  for (int i = (int)array.size(); i-- > 0;) {
127  assert(i < (int)array2.size());
128  array2[i] = array[i];
129  }
130  array = array2;
131  }
132 
133  // Percolate up
134  int hole = ++currentSize;
135  for (; hole > 1 && (x.first < array[ hole / 2 ].first); hole /= 2) {
136  assert((int)array.size() > hole);
137  array[hole] = array[ hole / 2 ];
138  }
139  assert((int)array.size() > hole);
140  array[hole] = x;
141 }
142 
143 
144 bool
146  return !isEmpty() && topTime() < time;
147 }
148 
149 
152  if (isEmpty()) {
153  throw 1;
154  }
155  assert(array.size() > 1);
156  return array[ 1 ].second;
157 }
158 
159 
160 SUMOTime
162  if (isEmpty()) {
163  throw 1;
164  }
165  assert(array.size() > 1);
166  return array[ 1 ].first;
167 }
168 
169 
170 void
172 
173 {
174  if (isEmpty()) {
175  throw 1;
176  }
177 
178  assert(array.size() > 1);
179  array[ 1 ] = array[ currentSize-- ];
180  percolateDown(1);
181 }
182 
183 
184 bool
186  return currentSize == 0;
187 }
188 
189 
190 bool
192  return currentSize >= ((int) array.size()) - 1;
193 }
194 
195 
196 void
198  int child;
199  assert((int)array.size() > hole);
200  VehicleDepartureVector tmp = array[ hole ];
201 
202  for (; hole * 2 <= currentSize; hole = child) {
203  child = hole * 2;
204  if (child != currentSize && (array[child + 1].first < array[child].first)) {
205  child++;
206  }
207  if ((array[ child ].first < tmp.first)) {
208  assert((int)array.size() > hole);
209  array[hole] = array[child];
210  } else {
211  break;
212  }
213  }
214  assert((int)array.size() > hole);
215  array[hole] = tmp;
216 }
217 
218 
219 int
221  return currentSize;
222 }
223 
224 
225 void
227  for (VehicleHeap::const_iterator i = array.begin() + 1; i != array.begin() + currentSize + 1; ++i) {
228  if (i != array.begin() + 1) {
229  std::cout << ", ";
230  }
231  std::cout << (*i).first;
232  }
233  std::cout << std::endl << "-------------------------" << std::endl;
234 }
235 
236 
237 std::ostream& operator << (std::ostream& strm, MSVehicleContainer& cont) {
238  strm << "------------------------------------" << std::endl;
239  while (!cont.isEmpty()) {
240  const MSVehicleContainer::VehicleVector& v = cont.top();
241  for (MSVehicleContainer::VehicleVector::const_iterator i = v.begin(); i != v.end(); ++i) {
242  strm << (*i)->getParameter().depart << std::endl;
243  }
244  cont.pop();
245  }
246  return strm;
247 }
248 
249 
250 
251 /****************************************************************************/
252 
MSVehicleContainer::DepartFinder
Searches for the VehicleDepartureVector with the wished depart.
Definition: MSVehicleContainer.h:113
MSVehicleContainer.h
MSVehicleContainer::pop
void pop()
Removes the uppermost vehicle vector.
Definition: MSVehicleContainer.cpp:171
SUMOVehicle::getParameter
virtual const SUMOVehicleParameter & getParameter() const =0
Returns the vehicle's parameter (including departure definition)
DELTA_T
SUMOTime DELTA_T
Definition: SUMOTime.cpp:36
SUMOTime
long long int SUMOTime
Definition: SUMOTime.h:34
SUMOVehicle
Representation of a vehicle.
Definition: SUMOVehicle.h:60
MSVehicleContainer::currentSize
int currentSize
Number of elements in heap.
Definition: MSVehicleContainer.h:127
operator<<
std::ostream & operator<<(std::ostream &strm, MSVehicleContainer &cont)
Definition: MSVehicleContainer.cpp:237
MSVehicleContainer::MSVehicleContainer
MSVehicleContainer(int capacity=10)
Constructor.
Definition: MSVehicleContainer.cpp:64
MSVehicleContainer::addReplacing
void addReplacing(const VehicleDepartureVector &cont)
Replaces the existing single departure time vector by the one given.
Definition: MSVehicleContainer.cpp:123
SUMOVehicleParameter::depart
SUMOTime depart
Definition: SUMOVehicleParameter.h:482
MSVehicle.h
MSVehicleContainer::~MSVehicleContainer
~MSVehicleContainer()
Destructor.
Definition: MSVehicleContainer.cpp:68
MSVehicleContainer::remove
void remove(SUMOVehicle *veh)
Removes a single vehicle.
Definition: MSVehicleContainer.cpp:92
MSVehicleContainer::VehicleDepartureVector
std::pair< SUMOTime, VehicleVector > VehicleDepartureVector
Definition: MSVehicleContainer.h:53
MSVehicleContainer::topTime
SUMOTime topTime() const
Returns the time the uppermost vehicle vector is assigned to.
Definition: MSVehicleContainer.cpp:161
MSVehicleContainer::VehicleVector
std::vector< SUMOVehicle * > VehicleVector
definition of a list of vehicles which have the same departure time
Definition: MSVehicleContainer.h:49
MSVehicleContainer
Definition: MSVehicleContainer.h:46
MSVehicleContainer::array
VehicleHeap array
The vehicle vector heap.
Definition: MSVehicleContainer.h:133
MSVehicleContainer::isEmpty
bool isEmpty() const
Returns the information whether the container is empty.
Definition: MSVehicleContainer.cpp:185
MSVehicleContainer::size
int size() const
Returns the size of the container.
Definition: MSVehicleContainer.cpp:220
MSVehicleContainer::anyWaitingBefore
bool anyWaitingBefore(SUMOTime time) const
Returns the information whether any vehicles want to depart before the given time.
Definition: MSVehicleContainer.cpp:145
MSVehicleContainer::isFull
bool isFull() const
Definition: MSVehicleContainer.cpp:191
MSVehicleContainer::percolateDown
void percolateDown(int hole)
Moves the elements down.
Definition: MSVehicleContainer.cpp:197
config.h
MSVehicleContainer::top
const VehicleVector & top()
Returns the uppermost vehicle vector.
Definition: MSVehicleContainer.cpp:151
MSVehicleContainer::DepartFinder::DepartFinder
DepartFinder(SUMOTime time)
constructor
Definition: MSVehicleContainer.cpp:49
MSVehicleContainer::showArray
void showArray() const
Prints the container (the departure times)
Definition: MSVehicleContainer.cpp:226
MSVehicleContainer::add
void add(SUMOVehicle *veh)
Adds a single vehicle.
Definition: MSVehicleContainer.cpp:74