const_multiset.h

Go to the documentation of this file.

 
/******************************************************************************
The MIT License(MIT)
 
Embedded Template Library.
https://github.com/ETLCPP/etl
https://www.etlcpp.com
 
Copyright(c) 2025 John Wellbelove
 
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files(the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions :
 
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
 
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
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.
******************************************************************************/
 
#ifndef ETL_CONST_MULTISET_INCLUDED
#define ETL_CONST_MULTISET_INCLUDED
 
#include "platform.h" 
 
#if ETL_NOT_USING_CPP11
  #error NOT SUPPORTED FOR C++03 OR BELOW
#endif
 
#include "algorithm.h"
#include "type_traits.h"
#include "functional.h"
#include "nth_type.h"
#include "span.h"
 
#include "private/comparator_is_transparent.h"

 
namespace etl
{
  template <typename TKey, typename TKeyCompare = etl::less<TKey>>
  class iconst_multiset
  {
  public:
 
    using key_type        = TKey;
    using value_type      = TKey;
    using key_compare     = TKeyCompare;
    using value_compare   = TKeyCompare;
    using const_reference = const value_type&;
    using const_pointer   = const value_type*;
    using const_iterator  = const value_type*;
    using size_type       = size_t;
 
    //*************************************************************************
    //*************************************************************************
    ETL_CONSTEXPR14 bool is_valid() const ETL_NOEXCEPT
    {
      return etl::is_sorted(begin(), end(), vcompare);
    }
 
    //*************************************************************************
    //*************************************************************************
    ETL_CONSTEXPR14 const_iterator begin() const ETL_NOEXCEPT
    {
      return element_list;
    }
 
    //*************************************************************************
    //*************************************************************************
    ETL_CONSTEXPR14 const_iterator cbegin() const ETL_NOEXCEPT
    {
      return element_list;
    }
 
    //*************************************************************************
    //*************************************************************************
    ETL_CONSTEXPR14 const_iterator end() const ETL_NOEXCEPT
    {
      return element_list_end;
    }
 
    //*************************************************************************
    //*************************************************************************
    ETL_CONSTEXPR14 const_iterator cend() const ETL_NOEXCEPT
    {
      return element_list_end;
    }
 
    //*************************************************************************
    //*************************************************************************
    ETL_CONSTEXPR14 const_pointer data() const ETL_NOEXCEPT
    {
      return element_list;
    }
 
    //*************************************************************************
    //*************************************************************************
    ETL_CONSTEXPR14 const_iterator find(const key_type& key) const ETL_NOEXCEPT
    {
      const_iterator itr = lower_bound(key);
 
      if ((itr != end()) && (keys_are_equal(*itr, key)))
      {
        return itr;
      }
 
      return end();
    }
 
    //*************************************************************************
    //*************************************************************************
    template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
    ETL_CONSTEXPR14 const_iterator find(const K& key) const ETL_NOEXCEPT
    {
      const_iterator itr = lower_bound(key);
 
      if ((itr != end()) && (keys_are_equal(*itr, key)))
      {
        return itr;
      }
 
      return end();
    }
 
    //*************************************************************************
    //*************************************************************************
    ETL_CONSTEXPR14 bool contains(const key_type& key) const ETL_NOEXCEPT
    {
      return find(key) != end();
    }
 
    //*************************************************************************
    //*************************************************************************
    template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
    ETL_CONSTEXPR14 bool contains(const K& key) const ETL_NOEXCEPT
    {
      return find(key) != end();
    }
 
    //*************************************************************************
    //*************************************************************************
    ETL_CONSTEXPR14 size_type count(const key_type& key) const ETL_NOEXCEPT
    {
      auto range = equal_range(key);
 
      return size_type(etl::distance(range.first, range.second));
    }
      
    //*************************************************************************
    //*************************************************************************
    template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
    ETL_CONSTEXPR14 size_type count(const K& key) const ETL_NOEXCEPT
    {
      auto range = equal_range(key);
 
      return size_type(etl::distance(range.first, range.second));
    }
 
    //*************************************************************************
    //*************************************************************************
    ETL_CONSTEXPR14 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(const key_type& key) const ETL_NOEXCEPT
    {
      return etl::equal_range(begin(), end(), key, vcompare);
    }
 
    //*************************************************************************
    //*************************************************************************
    template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
    ETL_CONSTEXPR14 ETL_OR_STD::pair<const_iterator, const_iterator> equal_range(const K& key) const ETL_NOEXCEPT
    {
      return etl::equal_range(begin(), end(), key, vcompare);
    }
 
    //*************************************************************************
    //*************************************************************************
    ETL_CONSTEXPR14 const_iterator lower_bound(const key_type& key) const ETL_NOEXCEPT
    {
      return etl::lower_bound(begin(), end(), key, vcompare);
    }
 
