STLContainerWrapper.h

Go to the documentation of this file.

/*
 * Copyright(c) Sophist Solutions, Inc. 1990-2026.  All rights reserved
 */
#ifndef _Stroika_Foundation_Containers_DataStructures_STLContainerWrapper_h_
#define _Stroika_Foundation_Containers_DataStructures_STLContainerWrapper_h_
 
#include "Stroika/Foundation/StroikaPreComp.h"
 
#include "Stroika/Foundation/Common/Common.h"
#include "Stroika/Foundation/Common/Concepts.h"
#include "Stroika/Foundation/Common/TypeHints.h"
#include "Stroika/Foundation/Containers/Common.h"
#include "Stroika/Foundation/Debug/AssertExternallySynchronizedChecker.h"
 
/**
 *  \file
 *
 *  Description:
 *      This module generically wraps STL containers (such as map, vector etc), and facilitates
 *      using them as backends for Stroika containers.
 *
 *  TODO:
 *
 *      @todo   Add special subclass of ForwardIterator that tracks PREVPTR - and use to cleanup stuff
 *              that uses forward_list code...
 *
 *  \note Code-Status:  <a href="Code-Status.md#Beta">Beta</a>
 */
 
namespace Stroika::Foundation::Containers::DataStructures {
 
    namespace Private_ {
        template <typename T>
        using has_erase_t = decltype (declval<T&> ().erase (begin (declval<T&> ()), end (declval<T&> ())));
        template <typename T>
        constexpr inline bool has_erase_v = Common::is_detected_v<has_erase_t, T>;
    }
 
    /**
     *  Use this to wrap an underlying stl container (like std::vector or stl:list, etc) to adapt
     *  it for Stroika containers.
     *
     *  \note   \em Thread-Safety   <a href="Thread-Safety.md#C++-Standard-Thread-Safety">C++-Standard-Thread-Safety</a>
     */
    template <typename STL_CONTAINER_OF_T>
    class STLContainerWrapper : public STL_CONTAINER_OF_T, public Debug::AssertExternallySynchronizedChecker {
    private:
        using inherited = STL_CONTAINER_OF_T;
 
    public:
        using value_type     = typename STL_CONTAINER_OF_T::value_type;
        using iterator       = typename STL_CONTAINER_OF_T::iterator;
        using const_iterator = typename STL_CONTAINER_OF_T::const_iterator;
 
    public:
        /**
         *  Basic (mostly internal) element used by ForwardIterator. Abstract name so can be referenced generically across 'DataStructure' objects
         */
        using UnderlyingIteratorRep = const_iterator;
 
    public:
        /**
         *  pass through CTOR args to underlying container
         */
        template <typename... EXTRA_ARGS>
        STLContainerWrapper (EXTRA_ARGS&&... args);
        constexpr STLContainerWrapper (const STLContainerWrapper&)     = default;
        constexpr STLContainerWrapper (STLContainerWrapper&&) noexcept = default;
 
    public:
        class ForwardIterator;
        class BidirectionalIterator;
        class RandomAccessIterator;
 
    public:
        /*
         *  Support for COW (CopyOnWrite):
         *
         *  Take iterator 'pi' which is originally a valid iterator from 'movedFrom' - and replace *pi with a valid
         *  iterator from 'this' - which points at the same logical position. This requires that this container
         *  was just 'copied' from 'movedFrom' - and is used to produce an equivalent iterator (since iterators are tied to
         *  the container they were iterating over).
         * 
         *      // we iterate over old data structure, and new ones at the same time. return true
         *      // when the newI should be considered to 'match' the old I value. NOTE - the argument lambda MAY use other information, like
         *      // the passed in pi forward iterator
         *      bool pointToSameThingTester (oldI, newI)
         *      {
         *          return true if newI now matches oldI;
         *      }
         * 
         *      // For example, to move in an INDEX like situation, just count the number of times pointToSameThingTester called
         *      bool pointToSameThingTester (oldI, newI)
         *      {
         *          return oldI == origIterator->GetOSRep();
         *      }
         *      // For example, to move in an key equals situation
         *      bool pointToSameThingTester (oldI, newI)
         *      {
         *          return  origIterator->GetOSRep()->fKey == newI->fKey;
         *      }
         */
        template <invocable<typename STL_CONTAINER_OF_T::const_iterator, typename STL_CONTAINER_OF_T::const_iterator> POINT_TO_SAME_THING>
        nonvirtual void MoveIteratorHereAfterClone (ForwardIterator* pi, const STLContainerWrapper* movedFrom, POINT_TO_SAME_THING&& pointToSameThingTester) const
            requires (convertible_to<invoke_result_t<POINT_TO_SAME_THING, typename STL_CONTAINER_OF_T::const_iterator, typename STL_CONTAINER_OF_T::const_iterator>, bool>)
        ;
 
    public:
        nonvirtual bool contains (Common::ArgByValueType<value_type> item) const;
 
