SUMO - Simulation of Urban MObility
|
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