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 /****************************************************************************/ 10 /// @file ValueTimeLine.h 11 /// @author Christian Roessel 12 /// @author Daniel Krajzewicz 13 /// @author Michael Behrisch 14 /// @date Sept 2002 15 /// @version $Id$ 16 /// 17 // A list of time ranges with assigned values 18 /****************************************************************************/ 19 #ifndef ValueTimeLine_h 20 #define ValueTimeLine_h 21 22 23 // =========================================================================== 24 // included modules 25 // =========================================================================== 26 #include <map> 27 #include <cassert> 28 #include <utility> 29 #include <utils/common/SUMOTime.h> 30 31 32 33 // =========================================================================== 34 // class definitions 35 // =========================================================================== 36 /** 37 * @class ValueTimeLine 38 * 39 * A time line being a sorted container of non-overlapping time-ranges 40 * with assigned values. The container is sorted by the first value of the 41 * time-range while being filled. Every new inserted time range 42 * may overwrite or split one or multiple earlier intervals. 43 */ 44 template<typename T> 45 class ValueTimeLine { 46 public: 47 /// @brief Constructor ValueTimeLine()48 ValueTimeLine() { } 49 50 /// @brief Destructor ~ValueTimeLine()51 ~ValueTimeLine() { } 52 53 /** @brief Adds a value for a time interval into the container. 54 * 55 * Make sure that begin >= 0 and begin < end. 56 * 57 * @param[in] begin the start time of the time range (inclusive) 58 * @param[in] end the end time of the time range (exclusive) 59 * @param[in] value the value to store 60 */ add(double begin,double end,T value)61 void add(double begin, double end, T value) { 62 assert(begin >= 0); 63 assert(begin < end); 64 // inserting strictly before the first or after the last interval (includes empty case) 65 if (myValues.upper_bound(begin) == myValues.end() || 66 myValues.upper_bound(end) == myValues.begin()) { 67 myValues[begin] = std::make_pair(true, value); 68 myValues[end] = std::make_pair(false, value); 69 return; 70 } 71 // our end already has a value 72 typename TimedValueMap::iterator endIt = myValues.find(end); 73 if (endIt != myValues.end()) { 74 myValues.erase(myValues.upper_bound(begin), endIt); 75 myValues[begin] = std::make_pair(true, value); 76 return; 77 } 78 // we have at least one entry strictly before our end 79 endIt = myValues.lower_bound(end); 80 --endIt; 81 ValidValue oldEndValue = endIt->second; 82 myValues.erase(myValues.upper_bound(begin), myValues.lower_bound(end)); 83 myValues[begin] = std::make_pair(true, value); 84 myValues[end] = oldEndValue; 85 } 86 87 /** @brief Returns the value for the given time. 88 * 89 * There is no bounds checking applied! If there was no value 90 * set, the return value is undefined, the method may even segfault. 91 * 92 * @param[in] the time for which the value should be retrieved 93 * @return the value for the time 94 */ getValue(double time)95 T getValue(double time) const { 96 assert(myValues.size() != 0); 97 typename TimedValueMap::const_iterator it = myValues.upper_bound(time); 98 assert(it != myValues.begin()); 99 --it; 100 return it->second.second; 101 } 102 103 /** @brief Returns whether a value for the given time is known. 104 * 105 * This method implements the bounds checking. It returns true 106 * if and only if an explicit value was set for the given time 107 * using add. Default values stemming from fillGaps are not 108 * considered valid. 109 * 110 * @param[in] the time for which the value should be retrieved 111 * @return whether a valid value was set 112 */ describesTime(double time)113 bool describesTime(double time) const { 114 typename TimedValueMap::const_iterator afterIt = myValues.upper_bound(time); 115 if (afterIt == myValues.begin()) { 116 return false; 117 } 118 --afterIt; 119 return afterIt->second.first; 120 } 121 122 /** @brief Returns the time point at which the value changes. 123 * 124 * If the two input parameters lie in two consecutive time 125 * intervals, this method returns the point at which the 126 * interval changes. In any other case -1 is returned. 127 * 128 * @param[in] low the time in the first interval 129 * @param[in] high the time in the second interval 130 * @return the split point 131 */ getSplitTime(double low,double high)132 double getSplitTime(double low, double high) const { 133 typename TimedValueMap::const_iterator afterLow = myValues.upper_bound(low); 134 typename TimedValueMap::const_iterator afterHigh = myValues.upper_bound(high); 135 --afterHigh; 136 if (afterLow == afterHigh) { 137 return afterLow->first; 138 } 139 return -1; 140 } 141 142 /** @brief Sets a default value for all unset intervals. 143 * 144 * @param[in] value the value to store 145 * @param[in] extendOverBoundaries whether the first/last value should be valid for later / earlier times as well 146 */ 147 void fillGaps(T value, bool extendOverBoundaries = false) { 148 for (typename TimedValueMap::iterator it = myValues.begin(); it != myValues.end(); ++it) { 149 if (!it->second.first) { 150 it->second.second = value; 151 } 152 } 153 if (extendOverBoundaries && !myValues.empty()) { 154 typename TimedValueMap::iterator it = --myValues.end(); 155 if (!it->second.first) { 156 myValues.erase(it, myValues.end()); 157 } 158 value = myValues.begin()->second.second; 159 } 160 myValues[-1] = std::make_pair(false, value); 161 } 162 163 private: 164 /// @brief Value of time line, indicating validity. 165 typedef std::pair<bool, T> ValidValue; 166 167 /// @brief Sorted map from start of intervals to values. 168 typedef std::map<double, ValidValue> TimedValueMap; 169 170 /// @brief The list of time periods (with values) 171 TimedValueMap myValues; 172 173 }; 174 175 176 #endif 177 178 /****************************************************************************/ 179