sequence.h

Go to the documentation of this file.

/****************************************************************************
 *   This file is part of the aGrUM/pyAgrum library.                        *
 *                                                                          *
 *   Copyright (c) 2005-2026 by                                             *
 *       - Pierre-Henri WUILLEMIN(_at_LIP6)                                 *
 *       - Christophe GONZALES(_at_AMU)                                     *
 *                                                                          *
 *   The aGrUM/pyAgrum library is free software; you can redistribute it    *
 *   and/or modify it under the terms of either :                           *
 *                                                                          *
 *    - the GNU Lesser General Public License as published by               *
 *      the Free Software Foundation, either version 3 of the License,      *
 *      or (at your option) any later version,                              *
 *    - the MIT license (MIT),                                              *
 *    - or both in dual license, as here.                                   *
 *                                                                          *
 *   (see https://agrum.gitlab.io/articles/dual-licenses-lgplv3mit.html)    *
 *                                                                          *
 *   This aGrUM/pyAgrum library is distributed in the hope that it will be  *
 *   useful, but WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,          *
 *   INCLUDING BUT NOT LIMITED TO THE WARRANTIES MERCHANTABILITY or FITNESS *
 *   FOR A PARTICULAR PURPOSE  AND NONINFRINGEMENT. IN NO EVENT SHALL THE   *
 *   AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER *
 *   LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,        *
 *   ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR  *
 *   OTHER DEALINGS IN THE SOFTWARE.                                        *
 *                                                                          *
 *   See LICENCES for more details.                                         *
 *                                                                          *
 *   SPDX-FileCopyrightText: Copyright 2005-2026                            *
 *       - Pierre-Henri WUILLEMIN(_at_LIP6)                                 *
 *       - Christophe GONZALES(_at_AMU)                                     *
 *   SPDX-License-Identifier: LGPL-3.0-or-later OR MIT                      *
 *                                                                          *
 *   Contact  : info_at_agrum_dot_org                                       *
 *   homepage : http://agrum.gitlab.io                                      *
 *   gitlab   : https://gitlab.com/agrumery/agrum                           *
 *                                                                          *
 ****************************************************************************/
 

#ifndef GUM_SEQUENCE_H
#define GUM_SEQUENCE_H
 
#include <limits>
#include <vector>
 
#include <agrum/agrum.h>
 
#include <agrum/base/core/set.h>
 
#include <initializer_list>
#include <type_traits>
 
namespace gum {
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
  template < typename Key, bool >
  class SequenceImplementation;
  template < typename Key >
  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, bool Gen >
  class SequenceImplementation {
    friend class SequenceIteratorSafe< Key >;
    friend class Sequence< Key >;
 
    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 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, Gen >& aSeq);

    SequenceImplementation(SequenceImplementation< Key, 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, Gen >& operator=(const SequenceImplementation< Key, Gen >& aSeq);

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

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

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

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

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

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

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

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

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

    void clear();

    Size size() const noexcept;

    bool empty() const noexcept;

    bool exists(const Key& k) const;

    optional_ref< const Idx > tryPos(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 > _h_;

    std::vector< Key* > _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;

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

    void _insert_(HashTableBucket< Key, Idx >&& bucket);
  };
 
#ifndef DOXYGEN_SHOULD_SKIP_THIS
 
  // ===========================================================================
  // ===          GUM_SEQUENCE_IMPLEMENTATION OPTIMIZED FOR SCALARS          ===
  // ===========================================================================
  template < typename Key >
  class SequenceImplementation< Key, true > {
    friend class SequenceIteratorSafe< Key >;
    friend class Sequence< Key >;
 
    public:
    using value_type          = Key;
    using size_type           = std::size_t;
    using difference_type     = std::ptrdiff_t;
    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, true >& aSeq);

    SequenceImplementation(SequenceImplementation< Key, 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, true >& operator=(const SequenceImplementation< Key, true >& aSeq);

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

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

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

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

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

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

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

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

    void clear();

    Size size() const noexcept;

    bool empty() const noexcept;

    bool exists(Key k) const;

    optional_ref< const Idx > tryPos(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 > _h_;

    std::vector< Key > _v_;

    SequenceIteratorSafe< Key > _end_safe_;

    SequenceIteratorSafe< Key > _rend_safe_;

    void _update_end_() noexcept;

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

    void _insert_(Key k);
  };
 
#endif /* DOXYGEN_SHOULD_SKIP_THIS */
 
  // ===========================================================================
  // ===                             GUM_SEQUENCE                            ===
  // ===========================================================================
  template < typename Key >
  class Sequence: public SequenceImplementation< Key, 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 iterator            = SequenceIterator< Key >;
    using const_iterator      = SequenceIterator< Key >;
    using iterator_safe       = SequenceIteratorSafe< Key >;
    using const_iterator_safe = SequenceIteratorSafe< Key >;

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

    Sequence(Size size_param = HashTableConst::default_size);

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

    Sequence(const Sequence< Key >& aSeq);

    Sequence(Sequence< Key >&& aSeq);

    ~Sequence() noexcept;

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

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

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

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

    Set< Key > diffSet(const Sequence< Key >& 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 >
    static const Key& op_star(const Key* x);
 
    template < typename Key >
    static const Key* op_arrow(const Key* x);
  };
 
  template <>
  struct SequenceIteratorGet< true > {
    template < typename Key >
    static const Key& op_star(const Key& x);
 
    template < typename Key >
    static const Key* op_arrow(const Key& x);
  };
 
#endif /* DOXYGEN_SHOULD_SKIP_THIS */
 
  // ===========================================================================
  // class SequenceIteratorSafe
  // ===========================================================================
  template < typename Key >
  class SequenceIteratorSafe {
    template < typename K, 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_v< Key > >;
 

    template < bool Gen >
    SequenceIteratorSafe(const SequenceImplementation< Key, Gen >& seq, Idx pos = 0) noexcept;
 
    public:
    // ============================================================================
    // ============================================================================
 
    SequenceIteratorSafe() = delete;

    SequenceIteratorSafe(const Sequence< Key >& 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::is_scalar_v< Key > >* _seq_{nullptr};

    void _setPos_(Idx pos) noexcept;

    void _setAtRend_() noexcept;

    void _setAtEnd_() noexcept;
  };

  template < typename Key >
  std::ostream& operator<<(std::ostream& stream, const Sequence< Key >& s);
 
} /* namespace gum */
 
 
#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
extern template class gum::Sequence< int >;
extern template class gum::Sequence< long >;
extern template class gum::Sequence< double >;
extern template class gum::Sequence< std::string >;
#endif
 
 
// always include the implementation of the templates
#include <agrum/base/core/sequence_tpl.h>
 
#endif   // GUM_SEQUENCE_H