    public:
        /**
         *  \note Runtime performance/complexity:
         *      Always: O(N)
         */
        template <invocable<typename STL_CONTAINER_OF_T::value_type> FUNCTION>
        nonvirtual void Apply (FUNCTION&& doToElement) const;
 
    public:
        /**
         *  \note Runtime performance/complexity:
         *      Worst Case: O(N)
         *      Typical: O(N), but can be less if systematically finding entries near start of container
         */
        template <predicate<typename STL_CONTAINER_OF_T::value_type> FUNCTION>
        nonvirtual iterator Find (FUNCTION&& firstThat);
        template <predicate<typename STL_CONTAINER_OF_T::value_type> FUNCTION>
        nonvirtual const_iterator Find (FUNCTION&& firstThat) const;
 
    public:
        template <predicate<typename STL_CONTAINER_OF_T::value_type> PREDICATE>
        nonvirtual bool FindIf (PREDICATE&& pred) const;
 
    public:
        nonvirtual void Invariant () const noexcept;
 
    public:
        nonvirtual iterator remove_constness (const_iterator it);
    };
 
    /**
     *      STLContainerWrapper::ForwardIterator is a private utility class designed
     *  to promote source code sharing among the patched iterator implementations.
     *
     *  \note   ForwardIterator takes a const-pointer the the container as argument since this
     *          iterator never MODIFIES the container.
     *
     *          However, it does a const-cast to maintain a non-const pointer since that is needed to
     *          option a non-const iterator pointer, which is needed by some classes that use this, and
     *          there is no zero (or even low for forward_list) cost way to map from const to non const
     *          iterators (needed to perform the update).
     *
     *          @see https://github.com/SophistSolutions/Stroika/issues/674 (STK-538)
     */
    template <typename STL_CONTAINER_OF_T>
    class STLContainerWrapper<STL_CONTAINER_OF_T>::ForwardIterator {
    public:
        // stuff STL requires you to set to look like an iterator
        using iterator_category = forward_iterator_tag;
        using value_type        = STLContainerWrapper::value_type;
        using difference_type   = ptrdiff_t;
        using pointer           = const value_type*;
        using reference         = const value_type&;
 
    public:
        /**
         *  /0 overload: sets iterator to 'end' - sentinel
         *  /1 (data) overload: sets iterator to begin
         *  /2 (data,startAt) overload: sets iterator to startAt
         */
        constexpr ForwardIterator () noexcept = default;
        explicit constexpr ForwardIterator (const STLContainerWrapper* data) noexcept;
        explicit constexpr ForwardIterator (const STLContainerWrapper* data, UnderlyingIteratorRep startAt) noexcept;
        constexpr ForwardIterator (const ForwardIterator&) noexcept = default;
        constexpr ForwardIterator (ForwardIterator&&) noexcept      = default;
 
    public:
        nonvirtual ForwardIterator& operator= (const ForwardIterator&)     = default;
        nonvirtual ForwardIterator& operator= (ForwardIterator&&) noexcept = default;
 
    public:
        /**
         *  return true if iterator not AtEnd
         */
        explicit operator bool () const;
 
    public:
        nonvirtual bool AtEnd () const noexcept;
 
    public:
        nonvirtual ForwardIterator& operator++ () noexcept;
        nonvirtual ForwardIterator  operator++ (int) noexcept;
 
    public:
        nonvirtual const value_type& operator* () const;
 
    public:
        nonvirtual const value_type* operator->() const;
 
    public:
        /**
         */
        nonvirtual size_t CurrentIndex () const;
 
    public:
        nonvirtual UnderlyingIteratorRep GetUnderlyingIteratorRep () const;
 
    public:
        nonvirtual void SetUnderlyingIteratorRep (UnderlyingIteratorRep l);
 
    public:
        nonvirtual bool operator== (const ForwardIterator& rhs) const;
 
    public:
        /**
         *  For debugging, assert the iterator data matches argument data
         */
        constexpr void AssertDataMatches (const STLContainerWrapper* data) const;
 
    protected:
        const STLContainerWrapper* _fData{nullptr};
        const_iterator             _fStdIterator{};
 
    private:
        friend class STLContainerWrapper;
    };
 
    // see Satisfies Concepts
    static_assert (forward_iterator<typename STLContainerWrapper<vector<int>>::ForwardIterator>);
    static_assert (regular<typename STLContainerWrapper<vector<int>>::ForwardIterator>);
 
    /**
     *  \brief like ForwardIterator, but adding the ability to reverse direction.
     *
     *  \note only usable if the wrapped STL container's iterator itself supports operator-- (e.g. vector, set,
     *        multiset, multimap - but not forward_list).
     *
     *  \note Satisfies Concepts:
     *      o   regular<BidirectionalIterator>
     *      o   bidirectional_iterator<BidirectionalIterator>
     */
    template <typename STL_CONTAINER_OF_T>
    class STLContainerWrapper<STL_CONTAINER_OF_T>::BidirectionalIterator : public ForwardIterator {
    private:
        using inherited = ForwardIterator;
 
