rangequeue.h

Go to the documentation of this file.

 
//  Copyright (c) 2003-2021 Xsens Technologies B.V. or subsidiaries worldwide.
//  All rights reserved.
//  
//  Redistribution and use in source and binary forms, with or without modification,
//  are permitted provided that the following conditions are met:
//  
//  1.  Redistributions of source code must retain the above copyright notice,
//      this list of conditions, and the following disclaimer.
//  
//  2.  Redistributions in binary form must reproduce the above copyright notice,
//      this list of conditions, and the following disclaimer in the documentation
//      and/or other materials provided with the distribution.
//  
//  3.  Neither the names of the copyright holders nor the names of their contributors
//      may be used to endorse or promote products derived from this software without
//      specific prior written permission.
//  
//  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
//  EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
//  MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
//  THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
//  SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT 
//  OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
//  HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY OR
//  TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
//  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.THE LAWS OF THE NETHERLANDS 
//  SHALL BE EXCLUSIVELY APPLICABLE AND ANY DISPUTES SHALL BE FINALLY SETTLED UNDER THE RULES 
//  OF ARBITRATION OF THE INTERNATIONAL CHAMBER OF COMMERCE IN THE HAGUE BY ONE OR MORE 
//  ARBITRATORS APPOINTED IN ACCORDANCE WITH SAID RULES.
//  
 
 
//  Copyright (c) 2003-2021 Xsens Technologies B.V. or subsidiaries worldwide.
//  All rights reserved.
//  
//  Redistribution and use in source and binary forms, with or without modification,
//  are permitted provided that the following conditions are met:
//  
//  1.  Redistributions of source code must retain the above copyright notice,
//      this list of conditions, and the following disclaimer.
//  
//  2.  Redistributions in binary form must reproduce the above copyright notice,
//      this list of conditions, and the following disclaimer in the documentation
//      and/or other materials provided with the distribution.
//  
//  3.  Neither the names of the copyright holders nor the names of their contributors
//      may be used to endorse or promote products derived from this software without
//      specific prior written permission.
//  
//  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
//  EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
//  MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
//  THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
//  SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT 
//  OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
//  HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY OR
//  TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
//  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.THE LAWS OF THE NETHERLANDS 
//  SHALL BE EXCLUSIVELY APPLICABLE AND ANY DISPUTES SHALL BE FINALLY SETTLED UNDER THE RULES 
//  OF ARBITRATION OF THE INTERNATIONAL CHAMBER OF COMMERCE IN THE HAGUE BY ONE OR MORE 
//  ARBITRATORS APPOINTED IN ACCORDANCE WITH SAID RULES.
//  
 
#ifndef RANGE_QUEUE_H
#define RANGE_QUEUE_H
 
#include <list>
#include <xscommon/xsens_mutex.h>
 
template <class T>
class RangeQueue
{
public:
        RangeQueue() : m_count(0)
        {
        }
 
        virtual ~RangeQueue()
        {
        }
 
        void clear()
        {
                xsens::Lock locky(&m_mutex);
                m_queue.clear();
                m_count = 0;
        }
 
        void pushBack(T start, T end)
        {
                if (end < start)
                        return;
 
                xsens::Lock locky(&m_mutex);
                if (!empty() && (start <= last()))
                        return;
 
                Range newRange(start, end);
                JLTRACEG("Adding range: [" << start << " - " << end << "]");
                m_queue.push_back(newRange);
                m_count += 1 + end - start;
        }
 
        void remove(T index)
        {
                xsens::Lock locky(&m_mutex);
                if (empty())
                        return;
 
                for (auto r = m_queue.rbegin(); r != m_queue.rend(); ++r)
                {
                        if ((index > r->m_end) || (index < r->m_start))
                                continue;
 
                        --m_count;
                        if (r->m_start == r->m_end)
                                m_queue.erase(--(r.base()));
                        else if (r->m_start == index)
                                r->m_start++;
                        else if (r->m_end == index)
                                r->m_end--;
                        else
                        {
                                Range split(r->m_start, index - 1);
                                r->m_start = index + 1;
                                m_queue.insert(--(r.base()), split);
                        }
                        return;
                }
        }
 
