Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2024 German Aerospace Center (DLR) and others.
4 : // This program and the accompanying materials are made available under the
5 : // terms of the Eclipse Public License 2.0 which is available at
6 : // https://www.eclipse.org/legal/epl-2.0/
7 : // This Source Code may also be made available under the following Secondary
8 : // Licenses when the conditions for such availability set forth in the Eclipse
9 : // Public License 2.0 are satisfied: GNU General Public License, version 2
10 : // or later which is available at
11 : // https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
12 : // SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
13 : /****************************************************************************/
14 : /// @file MSVehicleContainer.cpp
15 : /// @author Christian Roessel
16 : /// @author Daniel Krajzewicz
17 : /// @author Michael Behrisch
18 : /// @date Mon, 12 Mar 2001
19 : ///
20 : // vehicles sorted by their departures
21 : /****************************************************************************/
22 : #include <config.h>
23 :
24 : #include <algorithm>
25 : #include <cassert>
26 : #include <iterator>
27 : #include "MSVehicle.h"
28 : #include "MSVehicleContainer.h"
29 :
30 :
31 : // ===========================================================================
32 : // method definitions
33 : // ===========================================================================
34 : /* -------------------------------------------------------------------------
35 : * methods from MSVehicleContainer::VehicleDepartureVectorSortCrit
36 : * ----------------------------------------------------------------------- */
37 : bool
38 0 : MSVehicleContainer::VehicleDepartureVectorSortCrit::operator()
39 : (const VehicleDepartureVector& e1, const VehicleDepartureVector& e2) const {
40 0 : return e1.first < e2.first;
41 : }
42 :
43 :
44 :
45 : /* -------------------------------------------------------------------------
46 : * methods from MSVehicleContainer::DepartFinder
47 : * ----------------------------------------------------------------------- */
48 4960271 : MSVehicleContainer::DepartFinder::DepartFinder(SUMOTime time)
49 4960271 : : myTime(time) {}
50 :
51 :
52 : bool
53 14333842 : MSVehicleContainer::DepartFinder::operator()
54 : (const VehicleDepartureVector& e) const {
55 14333842 : return myTime + DELTA_T > e.first && myTime <= e.first;
56 : }
57 :
58 :
59 :
60 : /* -------------------------------------------------------------------------
61 : * methods from MSVehicleContainer
62 : * ----------------------------------------------------------------------- */
63 42995 : MSVehicleContainer::MSVehicleContainer(int capacity)
64 85990 : : currentSize(0), array(capacity + 1, VehicleDepartureVector()) {}
65 :
66 :
67 40024 : MSVehicleContainer::~MSVehicleContainer() {
68 : // !!! vehicles are deleted in MSVehicle
69 40024 : }
70 :
71 :
72 : void
73 4957979 : MSVehicleContainer::add(SUMOVehicle* veh) {
74 : // check whether a new item shall be added or the vehicle may be
75 : // added to an existing list
76 : VehicleHeap::iterator i =
77 4957979 : find_if(array.begin() + 1, array.begin() + currentSize + 1, DepartFinder(veh->getParameter().depart));
78 4957979 : if (currentSize == 0 || i == array.begin() + currentSize + 1) {
79 : // a new heap-item is necessary
80 3408808 : const SUMOTime delay = veh->getParameter().depart % DELTA_T;
81 3408808 : const SUMOTime depart = veh->getParameter().depart + (delay == 0 ? 0 : DELTA_T - delay);
82 3408808 : VehicleDepartureVector newElem(depart, VehicleVector());
83 3408808 : newElem.second.push_back(veh);
84 3408808 : addReplacing(newElem);
85 : } else {
86 : // add vehicle to an existing heap-item
87 1549171 : (*i).second.push_back(veh);
88 : }
89 4957979 : }
90 :
91 :
92 : void
93 2292 : MSVehicleContainer::remove(SUMOVehicle* veh) {
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 2292 : find_if(array.begin() + 1, array.begin() + currentSize + 1, DepartFinder(veh->getParameter().depart));
98 2292 : if (!(currentSize == 0 || i == array.begin() + currentSize + 1)) {
99 : // remove vehicle from an existing heap-item
100 2053 : (*i).second.erase(std::remove((*i).second.begin(), (*i).second.end(), veh), (*i).second.end());
101 : }
102 2292 : }
103 :
104 :
105 : void
106 0 : MSVehicleContainer::add(SUMOTime time, const VehicleVector& cont) {
107 : VehicleHeap::iterator j =
108 0 : find_if(array.begin() + 1, array.begin() + currentSize + 1,
109 : DepartFinder(time));
110 0 : if (currentSize == 0 || j == array.begin() + currentSize + 1) {
111 : VehicleDepartureVector newElem(time,
112 0 : VehicleVector(cont));
113 0 : addReplacing(newElem);
114 : } else {
115 0 : VehicleVector& stored = (*j).second;
116 0 : stored.reserve(stored.size() + cont.size());
117 : copy(cont.begin(), cont.end(), back_inserter(stored));
118 : }
119 0 : }
120 :
121 :
122 :
123 : void
124 3408808 : MSVehicleContainer::addReplacing(const VehicleDepartureVector& x) {
125 3408808 : if (isFull()) {
126 2936 : std::vector<VehicleDepartureVector> array2((array.size() - 1) * 2 + 1, VehicleDepartureVector());
127 59436 : for (int i = (int)array.size(); i-- > 0;) {
128 : assert(i < (int)array2.size());
129 57968 : array2[i] = array[i];
130 : }
131 1468 : array = array2;
132 1468 : }
133 :
134 : // Percolate up
135 3408808 : int hole = ++currentSize;
136 3421582 : for (; hole > 1 && (x.first < array[ hole / 2 ].first); hole /= 2) {
137 : assert((int)array.size() > hole);
138 12774 : array[hole] = array[ hole / 2 ];
139 : }
140 : assert((int)array.size() > hole);
141 3408808 : array[hole] = x;
142 3408808 : }
143 :
144 :
145 : bool
146 95178705 : MSVehicleContainer::anyWaitingBefore(SUMOTime time) const {
147 95178705 : return !isEmpty() && topTime() <= time;
148 : }
149 :
150 :
151 : const MSVehicleContainer::VehicleVector&
152 3406765 : MSVehicleContainer::top() {
153 3406765 : if (isEmpty()) {
154 0 : throw 1; //!!!Underflow( );
155 : }
156 : assert(array.size() > 1);
157 3406765 : return array[ 1 ].second;
158 : }
159 :
160 :
161 : SUMOTime
162 5106017 : MSVehicleContainer::topTime() const {
163 5106017 : if (isEmpty()) {
164 0 : throw 1; //!!!Underflow( );
165 : }
166 : assert(array.size() > 1);
167 5106017 : return array[ 1 ].first;
168 : }
169 :
170 :
171 : void
172 3406765 : MSVehicleContainer::pop()
173 :
174 : {
175 3406765 : if (isEmpty()) {
176 0 : throw 1; //!!!Underflow( );
177 : }
178 :
179 : assert(array.size() > 1);
180 3406765 : array[ 1 ] = array[ currentSize-- ];
181 3406765 : percolateDown(1);
182 3406765 : }
183 :
184 :
185 : bool
186 107098252 : MSVehicleContainer::isEmpty() const {
187 107098252 : return currentSize == 0;
188 : }
189 :
190 :
191 : bool
192 3408808 : MSVehicleContainer::isFull() const {
193 3408808 : return currentSize >= ((int) array.size()) - 1;
194 : }
195 :
196 :
197 : void
198 3406765 : MSVehicleContainer::percolateDown(int hole) {
199 : int child;
200 : assert((int)array.size() > hole);
201 3406765 : VehicleDepartureVector tmp = array[ hole ];
202 :
203 4145481 : for (; hole * 2 <= currentSize; hole = child) {
204 : child = hole * 2;
205 767627 : if (child != currentSize && (array[child + 1].first < array[child].first)) {
206 : child++;
207 : }
208 767627 : if ((array[ child ].first < tmp.first)) {
209 : assert((int)array.size() > hole);
210 738716 : array[hole] = array[child];
211 : } else {
212 : break;
213 : }
214 : }
215 : assert((int)array.size() > hole);
216 3406765 : array[hole] = tmp;
217 3406765 : }
218 :
219 :
220 : int
221 0 : MSVehicleContainer::size() const {
222 0 : return currentSize;
223 : }
224 :
225 :
226 : void
227 0 : MSVehicleContainer::showArray() const {
228 0 : for (VehicleHeap::const_iterator i = array.begin() + 1; i != array.begin() + currentSize + 1; ++i) {
229 0 : if (i != array.begin() + 1) {
230 0 : std::cout << ", ";
231 : }
232 0 : std::cout << (*i).first;
233 : }
234 : std::cout << std::endl << "-------------------------" << std::endl;
235 0 : }
236 :
237 :
238 0 : std::ostream& operator << (std::ostream& strm, MSVehicleContainer& cont) {
239 : strm << "------------------------------------" << std::endl;
240 0 : while (!cont.isEmpty()) {
241 0 : const MSVehicleContainer::VehicleVector& v = cont.top();
242 0 : for (MSVehicleContainer::VehicleVector::const_iterator i = v.begin(); i != v.end(); ++i) {
243 0 : strm << (*i)->getParameter().depart << std::endl;
244 : }
245 0 : cont.pop();
246 : }
247 0 : return strm;
248 : }
249 :
250 : void
251 177 : MSVehicleContainer::clearState() {
252 3714 : for (VehicleDepartureVector& vdv : array) {
253 3537 : vdv.first = 0;
254 : vdv.second.clear();
255 : }
256 177 : currentSize = 0;
257 177 : }
258 :
259 : /****************************************************************************/
|
