/**
 * @file llstl.h
 * @brief helper object & functions for use with the stl.
 *
 * $LicenseInfo:firstyear=2003&license=viewerlgpl$
 * Second Life Viewer Source Code
 * Copyright (C) 2010, Linden Research, Inc.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation;
 * version 2.1 of the License only.
 *
 * This library 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
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 *
 * Linden Research, Inc., 945 Battery Street, San Francisco, CA  94111  USA
 * $/LicenseInfo$
 */

#ifndef LL_LLSTL_H
#define LL_LLSTL_H

#include "stdtypes.h"
#include <functional>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <typeindex>
#include <typeinfo>
#include <boost/iterator/filter_iterator.hpp>

#ifdef LL_LINUX
// <ND> For strcmp
#include <string.h>
#endif
// Use to compare the first element only of a pair
// e.g. typedef std::set<std::pair<int, Data*>, compare_pair<int, Data*> > some_pair_set_t;
template <typename T1, typename T2>
struct compare_pair_first
{
    bool operator()(const std::pair<T1, T2>& a, const std::pair<T1, T2>& b) const
    {
        return a.first < b.first;
    }
};

template <typename T1, typename T2>
struct compare_pair_greater
{
    bool operator()(const std::pair<T1, T2>& a, const std::pair<T1, T2>& b) const
    {
        if (!(a.first < b.first))
            return true;
        else if (!(b.first < a.first))
            return false;
        else
            return !(a.second < b.second);
    }
};

// Use to compare the contents of two pointers (e.g. std::string*)
template <typename T>
struct compare_pointer_contents
{
    typedef const T* Tptr;
    bool operator()(const Tptr& a, const Tptr& b) const
    {
        return *a < *b;
    }
};

// DeletePointer is a simple helper for deleting all pointers in a container.
// The general form is:
//
//  std::for_each(cont.begin(), cont.end(), DeletePointer());
//  somemap.clear();
//
// Don't forget to clear()!

struct DeletePointer
{
    template<typename T> void operator()(T* ptr) const
    {
        delete ptr;
    }
};
struct DeletePointerArray
{
    template<typename T> void operator()(T* ptr) const
    {
        delete[] ptr;
    }
};

// DeletePairedPointer is a simple helper for deleting all pointers in a map.
// The general form is:
//
//  std::for_each(somemap.begin(), somemap.end(), DeletePairedPointer());
//  somemap.clear();        // Don't leave dangling pointers around

struct DeletePairedPointer
{
    template<typename T> void operator()(T &ptr) const
    {
        delete ptr.second;
        ptr.second = NULL;
    }
};
struct DeletePairedPointerArray
{
    template<typename T> void operator()(T &ptr) const
    {
        delete[] ptr.second;
        ptr.second = NULL;
    }
};


// Alternate version of the above so that has a more cumbersome
// syntax, but it can be used with compositional functors.
// NOTE: The functor retuns a bool because msdev bombs during the
// composition if you return void. Once we upgrade to a newer
// compiler, the second unary_function template parameter can be set
// to void.
//
// Here's a snippet showing how you use this object:
//
// typedef std::map<int, widget*> map_type;
// map_type widget_map;
// ... // add elements
// // delete them all
// for_each(widget_map.begin(),
//          widget_map.end(),
//          llcompose1(DeletePointerFunctor<widget>(),
//                     llselect2nd<map_type::value_type>()));

template<typename T>
struct DeletePointerFunctor
{
    bool operator()(T* ptr) const
    {
        delete ptr;
        return true;
    }
};

// See notes about DeleteArray for why you should consider avoiding this.
template<typename T>
struct DeleteArrayFunctor
{
    bool operator()(T* ptr) const
    {
        delete[] ptr;
        return true;
    }
};

// CopyNewPointer is a simple helper which accepts a pointer, and
// returns a new pointer built with the copy constructor. Example:
//
//  transform(in.begin(), in.end(), out.end(), CopyNewPointer());

struct CopyNewPointer
{
    template<typename T> T* operator()(const T* ptr) const
    {
        return new T(*ptr);
    }
};

template<typename T, typename ALLOC>
void delete_and_clear(std::list<T*, ALLOC>& list)
{
    std::for_each(list.begin(), list.end(), DeletePointer());
    list.clear();
}

template<typename T, typename ALLOC>
void delete_and_clear(std::vector<T*, ALLOC>& vector)
{
    std::for_each(vector.begin(), vector.end(), DeletePointer());
    vector.clear();
}

