llstl.h

Go to the documentation of this file.

#ifndef LL_LLSTL_H
#define LL_LLSTL_H

#include <functional>
#include <algorithm>
#include <map>
#include <vector>
#include <set>
#include <deque>

// 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());

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

// DeletePointer is a simple helper for deleting all pointers in a map.
// The general form is:
//
//  std::for_each(somemap.begin(), somemap.end(), DeletePairedPointer());

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


// 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 snippit 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 : public std::unary_function<T*, bool>
{
        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 : public std::unary_function<T*, bool>
{
        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);
        }
};

// 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 K, typename T>
inline T* get_ptr_in_map(const std::map<K,T*>& inmap, const K& key)
{
        // Typedef here avoids warnings because of new c++ naming rules.
        typedef typename std::map<K,T*>::const_iterator map_iter;
        map_iter iter = inmap.find(key);
        if(iter == inmap.end())
        {
                return NULL;
        }
        else
        {
                return iter->second;
        }
};

// helper function which returns true if key is in inmap.
template <typename K, typename T>
inline bool is_in_map(const std::map<K,T>& inmap, const K& key)
{
        typedef typename std::map<K,T>::const_iterator map_iter;
        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 K, typename T>
inline T get_if_there(const std::map<K,T>& inmap, const K& key, T default_value)
{
        // Typedef here avoids warnings because of new c++ naming rules.
        typedef typename std::map<K,T>::const_iterator map_iter;
        map_iter 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, typename Iter>
inline Iter vector_replace_with_last(std::vector<T>& invec, Iter 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;
        }
};

// Useful for replacing the removeObj() functionality of LLDynamicArray
// 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)
{
        U32 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 : public std::unary_function<_Pair, typename _Pair::first_type> {
  const typename _Pair::first_type& operator()(const _Pair& __x) const {
    return __x.first;
  }
};

template <class _Pair>
struct _LLSelect2nd : public std::unary_function<_Pair, typename _Pair::second_type>
{
  const typename _Pair::second_type& 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 :
        public std::unary_function<typename _Operation2::argument_type,
                                                           typename _Operation1::result_type>
{
protected:
  _Operation1 __op1;
  _Operation2 __op2;
public:
  ll_unary_compose(const _Operation1& __x, const _Operation2& __y)
    : __op1(__x), __op2(__y) {}
  typename _Operation1::result_type
  operator()(const typename _Operation2::argument_type& __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
  : public std::unary_function<typename _Operation2::argument_type,
                                                           typename _Operation1::result_type> {
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) { }
  typename _Operation1::result_type
  operator()(const typename _Operation2::argument_type& __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>
class llbinder1st :
        public std::unary_function<typename _Operation::second_argument_type,
                                                           typename _Operation::result_type> {
protected:
  _Operation op;
  typename _Operation::first_argument_type value;
public:
  llbinder1st(const _Operation& __x,
                          const typename _Operation::first_argument_type& __y)
      : op(__x), value(__y) {}
        typename _Operation::result_type
        operator()(const typename _Operation::second_argument_type& __x) const {
                return op(value, __x);
        }
};

template <class _Operation, class _Tp>
inline llbinder1st<_Operation>
llbind1st(const _Operation& __oper, const _Tp& __x)
{
  typedef typename _Operation::first_argument_type _Arg1_type;
  return llbinder1st<_Operation>(__oper, _Arg1_type(__x));
}

template <class _Operation>
class llbinder2nd
        : public std::unary_function<typename _Operation::first_argument_type,
                                                                 typename _Operation::result_type> {
protected:
        _Operation op;
        typename _Operation::second_argument_type value;
public:
        llbinder2nd(const _Operation& __x,
                                const typename _Operation::second_argument_type& __y)
                : op(__x), value(__y) {}
        typename _Operation::result_type
        operator()(const typename _Operation::first_argument_type& __x) const {
                return op(__x, value);
        }
};

template <class _Operation, class _Tp>
inline llbinder2nd<_Operation>
llbind2nd(const _Operation& __oper, const _Tp& __x)
{
  typedef typename _Operation::second_argument_type _Arg2_type;
  return llbinder2nd<_Operation>(__oper, _Arg2_type(__x));
}

#endif // LL_LLSTL_H

---