X-Git-Url: http://git.buserror.net/cgi-bin/gitweb.cgi?p=polintos%2Fscott%2Fpriv.git;a=blobdiff_plain;f=include%2Fc%2B%2B%2Fstl%2Fstl%2F_algobase.c;fp=include%2Fc%2B%2B%2Fstl%2Fstl%2F_algobase.c;h=8a1f657f7f854d2f30c4cf8fad0480e55b9da963;hp=0000000000000000000000000000000000000000;hb=173d8903eb9d51a4ea7d7fa3e52dc86c9bb6d4f1;hpb=b024710fe2b60cd4a42a8993b61333d6cdb56ca3

diff --git a/include/c++/stl/stl/_algobase.c b/include/c++/stl/stl/_algobase.c
new file mode 100644
index 0000000..8a1f657
--- /dev/null
+++ b/include/c++/stl/stl/_algobase.c
@@ -0,0 +1,403 @@
+/*
+ *
+ * Copyright (c) 1994
+ * Hewlett-Packard Company
+ *
+ * Copyright (c) 1996,1997
+ * Silicon Graphics Computer Systems, Inc.
+ *
+ * Copyright (c) 1997
+ * Moscow Center for SPARC Technology
+ *
+ * Copyright (c) 1999
+ * Boris Fomitchev
+ *
+ * This material is provided "as is", with absolutely no warranty expressed
+ * or implied. Any use is at your own risk.
+ *
+ * Permission to use or copy this software for any purpose is hereby granted
+ * without fee, provided the above notices are retained on all copies.
+ * Permission to modify the code and to distribute modified code is granted,
+ * provided the above notices are retained, and a notice that the code was
+ * modified is included with the above copyright notice.
+ *
+ */
+#ifndef _STLP_ALGOBASE_C
+#define _STLP_ALGOBASE_C
+
+#ifndef _STLP_INTERNAL_ALGOBASE_H
+#  include <stl/_algobase.h>
+#endif
+
+_STLP_BEGIN_NAMESPACE
+
+template <class _InputIter1, class _InputIter2>
+bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
+                             _InputIter2 __first2, _InputIter2 __last2) {
+  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
+  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
+  for ( ; __first1 != __last1 && __first2 != __last2
+        ; ++__first1, ++__first2) {
+    if (*__first1 < *__first2) {
+      return true;
+    }
+    if (*__first2 < *__first1)
+      return false;
+  }
+  return __first1 == __last1 && __first2 != __last2;
+}
+
+template <class _InputIter1, class _InputIter2, class _Compare>
+bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
+                             _InputIter2 __first2, _InputIter2 __last2,
+                             _Compare __comp) {
+  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
+  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
+  for ( ; __first1 != __last1 && __first2 != __last2
+        ; ++__first1, ++__first2) {
+    if (__comp(*__first1, *__first2)) {
+      return true;
+    }
+    if (__comp(*__first2, *__first1))
+      return false;
+  }
+  return __first1 == __last1 && __first2 != __last2;
+}
+
+#if !defined (_STLP_NO_EXTENSIONS)
+_STLP_MOVE_TO_PRIV_NAMESPACE
+
+template <class _InputIter1, class _InputIter2>
+int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
+                                   _InputIter2 __first2, _InputIter2 __last2) {
+  while (__first1 != __last1 && __first2 != __last2) {
+    if (*__first1 < *__first2) {
+      _STLP_VERBOSE_ASSERT(!(*__first2 < *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
+      return -1;
+    }
+    if (*__first2 < *__first1)
+      return 1;
+    ++__first1;
+    ++__first2;
+  }
+  if (__first2 == __last2) {
+    return !(__first1 == __last1);
+  }
+  else {
+    return -1;
+  }
+}
+
+_STLP_MOVE_TO_STD_NAMESPACE
+
+template <class _InputIter1, class _InputIter2>
+int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
+                                 _InputIter2 __first2, _InputIter2 __last2) {
+  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
+  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
+  return _STLP_PRIV __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
+}
+#endif
+
+_STLP_MOVE_TO_PRIV_NAMESPACE
+
+template <class _RandomAccessIter, class _Tp>
+_STLP_INLINE_LOOP _RandomAccessIter __find(_RandomAccessIter __first, _RandomAccessIter __last,
+                                           const _Tp& __val,
+                                           const random_access_iterator_tag &) {
+  _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;
+
+  for ( ; __trip_count > 0 ; --__trip_count) {
+    if (*__first == __val) return __first;
+    ++__first;
+
+    if (*__first == __val) return __first;
+    ++__first;
+
+    if (*__first == __val) return __first;
+    ++__first;
+
+    if (*__first == __val) return __first;
+    ++__first;
+  }
+
+  switch (__last - __first) {
+  case 3:
+    if (*__first == __val) return __first;
+    ++__first;
+  case 2:
+    if (*__first == __val) return __first;
+    ++__first;
+  case 1:
+    if (*__first == __val) return __first;
+    //++__first;
+  case 0:
+  default:
+    return __last;
+  }
+}
+
+inline char*
+__find(char* __first, char* __last, char __val, const random_access_iterator_tag &) {
+  void *res =  memchr(__first, __val, __last - __first);
+  return res != 0 ? __STATIC_CAST(char*, res) : __last;
+}
+inline const char*
+__find(const char* __first, const char* __last, char __val, const random_access_iterator_tag &) {
+  const void *res =  memchr(__first, __val, __last - __first);
+  return res != 0 ? __STATIC_CAST(const char*, res) : __last;
+}
+
+template <class _RandomAccessIter, class _Predicate>
+_STLP_INLINE_LOOP _RandomAccessIter __find_if(_RandomAccessIter __first, _RandomAccessIter __last,
+                                              _Predicate __pred,
+                                              const random_access_iterator_tag &) {
+  _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;
+
+  for ( ; __trip_count > 0 ; --__trip_count) {
+    if (__pred(*__first)) return __first;
+    ++__first;
+
+    if (__pred(*__first)) return __first;
+    ++__first;
+
+    if (__pred(*__first)) return __first;
+    ++__first;
+
+    if (__pred(*__first)) return __first;
+    ++__first;
+  }
+
+  switch(__last - __first) {
+  case 3:
+    if (__pred(*__first)) return __first;
+    ++__first;
+  case 2:
+    if (__pred(*__first)) return __first;
+    ++__first;
+  case 1:
+    if (__pred(*__first)) return __first;
+      //++__first;
+  case 0:
+  default:
+    return __last;
+  }
+}
+
+template <class _InputIter, class _Tp>
+_STLP_INLINE_LOOP _InputIter __find(_InputIter __first, _InputIter __last,
+                                    const _Tp& __val,
+                                    const input_iterator_tag &) {
+  while (__first != __last && !(*__first == __val)) ++__first;
+  return __first;
+}
+
+template <class _InputIter, class _Predicate>
+_STLP_INLINE_LOOP _InputIter __find_if(_InputIter __first, _STLP_MPW_EXTRA_CONST _InputIter __last,
+                                       _Predicate __pred,
+                                       const input_iterator_tag &) {
+  while (__first != __last && !__pred(*__first))
+    ++__first;
+  return __first;
+}
+
+_STLP_MOVE_TO_STD_NAMESPACE
+
+template <class _InputIter, class _Predicate>
+_InputIter find_if(_InputIter __first, _InputIter __last,
+                   _Predicate __pred) {
+  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
+  return _STLP_PRIV __find_if(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
+}
+
+template <class _InputIter, class _Tp>
+_InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val) {
+  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
+  return _STLP_PRIV __find(__first, __last, __val, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
+}
+
+template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
+_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
+                     _ForwardIter2 __first2, _ForwardIter2 __last2,
+                     _BinaryPred  __pred) {
+  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
+  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
+  // Test for empty ranges
+  if (__first1 == __last1 || __first2 == __last2)
+    return __first1;
+
+  // Test for a pattern of length 1.
+  _ForwardIter2 __p1(__first2);
+
+  if ( ++__p1 == __last2 ) {
+    while (__first1 != __last1 && !__pred(*__first1, *__first2)) {
+      ++__first1;
+    }
+    return __first1;
+  }
+
+  // General case.
+
+  for ( ; ; ) { // __first1 != __last1 will be checked below
+    while (__first1 != __last1 && !__pred(*__first1, *__first2)) {
+      ++__first1;
+    }
+    if (__first1 == __last1) {
+      return __last1;
+    }
+    _ForwardIter2 __p = __p1;
+    _ForwardIter1 __current = __first1;
+    if (++__current == __last1) return __last1;
+
+    while (__pred(*__current, *__p)) {
+      if (++__p == __last2)
+        return __first1;
+      if (++__current == __last1)
+        return __last1;
+    }
+
+    ++__first1;
+  }
+  return __first1;
+}
+
+_STLP_MOVE_TO_PRIV_NAMESPACE
+
+// find_first_of, with and without an explicitly supplied comparison function.
+template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
+_InputIter __find_first_of(_InputIter __first1, _InputIter __last1,
+                           _ForwardIter __first2, _ForwardIter __last2,
+                           _BinaryPredicate __comp) {
+  for ( ; __first1 != __last1; ++__first1) {
+    for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) {
+      if (__comp(*__first1, *__iter)) {
+        return __first1;
+      }
+    }
+  }
+  return __last1;
+}
+
+// find_end, with and without an explicitly supplied comparison function.
+// Search [first2, last2) as a subsequence in [first1, last1), and return
+// the *last* possible match.  Note that find_end for bidirectional iterators
+// is much faster than for forward iterators.
+
+// find_end for forward iterators.
+template <class _ForwardIter1, class _ForwardIter2,
+  class _BinaryPredicate>
+_ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
+                         _ForwardIter2 __first2, _ForwardIter2 __last2,
+                         const forward_iterator_tag &, const forward_iterator_tag &,
+                         _BinaryPredicate __comp) {
+  if (__first2 == __last2)
+    return __last1;
+  else {
+    _ForwardIter1 __result = __last1;
+    for (;;) {
+      _ForwardIter1 __new_result = search(__first1, __last1, __first2, __last2, __comp);
+      if (__new_result == __last1)
+        return __result;
+      else {
+        __result = __new_result;
+        __first1 = __new_result;
+        ++__first1;
+      }
+    }
+  }
+}
+
+_STLP_MOVE_TO_STD_NAMESPACE
+
+// find_end for bidirectional iterators.  Requires partial specialization.
+#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
+
+#  ifndef _STLP_INTERNAL_ITERATOR_H
+_STLP_END_NAMESPACE
+#    include <stl/_iterator.h>
+_STLP_BEGIN_NAMESPACE
+#  endif /*_STLP_INTERNAL_ITERATOR_H*/
+
+_STLP_MOVE_TO_PRIV_NAMESPACE
+
+template <class _BidirectionalIter1, class _BidirectionalIter2,
+          class _BinaryPredicate>
+_BidirectionalIter1
+__find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
+           _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
+           const bidirectional_iterator_tag &, const bidirectional_iterator_tag &,
+           _BinaryPredicate __comp) {
+  typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
+  typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
+
+  _RevIter1 __rlast1(__first1);
+  _RevIter2 __rlast2(__first2);
+  _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
+                               _RevIter2(__last2), __rlast2,
+                               __comp);
+
+  if (__rresult == __rlast1)
+    return __last1;
+  else {
+    _BidirectionalIter1 __result = __rresult.base();
+    advance(__result, -distance(__first2, __last2));
+    return __result;
+  }
+}
+
+_STLP_MOVE_TO_STD_NAMESPACE
+#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
+
+template <class _ForwardIter1, class _ForwardIter2,
+          class _BinaryPredicate>
+_ForwardIter1
+find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
+         _ForwardIter2 __first2, _ForwardIter2 __last2,
+         _BinaryPredicate __comp) {
+  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
+  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
+  return _STLP_PRIV __find_end(__first1, __last1, __first2, __last2,
+#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
+                               _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),
+                               _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),
+#else
+                               forward_iterator_tag(),
+                               forward_iterator_tag(),
+#endif
+                               __comp);
+}
+
+_STLP_MOVE_TO_PRIV_NAMESPACE
+
+template <class _ForwardIter, class _Tp, class _Compare1, class _Compare2, class _Distance>
+_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
+                           _Compare1 __comp1, _Compare2 __comp2, _Distance*) {
+  _Distance __len = distance(__first, __last);
+  _Distance __half;
+  _ForwardIter __middle;
+
+  while (__len > 0) {
+    __half = __len >> 1;
+    __middle = __first;
+    advance(__middle, __half);
+    if (__comp1(*__middle, __val)) {
+      _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
+      __first = __middle;
+      ++__first;
+      __len = __len - __half - 1;
+    }
+    else
+      __len = __half;
+  }
+  return __first;
+}
+
+_STLP_MOVE_TO_STD_NAMESPACE
+
+_STLP_END_NAMESPACE
+
+#endif /* _STLP_ALGOBASE_C */
+
+// Local Variables:
+// mode:C++
+// End: