Change to search_n

[Chris Jefferson <caj at cs dot york dot ac dot uk>]

Hello!

I apologise in advance for what will be I suspect a badly formed e-mail. 
I hope that with your help I can shape it up a little, and that I will 
have some useful things to say.

I was recently looking at the STL function search_n, included in 
stl_algo.h. The version I have is gcc 3.3.4 (as this appears to be the 
most recent version in Debian). I have been having some minor 
difficulties getting the CVS version, so I hope things have not changed 
too much!

First of all, a very small patch near the end of the function:

if(__n == 0)
   return __first;
else
   __first = find(__i, __last, __val);

Can be changed to:

if(__n == 0)
   return __first;
if(__i == __last)
   return __last;
__first = __find(++__i, __last, __val);

This creates a small speed improvement generally, and in the best case 
(where you are for example searching through a list which alternates 
a,b,a,b,a,b... , you are looking for 2 (or more) a's, and the comparison 
function is expensive) then can lead to a 50% speed improvement (as 
previously each "b" would be checked twice). This new version also has 
the advantage it checks each variable only once.

Further to this, I have also introduced a special search_n for random 
access iterators in the same way as exists for some other functions (and 
in I hope a similar way), which I have included in an attached file. 
This will also compare no two objects more than once, and also while 
having the same worst case complexity, the average case complexity is 
closer to (length/n) where length is the distance between the input 
iterators and n is the length of symbols to be found. The only 
difference between this and the implentation of find_if (which is where 
I borrowed the idea and implementation from) is that the "specialised 
"search_n" functions are not called search_n, as this appears to 
interfere with the varient of search_n which takes an extra parameter.

I also have a testing program which checks a range of areas where I 
suspected the algorithms could go wrong, and also compares them to each 
other for all possible inputs of length 12 or less to make sure they 
agree. I haven't attached this because it isn't really very clean.

I hope that this is useful and interesting, and also perhaps someone 
might be able to point me to what I should do to a) include these in the 
standard library should they be applicable b) get my own version and get 
it compiled, and c) add things to the test suite. I tried checking the 
stdlib webpage but was worried it hasn't been updated since 2002 (it 
appears) so may be very out of date.

Thank you,

Chris
  template<typename _InputIter, typename _Integer, typename _Tp>
  inline _InputIter
  search_n(_InputIter __first, _InputIter __last,
       _Integer __count, const _Tp& __val)
  {
    // concept requirements
    __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
      __glibcpp_function_requires(_EqualityComparableConcept<
				  typename iterator_traits<_ForwardIter>::value_type>)
      __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)

      return _search_n(__first, __last, __count, __val, __iterator_category(__first));
  }
  


  template<typename _ForwardIter, typename _Integer, typename _Tp>
  _ForwardIter
  _search_n(_ForwardIter __first, _ForwardIter __last,
	   _Integer __count, const _Tp& __val,random_access_iterator_tag)
  {
    if(__count<=0) return __first;
 
    while(__first<=__last) {
      if(__count>__last-__first)
	return __last;
      _ForwardIter __i = __first;
      
      __i+=__count-1;
      if(__i>=__last) return __last;
      if(*__i==__val) {
	int __equal=0;
	while((*__i==__val) && (__i>=__first)) {
	  __equal++; __i--;
	}
	__i++;
	_ForwardIter __possibleFirst = __i;

	__i=__first+__count;
	while(*__i==__val && __i<__last && __equal<__count) {    
	  __equal++; __i++;
	}
	if(__equal==__count)
	  return __possibleFirst;
	if(__i==__last) 
	  return __last;
      }
      __i++;
      
      __first=__i;
    }
    return __last;
  }
  
  
  template<typename _ForwardIter, typename _Integer, typename _Tp>
  _ForwardIter
  _search_n(_ForwardIter __first, _ForwardIter __last,
		    _Integer __count, const _Tp& __val,input_iterator_tag)
  {
      if (__count <= 0)
	return __first;
      else {
	__first = find(__first, __last, __val);
	while (__first != __last) {
	  typename iterator_traits<_ForwardIter>::difference_type __n = __count;
	  --__n;
	  _ForwardIter __i = __first;
	  ++__i;
	  while (__i != __last && __n != 0 && *__i == __val) {
	    ++__i;
	    --__n;
	  }
	  if (__n == 0)
	    return __first;
	  if (__i == __last)
	    return __last;

	    __first = find(++__i, __last, __val);
	}
	return __last;
      }
  }