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