    public:
        using iterator_category = bidirectional_iterator_tag;
        using value_type        = typename inherited::value_type;
        using difference_type   = typename inherited::difference_type;
        using pointer           = typename inherited::pointer;
        using reference         = typename inherited::reference;
 
    public:
        using inherited::inherited;
 
    public:
        /**
         *  \brief same as inherited operator++ () - advances iterator - but returning the subclass iterator type.
         */
        nonvirtual BidirectionalIterator& operator++ () noexcept;
        nonvirtual BidirectionalIterator  operator++ (int) noexcept;
 
    public:
        nonvirtual bool AtStart () const noexcept;
 
    public:
        /**
         *  \pre not AtStart ()
         */
        nonvirtual BidirectionalIterator& operator-- () noexcept;
        nonvirtual BidirectionalIterator  operator-- (int) noexcept;
    };
 
    // see Satisfies Concepts
    static_assert (bidirectional_iterator<typename STLContainerWrapper<vector<int>>::BidirectionalIterator>);
    static_assert (regular<typename STLContainerWrapper<vector<int>>::BidirectionalIterator>);
 
    /**
     *  \brief like BidirectionalIterator, but adding random access (operator+=, operator[], etc).
     *
     *  \note only usable if the wrapped STL container's iterator itself is random-access (e.g. vector - but not
     *        set/multiset/multimap/forward_list).
     *
     *  \note Satisfies Concepts:
     *      o   regular<RandomAccessIterator>
     *      o   random_access_iterator<RandomAccessIterator>
     */
    template <typename STL_CONTAINER_OF_T>
    class STLContainerWrapper<STL_CONTAINER_OF_T>::RandomAccessIterator : public BidirectionalIterator {
    private:
        using inherited = BidirectionalIterator;
 
    public:
        using iterator_category = random_access_iterator_tag;
        using value_type        = typename inherited::value_type;
        using difference_type   = ptrdiff_t;
        using pointer           = typename inherited::pointer;
        using reference         = typename inherited::reference;
 
    public:
        using inherited::inherited;
 
    public:
        /**
         *  \brief same as inherited operator++ ()/operator-- () - but returning the subclass iterator type.
         */
        nonvirtual RandomAccessIterator& operator++ () noexcept;
        nonvirtual RandomAccessIterator  operator++ (int) noexcept;
        nonvirtual RandomAccessIterator& operator-- () noexcept;
        nonvirtual RandomAccessIterator  operator-- (int) noexcept;
 
    public:
        nonvirtual RandomAccessIterator  operator+ (difference_type i) const;
        nonvirtual RandomAccessIterator  operator- (difference_type i) const;
        nonvirtual RandomAccessIterator& operator+= (difference_type i);
        nonvirtual RandomAccessIterator& operator-= (difference_type i);
 
    public:
        /**
         *  \brief access the element at the specified index, relative to the current position.
         */
        nonvirtual const value_type& operator[] (difference_type i) const;
 
    public:
        nonvirtual strong_ordering operator<=> (const RandomAccessIterator& rhs) const;
 
    public:
        friend RandomAccessIterator operator+ (difference_type i, const RandomAccessIterator& it)
        {
            return it + i;
        }
 
    public:
        /**
         *  \brief difference between two iterators - handling the 'sentinel' (default-constructed, _fData ==
         *         nullptr, meaning logically 'end') case on either side, same as
         *         Array<T>::ForwardIterator::operator- does.
         */
        friend difference_type operator- (const RandomAccessIterator& lhs, const RandomAccessIterator& rhs)
        {
            if (lhs._fData == nullptr) {
                if (rhs._fData == nullptr) {
                    return 0;
                }
                return static_cast<difference_type> (rhs._fData->size ()) - static_cast<difference_type> (rhs.CurrentIndex ());
            }
            else if (rhs._fData == nullptr) {
                return static_cast<difference_type> (lhs.CurrentIndex ()) - static_cast<difference_type> (lhs._fData->size ());
            }
            else {
                return static_cast<difference_type> (lhs._fStdIterator - rhs._fStdIterator);
            }
        }
    };
 
    // see Satisfies Concepts
    static_assert (random_access_iterator<typename STLContainerWrapper<vector<int>>::RandomAccessIterator>);
    static_assert (regular<typename STLContainerWrapper<vector<int>>::RandomAccessIterator>);
 
    static_assert (ranges::input_range<STLContainerWrapper<vector<int>>>); // smoke test - make sure basic iteration etc should work (allows formattable to work)
 
}
 
/*
 ********************************************************************************
 ***************************** Implementation Details ***************************
 ********************************************************************************
 */
#include "STLContainerWrapper.inl"
 
#endif /*_Stroika_Foundation_Containers_DataStructures_STLContainerWrapper_h_ */