        void popFront(T upto)
        {
                xsens::Lock locky(&m_mutex);
 
                while (!m_queue.empty() && (m_queue.front().m_end <= upto))
                {
                        auto const& i = m_queue.front();
                        m_count -= (i.m_end - i.m_start) + 1;
                        m_queue.pop_front();
                }
 
                if (empty())
                {
                        JLDEBUGG("Removed upto: " << upto << ", now empty");
                        m_count = 0;
                        return;
                }
                if (m_queue.front().m_start <= upto)
                {
                        m_count -= 1 + upto - m_queue.front().m_start;
                        m_queue.front().m_start = upto + 1;
                }
                JLDEBUGG("Removed upto: " << upto << ", new first = " << m_queue.front().m_start);
        }
 
        void popBack(T upto)
        {
                xsens::Lock locky(&m_mutex);
 
                while (!m_queue.empty() && (m_queue.back().m_start >= upto))
                {
                        auto const& i = m_queue.back();
                        m_count -= (i.m_end - i.m_start) + 1;
                        m_queue.pop_back();
                }
 
                if (empty())
                {
                        JLDEBUGG("Removed upto: " << upto << ", now empty");
                        m_count = 0;
                        return;
                }
                if (m_queue.back().m_end >= upto)
                {
                        m_count -= 1 + m_queue.back().m_end - upto;
                        m_queue.back().m_end = upto - 1;
                }
                JLDEBUGG("Removed upto: " << upto << ", new last = " << m_queue.back().m_end);
        }
 
        T first() const
        {
                xsens::Lock locky(&m_mutex);
                if (empty())
                        return illegalIndex();
                return m_queue.front().m_start;
        }
 
        T last() const
        {
                xsens::Lock locky(&m_mutex);
                if (empty())
                        return illegalIndex();
 
                return m_queue.back().m_end;
        }
 
        const T operator[](std::size_t index) const
        {
                xsens::Lock locky(&m_mutex);
 
                std::size_t range = index / 2;
                uint32_t end = index % 2;
 
                if (m_queue.size() < range)
                        return illegalIndex();
 
                auto it = m_queue.begin();
 
                for (uint32_t i = 0; i < range; ++i)
                        ++it;
 
                if (end)
                        return it->m_end;
                else
                        return it->m_start;
        }
 
        bool contains(uint32_t index) const
        {
                xsens::Lock locky(&m_mutex);
                for (auto i = m_queue.begin(); i != m_queue.end(); ++i)
                {
                        if ((index >= i->m_start) && (index <= i->m_end))
                                return true;
                }
                return false;
        }
 
        T count() const
        {
                xsens::Lock locky(&m_mutex);
                return m_count;
        }
 
        T recount()
        {
                xsens::Lock locky(&m_mutex);
                m_count = 0;
                for (auto i = m_queue.begin(); i != m_queue.end(); ++i)
                        m_count += (i->m_end - i->m_start) + 1;
                return m_count;
        }
 
        bool empty() const
        {
                return m_queue.empty();
        }
 
        static const T illegalIndex()
        {
                return (T) - 1;
        }
 
        void copy(RangeQueue<T>& destination, T start, T end)
        {
                xsens::Lock locky(&m_mutex);
 
                for (auto i = m_queue.begin(); i != m_queue.end(); ++i)
                {
                        if ((i->m_start >= start && start <= i->m_end) && (i->m_start <= end))
                                destination.pushBack(i->m_start, std::min<T>(i->m_end, end));
                        else if (i->m_start < start && i->m_start < end)
                                destination.pushBack(start, std::min<T>(i->m_end, end));
                }
        }
 
private:
        struct Range
        {
                T m_start;
                T m_end;
                Range(T start, T end)
                        : m_start(start)
                        , m_end(end)
                {}
        };
        T m_count;
 
        std::list<Range> m_queue;
        mutable xsens::Mutex m_mutex;
};
 
#endif