libbase/GnashAlgorithm.h

   1 // GnashAlgorithm.h: useful templates and functors for generic algorithms
   2 //
   3 //   Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
   4 //
   5 // This program is free software; you can redistribute it and/or modify
   6 // it under the terms of the GNU General Public License as published by
   7 // the Free Software Foundation; either version 3 of the License, or
   8 // (at your option) any later version.
   9 //
  10 // This program is distributed in the hope that it will be useful,
  11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 // GNU General Public License for more details.
  14 //
  15 // You should have received a copy of the GNU General Public License
  16 // along with this program; if not, write to the Free Software
  17 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  18 //
  19
  20 #ifndef GNASH_ALGORITHM_H
  21 #define GNASH_ALGORITHM_H
  22
  23 #include <algorithm>
  24 #include <boost/checked_delete.hpp>
  25 #include <boost/intrusive_ptr.hpp>
  26 #include <boost/shared_ptr.hpp>
  27 #include <boost/bind.hpp>
  28
  29 namespace gnash {
  30
  31 /// Retrieve the second element of a container with std::pairs.
  32 template<typename T>
  33 struct SecondElement
  34 {
  35     typedef typename T::second_type result_type;
  36
  37     const result_type& operator()(const T& pair) const {
  38         return pair.second;
  39     }
  40 };
  41
  42 /// Retrieve the first element of a container with std::pairs.
  43 template<typename T>
  44 struct FirstElement
  45 {
  46     typedef typename T::first_type result_type;
  47
  48     const result_type& operator()(const T& pair) const {
  49         return pair.first;
  50     }
  51 };
  52
  53 /// Return a pointer to a type
  54 template<typename T>
  55 struct CreatePointer
  56 {
  57     const T* operator()(const T& t) {
  58         return &t;
  59     }
  60 };
  61
  62 /// Recurse to the base type of a pointer.
  63 template<typename T>
  64 struct RemovePointer
  65 {
  66     typedef T value_type;
  67 };
  68
  69 template<typename T>
  70 struct RemovePointer<T*>
  71 {
  72     typedef typename RemovePointer<T>::value_type value_type;
  73 };
  74
  75 template<typename T>
  76 struct RemovePointer<boost::intrusive_ptr<T> >
  77 {
  78     typedef typename RemovePointer<T>::value_type value_type;
  79 };
  80
  81 template<typename T>
  82 struct RemovePointer<boost::shared_ptr<T> >
  83 {
  84     typedef typename RemovePointer<T>::value_type value_type;
  85 };
  86
  87 /// Erase elements from an associative container based on a predicate
  88 //
  89 /// This removes elements from a container such as a map if they fulfil a
  90 /// particular condition. Because keys of associative container are const,
  91 /// we can't do this using iterators, because we can't write to them.
  92 template<typename Container, typename Predicate>
  93 void EraseIf(Container& c, Predicate p)
  94 {
  95     typedef typename Container::iterator iterator;
  96
  97     for (iterator i = c.begin(), e = c.end(); i != e; ) {
  98         iterator stored = i++;
  99         if (p(*stored)) c.erase(stored);
 100     }
 101 }
 102
 103
 104 /// Get the size of an array without passing a pointer by mistake
 105 template<typename T, size_t N>
 106 size_t
 107 arraySize(T(&)[N])
 108 {
 109     return N;
 110 }
 111
 112
 113 /// Delete a pointer safely
 114 //
 115 /// Any depth of pointers-to-pointers (up to maximum template recursion) can
 116 /// be passed to this struct. The type of the pointee is deduced and passed
 117 /// to boost::checked_deleter, which ensures that the type is fully known
 118 /// at the point of deletion. It does not, of course, check that the pointer
 119 /// was allocated with new, so this isn't completely idiot-proof.
 120 template<typename T>
 121 struct CheckedDeleter
 122 {
 123 };
 124
 125 template<typename T>
 126 struct CheckedDeleter<T**>
 127 {
 128     /// Typedef for use in boost::bind.
 129     typedef typename CheckedDeleter<T*>::result_type result_type;
 130
 131     void operator()(T** p) const {
 132         CheckedDeleter<T*>()(*p);
 133     }
 134 };
 135
 136 template<typename T>
 137 struct CheckedDeleter<T*>
 138 {
 139     /// Typedef for use in boost::bind.
 140     typedef void result_type;
 141
 142     void operator()(T* p) const {
 143         boost::checked_delete<T>(p);
 144     }
 145 };
 146
 147
 148 /// Call a functor on the second element of each element in a range.
 149 //
 150 /// @tparam T           An iterator type satisfying the requirements of a
 151 ///                     forward iterator
 152 /// @tparam U           The type of the functor op.
 153 /// @param begin        The start of the range to call op on.
 154 /// @param end          The end of the range to call op on.
 155 /// @param op           The function to call on each second element.
 156 template<typename T, typename U>
 157 void
 158 foreachSecond(T begin, T end, U op)
 159 {
 160     typedef SecondElement<typename std::iterator_traits<T>::value_type> S;
 161     std::for_each(begin, end, boost::bind(op, boost::bind(S(), _1)));
 162 }
 163
 164 /// Call a functor on the first element of each element in a range.
 165 //
 166 /// @tparam T           An iterator type satisfying the requirements of a
 167 ///                     forward iterator
 168 /// @tparam U           The type of the functor op.
 169 /// @param begin        The start of the range to call op on.
 170 /// @param end          The end of the range to call op on.
 171 /// @param op           The function to call on each second element.
 172 template<typename T, typename U>
 173 void
 174 foreachFirst(T begin, T end, U op)
 175 {
 176     typedef FirstElement<typename std::iterator_traits<T>::value_type> S;
 177     std::for_each(begin, end, boost::bind(op, boost::bind(S(), _1)));
 178 }
 179
 180 /// Safely call delete on each element in a range.
 181 //
 182 /// This checks that the type is fully known, but cannot check whether the
 183 /// pointer was allocated with new. Pointers allocated with new[] or any other
 184 /// allocation function should never be passed to this function.
 185 //
 186 /// @param begin        The start of the range to call delete on.
 187 /// @param end          The end of the range to call delete on.
 188 template<typename T>
 189 void
 190 deleteChecked(T begin, T end)
 191 {
 192     typedef typename std::iterator_traits<T>::value_type value_type;
 193     std::for_each(begin, end, CheckedDeleter<value_type>());
 194 }
 195
 196 /// Safely call delete on each second element in a range of pairs.
 197 //
 198 /// This checks that the type is fully known, but cannot check whether the
 199 /// pointer was allocated with new. Pointers allocated with new[] or any other
 200 /// allocation function should never be passed to this function.
 201 //
 202 /// @param begin        The start of the range to call delete on.
 203 /// @param end          The end of the range to call delete on.
 204 template<typename T>
 205 void
 206 deleteSecondElements(T begin, T end)
 207 {
 208     typedef SecondElement<typename std::iterator_traits<T>::value_type> S;
 209     foreachSecond(begin, end, CheckedDeleter<typename S::result_type>());
 210 }
 211
 212
 213 } // namespace gnash
 214
 215 #endif
 216