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