bitset.hh

Go to the documentation of this file.

// bitset.hh: this file is part of the Vaucanson project.
//
// Vaucanson, a generic library for finite state machines.
//
// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 The Vaucanson Group.
//
// This program 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 2
// of the License, or (at your option) any later version.
//
// The complete GNU General Public Licence Notice can be found as the
// `COPYING' file in the root directory.
//
// The Vaucanson Group consists of people listed in the `AUTHORS' file.
//
#ifndef VCSN_MISC_BITSET_HH
# define VCSN_MISC_BITSET_HH

# include <iterator>
# include <iostream>
# include <functional>

namespace vcsn
{
  namespace misc
  {

    struct Bitset
    {
        typedef int                     key_type;
        typedef int                     value_type;
        typedef std::less<key_type>     key_compare;
        typedef key_compare             value_compare;
        // FIXME: Missing to be std::set compliant: allocator_type.
        // FIXME: reference and const_reference are not real references, because
        // it would prevents a code using a reverse_iterator to compile.
        typedef value_type              reference;
        typedef const value_type        const_reference;
        struct                          iterator;
        struct                          const_iterator;
        typedef unsigned int            size_type;
        typedef int                     difference_type;
        typedef value_type*             pointer;
        typedef const value_type*       const_pointer;
        typedef std::reverse_iterator<iterator>         reverse_iterator;
        typedef std::reverse_iterator<const_iterator>   const_reverse_iterator;

        // data_type is the type used for the bit field.
        typedef unsigned int            data_type;

        // FIXME: Constructors have almost nothing common to std::set.

        Bitset (size_type max);

        Bitset (size_type max, const data_type* data);

        Bitset (const Bitset& bs);

        template <class InputIterator>
        Bitset (InputIterator first, InputIterator last);

        ~Bitset ();

        Bitset& operator= (const Bitset& rhs);


        iterator        begin ();
        const_iterator  begin () const;
        iterator        end ();
        const_iterator  end () const;


        reverse_iterator                rbegin ();
        const_reverse_iterator  rbegin () const;
        reverse_iterator                rend ();
        const_reverse_iterator  rend () const;
        bool    empty () const;
        size_type       size () const;
        size_type       max_size () const;


        std::pair<iterator, bool>       insert (const value_type& x);
        iterator                        insert (iterator position, const value_type& x);
        template <class InputIterator>
        void                    insert (InputIterator first,
                                        InputIterator last);


        void    erase (iterator position);
        size_type       erase (const key_type& x);
        void    erase (iterator first, iterator last);

        void    swap (Bitset& other);

        void    clear ();

        key_compare             key_comp () const;
        value_compare   value_comp () const;

        iterator        find (const key_type& x) const;

        size_type       count (const key_type& x) const;

        iterator                                lower_bound (const key_type& x) const;
        iterator                                upper_bound (const key_type& x) const;
        std::pair<iterator, iterator>   equal_range (const key_type& x) const;

        bool    operator== (const Bitset& rhs) const;
        bool    operator< (const Bitset& rhs) const;
        bool    operator!= (const Bitset& rhs) const;
        bool    operator> (const Bitset& rhs) const;
        bool    operator>= (const Bitset& rhs) const;
        bool    operator<= (const Bitset& rhs) const;

        Bitset  operator& (const Bitset& rhs) const;
        Bitset  operator| (const Bitset& rhs) const;

        bool    operator[] (const key_type& x) const;

        Bitset  project (const Bitset& b) const;

        Bitset  unproject (const Bitset& b) const;

        unsigned        to_unsigned () const;

        template <typename Type>
        const Type      cast () const;

        std::ostream&   print (std::ostream& ostr) const;

      protected:
        static
        size_type       get_data_size (size_type max);

        static
        size_type       get_index (const key_type& x);

        static
        size_type       get_bitnum (const key_type& x);

        bool    get_bit (size_type index, size_type bit) const;

        size_type       compute_size () const;

    /*-------------------.
    | Iterator on bits.  |
    `-------------------*/
        struct bit_iterator
        {
            bit_iterator (size_type index = 0, size_type bitnum = 0);
            const bit_iterator& operator-- ();
            const bit_iterator& operator++ ();
            value_type          operator* () const;
            bool                operator== (const bit_iterator& rhs) const;
            bool                operator!= (const bit_iterator& rhs) const;
            size_type           get_index () const;
            size_type           get_bitnum () const;
          protected:
            size_type   index_;
            size_type   bitnum_;
            value_type  value_;
        };

        bit_iterator            bit_begin () const;
        const bit_iterator&     bit_end () const;

        bool get_bit (const bit_iterator& it) const;