template<typename T, typename COMPARE, typename ALLOC>
void delete_and_clear(std::set<T*, COMPARE, ALLOC>& set)
{
    std::for_each(set.begin(), set.end(), DeletePointer());
    set.clear();
}

template<typename K, typename V, typename COMPARE, typename ALLOC>
void delete_and_clear(std::map<K, V*, COMPARE, ALLOC>& map)
{
    std::for_each(map.begin(), map.end(), DeletePairedPointer());
    map.clear();
}

template<typename T>
void delete_and_clear(T*& ptr)
{
    delete ptr;
    ptr = NULL;
}


template<typename T>
void delete_and_clear_array(T*& ptr)
{
    delete[] ptr;
    ptr = NULL;
}

// Simple function to help with finding pointers in maps.
// For example:
//  typedef  map_t;
//  std::map<int, const char*> foo;
//  foo[18] = "there";
//  foo[2] = "hello";
//  const char* bar = get_ptr_in_map(foo, 2); // bar -> "hello"
//  const char* baz = get_ptr_in_map(foo, 3); // baz == NULL
template <typename T>
inline typename T::mapped_type get_ptr_in_map(const T& inmap, typename T::key_type const& key)
{
    auto iter = inmap.find(key);
    if(iter == inmap.end())
    {
        return nullptr;
    }
    else
    {
        return iter->second;
    }
};

// helper function which returns true if key is in inmap.
template <typename T>
inline bool is_in_map(const T& inmap, typename T::key_type const& key)
{
    if(inmap.find(key) == inmap.end())
    {
        return false;
    }
    else
    {
        return true;
    }
}

// Similar to get_ptr_in_map, but for any type with a valid T(0) constructor.
// To replace LLSkipMap getIfThere, use:
//   get_if_there(map, key, 0)
// WARNING: Make sure default_value (generally 0) is not a valid map entry!
template <typename T>
inline typename T::mapped_type get_if_there(const T& inmap, typename T::key_type const& key, typename T::mapped_type default_value)
{
    auto iter = inmap.find(key);
    if(iter == inmap.end())
    {
        return default_value;
    }
    else
    {
        return iter->second;
    }
};

// Useful for replacing the removeObj() functionality of LLDynamicArray
// Example:
//  for (std::vector<T>::iterator iter = mList.begin(); iter != mList.end(); )
//  {
//    if ((*iter)->isMarkedForRemoval())
//      iter = vector_replace_with_last(mList, iter);
//    else
//      ++iter;
//  }
template <typename T>
inline typename std::vector<T>::iterator vector_replace_with_last(std::vector<T>& invec, typename std::vector<T>::iterator iter)
{
    typename std::vector<T>::iterator last = invec.end(); --last;
    if (iter == invec.end())
    {
        return iter;
    }
    else if (iter == last)
    {
        invec.pop_back();
        return invec.end();
    }
    else
    {
        *iter = *last;
        invec.pop_back();
        return iter;
    }
};

// Example:
//   vector_replace_with_last(mList, x);
template <typename T>
inline bool vector_replace_with_last(std::vector<T>& invec, const T& val)
{
    typename std::vector<T>::iterator iter = std::find(invec.begin(), invec.end(), val);
    if (iter != invec.end())
    {
        typename std::vector<T>::iterator last = invec.end(); --last;
        *iter = *last;
        invec.pop_back();
        return true;
    }
    return false;
}

// Append N elements to the vector and return a pointer to the first new element.
template <typename T>
inline T* vector_append(std::vector<T>& invec, S32 N)
{
    auto sz = invec.size();
    invec.resize(sz+N);
    return &(invec[sz]);
}

// call function f to n members starting at first. similar to std::for_each
template <class InputIter, class Size, class Function>
Function ll_for_n(InputIter first, Size n, Function f)
{
    for ( ; n > 0; --n, ++first)
        f(*first);
    return f;
}

// copy first to result n times, incrementing each as we go
template <class InputIter, class Size, class OutputIter>
OutputIter ll_copy_n(InputIter first, Size n, OutputIter result)
{
    for ( ; n > 0; --n, ++result, ++first)
        *result = *first;
    return result;
}

// set  *result = op(*f) for n elements of f
template <class InputIter, class OutputIter, class Size, class UnaryOp>
OutputIter ll_transform_n(
    InputIter first,
    Size n,
    OutputIter result,
    UnaryOp op)
{
    for ( ; n > 0; --n, ++result, ++first)
        *result = op(*first);
    return result;
}



