// (C) Copyright 2008-2009 SDML (www.sdml.info)
//
// Use, modification and distribution is subject to 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)

// Copyright Andrew Sutton 2007
//
// Use, modification and distribution are subject to 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)

#ifndef BOOST_SETS_DYNAMIC_BITSET_ITERATOR_HPP
#define BOOST_SETS_DYNAMIC_BITSET_ITERATOR_HPP

namespace boost {
namespace sets {

    // The bitset iterator is kind of strange because it's very much unlike
    // other iterators. From an iteration standpoint, this simply lets us
    // count from 0 to the size of the underlying bitset. Sort of. In order
    // to preserve set-like iteration, it should only iterate on objects
    // that are actually _in_ the set (where the bit is on).
    //
    // From a object access standpoint, the bitset iterator should return
    // the object in the set. This happens to correspond to the index where
    // a bit is set, rather than the boolean value of the bit at the index.
    template <typename Block, typename Allocator>
    class bitset_iterator
    {
        typedef dynamic_bitset<Block, Allocator> bitset_type;

        template <typename B, typename A>
        friend bool operator ==(const bitset_iterator<B,A>&, const bitset_iterator<B,A>&);
    public:
        // Important iterator types.
        typedef std::size_t difference_type;
        typedef std::forward_iterator_tag iterator_category;

        // Value related types.
        typedef std::size_t value_type;
        typedef std::size_t* pointer;
        typedef std::size_t reference;

        // Default constructor is past the end of a null bitset. This is
        // basically unitialized.
        bitset_iterator()
            : m_bitset(0)
            , m_index(0)
        { }

        // Copy constructor.
        bitset_iterator(const bitset_iterator& iter)
            : m_bitset(iter.m_bitset)
            , m_index(iter.m_index)
        { }

        // Construct an iterator over the given bitset, starting at the
        // given index. Note that this will search for the first on bit starting
        // at the given index.
        bitset_iterator(const bitset_type& bits, size_t index = 0)
            : m_bitset(&bits)
            , m_index(next(index))
        { }

        bitset_iterator& operator=(const bitset_iterator& x)
        {
            m_bitset = x.m_bitset;
            m_index = x.m_index;
            return *this;
        }

        bitset_iterator& operator ++()
        {
            m_index = next(m_index + 1);
            return *this;
        }


        // The strange thing about the iterator is that it actually returns
        // the index - not the boolean value stored there.
        reference operator *()
        { return m_index; }


    private:
        // This is a helper function that finds the next set bit in the
        // bitset and returns its index. If there is no next element in
        // the set, return past the end.
        std::size_t next(std::size_t index)
        {
            std::size_t n = m_bitset->size();
            for( ; index < n; ++index) {
                if(m_bitset->test(index)) {
                    return index;
                }
            }
            return n;
        }

    private:
        const bitset_type*  m_bitset;
        std::size_t         m_index;
    };


    template <typename B, typename A>
    bool operator ==(const bitset_iterator<B,A>& l, const bitset_iterator<B,A>& r)
    { return l.m_bitset == r.m_bitset && l.m_index == r.m_index; }

    template <typename B, typename A>
    bool operator !=(const bitset_iterator<B,A>& l, const bitset_iterator<B,A>& r)
    { return !(l == r); }

} /* namespace sets */
} /* namespace boost */

#endif