[Patch] find_end() for random_access iterators.

[Dhruv Matani]

Hello,
	I have attached a patch along with a test case for the find_end()
function.

I intend implementing basic_string<>::rfind() using this version if and
when this piece of code is committed.

-- 
        -Dhruv Matani.
http://www.geocities.com/dhruvbird/

The price of freedom is responsibility, but it's a bargain, because
freedom is priceless. ~ Hugh Downs
-------------- next part --------------
--- stl_algo.h	2004-12-16 15:36:43.000000000 +0530
+++ /home/dhruv/projects/new_libstdc++-v3/stl_algo.h	2004-12-16 16:33:08.000000000 +0530
@@ -5032,6 +5032,54 @@ namespace std
 	}
     }
 
+  // find_end for random-access iterators.  Requires partial specialization.
+  template<typename _RandomAccessIterator1, typename _RandomAccessIterator2>
+    _RandomAccessIterator1
+    __find_end(_RandomAccessIterator1 __first1,
+	       _RandomAccessIterator1 __last1,
+	       _RandomAccessIterator2 __first2,
+	       _RandomAccessIterator2 __last2,
+	       random_access_iterator_tag, random_access_iterator_tag)
+    {
+      typename std::iterator_traits<_RandomAccessIterator2>::difference_type 
+	__dest_diff = __last2 - __first2;
+      typename std::iterator_traits<_RandomAccessIterator1>::difference_type 
+	__src_diff = __last1 - __first1;
+      
+      if (__dest_diff > __src_diff)
+	return __last1;
+      if (__first2 == __last2)
+	return __last1;
+
+      _RandomAccessIterator1 __src1 = __last1 - __dest_diff;
+      while (__src1 != __first1)
+	{
+	  if (*__src1 == *__first2)
+	    {
+	      _RandomAccessIterator1 __temp1 = 
+		std::search(__src1, __src1 + __dest_diff, __first2, __last2);
+	      if (__temp1 == __src1)
+		return __src1;
+	      else
+		--__src1;
+	    }
+	  else
+	    --__src1;
+	}
+
+      if (*__src1 == *__first2)
+	{
+	  _RandomAccessIterator1 __ret1 = 
+	    std::search(__first1, __first1 + __dest_diff, __first2, __last2);
+	  if (__ret1 == __first1 + __dest_diff)
+	    return __last1;
+	  else
+	    return __ret1;
+	}
+
+      return __last1;
+    }
+
   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
 	   typename _BinaryPredicate>
     _BidirectionalIterator1
-------------- next part --------------
A non-text attachment was scrubbed...
Name: fend_test.cpp
Type: text/x-c++
Size: 736 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20041216/bd2f6d59/attachment.bin>