    /*------------------.
    | Actions on bits.  |
    `------------------*/

        template <typename CountType, CountType Start, CountType Step>
        struct BitActionCount
        {
            BitActionCount ();
            CountType value;
            bool operator() (const Bitset& bitset,
                              size_type index,
                              size_type bit,
                              bool value);
        };

    /*--------------------------------.
    | do_on_bit (BitAction, element_t) |
    `--------------------------------*/


        template <class BitAction>
        bool    do_on_bit (BitAction& action, const key_type& x);
        template <class BitAction>
        bool    do_on_bit (BitAction& action, const bit_iterator& it);


        template <class ConstBitAction>
        bool    do_on_bit (ConstBitAction& action, const key_type& x) const;
        template <class ConstBitAction>
        bool    do_on_bit (ConstBitAction& action,
                           const bit_iterator& it) const;
    /*-------------------.
    | Attributes, misc.  |
    `-------------------*/

        enum { invalid_size = static_cast <unsigned int> (-1) };

        size_type               data_size_;
        data_type*              data_;

        size_type               max_size_;
        mutable size_type       size_;
        bit_iterator            end_;

      public:

    /*-----------------.
    | const_iterator.  |
    `-----------------*/

        struct const_iterator
        {
            typedef std::bidirectional_iterator_tag iterator_category;
            typedef Bitset::value_type              value_type;
            typedef Bitset::difference_type         difference_type;
            typedef Bitset::reference               reference;
            typedef Bitset::pointer                 pointer;

            const_iterator ();
            const_iterator (const Bitset* bs);
            const_iterator (const Bitset* bs, const bit_iterator& cbit);
            const_iterator (const const_iterator& it);
            const_iterator (const iterator& it);

            const const_iterator& operator++ ();
            const_iterator        operator++ (int);
            const const_iterator& operator-- ();
            const_iterator        operator-- (int);
            bool                  operator== (const const_iterator& rhs) const;
            bool                  operator== (const iterator& rhs) const;
            bool                  operator!= (const const_iterator& rhs) const;
            bool                  operator!= (const iterator& rhs) const;
            value_type            operator* () const;

          protected:
            void                  skip_zeros_forward ();
            void                  skip_zeros_backward ();

            const Bitset* bs_;
            bit_iterator  cbit_;
        };

    /*-----------.
    | iterator.  |
    `-----------*/

        struct iterator
        {
            typedef std::bidirectional_iterator_tag     iterator_category;
            typedef Bitset::value_type                  value_type;
            typedef Bitset::difference_type             difference_type;
            typedef Bitset::reference                   reference;
            typedef Bitset::pointer                     pointer;

            iterator ();
            iterator (const Bitset* bs);
            iterator (const Bitset* bs, const bit_iterator& cbit);
            iterator (const iterator& it);

            // Friend functions for const_iterator
            friend const_iterator::const_iterator (const iterator& it);

            const iterator&     operator++ ();
            iterator            operator++ (int);
            const iterator&     operator-- ();
            iterator            operator-- (int);
            bool                operator== (const iterator& rhs) const;
            bool                operator== (const const_iterator& rhs) const;
            bool                operator!= (const iterator& rhs) const;
            bool                operator!= (const const_iterator& rhs) const;
            value_type          operator* () const;

          protected:
            void                skip_zeros_forward ();
            void                skip_zeros_backward ();

            const Bitset* bs_;
            bit_iterator  cbit_;
        };
    };


    std::ostream&
    operator<< (std::ostream& ostr, const Bitset& set);

  } // end of namespace misc.
} // end of namespace vcsn.

namespace std
{
  template <>
  void swap (vcsn::misc::Bitset& lhs, vcsn::misc::Bitset& rhs);

  template <>
  class insert_iterator<vcsn::misc::Bitset> :
      public iterator<output_iterator_tag, void, void, void, void>
  {
    public:
      typedef vcsn::misc::Bitset container_type;

      insert_iterator (vcsn::misc::Bitset& x, vcsn::misc::Bitset::iterator);
      insert_iterator<vcsn::misc::Bitset>&
      operator= (vcsn::misc::Bitset::const_reference value);
      insert_iterator<vcsn::misc::Bitset>& operator* ();
      insert_iterator<vcsn::misc::Bitset>& operator++ ();
      insert_iterator<vcsn::misc::Bitset>& operator++ (int);
    protected:
      vcsn::misc::Bitset* container;
  };
}


# if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
#  include <vaucanson/misc/bitset.hxx>
# endif // VCSN_USE_INTERFACE_ONLY


#endif // ! VCSN_MISC_BITSET_HH