HistoryContainer.h

Go to the documentation of this file.

// Copyright 2016 Sensics, Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//        http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#ifndef INCLUDED_HistoryContainer_h_GUID_7CD22B1E_6EAC_49BF_F9FB_030C4BE3FA54
#define INCLUDED_HistoryContainer_h_GUID_7CD22B1E_6EAC_49BF_F9FB_030C4BE3FA54

// Internal Includes
// - none

// Library/third-party includes
#include <osvr/Util/TimeValue.h>

// Standard includes
#include <deque>
#include <stdexcept>
#include <iterator>

namespace osvr {
namespace vbtracker {
    namespace history {

        namespace detail {
            using timestamp = osvr::util::time::TimeValue;

            template <typename ValueType>
            using full_value_type = std::pair<timestamp, ValueType>;

            template <typename ValueType>
            using inner_container_type = std::deque<full_value_type<ValueType>>;

            template <typename ValueType>
            using container_size_type =
                typename inner_container_type<ValueType>::size_type;

            template <typename ValueType>
            using iterator =
                typename inner_container_type<ValueType>::const_iterator;

            template <typename ValueType>
            using nonconst_iterator =
                typename inner_container_type<ValueType>::iterator;

            template <typename ValueType> class TimestampPairLessThan {
              public:
                bool operator()(timestamp const &lhs,
                                full_value_type<ValueType> const &rhs) {
                    return lhs < rhs.first;
                }

                bool operator()(full_value_type<ValueType> const &lhs,
                                timestamp const &rhs) {
                    return lhs.first < rhs;
                }
            };
            template <typename ValueType> class HistorySubsetRange {
              public:
                using iterator = detail::iterator<ValueType>;
                using const_iterator = detail::iterator<ValueType>;
                HistorySubsetRange(iterator begin_, iterator end_)
                    : m_begin(begin_), m_end(end_) {
                }

                iterator begin() const { return m_begin; }
                const_iterator cbegin() const { return m_begin; }
                iterator end() const { return m_end; }
                const_iterator cend() const { return m_end; }

              private:
                iterator m_begin;
                iterator m_end;
            };
        } // namespace detail

        template <typename ValueType, bool AllowDuplicateTimes_ = true>
        class HistoryContainer {
          public:
            using value_type = ValueType;

            using timestamp_type = detail::timestamp;
            using full_value_type = detail::full_value_type<value_type>;
            using container_type = detail::inner_container_type<value_type>;
            using size_type = detail::container_size_type<value_type>;

            using iterator = detail::iterator<value_type>;
            using const_iterator = iterator;

            using comparator_type = detail::TimestampPairLessThan<value_type>;

            using subset_range_type = detail::HistorySubsetRange<value_type>;

            static const bool AllowDuplicateTimes = AllowDuplicateTimes_;

            size_type size() const { return m_history.size(); }

            size_type highWaterMark() const { return m_sizeHighWaterMark; }

            bool empty() const { return m_history.empty(); }

            timestamp_type const &oldest_timestamp() const {
                if (empty()) {
                    throw std::logic_error(
                        "Can't get time of oldest entry in an "
                        "empty history container!");
                }
                return m_history.front().first;
            }

            value_type const &oldest() const {
                if (empty()) {
                    throw std::logic_error("Can't get oldest entry in an "
                                           "empty history container!");
                }
                return m_history.front().first;
            }

            timestamp_type const &newest_timestamp() const {
                if (empty()) {
                    throw std::logic_error(
                        "Can't get time of newest entry in an "
                        "empty history container!");
                }

                return m_history.back().first;
            }

            value_type const &newest() const {
                if (empty()) {
                    throw std::logic_error("Can't get newest entry in an "
                                           "empty history container!");
                }

                return m_history.back().second;
            }

            static comparator_type comparator() { return comparator_type{}; }

            void pop_oldest() { m_history.pop_front(); }
            void pop_newest() { m_history.pop_back(); }

            const_iterator begin() const { return m_history.cbegin(); }
            const_iterator cbegin() const { return m_history.cbegin(); }
            const_iterator end() const { return m_history.cend(); }
            const_iterator cend() const { return m_history.cend(); }