    //*************************************************************************
    //*************************************************************************
    template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
    ETL_CONSTEXPR14 const_iterator lower_bound(const K& key) const ETL_NOEXCEPT
    {
      return etl::lower_bound(begin(), end(), key, vcompare);
    }
 
    //*************************************************************************
    //*************************************************************************
    ETL_CONSTEXPR14 const_iterator upper_bound(const key_type& key) const ETL_NOEXCEPT
    {
      return etl::upper_bound(begin(), end(), key, vcompare);
    }
 
    //*************************************************************************
    //*************************************************************************
    template <typename K, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
    ETL_CONSTEXPR14 const_iterator upper_bound(const K& key) const ETL_NOEXCEPT
    {
      return etl::upper_bound(begin(), end(), key, vcompare);
    }
 
    //*************************************************************************
    //*************************************************************************
    ETL_CONSTEXPR14 size_type empty() const ETL_NOEXCEPT
    {
      return size() == 0U;
    }
 
    //*************************************************************************
    //*************************************************************************
    ETL_CONSTEXPR14 size_type full() const ETL_NOEXCEPT
    {
      return (max_elements != 0) && (size() == max_elements);
    }
 
    //*************************************************************************
    //*************************************************************************
    ETL_CONSTEXPR14 size_type size() const ETL_NOEXCEPT
    {
      return size_type(element_list_end - element_list);
    }
 
    //*************************************************************************
    //*************************************************************************
    ETL_CONSTEXPR14 size_type max_size() const ETL_NOEXCEPT
    {
      return max_elements;
    }
 
    //*************************************************************************
    //*************************************************************************
    ETL_CONSTEXPR14 size_type capacity() const ETL_NOEXCEPT
    {
      return max_elements;
    }
 
    //*************************************************************************
    //*************************************************************************
    ETL_CONSTEXPR14 key_compare key_comp() const ETL_NOEXCEPT
    {
      return kcompare;
    }
 
    //*************************************************************************
    //*************************************************************************
    ETL_CONSTEXPR14 value_compare value_comp() const ETL_NOEXCEPT
    {
      return vcompare;
    }
 
  protected:
 
    //*************************************************************************
    //*************************************************************************
    template <typename... TElements>
    ETL_CONSTEXPR14 explicit iconst_multiset(const value_type* element_list_, size_type size_, size_type max_elements_) ETL_NOEXCEPT
      : element_list(element_list_)
      , element_list_end{element_list_ + size_}
      , max_elements(max_elements_)
    {
    }
 
  private:
 
    //*********************************************************************
    //*********************************************************************
    ETL_CONSTEXPR14 bool keys_are_equal(const key_type& key1, const key_type& key2) const ETL_NOEXCEPT
    {
      return !key_compare()(key1, key2) && !key_compare()(key2, key1);
    }
 
    //*********************************************************************
    //*********************************************************************
    template <typename K1, typename K2, typename KC = TKeyCompare, etl::enable_if_t<comparator_is_transparent<KC>::value, int> = 0>
    ETL_CONSTEXPR14 bool keys_are_equal(const K1& key1, const K2& key2) const ETL_NOEXCEPT
    {
      return !key_compare()(key1, key2) && !key_compare()(key2, key1);
    }
 
    key_compare   kcompare;
    value_compare vcompare;
 
    const value_type* element_list;
    const value_type* element_list_end;
    size_type   max_elements;
  };
 
  //*************************************************************************
  //*************************************************************************
  template <typename TKey, size_t Size, typename TKeyCompare = etl::less<TKey>>
  class const_multiset : public iconst_multiset<TKey, TKeyCompare>
  {
  public:
 
    using base_t = iconst_multiset<TKey, TKeyCompare>;
 
    using key_type        = typename base_t::key_type;
    using value_type      = typename base_t::value_type;
    using key_compare     = typename base_t::key_compare;
    using const_reference = typename base_t::const_reference;
    using const_pointer   = typename base_t::const_pointer;
    using const_iterator  = typename base_t::const_iterator;
    using size_type       = typename base_t::size_type;
 
    static_assert((etl::is_default_constructible<key_type>::value), "key_type must be default constructible");
 
    //*************************************************************************
    //*************************************************************************
    template <typename... TElements>
    ETL_CONSTEXPR14 explicit const_multiset(TElements&&... elements) ETL_NOEXCEPT
      : iconst_multiset<TKey, TKeyCompare>(element_list, sizeof...(elements), Size)
      , element_list{etl::forward<TElements>(elements)...}
    {
      static_assert((etl::are_all_same<value_type, etl::decay_t<TElements>...>::value), "All elements must be value_type");
      static_assert(sizeof...(elements) <= Size,                                        "Number of elements exceeds capacity");
    }
 
  private:
 
    value_type element_list[Size];
  };
 
