sequence.h

Go to the documentation of this file.

/***************************************************************************
 *   Copyright (C) 2005 by Pierre-Henri WUILLEMIN et Christophe GONZALES   *
 *   {prenom.nom}_at_lip6.fr                                               *
 *                                                                         *
 *   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.                                   *
 *                                                                         *
 *   This program 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 this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/
#ifndef GUM_SEQUENCE_H
#define GUM_SEQUENCE_H

#include <initializer_list>
#include <limits>
#include <type_traits>
#include <vector>

#include <agrum/agrum.h>
#include <agrum/core/hashTable.h>
#include <agrum/core/set.h>

namespace gum {

#ifndef DOXYGEN_SHOULD_SKIP_THIS
  template < typename Key, typename Alloc, bool >
  class SequenceImplementation;
  template < typename Key, typename Alloc >
  class Sequence;
  template < typename Key >
  class SequenceIteratorSafe;
  template < typename Key >
  using SequenceIterator = SequenceIteratorSafe< Key >;
  template < typename Key >
  using SequenceConstIterator = SequenceIteratorSafe< Key >;
#endif

  // ===========================================================================
  // ===                 NON SCALAR GUM SEQUENCE IMPLEMENTATION              ===
  // ===========================================================================
  template < typename Key, typename Alloc, bool Gen >
  class SequenceImplementation {
    template < typename K, typename A, bool >
    friend class SequenceImplementation;
    friend class SequenceIteratorSafe< Key >;
    friend class Sequence< Key, Alloc >;

    public:
    using value_type = Key;
    using reference = Key&;
    using const_reference = const Key&;
    using pointer = Key*;
    using const_pointer = const Key*;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using allocator_type = Alloc;
    using iterator = SequenceIterator< Key >;
    using const_iterator = SequenceIterator< Key >;
    using iterator_safe = SequenceIteratorSafe< Key >;
    using const_iterator_safe = SequenceIteratorSafe< Key >;

    private:
    // ============================================================================
    // ============================================================================

    SequenceImplementation(Size size_param = HashTableConst::default_size);

    SequenceImplementation(std::initializer_list< Key > list);

    SequenceImplementation(const SequenceImplementation< Key, Alloc, Gen >& aSeq);

    template < typename OtherAlloc >
    SequenceImplementation(
       const SequenceImplementation< Key, OtherAlloc, Gen >& aSeq);

    SequenceImplementation(SequenceImplementation< Key, Alloc, Gen >&& aSeq);


    public:
    // ============================================================================
    // ============================================================================

    ~SequenceImplementation() noexcept;

    // ============================================================================
    // ============================================================================

    iterator_safe beginSafe() const;

    iterator_safe rbeginSafe() const;

    const iterator_safe& endSafe() const noexcept;

    const iterator_safe& rendSafe() const noexcept;

    iterator begin() const;

    iterator rbegin() const;

    const iterator& end() const noexcept;

    const iterator& rend() const noexcept;


    private:
    // ============================================================================
    // ============================================================================

    SequenceImplementation< Key, Alloc, Gen >&
       operator=(const SequenceImplementation< Key, Alloc, Gen >& aSeq);

    template < typename OtherAlloc >
    SequenceImplementation< Key, Alloc, Gen >&
       operator=(const SequenceImplementation< Key, OtherAlloc, Gen >& aSeq);

    SequenceImplementation< Key, Alloc, Gen >&
       operator=(SequenceImplementation< Key, Alloc, Gen >&& aSeq);


    public:
    // ============================================================================
    // ============================================================================

    SequenceImplementation< Key, Alloc, Gen >& operator<<(const Key& k);

    SequenceImplementation< Key, Alloc, Gen >& operator<<(Key&& k);

    SequenceImplementation< Key, Alloc, Gen >& operator>>(const Key& k);

    const Key& operator[](Idx i) const;

    template < typename OtherAlloc >
    bool operator==(const SequenceImplementation< Key, OtherAlloc, Gen >& k) const;

    template < typename OtherAlloc >
    bool operator!=(const SequenceImplementation< Key, OtherAlloc, Gen >& k) const;

    // ============================================================================
    // ============================================================================

    void clear();

    Size size() const noexcept;

    bool empty() const noexcept;

    bool exists(const Key& k) const;

    void insert(const Key& k);

    void insert(Key&& k);

    template < typename... Args >
    void emplace(Args&&... args);

    void erase(const Key& k);

    void erase(const iterator_safe& k);

    const Key& atPos(Idx i) const;

    Idx pos(const Key& key) const;

    void setAtPos(Idx i, const Key& newKey);

    void setAtPos(Idx i, Key&& newKey);

    void swap(Idx i, Idx j);

    const Key& front() const;

    const Key& back() const;

    std::string toString() const;

    void resize(Size new_size);


    private:
    HashTable< Key, Idx, Alloc > __h;

    std::vector< Key*, typename Alloc::template rebind< Key* >::other > __v;

    // Note that, using Key* in __v, we actually store the Key only once in the
    // sequence (that is, within __h). This enables storing big objects within
    // sequences without having memory overhead.

    SequenceIteratorSafe< Key > __end_safe;

    SequenceIteratorSafe< Key > __rend_safe;

    void __update_end() noexcept;

    template < typename OtherAlloc >
    void __copy(const SequenceImplementation< Key, OtherAlloc, Gen >& aSeq);

    void __insert(HashTableBucket< Key, Idx >&& bucket);
  };

#ifndef DOXYGEN_SHOULD_SKIP_THIS

  // ===========================================================================
  // ===          GUM_SEQUENCE_IMPLEMENTATION OPTIMIZED FOR SCALARS          ===
  // ===========================================================================
  template < typename Key, typename Alloc >
  class SequenceImplementation< Key, Alloc, true > {
    template < typename K, typename A, bool >
    friend class SequenceImplementation;
    friend class SequenceIteratorSafe< Key >;
    friend class Sequence< Key, Alloc >;

    public:
    using value_type = Key;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using allocator_type = Alloc;
    using iterator = SequenceIterator< Key >;
    using const_iterator = SequenceIterator< Key >;
    using iterator_safe = SequenceIteratorSafe< Key >;
    using const_iterator_safe = SequenceIteratorSafe< Key >;

    private:
    // ============================================================================
    // ============================================================================

    SequenceImplementation(Size size_param = HashTableConst::default_size);

    SequenceImplementation(std::initializer_list< Key > list);

    SequenceImplementation(const SequenceImplementation< Key, Alloc, true >& aSeq);

    template < typename OtherAlloc >
    SequenceImplementation(
       const SequenceImplementation< Key, OtherAlloc, true >& aSeq);

    SequenceImplementation(SequenceImplementation< Key, Alloc, true >&& aSeq);

    public:
    // ============================================================================
    // ============================================================================

    ~SequenceImplementation() noexcept;

    // ============================================================================
    // ============================================================================

    iterator_safe beginSafe() const;

    iterator_safe rbeginSafe() const;

    const iterator_safe& endSafe() const noexcept;

    const iterator_safe& rendSafe() const noexcept;

    iterator begin() const;

    iterator rbegin() const;

    const iterator& end() const noexcept;

    const iterator& rend() const noexcept;


    private:
    // ============================================================================
    // ============================================================================

    SequenceImplementation< Key, Alloc, true >&
       operator=(const SequenceImplementation< Key, Alloc, true >& aSeq);

    template < typename OtherAlloc >
    SequenceImplementation< Key, Alloc, true >&
       operator=(const SequenceImplementation< Key, OtherAlloc, true >& aSeq);

    SequenceImplementation< Key, Alloc, true >&
       operator=(SequenceImplementation< Key, Alloc, true >&& aSeq);


    public:
    // ============================================================================
    // ============================================================================

    SequenceImplementation< Key, Alloc, true >& operator<<(Key k);

    SequenceImplementation< Key, Alloc, true >& operator>>(Key k);

    const Key& operator[](Idx i) const;

    template < typename OtherAlloc >
    bool
       operator==(const SequenceImplementation< Key, OtherAlloc, true >& k) const;

    template < typename OtherAlloc >
    bool
       operator!=(const SequenceImplementation< Key, OtherAlloc, true >& k) const;

    // ============================================================================
    // ============================================================================

    void clear();

    Size size() const noexcept;

    bool empty() const noexcept;

    bool exists(Key k) const;

    void insert(Key k);

    template < typename... Args >
    void emplace(Args&&... args);

    void erase(Key k);

    void erase(const iterator_safe& k);

    const Key& atPos(Idx i) const;

    Idx pos(Key key) const;

    void setAtPos(Idx i, Key newKey);

    void swap(Idx i, Idx j);

    const Key& front() const;

    const Key& back() const;

    std::string toString() const;

    void resize(Size new_size);


    private:
    HashTable< Key, Idx, Alloc > __h;

    std::vector< Key, Alloc > __v;

    SequenceIteratorSafe< Key > __end_safe;

    SequenceIteratorSafe< Key > __rend_safe;

    void __update_end() noexcept;

    template < typename OtherAlloc >
    void __copy(const SequenceImplementation< Key, OtherAlloc, true >& aSeq);

    void __insert(Key k);
  };

#endif /* DOXYGEN_SHOULD_SKIP_THIS */

  // ===========================================================================
  // ===                             GUM_SEQUENCE                            ===
  // ===========================================================================
  template < typename Key, typename Alloc = std::allocator< Key > >
  class Sequence
      : public SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value > {
    public:
    using value_type = Key;
    using reference = Key&;
    using const_reference = const Key&;
    using pointer = Key*;
    using const_pointer = const Key*;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using allocator_type = Alloc;
    using iterator = SequenceIterator< Key >;
    using const_iterator = SequenceIterator< Key >;
    using iterator_safe = SequenceIteratorSafe< Key >;
    using const_iterator_safe = SequenceIteratorSafe< Key >;

    using Implementation =
       SequenceImplementation< Key, Alloc, std::is_scalar< Key >::value >;

    // ============================================================================
    // ============================================================================

    Sequence(Size size_param = HashTableConst::default_size);

    Sequence(std::initializer_list< Key > list);

    Sequence(const Sequence< Key, Alloc >& aSeq);

    template < typename OtherAlloc >
    Sequence(const Sequence< Key, OtherAlloc >& aSeq);

    Sequence(Sequence< Key, Alloc >&& aSeq);

    ~Sequence() noexcept;

    // ============================================================================
    // ============================================================================

    Sequence< Key, Alloc >& operator=(const Sequence< Key, Alloc >& aSeq);

    template < typename OtherAlloc >
    Sequence< Key, Alloc >& operator=(const Sequence< Key, OtherAlloc >& aSeq);

    Sequence< Key, Alloc >& operator=(Sequence< Key, Alloc >&& aSeq);

    // ============================================================================
    // ============================================================================

    template < typename OtherAlloc >
    Set< Key, Alloc > diffSet(const Sequence< Key, OtherAlloc >& seq) const;

  };

