--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/webengine/osswebengine/JavaScriptCore/wtf/symbian/algorithm Mon Mar 30 12:54:55 2009 +0300
@@ -0,0 +1,370 @@
+// Bits and pieces used in algorithms -*- C++ -*-
+
+// Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// 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 General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING. If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction. Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License. This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+/*
+ *
+ * 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.
+ */
+
+#ifndef __ALGORITHM
+#define __ALGORITHM
+
+#define __glibcxx_function_requires(__A)
+#define __glibcxx_requires_valid_range(__A, __B)
+
+namespace std
+{
+
+ typedef int ptrdiff_t;
+
+ #undef min
+ #undef max
+
+ /**
+ * @brief This does what you think it does.
+ * @param a A thing of arbitrary type.
+ * @param b Another thing of arbitrary type.
+ * @return The lesser of the parameters.
+ *
+ * This is the simple classic generic implementation. It will work on
+ * temporary expressions, since they are only evaluated once, unlike a
+ * preprocessor macro.
+ */
+ template<typename _Tp>
+ inline const _Tp&
+ min(const _Tp& __a, const _Tp& __b)
+ {
+ if (__b < __a)
+ return __b;
+ return __a;
+ }
+
+ /**
+ * @brief This does what you think it does.
+ * @param a A thing of arbitrary type.
+ * @param b Another thing of arbitrary type.
+ * @return The greater of the parameters.
+ *
+ * This is the simple classic generic implementation. It will work on
+ * temporary expressions, since they are only evaluated once, unlike a
+ * preprocessor macro.
+ */
+ template<typename _Tp>
+ inline const _Tp&
+ max(const _Tp& __a, const _Tp& __b)
+ {
+ if (__a < __b)
+ return __b;
+ return __a;
+ }
+
+ /**
+ * @brief Swaps two values.
+ * @param a A thing of arbitrary type.
+ * @param b Another thing of arbitrary type.
+ * @return Nothing.
+ *
+ * This is the simple classic generic implementation. It will work on
+ * any type which has a copy constructor and an assignment operator.
+ */
+ template<typename _Tp>
+ inline void
+ swap(_Tp& __a, _Tp& __b)
+ {
+ const _Tp __tmp = __a;
+ __a = __b;
+ __b = __tmp;
+ }
+
+ /**
+ * a simplied version of libstdc++ * std::copy,
+ * should be sufficient for our purpose.
+ */
+ template<typename _InputIterator, typename _OutputIterator>
+ inline _OutputIterator
+ copy( _InputIterator __first, _InputIterator __last, _OutputIterator __result )
+ {
+ for(; __first != __last; ++__result, ++__first )
+ *__result = *__first;
+ return __result;
+ }
+
+ /**
+ * a simplied version of libstdc++ * std::fill,
+ * should be sufficient for our purpose.
+ */
+ template<typename _Iterator, typename _Value>
+ inline void
+ fill( _Iterator __start, _Iterator __end, _Value __val )
+ {
+ for(; __start != __end; ++__start )
+ *__start = __val;
+ }
+
+ // FIXME bubblesort
+ template<typename Type, typename Compare>
+ inline void stable_sort(Type* begin, Type* end, Compare compare)
+ {
+ if( begin == end ) return;
+ Type* e = end-1;
+ while (e!=begin) {
+ bool sorted = true;
+ for (Type* i = begin; i!=e; i++) {
+ //if (!compare(*i,*(i+1))) {
+ if (compare(*(i+1),*i)) {
+ Type temp = *i;
+ *i = *(i+1);
+ *(i+1)=temp;
+ sorted = false;
+ }
+ }
+
+ if (sorted)
+ break;
+ e--;
+ }
+ }
+
+ template<typename Type, typename Compare>
+ inline void sort(Type* begin, Type* end, Compare compare)
+ {
+ stable_sort(begin,end,compare);
+ }
+
+#if 0
+FIXME:: These templates are needed for binary_search, but currently do not compile
+
+ template<typename _InputIterator, typename _Distance>
+ inline void
+ __advance(_InputIterator& __i, _Distance __n, input_iterator_tag)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
+ while (__n--)
+ ++__i;
+ }
+
+
+ /**
+ * @if maint
+ * This function is not a part of the C++ standard but is syntactic
+ * sugar for internal library use only.
+ * @endif
+ */
+ template<typename _Iter>
+ inline typename iterator_traits<_Iter>::iterator_category
+ __iterator_category(const _Iter&)
+ { return typename iterator_traits<_Iter>::iterator_category(); }
+
+
+ /**
+ * @brief A generalization of pointer arithmetic.
+ * @param first An input iterator.
+ * @param last An input iterator.
+ * @return The distance between them.
+ *
+ * Returns @c n such that first + n == last. This requires that @p last
+ * must be reachable from @p first. Note that @c n may be negative.
+ *
+ * For random access iterators, this uses their @c + and @c - operations
+ * and are constant time. For other %iterator classes they are linear time.
+ */
+ template<typename _InputIterator>
+ inline typename iterator_traits<_InputIterator>::difference_type
+ distance(_InputIterator __first, _InputIterator __last)
+ {
+ // concept requirements -- taken care of in __distance
+ return std::__distance(__first, __last,
+ std::__iterator_category(__first));
+ }
+
+ template<typename _InputIterator, typename _Distance>
+ inline void
+ __advance(_InputIterator& __i, _Distance __n, input_iterator_tag)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
+ while (__n--)
+ ++__i;
+ }
+
+ template<typename _BidirectionalIterator, typename _Distance>
+ inline void
+ __advance(_BidirectionalIterator& __i, _Distance __n,
+ bidirectional_iterator_tag)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_BidirectionalIteratorConcept<
+ _BidirectionalIterator>)
+ if (__n > 0)
+ while (__n--)
+ ++__i;
+ else
+ while (__n++)
+ --__i;
+ }
+
+ template<typename _RandomAccessIterator, typename _Distance>
+ inline void
+ __advance(_RandomAccessIterator& __i, _Distance __n,
+ random_access_iterator_tag)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_RandomAccessIteratorConcept<
+ _RandomAccessIterator>)
+ __i += __n;
+ }
+
+ /**
+ * @brief A generalization of pointer arithmetic.
+ * @param i An input iterator.
+ * @param n The "delta" by which to change @p i.
+ * @return Nothing.
+ *
+ * This increments @p i by @p n. For bidirectional and random access
+ * iterators, @p n may be negative, in which case @p i is decremented.
+ *
+ * For random access iterators, this uses their @c + and @c - operations
+ * and are constant time. For other %iterator classes they are linear time.
+ */
+ template<typename _InputIterator, typename _Distance>
+ inline void
+ advance(_InputIterator& __i, _Distance __n)
+ {
+ // concept requirements -- taken care of in __advance
+ std::__advance(__i, __n, std::__iterator_category(__i));
+ }
+
+
+
+ /**
+ * @brief Finds the first position in which @a val could be inserted
+ * without changing the ordering.
+ * @param first An iterator.
+ * @param last Another iterator.
+ * @param val The search term.
+ * @return An iterator pointing to the first element "not less than" @a val,
+ * or end() if every element is less than @a val.
+ * @ingroup binarysearch
+ */
+ template<typename _ForwardIterator, typename _Tp>
+ _ForwardIterator
+ lower_bound(_ForwardIterator __first, _ForwardIterator __last,
+ const _Tp& __val)
+ {
+ typedef typename iterator_traits<_ForwardIterator>::value_type
+ _ValueType;
+ typedef typename iterator_traits<_ForwardIterator>::difference_type
+ _DistanceType;
+
+ // concept requirements
+ // Note that these are slightly stricter than those of the 4-argument
+ // version, defined next. The difference is in the strictness of the
+ // comparison operations... so for looser checking, define your own
+ // comparison function, as was intended.
+ __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
+ __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>)
+ __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
+ __glibcxx_requires_partitioned(__first, __last, __val);
+
+ _DistanceType __len = std::distance(__first, __last);
+ _DistanceType __half;
+ _ForwardIterator __middle;
+
+ while (__len > 0)
+ {
+ __half = __len >> 1;
+ __middle = __first;
+ std::advance(__middle, __half);
+ if (*__middle < __val)
+ {
+ __first = __middle;
+ ++__first;
+ __len = __len - __half - 1;
+ }
+ else
+ __len = __half;
+ }
+ return __first;
+ }
+
+ /**
+ * @brief Determines whether an element exists in a range.
+ * @param first An iterator.
+ * @param last Another iterator.
+ * @param val The search term.
+ * @return True if @a val (or its equivelent) is in [@a first,@a last ].
+ * @ingroup binarysearch
+ *
+ * Note that this does not actually return an iterator to @a val. For
+ * that, use std::find or a container's specialized find member functions.
+ */
+ template<typename _ForwardIterator, typename _Tp>
+ bool
+ binary_search(_ForwardIterator __first, _ForwardIterator __last,
+ const _Tp& __val)
+ {
+ // concept requirements
+ // See comments on lower_bound.
+ __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
+ __glibcxx_function_requires(_SameTypeConcept<_Tp,
+ typename iterator_traits<_ForwardIterator>::value_type>)
+ __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
+ __glibcxx_requires_partitioned(__first, __last, __val);
+
+ _ForwardIterator __i = std::lower_bound(__first, __last, __val);
+ return __i != __last && !(__val < *__i);
+ }
+
+#endif // 0
+
+}
+
+#endif
\ No newline at end of file