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         353 : class ValueTimeLine {
      44             : public:
      45             :     /// @brief Constructor
      46             :     ValueTimeLine() { }
      47             : 
      48             :     /// @brief Destructor
      49      322391 :     ~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      499084 :     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      979620 :         if (myValues.upper_bound(begin) == myValues.end() ||
      64             :                 myValues.upper_bound(end) == myValues.begin()) {
      65       18548 :             myValues[begin] = std::make_pair(true, value);
      66       18548 :             myValues[end] = std::make_pair(false, value);
      67       18548 :             return;
      68             :         }
      69             :         // our end already has a value
      70             :         typename TimedValueMap::iterator endIt = myValues.find(end);
      71      480536 :         if (endIt != myValues.end()) {
      72             :             myValues.erase(myValues.upper_bound(begin), endIt);
      73      478281 :             myValues[begin] = std::make_pair(true, value);
      74      478281 :             return;
      75             :         }
      76             :         // we have at least one entry strictly before our end
      77             :         endIt = myValues.lower_bound(end);
      78             :         --endIt;
      79        2255 :         ValidValue oldEndValue = endIt->second;
      80             :         myValues.erase(myValues.upper_bound(begin), myValues.lower_bound(end));
      81        2255 :         myValues[begin] = std::make_pair(true, value);
      82        2255 :         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     8428904 :     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     8428904 :         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     9851967 :     bool describesTime(double time) const {
     112             :         typename TimedValueMap::const_iterator afterIt = myValues.upper_bound(time);
     113     9851967 :         if (afterIt == myValues.begin()) {
     114             :             return false;
     115             :         }
     116             :         --afterIt;
     117     8223667 :         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        6569 :     void fillGaps(T value, bool extendOverBoundaries = false) {
     146       22967 :         for (typename TimedValueMap::iterator it = myValues.begin(); it != myValues.end(); ++it) {
     147       16398 :             if (!it->second.first) {
     148        6713 :                 it->second.second = value;
     149             :             }
     150             :         }
     151        6569 :         if (extendOverBoundaries && !myValues.empty()) {
     152             :             typename TimedValueMap::iterator it = --myValues.end();
     153        5784 :             if (!it->second.first) {
     154             :                 myValues.erase(it, myValues.end());
     155             :             }
     156        5784 :             value = myValues.begin()->second.second;
     157             :         }
     158        6569 :         myValues[-1] = std::make_pair(false, value);
     159        6569 :     }
     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             : };