split_std_deque_policy.hpp

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

//  Copyright (c) 2001, Daniel C. Nuffer
//  Copyright (c) 2001-2008, Hartmut Kaiser
// 
//  Distributed under the Boost Software License, Version 1.0. (See accompanying
//  file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

#if !defined(BOOST_SPIRIT_ITERATOR_SPLIT_DEQUE_POLICY_APR_06_2008_0138PM)
#define BOOST_SPIRIT_ITERATOR_SPLIT_DEQUE_POLICY_APR_06_2008_0138PM

#include <boost/spirit/home/support/iterators/multi_pass_fwd.hpp>
#include <boost/spirit/home/support/iterators/detail/multi_pass.hpp>
#include <boost/assert.hpp>
#include <vector>

namespace boost { namespace spirit { namespace multi_pass_policies
{
    ///////////////////////////////////////////////////////////////////////////
    //  class split_std_deque
    //
    //  Implementation of the StoragePolicy used by multi_pass
    //  This stores all data in a std::vector (despite its name), and keeps an 
    //  offset to the current position. It stores all the data unless there is 
    //  only one iterator using the queue.
    // 
    ///////////////////////////////////////////////////////////////////////////
    struct split_std_deque
    {
        enum { threshold = 16 };
        
        ///////////////////////////////////////////////////////////////////////
        template <typename Value>
        class unique //: public detail::default_storage_policy
        {
        private:
            typedef std::vector<Value> queue_type;

        protected:
            unique()
              : queued_position(0)
            {}

            unique(unique const& x)
              : queued_position(x.queued_position)
            {}

            void swap(unique& x)
            {
                spirit::detail::swap(queued_position, x.queued_position);
            }

            // This is called when the iterator is dereferenced.  It's a 
            // template method so we can recover the type of the multi_pass 
            // iterator and call advance_input and input_is_valid.
            template <typename MultiPass>
            static typename MultiPass::reference 
            dereference(MultiPass const& mp)
            {
                queue_type& queue = mp.shared->queued_elements;
                if (0 == mp.queued_position) 
                {
                    if (queue.empty())
                    {
                        queue.push_back(Value());
                        return MultiPass::advance_input(mp, queue[mp.queued_position++]);
                    }
                    return queue[mp.queued_position++];
                }
                else if (!MultiPass::input_is_valid(mp, queue[mp.queued_position-1]))
                {
                    MultiPass::advance_input(mp, queue[mp.queued_position-1]);
                }
                return queue[mp.queued_position-1];
            }

            // This is called when the iterator is incremented. It's a template
            // method so we can recover the type of the multi_pass iterator
            // and call is_unique and advance_input.
            template <typename MultiPass>
            static void increment(MultiPass& mp)
            {
                queue_type& queue = mp.shared->queued_elements;
                typename queue_type::size_type size = queue.size();
                BOOST_ASSERT(0 != size && mp.queued_position <= size);
                if (mp.queued_position == size)
                {
                    // check if this is the only iterator
                    if (size >= threshold && MultiPass::is_unique(mp))
                    {
                        // free up the memory used by the queue. we avoid 
                        // clearing the queue on every increment, though, 
                        // because this would be too time consuming

                        // erase all but first item in queue
                        queue.erase(queue.begin()+1, queue.end());
                        mp.queued_position = 0;
                        
                        // reuse first entry in the queue and initialize 
                        // it from the input
                        MultiPass::advance_input(mp, queue[mp.queued_position++]);
                    }
                    else
                    {
                        // create a new entry in the queue and initialize 
                        // it from the input
                        queue.push_back(Value());
                        MultiPass::advance_input(mp, queue[mp.queued_position++]);
                    }
                }
                else
                {
                    ++mp.queued_position;
                }
            }

            // called to forcibly clear the queue
            template <typename MultiPass>
            static void clear_queue(MultiPass& mp)
            {
                mp.shared->queued_elements.clear();
                mp.queued_position = 0;
            }

            // called to determine whether the iterator is an eof iterator
            template <typename MultiPass>
            static bool is_eof(MultiPass const& mp)
            {
                queue_type& queue = mp.shared->queued_elements;
                return 0 != mp.queued_position && 
                    mp.queued_position == queue.size() && 
                    MultiPass::input_at_eof(mp, queue[mp.queued_position-1]);
            }

            // called by operator==
            template <typename MultiPass>
            static bool equal_to(MultiPass const& mp, MultiPass const& x) 
            {
                return mp.queued_position == x.queued_position;
            }

            // called by operator<
            template <typename MultiPass>
            static bool less_than(MultiPass const& mp, MultiPass const& x)
            {
                return mp.queued_position < x.queued_position;
            }
            
            template <typename MultiPass>
            static void destroy(MultiPass&) 
            {}

        protected:
            mutable typename queue_type::size_type queued_position;
        }; 

        ///////////////////////////////////////////////////////////////////////
        template <typename Value>
        struct shared
        {
            shared() { queued_elements.reserve(threshold); }
            
            typedef std::vector<Value> queue_type;
            queue_type queued_elements;
        }; 

    }; // split_std_deque

}}}

#endif