1 //  Copyright (c) 2001 Daniel C. Nuffer
2 //  Copyright (c) 2001-2011 Hartmut Kaiser
3 //
4 //  Distributed under the Boost Software License, Version 1.0. (See accompanying
5 //  file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 
7 #if !defined(BOOST_SPIRIT_ITERATOR_FIXED_SIZE_QUEUE_POLICY_MAR_16_2007_1134AM)
8 #define BOOST_SPIRIT_ITERATOR_FIXED_SIZE_QUEUE_POLICY_MAR_16_2007_1134AM
9 
10 #include <boost/spirit/home/support/iterators/detail/multi_pass.hpp>
11 #include <boost/spirit/home/support/iterators/detail/fixed_size_queue.hpp>
12 #include <boost/assert.hpp>
13 #include <cstdlib>
14 
15 namespace boost { namespace spirit { namespace iterator_policies
16 {
17     ///////////////////////////////////////////////////////////////////////////
18     //  class fixed_size_queue
19     //  Implementation of the StoragePolicy used by multi_pass
20     //  fixed_size_queue keeps a circular buffer (implemented by
21     //  boost::spirit::fixed_size_queue class) that is size N+1 and stores N
22     //  elements.
23     //
24     //  It is up to the user to ensure that there is enough look ahead for
25     //  their grammar. Currently there is no way to tell if an iterator is
26     //  pointing to forgotten data. The leading iterator will put an item in
27     //  the queue and remove one when it is incremented. No dynamic allocation
28     //  is done, except on creation of the queue (fixed_size_queue constructor).
29     ///////////////////////////////////////////////////////////////////////////
30     template <std::size_t N>
31     struct fixed_size_queue
32     {
33         ///////////////////////////////////////////////////////////////////////
34         template <typename Value>
35         class unique : public detail::default_storage_policy
36         {
37         private:
38             typedef detail::fixed_size_queue<Value, N> queue_type;
39 
40         protected:
unique()41             unique() {}
42 
unique(unique const & x)43             unique(unique const& x)
44               : queued_position(x.queued_position) {}
45 
swap(unique & x)46             void swap(unique& x)
47             {
48                 boost::swap(queued_position, x.queued_position);
49             }
50 
51             //  This is called when the iterator is dereferenced. It's a
52             //  template method so we can recover the type of the multi_pass
53             //  iterator and access the m_input data member.
54             template <typename MultiPass>
55             static typename MultiPass::reference
dereference(MultiPass const & mp)56             dereference(MultiPass const& mp)
57             {
58                 if (!mp.queued_position.get_position().is_initialized())
59                    mp.queued_position.get_position().set_queue(&mp.shared()->queued_elements);
60 
61                 if (mp.queued_position == mp.shared()->queued_elements.end())
62                     return MultiPass::get_input(mp);
63 
64                 return *mp.queued_position;
65             }
66 
67             //  This is called when the iterator is incremented. It's a
68             //  template method so we can recover the type of the multi_pass
69             //  iterator and access the m_input data member.
70             template <typename MultiPass>
increment(MultiPass & mp)71             static void increment(MultiPass& mp)
72             {
73                 if (!mp.queued_position.get_position().is_initialized())
74                     mp.queued_position.get_position().set_queue(&mp.shared()->queued_elements);
75 
76                 if (mp.queued_position == mp.shared()->queued_elements.end())
77                 {
78                     // don't let the queue get larger than N
79                     if (mp.shared()->queued_elements.size() >= N)
80                         mp.shared()->queued_elements.pop_front();
81 
82                     mp.shared()->queued_elements.push_back(
83                         MultiPass::get_input(mp));
84                     MultiPass::advance_input(mp);
85                 }
86                 ++mp.queued_position;
87             }
88 
89             // clear_queue is a no-op
90 
91             // called to determine whether the iterator is an eof iterator
92             template <typename MultiPass>
is_eof(MultiPass const & mp)93             static bool is_eof(MultiPass const& mp)
94             {
95                 return mp.queued_position == mp.shared()->queued_elements.end() &&
96                        MultiPass::input_at_eof(mp);
97             }
98 
99             // called by operator==
100             template <typename MultiPass>
equal_to(MultiPass const & mp,MultiPass const & x)101             static bool equal_to(MultiPass const& mp, MultiPass const& x)
102             {
103                 return mp.queued_position == x.queued_position;
104             }
105 
106             // called by operator<
107             template <typename MultiPass>
less_than(MultiPass const & mp,MultiPass const & x)108             static bool less_than(MultiPass const& mp, MultiPass const& x)
109             {
110                 return mp.queued_position < x.queued_position;
111             }
112 
113         protected:
114             mutable typename queue_type::iterator queued_position;
115         };
116 
117         ///////////////////////////////////////////////////////////////////////
118         template <typename Value>
119         struct shared
120         {
121             typedef detail::fixed_size_queue<Value, N> queue_type;
122             queue_type queued_elements;
123         };
124     };
125 
126 }}}
127 
128 #endif
129