rle_queue.hpp

Go to the documentation of this file.

/*
 * Copyright 2008,2009,2010,2011,2012 Stephan Ossowski, Korbinian Schneeberger,
 * Felix Ott, Joerg Hagmann, Alf Scotland, Sebastian Bender
 * 
 * This file is part of SHORE.
 * 
 * SHORE is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * SHORE is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with SHORE.  If not, see <http://www.gnu.org/licenses/>.
 */


#ifndef SHORE_CONTAINER_RLE_QUEUE_HPP__
#define SHORE_CONTAINER_RLE_QUEUE_HPP__

#include <algorithm>
#include <deque>

namespace shore {

template<typename T>
class rle_queue
{
 public:

        typedef T value_type;

 private:

        struct compare
        {
                bool operator()(const size_t ofs,
                                const std::pair<size_t,value_type> &p)
                {
                        return ofs<p.first;
                }
                bool operator()(const std::pair<size_t,value_type> &p,
                                const size_t ofs)
                {
                        return p.first<ofs;
                }
                bool operator()(const std::pair<size_t,value_type> &p1,
                                const std::pair<size_t,value_type> &p2)
                {
                        return p1.first<p2.first;
                }
        };

        std::deque<std::pair<size_t,value_type> > m_endofs_and_values;

        uint64_t m_off_offset;

        compare m_cmp;

 public:

        rle_queue()
        :m_off_offset(0)
        {}

        size_t size() const
        {
                return empty()?0:(m_endofs_and_values.back().first-m_off_offset);
        }

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

        void clear()
        {
                m_endofs_and_values.clear();
                m_off_offset=0;
        }

        const value_type &operator[](const size_t idx) const
        {
                const std::deque<size_t>::const_iterator ub=
                        std::upper_bound(m_endofs_and_values.begin(),m_endofs_and_values.end(),
                                         idx+m_off_offset,m_cmp);

                return ub->second;
        }

        const value_type &front() const
        {
                return m_endofs_and_values.front().second;
        }

        const value_type &back() const
        {
                return m_endofs_and_values.back().second;
        }

        void push_back(const value_type &v)
        {
                if(empty())
                {
                        m_endofs_and_values.push_back(std::make_pair(1,v));
                }
                else if(m_endofs_and_values.back()==v)
                {
                        m_endofs_and_values.back().first+=1;
                }
                else
                {
                        m_endofs_and_values.push_back(std::make_pair(m_endofs_and_values.back().first+1,v));
                }
        }

        void pop_front()
        {
                ++m_off_offset;
                if(m_off_offset==m_endofs_and_values.front().first)
                {
                        m_endofs_and_values.pop_front();
                        if(empty())
                                m_off_offset=0;
                }
        }

        void pop_back()
        {
                --m_endofs_and_values.back().first;
                if(m_endofs_and_values.size()==1)
                {
                        if(m_endofs_and_values.back().first==m_off_offset)
                                clear();
                }
                else
                {
                        if(m_endofs_and_values.back().first
                           ==m_endofs_and_values[m_endofs_and_values.size()-2].first)
                        {
                                m_endofs_and_values.pop_back();
                        }
                }
        }
};

} // namespace

#endif // SHORE_CONTAINER_RLE_QUEUE_HPP__