  //*************************************************************************
  //*************************************************************************
#if ETL_USING_CPP17
  template <typename... TElements>
  const_multiset(TElements...) -> const_multiset<etl::nth_type_t<0, TElements...>, sizeof...(TElements)>;
#endif
 
  //*********************************************************************
  //*********************************************************************
  template <typename TKey, typename TKeyCompare = etl::less<TKey>>
  class const_multiset_ext : public iconst_multiset<TKey, TKeyCompare>
  {
  public:
 
    using base_t = iconst_multiset<TKey, TKeyCompare>;
 
    using key_type        = typename base_t::key_type;
    using value_type      = typename base_t::value_type;
    using key_compare     = typename base_t::key_compare;
    using const_reference = typename base_t::const_reference;
    using const_pointer   = typename base_t::const_pointer;
    using const_iterator  = typename base_t::const_iterator;
    using size_type       = typename base_t::size_type;
 
    static_assert((etl::is_default_constructible<key_type>::value), "key_type must be default constructible");
 
    //*************************************************************************
    //*************************************************************************
    ETL_CONSTEXPR14 const_multiset_ext() ETL_NOEXCEPT
      : iconst_multiset<TKey, TKeyCompare>(nullptr, 0, 0)
    {
    }
 
    //*************************************************************************
    //*************************************************************************
    template <size_type Size>
    ETL_CONSTEXPR14 explicit const_multiset_ext(const etl::span<const value_type, Size>& sp) ETL_NOEXCEPT
      : iconst_multiset<TKey, TKeyCompare>(sp.data(), Size, Size)
    {
    }
 
    //*************************************************************************
    //*************************************************************************
    template <size_type Size>
    ETL_CONSTEXPR14 explicit const_multiset_ext(const value_type(&begin_)[Size]) ETL_NOEXCEPT
      : iconst_multiset<TKey, TKeyCompare>(begin_, Size, Size)
    {
    }
  };
 
  //*************************************************************************
  //*************************************************************************
#if ETL_USING_CPP17
  template <typename TElements, size_t Size>
  const_multiset_ext(const etl::span<TElements, Size>&) -> const_multiset_ext<TElements>;
 
  template <typename TElements, size_t Size>
  const_multiset_ext(const TElements(&)[Size]) -> const_multiset_ext<TElements>;
#endif
 
  //*************************************************************************
  //*************************************************************************
  template <typename TKey, typename TKeyCompare>
  ETL_CONSTEXPR14 bool operator ==(const etl::iconst_multiset<TKey, TKeyCompare>& lhs,
                                   const etl::iconst_multiset<TKey, TKeyCompare>& rhs) ETL_NOEXCEPT
  {
    return (lhs.size() == rhs.size()) && etl::equal(lhs.begin(), lhs.end(), rhs.begin());
  }
 
  //*************************************************************************
  //*************************************************************************
  template <typename TKey, typename TKeyCompare>
  ETL_CONSTEXPR14 bool operator !=(const etl::iconst_multiset<TKey, TKeyCompare>& lhs,
                                   const etl::iconst_multiset<TKey, TKeyCompare>& rhs) ETL_NOEXCEPT
  {
    return !(lhs == rhs);
  }
 
  //*************************************************************************
  //*************************************************************************
  template <typename TKey, typename TKeyCompare>
  ETL_CONSTEXPR14 bool operator <(const etl::iconst_multiset<TKey, TKeyCompare>& lhs,
                                  const etl::iconst_multiset<TKey, TKeyCompare>& rhs) ETL_NOEXCEPT
  {
    return etl::lexicographical_compare(lhs.begin(), lhs.end(), 
                                        rhs.begin(), rhs.end(),
                                        lhs.value_comp());
  }
 
  //*************************************************************************
  //*************************************************************************
  template <typename TKey, typename TKeyCompare>
  ETL_CONSTEXPR14 bool operator >(const etl::iconst_multiset<TKey, TKeyCompare>& lhs,
                                  const etl::iconst_multiset<TKey, TKeyCompare>& rhs) ETL_NOEXCEPT
  {
    return (rhs < lhs);
  }
 
  //*************************************************************************
  //*************************************************************************
  template <typename TKey, typename TKeyCompare>
  ETL_CONSTEXPR14 bool operator <=(const etl::iconst_multiset<TKey, TKeyCompare>& lhs,
                                   const etl::iconst_multiset<TKey, TKeyCompare>& rhs) ETL_NOEXCEPT
  {
    return !(rhs < lhs);
  }
 
  //*************************************************************************
  //*************************************************************************
  template <typename TKey, typename TKeyCompare>
  ETL_CONSTEXPR14 bool operator >=(const etl::iconst_multiset<TKey, TKeyCompare>& lhs,
                                   const etl::iconst_multiset<TKey, TKeyCompare>& rhs) ETL_NOEXCEPT
  {
    return !(lhs < rhs);
  }
}
 
#endif