/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1996-1998
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */


// helper to deal with the fact that MSDev does not package
// select... with the stl. Look up usage on the sgi website.

template <class _Pair>
struct _LLSelect1st
{
  const auto& operator()(const _Pair& __x) const {
    return __x.first;
  }
};

template <class _Pair>
struct _LLSelect2nd
{
  const auto& operator()(const _Pair& __x) const {
    return __x.second;
  }
};

template <class _Pair> struct llselect1st : public _LLSelect1st<_Pair> {};
template <class _Pair> struct llselect2nd : public _LLSelect2nd<_Pair> {};

// helper to deal with the fact that MSDev does not package
// compose... with the stl. Look up usage on the sgi website.

template <class _Operation1, class _Operation2>
class ll_unary_compose
{
protected:
  _Operation1 __op1;
  _Operation2 __op2;
public:
  ll_unary_compose(const _Operation1& __x, const _Operation2& __y)
    : __op1(__x), __op2(__y) {}
  template <typename _Op2Arg>
  auto
  operator()(const _Op2Arg& __x) const {
    return __op1(__op2(__x));
  }
};

template <class _Operation1, class _Operation2>
inline ll_unary_compose<_Operation1,_Operation2>
llcompose1(const _Operation1& __op1, const _Operation2& __op2)
{
  return ll_unary_compose<_Operation1,_Operation2>(__op1, __op2);
}

template <class _Operation1, class _Operation2, class _Operation3>
class ll_binary_compose
{
protected:
  _Operation1 _M_op1;
  _Operation2 _M_op2;
  _Operation3 _M_op3;
public:
  ll_binary_compose(const _Operation1& __x, const _Operation2& __y,
                    const _Operation3& __z)
    : _M_op1(__x), _M_op2(__y), _M_op3(__z) { }
  template<typename OP2ARG>
  auto
  operator()(const OP2ARG& __x) const {
    return _M_op1(_M_op2(__x), _M_op3(__x));
  }
};

template <class _Operation1, class _Operation2, class _Operation3>
inline ll_binary_compose<_Operation1, _Operation2, _Operation3>
llcompose2(const _Operation1& __op1, const _Operation2& __op2,
         const _Operation3& __op3)
{
  return ll_binary_compose<_Operation1,_Operation2,_Operation3>
    (__op1, __op2, __op3);
}

// helpers to deal with the fact that MSDev does not package
// bind... with the stl. Again, this is from sgi.
template <class _Operation, typename _Arg1>
class llbinder1st
{
protected:
  _Operation op;
  _Arg1 value;
public:
  llbinder1st(const _Operation& __x, const _Arg1& __y)
      : op(__x), value(__y) {}
    template <typename _Arg2>
    auto
    operator()(const _Arg2& __x) const {
        return op(value, __x);
    }
};

template <class _Operation, class _Tp>
inline auto
llbind1st(const _Operation& __oper, const _Tp& __x)
{
  return llbinder1st<_Operation, _Tp>(__oper, __x);
}

template <class _Operation, typename _Arg2>
class llbinder2nd
{
protected:
    _Operation op;
    _Arg2 value;
public:
    llbinder2nd(const _Operation& __x,
                const _Arg2& __y)
        : op(__x), value(__y) {}
    template <typename _Arg1>
    auto
    operator()(const _Arg1& __x) const {
        return op(__x, value);
    }
};

template <class _Operation, class _Tp>
inline auto
llbind2nd(const _Operation& __oper, const _Tp& __x)
{
  return llbinder2nd<_Operation, _Tp>(__oper, __x);
}

/**
 * Compare std::type_info* pointers a la std::less. We break this out as a
 * separate function for use in two different std::less specializations.
 */
inline
bool before(const std::type_info* lhs, const std::type_info* rhs)
{
    // Just use before(), as we normally would
    return lhs->before(*rhs);
}

/**
 * Specialize std::less<std::type_info*> to use std::type_info::before().
 * See MAINT-1175. It is NEVER a good idea to directly compare std::type_info*
 * because, on Linux, you might get different std::type_info* pointers for the
 * same type (from different load modules)!
 */
namespace std
{
    template <>
    struct less<const std::type_info*>
    {
        bool operator()(const std::type_info* lhs, const std::type_info* rhs) const
        {
            return before(lhs, rhs);
        }
    };

