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-2017 German Aerospace Center (DLR) and others.
4 /****************************************************************************/
5 //
6 // This program and the accompanying materials
7 // are made available under the terms of the Eclipse Public License v2.0
8 // which accompanies this distribution, and is available at
9 // http://www.eclipse.org/legal/epl-v20.html
10 //
11 /****************************************************************************/
19 // vehicles sorted by their departures
20 /****************************************************************************/
21 
22 
23 // ===========================================================================
24 // included modules
25 // ===========================================================================
26 #ifdef _MSC_VER
27 #include <windows_config.h>
28 #else
29 #include <config.h>
30 #endif
31 
32 #include <algorithm>
33 #include <cassert>
34 #include <iterator>
35 #include "MSVehicle.h"
36 #include "MSVehicleContainer.h"
37 
38 
39 // ===========================================================================
40 // method definitions
41 // ===========================================================================
42 /* -------------------------------------------------------------------------
43  * methods from MSVehicleContainer::VehicleDepartureVectorSortCrit
44  * ----------------------------------------------------------------------- */
45 bool
46 MSVehicleContainer::VehicleDepartureVectorSortCrit::operator()
47 (const VehicleDepartureVector& e1, const VehicleDepartureVector& e2) const {
48  return e1.first < e2.first;
49 }
50 
51 
52 
53 /* -------------------------------------------------------------------------
54  * methods from MSVehicleContainer::DepartFinder
55  * ----------------------------------------------------------------------- */
57  : myTime(time) {}
58 
59 
60 bool
61 MSVehicleContainer::DepartFinder::operator()
62 (const VehicleDepartureVector& e) const {
63  return myTime + DELTA_T > e.first && myTime <= e.first;
64 }
65 
66 
67 
68 /* -------------------------------------------------------------------------
69  * methods from MSVehicleContainer
70  * ----------------------------------------------------------------------- */
72  : currentSize(0), array(capacity + 1, VehicleDepartureVector()) {}
73 
74 
76  // !!! vehicles are deleted in MSVehicle
77 }
78 
79 
80 void
82  // check whether a new item shall be added or the vehicle may be
83  // added to an existing list
84  VehicleHeap::iterator i =
85  find_if(array.begin() + 1, array.begin() + currentSize + 1, DepartFinder(veh->getParameter().depart));
86  if (currentSize == 0 || i == array.begin() + currentSize + 1) {
87  // a new heap-item is necessary
89  newElem.second.push_back(veh);
90  addReplacing(newElem);
91  } else {
92  // add vehicle to an existing heap-item
93  (*i).second.push_back(veh);
94  }
95 }
96 
97 
98 void
100  // check whether a new item shall be added or the vehicle may be
101  // added to an existing list
102  VehicleHeap::iterator i =
103  find_if(array.begin() + 1, array.begin() + currentSize + 1, DepartFinder(veh->getParameter().depart));
104  if (!(currentSize == 0 || i == array.begin() + currentSize + 1)) {
105  // remove vehicle from an existing heap-item
106  (*i).second.erase(std::remove((*i).second.begin(), (*i).second.end(), veh), (*i).second.end());
107  }
108 }
109 
110 
111 void
113  VehicleHeap::iterator j =
114  find_if(array.begin() + 1, array.begin() + currentSize + 1,
115  DepartFinder(time));
116  if (currentSize == 0 || j == array.begin() + currentSize + 1) {
117  VehicleDepartureVector newElem(time,
118  VehicleVector(cont));
119  addReplacing(newElem);
120  } else {
121  VehicleVector& stored = (*j).second;
122  stored.reserve(stored.size() + cont.size());
123  copy(cont.begin(), cont.end(), back_inserter(stored));
124  }
125 }
126 
127 
128 
129 void
131  if (isFull()) {
132  std::vector<VehicleDepartureVector> array2((array.size() - 1) * 2 + 1, VehicleDepartureVector());
133  for (int i = (int)array.size(); i-- > 0;) {
134  assert(i < (int)array2.size());
135  array2[i] = array[i];
136  }
137  array = array2;
138  }
139 
140  // Percolate up
141  int hole = ++currentSize;
142  for (; hole > 1 && (x.first < array[ hole / 2 ].first); hole /= 2) {
143  assert((int)array.size() > hole);
144  array[hole] = array[ hole / 2 ];
145  }
146  assert((int)array.size() > hole);
147  array[hole] = x;
148 }
149 
150 
151 bool
153  return !isEmpty() && topTime() < time;
154 }
155 
156 
159  if (isEmpty()) {
160  throw 1;
161  }
162  assert(array.size() > 1);
163  return array[ 1 ].second;
164 }
165 
166 
167 SUMOTime
169  if (isEmpty()) {
170  throw 1;
171  }
172  assert(array.size() > 1);
173  return array[ 1 ].first;
174 }
175 
176 
177 void
179 
180 {
181  if (isEmpty()) {
182  throw 1;
183  }
184 
185  assert(array.size() > 1);
186  array[ 1 ] = array[ currentSize-- ];
187  percolateDown(1);
188 }
189 
190 
191 bool
193  return currentSize == 0;
194 }
195 
196 
197 bool
199  return currentSize >= ((int) array.size()) - 1;
200 }
201 
202 
203 void
205  int child;
206  assert((int)array.size() > hole);
207  VehicleDepartureVector tmp = array[ hole ];
208 
209  for (; hole * 2 <= currentSize; hole = child) {
210  child = hole * 2;
211  if (child != currentSize && (array[child + 1].first < array[child].first)) {
212  child++;
213  }
214  if ((array[ child ].first < tmp.first)) {
215  assert((int)array.size() > hole);
216  array[hole] = array[child];
217  } else {
218  break;
219  }
220  }
221  assert((int)array.size() > hole);
222  array[hole] = tmp;
223 }
224 
225 
226 int
228  return currentSize;
229 }
230 
231 
232 void
234  for (VehicleHeap::const_iterator i = array.begin() + 1; i != array.begin() + currentSize + 1; ++i) {
235  if (i != array.begin() + 1) {
236  std::cout << ", ";
237  }
238  std::cout << (*i).first;
239  }
240  std::cout << std::endl << "-------------------------" << std::endl;
241 }
242 
243 
244 std::ostream& operator << (std::ostream& strm, MSVehicleContainer& cont) {
245  strm << "------------------------------------" << std::endl;
246  while (!cont.isEmpty()) {
247  const MSVehicleContainer::VehicleVector& v = cont.top();
248  for (MSVehicleContainer::VehicleVector::const_iterator i = v.begin(); i != v.end(); ++i) {
249  strm << (*i)->getParameter().depart << std::endl;
250  }
251  cont.pop();
252  }
253  return strm;
254 }
255 
256 
257 
258 /****************************************************************************/
259 
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: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
long long int SUMOTime
Definition: TraCIDefs.h:51
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.