#ifndef DOXYGEN_SHOULD_SKIP_THIS

  // dummy classes that will enable discriminate without overhead between
  // scalars and non-scalars operators * and ->
  template < bool gen >
  struct SequenceIteratorGet {
    template < typename Key >
    INLINE static const Key& op_star(const Key* x) {
      return *x;
    }
    template < typename Key >
    INLINE static const Key* op_arrow(const Key* x) {
      return x;
    }
  };

  template <>
  struct SequenceIteratorGet< true > {
    template < typename Key >
    INLINE static const Key& op_star(const Key& x) {
      return x;
    }
    template < typename Key >
    INLINE static const Key* op_arrow(const Key& x) {
      return &x;
    }
  };

#endif /* DOXYGEN_SHOULD_SKIP_THIS */

  // ===========================================================================
  // class SequenceIteratorSafe
  // ===========================================================================
  template < typename Key >
  class SequenceIteratorSafe {
    template < typename K, typename A, bool >
    friend class SequenceImplementation;

    public:
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = Key;
    using reference = Key&;
    using const_reference = const Key&;
    using pointer = Key*;
    using const_pointer = const Key*;
    using difference_type = std::ptrdiff_t;

    private:
    using Getter = SequenceIteratorGet< std::is_scalar< Key >::value >;


    template < typename Alloc, bool Gen >
    SequenceIteratorSafe(const SequenceImplementation< Key, Alloc, Gen >& seq,
                         Idx pos = 0) noexcept;

    public:
    // ============================================================================
    // ============================================================================


    template < typename Alloc >
    SequenceIteratorSafe(const Sequence< Key, Alloc >& seq, Idx pos = 0) noexcept;

    SequenceIteratorSafe(const SequenceIteratorSafe< Key >& source) noexcept;

    SequenceIteratorSafe(SequenceIteratorSafe< Key >&& source) noexcept;

    ~SequenceIteratorSafe() noexcept;

    // ============================================================================
    // ============================================================================

    SequenceIteratorSafe< Key >&
       operator=(const SequenceIteratorSafe< Key >& source) noexcept;

    SequenceIteratorSafe< Key >&
       operator=(SequenceIteratorSafe< Key >&& source) noexcept;

    SequenceIteratorSafe< Key >& operator++() noexcept;

    SequenceIteratorSafe< Key >& operator--() noexcept;

    SequenceIteratorSafe< Key >& operator+=(Size nb) noexcept;

    SequenceIteratorSafe< Key >& operator-=(Size nb) noexcept;

    SequenceIteratorSafe< Key > operator+(Size nb) noexcept;

    SequenceIteratorSafe< Key > operator-(Size nb) noexcept;

    bool operator!=(const SequenceIteratorSafe< Key >& source) const noexcept;

    bool operator==(const SequenceIteratorSafe< Key >& source) const noexcept;

    const Key& operator*() const;

    const Key* operator->() const;

    // ============================================================================
    // ============================================================================

    Idx pos() const;


    private:
    Idx __iterator;

    const SequenceImplementation< Key,
                                  std::allocator< Key >,
                                  std::is_scalar< Key >::value >* __seq;

    void __setPos(Idx pos) noexcept;

    void __setAtRend() noexcept;

    void __setAtEnd() noexcept;
  };

  template < typename Key, typename Alloc >
  std::ostream& operator<<(std::ostream& stream, const Sequence< Key, Alloc >& s);

} /* namespace gum */


#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#  ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#    ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#      ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
extern template class gum::Sequence< int >;
#      endif
#    endif
#  endif
#endif
#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#  ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#    ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#      ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
extern template class gum::Sequence< long >;
#      endif
#    endif
#  endif
#endif

#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#  ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#    ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#      ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
extern template class gum::Sequence< double >;
#      endif
#    endif
#  endif
#endif
#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#  ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#    ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
#      ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
extern template class gum::Sequence< std::string >;
#      endif
#    endif
#  endif
#endif


// always include the implementation of the templates
#include <agrum/core/sequence_tpl.h>

#endif   // GUM_SEQUENCE_H