SUMO - Simulation of Urban MObility
MSVehicleContainer.cpp
Go to the documentation of this file.
00001 /****************************************************************************/
00009 // vehicles sorted by their departures
00010 /****************************************************************************/
00011 // SUMO, Simulation of Urban MObility; see http://sumo.sourceforge.net/
00012 // Copyright (C) 2001-2012 DLR (http://www.dlr.de/) and contributors
00013 /****************************************************************************/
00014 //
00015 //   This file is part of SUMO.
00016 //   SUMO is free software: you can redistribute it and/or modify
00017 //   it under the terms of the GNU General Public License as published by
00018 //   the Free Software Foundation, either version 3 of the License, or
00019 //   (at your option) any later version.
00020 //
00021 /****************************************************************************/
00022 
00023 
00024 // ===========================================================================
00025 // included modules
00026 // ===========================================================================
00027 #ifdef _MSC_VER
00028 #include <windows_config.h>
00029 #else
00030 #include <config.h>
00031 #endif
00032 
00033 #include <algorithm>
00034 #include <cassert>
00035 #include <iterator>
00036 #include "MSVehicle.h"
00037 #include "MSVehicleContainer.h"
00038 
00039 #ifdef CHECK_MEMORY_LEAKS
00040 #include <foreign/nvwa/debug_new.h>
00041 #endif // CHECK_MEMORY_LEAKS
00042 
00043 
00044 // ===========================================================================
00045 // method definitions
00046 // ===========================================================================
00047 /* -------------------------------------------------------------------------
00048  * methods from MSVehicleContainer::VehicleDepartureVectorSortCrit
00049  * ----------------------------------------------------------------------- */
00050 bool
00051 MSVehicleContainer::VehicleDepartureVectorSortCrit::operator()
00052 (const VehicleDepartureVector& e1, const VehicleDepartureVector& e2) const {
00053     return e1.first < e2.first;
00054 }
00055 
00056 
00057 
00058 /* -------------------------------------------------------------------------
00059  * methods from MSVehicleContainer::DepartFinder
00060  * ----------------------------------------------------------------------- */
00061 MSVehicleContainer::DepartFinder::DepartFinder(SUMOTime time)
00062     : myTime(time) {}
00063 
00064 
00065 bool
00066 MSVehicleContainer::DepartFinder::operator()
00067 (const VehicleDepartureVector& e) const {
00068     return myTime + DELTA_T > e.first && myTime <= e.first;
00069 }
00070 
00071 
00072 
00073 /* -------------------------------------------------------------------------
00074  * methods from MSVehicleContainer
00075  * ----------------------------------------------------------------------- */
00076 MSVehicleContainer::MSVehicleContainer(size_t capacity)
00077     : currentSize(0), array(capacity + 1, VehicleDepartureVector()) {}
00078 
00079 
00080 MSVehicleContainer::~MSVehicleContainer() {
00081     // !!! vehicles are deleted in MSVehicle
00082 }
00083 
00084 
00085 void
00086 MSVehicleContainer::add(SUMOVehicle* veh) {
00087     // check whether a new item shall be added or the vehicle may be
00088     //  added to an existing list
00089     VehicleHeap::iterator i =
00090         find_if(array.begin() + 1, array.begin() + currentSize + 1, DepartFinder(veh->getParameter().depart));
00091     if (currentSize == 0 || i == array.begin() + currentSize + 1) {
00092         // a new heap-item is necessary
00093         VehicleDepartureVector newElem(veh->getParameter().depart, VehicleVector());
00094         newElem.second.push_back(veh);
00095         addReplacing(newElem);
00096     } else {
00097         // add vehicle to an existing heap-item
00098         (*i).second.push_back(veh);
00099     }
00100 }
00101 
00102 
00103 void
00104 MSVehicleContainer::add(SUMOTime time, const VehicleVector& cont) {
00105     VehicleHeap::iterator j =
00106         find_if(array.begin() + 1, array.begin() + currentSize + 1,
00107                 DepartFinder(time));
00108     if (currentSize == 0 || j == array.begin() + currentSize + 1) {
00109         VehicleDepartureVector newElem(time,
00110                                        VehicleVector(cont));
00111         addReplacing(newElem);
00112     } else {
00113         VehicleVector& stored = (*j).second;
00114         stored.reserve(stored.size() + cont.size());
00115         copy(cont.begin(), cont.end(), back_inserter(stored));
00116     }
00117 }
00118 
00119 
00120 
00121 void
00122 MSVehicleContainer::addReplacing(const VehicleDepartureVector& x) {
00123     if (isFull()) {
00124         std::vector<VehicleDepartureVector> array2((array.size() - 1) * 2 + 1, VehicleDepartureVector());
00125         for (size_t i = array.size(); i-- > 0;) {
00126             assert(array2.size() > i);
00127             array2[i] = array[i];
00128         }
00129         array = array2;
00130     }
00131 
00132     // Percolate up
00133     int hole = ++currentSize;
00134     for (; hole > 1 && (x.first < array[ hole / 2 ].first); hole /= 2) {
00135         assert(array.size() > (size_t) hole);
00136         array[ hole ] = array[ hole / 2 ];
00137     }
00138     assert(array.size() > (size_t) hole);
00139     array[ hole ] = x;
00140 }
00141 
00142 
00143 bool
00144 MSVehicleContainer::anyWaitingFor(SUMOTime time) const {
00145     VehicleHeap::const_iterator j =
00146         find_if(array.begin() + 1, array.begin() + currentSize + 1, DepartFinder(time));
00147     return j != array.begin() + currentSize + 1;
00148 }
00149 
00150 
00151 const MSVehicleContainer::VehicleVector&
00152 MSVehicleContainer::top() {
00153     if (isEmpty()) {
00154         throw 1;    
00155     }
00156     assert(array.size() > 1);
00157     return array[ 1 ].second;
00158 }
00159 
00160 
00161 SUMOTime
00162 MSVehicleContainer::topTime() const {
00163     if (isEmpty()) {
00164         throw 1;    
00165     }
00166     assert(array.size() > 1);
00167     return array[ 1 ].first;
00168 }
00169 
00170 
00171 void
00172 MSVehicleContainer::pop()
00173 
00174 {
00175     if (isEmpty()) {
00176         throw 1;    
00177     }
00178 
00179     assert(array.size() > 1);
00180     array[ 1 ] = array[ currentSize-- ];
00181     percolateDown(1);
00182 }
00183 
00184 
00185 bool
00186 MSVehicleContainer::isEmpty() const {
00187     return currentSize == 0;
00188 }
00189 
00190 
00191 bool
00192 MSVehicleContainer::isFull() const {
00193     return currentSize >= ((int) array.size()) - 1;
00194 }
00195 
00196 
00197 void
00198 MSVehicleContainer::percolateDown(int hole) {
00199     int child;
00200     assert(array.size() > (size_t)hole);
00201     VehicleDepartureVector tmp = array[ hole ];
00202 
00203     for (; hole * 2 <= currentSize; hole = child) {
00204         child = hole * 2;
00205         if (child != currentSize && (array[ child + 1 ].first < array[ child ].first)) {
00206             child++;
00207         }
00208         if ((array[ child ].first < tmp.first)) {
00209             assert(array.size() > (size_t) hole);
00210             array[ hole ] = array[ child ];
00211         } else {
00212             break;
00213         }
00214     }
00215     assert(array.size() > (size_t) hole);
00216     array[ hole ] = tmp;
00217 }
00218 
00219 
00220 size_t
00221 MSVehicleContainer::size() const {
00222     return currentSize;
00223 }
00224 
00225 
00226 void
00227 MSVehicleContainer::showArray() const {
00228     for (VehicleHeap::const_iterator i = array.begin() + 1; i != array.begin() + currentSize + 1; ++i) {
00229         if (i != array.begin() + 1) {
00230             std::cout << ", ";
00231         }
00232         std::cout << (*i).first;
00233     }
00234     std::cout << std::endl << "-------------------------" << std::endl;
00235 }
00236 
00237 
00238 std::ostream& operator << (std::ostream& strm, MSVehicleContainer& cont) {
00239     strm << "------------------------------------" << std::endl;
00240     while (!cont.isEmpty()) {
00241         const MSVehicleContainer::VehicleVector& v = cont.top();
00242         for (MSVehicleContainer::VehicleVector::const_iterator i = v.begin(); i != v.end(); ++i) {
00243             strm << (*i)->getParameter().depart << std::endl;
00244         }
00245         cont.pop();
00246     }
00247     return strm;
00248 }
00249 
00250 
00251 
00252 /****************************************************************************/
00253 
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Defines