    template <>
    struct less<std::type_info*>
    {
        bool operator()(std::type_info* lhs, std::type_info* rhs) const
        {
            return before(lhs, rhs);
        }
    };
} // std


/**
 * Implementation for ll_template_cast() (q.v.).
 *
 * Default implementation: trying to cast two completely unrelated types
 * returns 0. Typically you'd specify T and U as pointer types, but in fact T
 * can be any type that can be initialized with 0.
 */
template <typename T, typename U>
struct ll_template_cast_impl
{
    T operator()(U)
    {
        return 0;
    }
};

/**
 * ll_template_cast<T>(some_value) is for use in a template function when
 * some_value might be of arbitrary type, but you want to recognize type T
 * specially.
 *
 * It's designed for use with pointer types. Example:
 * @code
 * struct SpecialClass
 * {
 *     void someMethod(const std::string&) const;
 * };
 *
 * template <class REALCLASS>
 * void somefunc(const REALCLASS& instance)
 * {
 *     const SpecialClass* ptr = ll_template_cast<const SpecialClass*>(&instance);
 *     if (ptr)
 *     {
 *         ptr->someMethod("Call method only available on SpecialClass");
 *     }
 * }
 * @endcode
 *
 * Why is this better than dynamic_cast<>? Because unless OtherClass is
 * polymorphic, the following won't even compile (gcc 4.0.1):
 * @code
 * OtherClass other;
 * SpecialClass* ptr = dynamic_cast<SpecialClass*>(&other);
 * @endcode
 * to say nothing of this:
 * @code
 * void function(int);
 * SpecialClass* ptr = dynamic_cast<SpecialClass*>(&function);
 * @endcode
 * ll_template_cast handles these kinds of cases by returning 0.
 */
template <typename T, typename U>
T ll_template_cast(U value)
{
    return ll_template_cast_impl<T, U>()(value);
}

/**
 * Implementation for ll_template_cast() (q.v.).
 *
 * Implementation for identical types: return same value.
 */
template <typename T>
struct ll_template_cast_impl<T, T>
{
    T operator()(T value)
    {
        return value;
    }
};

/**
 * LL_TEMPLATE_CONVERTIBLE(dest, source) asserts that, for a value @c s of
 * type @c source, <tt>ll_template_cast<dest>(s)</tt> will return @c s --
 * presuming that @c source can be converted to @c dest by the normal rules of
 * C++.
 *
 * By default, <tt>ll_template_cast<dest>(s)</tt> will return 0 unless @c s's
 * type is literally identical to @c dest. (This is because of the
 * straightforward application of template specialization rules.) That can
 * lead to surprising results, e.g.:
 *
 * @code
 * Foo myFoo;
 * const Foo* fooptr = ll_template_cast<const Foo*>(&myFoo);
 * @endcode
 *
 * Here @c fooptr will be 0 because <tt>&myFoo</tt> is of type <tt>Foo*</tt>
 * -- @em not <tt>const Foo*</tt>. (Declaring <tt>const Foo myFoo;</tt> would
 * force the compiler to do the right thing.)
 *
 * More disappointingly:
 * @code
 * struct Base {};
 * struct Subclass: public Base {};
 * Subclass object;
 * Base* ptr = ll_template_cast<Base*>(&object);
 * @endcode
 *
 * Here @c ptr will be 0 because <tt>&object</tt> is of type
 * <tt>Subclass*</tt> rather than <tt>Base*</tt>. We @em want this cast to
 * succeed, but without our help ll_template_cast can't recognize it.
 *
 * The following would suffice:
 * @code
 * LL_TEMPLATE_CONVERTIBLE(Base*, Subclass*);
 * ...
 * Base* ptr = ll_template_cast<Base*>(&object);
 * @endcode
 *
 * However, as noted earlier, this is easily fooled:
 * @code
 * const Base* ptr = ll_template_cast<const Base*>(&object);
 * @endcode
 * would still produce 0 because we haven't yet seen:
 * @code
 * LL_TEMPLATE_CONVERTIBLE(const Base*, Subclass*);
 * @endcode
 *
 * @TODO
 * This macro should use Boost type_traits facilities for stripping and
 * re-adding @c const and @c volatile qualifiers so that invoking
 * LL_TEMPLATE_CONVERTIBLE(dest, source) will automatically generate all
 * permitted permutations. It's really not fair to the coder to require
 * separate:
 * @code
 * LL_TEMPLATE_CONVERTIBLE(Base*, Subclass*);
 * LL_TEMPLATE_CONVERTIBLE(const Base*, Subclass*);
 * LL_TEMPLATE_CONVERTIBLE(const Base*, const Subclass*);
 * @endcode
 *
 * (Naturally we omit <tt>LL_TEMPLATE_CONVERTIBLE(Base*, const Subclass*)</tt>
 * because that's not permitted by normal C++ assignment anyway.)
 */
