Standard C++	Library
 		 Copyright 1996, Rogue Wave Software, Inc.

 NAME

   rotate, rotate_copy  - Left rotates the order	of items in a
   collection, placing the first item at the	end, second item
   first,	etc., until the	item pointed to by	a specified
   iterator is	the first item in the collection.

 SYNOPSIS

   #include <algorithm>

   template <class ForwardIterator>
   void rotate (ForwardIterator first,
 	      ForwardIterator middle,
 	      ForwardIterator last);

   template <class ForwardIterator, class OutputIterator>
   OutputIterator rotate_copy (ForwardIterator first,
 			     ForwardIterator middle,
 			     ForwardIterator last,
 			     OutputIterator result);

 DESCRIPTION

   The rotate algorithm takes three iterator arguments, first, which
   defines the start of a sequence, last, which defines the end of the
   sequence,	and middle which defines a point within the sequence.
   rotate "swaps" the	segment that contains elements from first
   through middle-1 with the segment that contains	the elements
   from middle through last.	After rotate has been applied, the
   element that was	in position middle, is in position first, and
   the other elements in	that segment are in the	same order relative to
   each other.  Similarly, the element that was in position first is
   now in position last-middle +1.	An example will	illustrate how
   rotate works:

   Say that we have the sequence:

     2 4	6 8 1 3	5

   If we	call rotate with middle	= 5, the two segments are

     2 4	6  8	  and	   1 3 5

   After	we apply rotate, the new sequence will be:

     1 3	5 2 4 6	8

   Note that the	element	that was in the	fifth position is now in the
   first position, and	the element that was in	the first position is
   in position 4 (last	- first	+ 1, or	8 - 5 +1 =4).

   The formal description of this algorithms is:	 for each non-negative
   integer i < (last - first), rotate places the	element	from the
   position first	+ i into position first	+ (i + (last -
   middle))	% (last	- first). [first, middle) and [middle, last)
   are valid ranges.

   rotate_copy rotates the elements as described	above, but instead of
   swapping elements	within the same	sequence, it copies the	result
   of the rotation to a container specified	by result.
   rotate_copy	copies the range [first, last)	to the range [result,
   result + (last - first)) such that for each non-negative integer i
   < (last - first)	the following assignment takes	place:

   *(result + (i	+ (last	- middle)) % (last -first)) = *(first +	i).

   The ranges [first,  last)  and [result, result, + (last - first)) may	not
   overlap.

 COMPLEXITY

   For rotate at	most last - first swaps	are performed.

   For rotate_copy last - first assignments are performed.

 EXAMPLE

   //
   // rotate
   //
    #include <algorithm>
    #include <vector>
    #include <iostream.h>

   int main()
    {
      //Initialize a vector with	an array of ints
     int	arr[10]	= {1,2,3,4,5,6,7,8,9,10};
     vector<int>	v(arr, arr+10);

      //Print out elements in original (sorted) order
     cout << "Elements before rotate: " << endl << "	";
     copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
     cout << endl << endl;

      //Rotate the elements
      rotate(v.begin(), v.begin()+4, v.end());

      //Print out the rotated elements
     cout << "Elements after rotate: " << endl << "     ";
     copy(v.begin(),v.end(),ostream_iterator<int,char>(cout," "));
     cout << endl;

     return 0;
    }

   Output :
   Elements before rotate:
       1	2 3 4 5	6 7 8 9	10
   Elements after rotate:
       5	6 7 8 9	10 1 2 3 4

 WARNING

   If your compiler does	not support default template parameters, then
   you need to always supply	the Allocator template argument.  For
   instance,	you will need to write :

   vector<int, allocator<int> >

   instead of :

   vector<int>

 STANDARDS CONFORMANCE
   ANSI X3J16/ISO WG21 Joint C++	Committee