            void clear() { m_history.clear(); }

          private:
            using nonconst_iterator = detail::nonconst_iterator<value_type>;

            nonconst_iterator ncbegin() { return m_history.begin(); }
            nonconst_iterator ncend() { return m_history.end(); }

          public:
            bool is_strictly_newest(timestamp_type const &tv) const {
                return empty() || newest_timestamp() < tv;
            }

            bool is_as_new_as_newest(timestamp_type const &tv) const {
                return empty() || !(tv < newest_timestamp());
            }

            bool is_valid_to_push_newest(timestamp_type const &tv) {
                return empty() || tv > newest_timestamp() ||
                       (AllowDuplicateTimes && newest_timestamp() == tv);
            }

            const_iterator upper_bound(timestamp_type const &tv) const {
                return std::upper_bound(begin(), end(), tv, comparator());
            }
            const_iterator lower_bound(timestamp_type const &tv) const {
                return std::lower_bound(begin(), end(), tv, comparator());
            }

          private:
            nonconst_iterator nc_upper_bound(timestamp_type const &tv) {
                return std::upper_bound(ncbegin(), ncend(), tv, comparator());
            }
            nonconst_iterator nc_lower_bound(timestamp_type const &tv) {
                return std::lower_bound(ncbegin(), ncend(), tv, comparator());
            }

          public:
            const_iterator closest_not_newer(timestamp_type const &tv) const {
                if (empty()) {
                    return end();
                }
                auto it = upper_bound(tv);
                if (begin() == it) {
                    // can't back iterator off if it's already at the beginning
                    return end();
                }
                --it;
                return it;
            }

            subset_range_type
            get_range_newer_than(timestamp_type const &tv) const {
                return subset_range_type(upper_bound(tv), end());
            }

#if 0
            size_type pop_before(timestamp_type const &tv) {
                auto count = size_type{0};
                while (!empty() && oldest_timestamp() < tv) {
                    pop_oldest();
                    ++count;
                }
                return count;
            }
#else
            size_type pop_before(timestamp_type const &tv) {
                if (empty()) {
                    return 0;
                }
                auto lastIt = nc_lower_bound(tv);
                if (ncend() == lastIt) {
                    // If we got end() back, that's ambiguous: is the last entry
                    // really >= our timestamp?
                    if (is_strictly_newest(tv)) {
                        // It's not - lower_bound couldn't find anything.
                        return 0;
                    }
                }
                auto count = std::distance(ncbegin(), lastIt);
                m_history.erase(ncbegin(), lastIt);
                return count;
            }
#endif

#if 0

            size_type pop_after(timestamp_type const &tv) {
                auto count = size_type{0};
                while (!empty() && tv < newest_timestamp()) {
                    pop_newest();
                    ++count;
                }
                return count;
            }
#else
            size_type pop_after(timestamp_type const &tv) {
                if (empty()) {
                    return 0;
                }
                auto firstIt = nc_upper_bound(tv);
                if (ncend() == firstIt) {
                    // If we got end() back, nothing found after our timestamp.
                    return 0;
                }
                auto count = std::distance(firstIt, ncend());
                m_history.erase(firstIt, ncend());
                return count;
            }
#endif

            void push_newest(osvr::util::time::TimeValue const &tv,
                             value_type const &value) {
                if (is_valid_to_push_newest(tv)) {
                    m_history.emplace_back(tv, value);
                    updateSizeHighWaterMark();
                } else {
                    throw std::logic_error(
                        "Can't push_newest a value that's older "
                        "than the most recent value!");
                }
            }

          private:
            void updateSizeHighWaterMark() {
                m_sizeHighWaterMark =
                    (std::max)(m_history.size(), m_sizeHighWaterMark);
            }
            container_type m_history;
            size_type m_sizeHighWaterMark = 0;
        };
    } // namespace history

    using history::HistoryContainer;

} // namespace vbtracker
} // namespace osvr
#endif // INCLUDED_HistoryContainer_h_GUID_7CD22B1E_6EAC_49BF_F9FB_030C4BE3FA54