#define LL_TEMPLATE_CONVERTIBLE(DEST, SOURCE)   \
template <>                                     \
struct ll_template_cast_impl<DEST, SOURCE>      \
{                                               \
    DEST operator()(SOURCE wrapper)             \
    {                                           \
        return wrapper;                         \
    }                                           \
}

//-----------------------------------------------
namespace LL
{
    /**
     * @brief A range adapter that provides filtered iteration over a container.
     *
     * filter_range creates a filtered view of an iterator range using a predicate function.
     * Only elements that satisfy the predicate will be accessible when iterating through
     * the range. This is useful for processing subsets of containers without copying data.
     *
     * The class uses boost::filter_iterator internally to provide the filtering functionality.
     *
     * @tparam Predicate A callable object (function, functor, lambda) that takes an element
     *                   from the iterator range and returns true if the element should be
     *                   included in the filtered range.
     * @tparam Iterator  The iterator type for the underlying container/range.
     *
     * Example usage:
     * @code
     * std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
     *
     * // Create a predicate to filter even numbers
     * auto is_even = [](int n) { return n % 2 == 0; };
     *
     * // Create filtered range using make_filter helper
     * auto even_range = LL::make_filter(is_even, numbers.begin(), numbers.end());
     *
     * // Iterate through only even numbers
     * for (auto value : even_range) {
     *     std::cout << value << " "; // Prints: 2 4 6 8 10
     * }
     *
     * // Or manually construct the filter_range
     * LL::filter_range<decltype(is_even), std::vector<int>::iterator>
     *     manual_range(is_even, numbers.begin(), numbers.end());
     * @endcode
     *
     * @note This class provides a lightweight view over the original data.
     *       No copying of elements occurs, making it efficient for large containers.
     * @note The predicate is applied during iteration, so complex predicates may
     *       impact performance for frequently-accessed ranges.
     * @note The underlying container must remain valid for the lifetime of the filter_range.
     *
     * @see make_filter() for a convenient factory function
     * @see boost::filter_iterator for the underlying implementation details
     */
    template<typename Predicate, typename Iterator>
    class filter_range
    {
    public:
        /// The filtered iterator type - combines predicate with base iterator
        using filter_iter = boost::filter_iterator<Predicate, Iterator>;

        /// Value type of the filtered elements
        using value_type = typename std::iterator_traits<Iterator>::value_type;

        /// Iterator type for range-based for loops and STL algorithms
        using iterator = filter_iter;
        using const_iterator = filter_iter;

        /**
         * @brief Constructs a filter_range with the given predicate and iterator range.
         *
         * @param pred  The predicate function/functor to filter elements.
         *              Must be callable with signature: bool(const value_type&)
         * @param begin Iterator to the beginning of the range to filter
         * @param end   Iterator to the end of the range to filter
         *
         * @pre begin and end must form a valid iterator range
         * @pre pred must be a valid callable that can be invoked with elements from [begin, end)
         */
        filter_range(Predicate pred, Iterator begin, Iterator end)
            : begin_(pred, begin, end), end_(pred, end, end) {}

        /**
         * @brief Returns an iterator to the first element that satisfies the predicate.
         *
         * @return filter_iter Iterator pointing to the first filtered element,
         *                     or equal to end() if no elements satisfy the predicate.
         */
        filter_iter begin() const { return begin_; }

        /**
         * @brief Returns an iterator representing the end of the filtered range.
         *
         * @return filter_iter Past-the-end iterator for the filtered range.
         */
        filter_iter end() const { return end_; }

        /**
         * @brief Checks if the filtered range is empty.
         *
         * @return true if no elements in the range satisfy the predicate, false otherwise.
         *
         * @note This operation has O(1) complexity as it only compares iterators.
         */
        bool empty() const { return begin_ == end_; }

    private:
        filter_iter begin_;  ///< Iterator to first element satisfying predicate
        filter_iter end_;    ///< Past-the-end iterator for the filtered range
    };

    /**
     * @brief Factory function to create a filter_range with automatic template deduction.
     *
     * This convenience function eliminates the need to explicitly specify template parameters
     * when creating a filter_range. The template parameters are automatically deduced from
     * the function arguments.
     *
     * @tparam Predicate Automatically deduced predicate type
     * @tparam Iterator  Automatically deduced iterator type
     *
     * @param pred  Predicate function/functor for filtering elements
     * @param begin Iterator to the beginning of the range
     * @param end   Iterator to the end of the range
     *
     * @return filter_range<Predicate, Iterator> A filter_range object configured with
     *                                           the provided predicate and range
     *
     * Example usage:
     * @code
     * std::vector<std::string> words = {"hello", "world", "test", "example"};
     *
     * // Filter strings longer than 4 characters
     * auto long_words = LL::make_filter(
     *     [](const std::string& s) { return s.length() > 4; },
     *     words.begin(),
     *     words.end()
     * );
     *
     * // Use with range-based for loop
     * for (const auto& word : long_words) {
     *     std::cout << word << std::endl; // Prints: hello, world, example
     * }
     *
     * // Use with STL algorithms
     * auto count = std::distance(long_words.begin(), long_words.end());
     * std::cout << "Found " << count << " long words." << std::endl;
     * @endcode
     *
     * @note This function is preferred over direct construction of filter_range
     *       for most use cases due to automatic template parameter deduction.
     */
    template<typename Predicate, typename Iterator>
    filter_range<Predicate, Iterator> make_filter(Predicate pred, Iterator begin, Iterator end)
    {
        return filter_range<Predicate, Iterator>(pred, begin, end);
    }

    /**
     * @brief Create a filter_range over an entire container with automatic template deduction.
     *
     * This convenience function creates a filtered view over an entire container without
     * requiring explicit begin() and end() calls. It automatically handles both const and
     * non-const containers, preserving constness in the resulting iterator types.
     *
     * @tparam Predicate Automatically deduced predicate type
     * @tparam Container Automatically deduced container type (const or non-const)
     *
     * @param pred      Predicate function/functor for filtering elements
     * @param container The container to filter (can be const or non-const)
     *
     * @return filter_range with appropriate iterator type for the container
     *
     * Example usage:
     * @code
     * // Non-const container
     * std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
     * auto evens = LL::make_filter([](int n) { return n % 2 == 0; }, numbers);
     *
     * // Const container
     * const std::list<std::string> words = {"cat", "elephant", "dog", "hippopotamus"};
     * auto long_words = LL::make_filter([](const std::string& s) { return s.size() > 3; }, words);
     *
     * // Works with any container that supports begin()/end()
     * std::set<double> values = {1.1, 2.2, 3.3, 4.4, 5.5};
     * auto large_values = LL::make_filter([](double d) { return d > 3.0; }, values);
     *
     * // Use with range-based for loops
     * for (const auto& word : long_words) {
     *     std::cout << word << " "; // Prints: elephant hippopotamus
     * }
     *
     * // Chain with STL algorithms
     * auto even_count = std::distance(evens.begin(), evens.end());
     * std::cout << "Found " << even_count << " even numbers." << std::endl;
     * @endcode
     *
     * @note This overload automatically calls begin() and end() on the container,
     *       making it more convenient than the iterator-based version.
     * @note The container must remain valid for the lifetime of the returned filter_range.
     * @note Constness of the container is preserved in the iterator type.
     */
    template<typename Predicate, typename Container>
    filter_range<Predicate, decltype(std::begin(std::declval<Container>()))>
    make_filter(Predicate pred, Container&& container)
    {
        return filter_range<Predicate, decltype(std::begin(std::declval<Container>()))>(
            pred, std::begin(container), std::end(container));
    }

} // namespace LL

// Transparent string hashing helper for use with std::unordered_*
// std::unordered_map<std::string, val, ll::string_hash, std::equal_to<>>
namespace ll
{
    struct string_hash
    {
        using is_transparent = void;
        [[nodiscard]] size_t operator()(char const* rhs) const { return std::hash<std::string_view>{}(rhs); }
        [[nodiscard]] size_t operator()(std::string_view rhs) const { return std::hash<std::string_view>{}(rhs); }
        [[nodiscard]] size_t operator()(const std::string& rhs) const { return std::hash<std::string>{}(rhs); }
    };
} // namespace ll

// Specialize ostream for std::type_index to allow log output
inline std::ostream& operator<<(std::ostream& s, std::type_index type)
{
    s << type.name();
    return s;
}

#endif // LL_LLSTL_H