NAME:

binary_partition - finds an insertion location in an ordered block

SYNOPSIS:

TYPE *binary_partition(TYPE value, 
		       TYPE *begin, 
		       TYPE *end);

DESCRIPTION:

binary_partition returns a location middle in an ordered block such
that for any location x in the block middle <= x < end if and only if
value < *x.  In other words it returns the position of the leftmost
element in an ordered block that is greater than value.

SEE ALSO:

binary_search, insert, set_insert

ASSUMPTIONS:

Less_than ("<") is defined for the TYPE

DEPENDS ON:

nothing

COMPLEXITY:

Logarithmic in the size of the block.  If N is the number of locations
in the block then at most logN operation less_than are performed.


IMPLEMENTATION:

TYPE *binary_partition(REGISTER TYPE value, 
		       register TYPE *begin, 
		       register TYPE *end)
{
  while (5 < end-begin)
    {
      register TYPE *index = begin + ((end - begin) >> 1);

      if (value < *index)
	end = index;
      else
	begin = index + 1;
    }

  while (begin < end) 
    if (!(value < *--end))
      return end + 1;

  return end;
}


NAME:

binary_partition - finds an insertion location in an ordered block

SYNOPSIS:

TYPE *binary_partition(int (*relation)(TYPE*, TYPE*), 
		       TYPE value, 
		       TYPE *begin, 
		       TYPE *end);

DESCRIPTION:

binary_partition returns a location middle in an ordered block such
that for any location x in the block middle <= x < end if and only if
0 < relation(*x, value).  In other words it returns the position of
the leftmost element in an ordered block that is greater than value.
relation is the name of the comparison function, which is called with
two arguments that point to the elements being compared.  As the
function must return an integer less than, equal to, or greater than
zero, so must the first argument to be considered be less than, equal
to, or greater than the second.

SEE ALSO:

binary_search, insert, set_insert

ASSUMPTIONS:

none

DEPENDS ON:

nothing

COMPLEXITY:

Logarithmic in the size of the block.  If N is the number of locations
in the block then at most logN calls to the relation are performed.


IMPLEMENTATION:

TYPE *binary_partition(register int (*relation)(TYPE*, TYPE*), 
		       TYPE value, 
		       register TYPE *begin, 
		       register TYPE *end)
{
  register TYPE *temp = &value;
  while (5 < end-begin)
    {
      register TYPE *index = begin + ((end - begin) >> 1);

      if ((*relation)(temp, index) < 0)
	end = index;
      else
	begin = index + 1;
    }

  while (begin < end) 
    if (!((*relation)(temp, --end) < 0))
      return end + 1;

  return end;
}


NAME:

binary_search - finds an element in an ordered block

SYNOPSIS:

TYPE *binary_search(TYPE value, 
		    TYPE *begin, 
		    TYPE *end);

DESCRIPTION:

binary_search returns the pointer to the rightmost element in an
ordered block equal to value if such an element exists and the 0
pointer otherwise.

SEE ALSO:

binary_partition

ASSUMPTIONS:

Less_than ("<") is defined for the TYPE

DEPENDS ON:

TYPE *binary_partition(TYPE value, 
		       TYPE *begin, 
		       TYPE *end);

COMPLEXITY:

Logarithmic in the size of the block.  If N is the number of locations
in the block then at most logN operations less_than are performed.


IMPLEMENTATION:

TYPE *binary_search(TYPE value, 
		    TYPE *begin, 
		    TYPE *end)
{
  TYPE *index = binary_partition(value, begin, end);

  if (begin < index && !(*(index - 1) < value))
    return index - 1;

  else
    return 0;
}


NAME:

binary_search - finds an element in an ordered block

SYNOPSIS:

TYPE *binary_search(int (*relation)(TYPE*, TYPE*), 
		    TYPE value, 
		    TYPE *begin, 
		    TYPE *end);

DESCRIPTION:

binary_search returns the pointer to the rightmost element in an
ordered block equal to value if such an element exists and the 0
pointer otherwise.  relation is the name of the comparison function,
which is called with two arguments that point to the elements being
compared.  As the function must return an integer less than, equal to,
or greater than zero, so must the first argument to be considered be
less than, equal to, or greater than the second.

SEE ALSO:

binary_partition

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE

DEPENDS ON:

TYPE *binary_partition(int (*relation)(TYPE*, TYPE*), 
		       TYPE value, 
		       TYPE *begin, 
		       TYPE *end);

COMPLEXITY:

Logarithmic in the size of the block.  If N is the number of locations
in the block then at most logN calls to the relation are performed.


IMPLEMENTATION:

TYPE *binary_search(int (*relation)(TYPE*, TYPE*), 
		    TYPE value, 
		    TYPE *begin, 
		    TYPE *end)
{
  TYPE *index = binary_partition(relation, value, begin, end);

  if (begin < index && !((*relation)(index - 1, &value) < 0))
    return index - 1;

  else
    return 0;
}


NAME:

copy - copies a block to a new location

SYNOPSIS:

void copy(TYPE *begin, 
          TYPE *end, 
	  TYPE *result);

DESCRIPTION:

Copy moves the contents of every location between begin (inclusive)
and end (exclusive) into memory locations starting with result, so
that for every integer i, 0 <= i < (end - begin), the location result
+ i gets a value from the location begin + i.

NOTE:

1) Copy is the only copying function among the block algorithms that
allows the initial block and the resulting block to intersect. In such
cases, copy makes certain that every location is copied before it is
overwritten.

2) If begin is equal to result no assignments are done.

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY: 

Linear in the size of the block.  If N is the number of locations in
the block exactly N assignments of TYPE are performed. (But see the
second note.)


IMPLEMENTATION:

void copy(register TYPE *begin, 
	  register TYPE *end, 
	  register TYPE *result)
{
  if (begin < result)
    {
      result += end - begin;
      while (begin < end)
	*--result = *--end;
    }
  else if (result < begin)
    while (begin < end)
      *result++ = *begin++;
}


NAME:

count - returns the number of locations in the block that satisfy predicate

SYNOPSIS:

ptrdiff_t count(int (*predicate)(TYPE*), 
		TYPE *begin, 
		TYPE *end);

DESCRIPTION:

Count returns the number of locations in the block that satisfy
predicate

SEE ALSO:

other count, position

ASSUMPTIONS:

none

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block at exactly N calls to predicate are done.


IMPLEMENTATION:

ptrdiff_t count(register int (*predicate)(TYPE*), 
		register TYPE *begin, 
		register TYPE *end)
{
  register ptrdiff_t n = 0; 

  while (begin < end)
   if ((*predicate)(begin++))
     n++;

  return n;
}


NAME:

count - counts the number of elements in the block equal to the given value

SYNOPSIS:

ptrdiff_t count(TYPE value, 
		TYPE *begin, 
		TYPE *end);

DESCRIPTION:

count returns the number of locations in the block containing values
equal to value.

SEE ALSO:

other count, position

ASSUMPTIONS:

Equality ("==") is defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N equalities of TYPE are performed.


IMPLEMENTATION:

ptrdiff_t count(REGISTER TYPE value, 
		register TYPE *begin, 
		register TYPE *end)
{
  register ptrdiff_t n = 0; 

  while (begin < end)
    if (*begin++ == value)
      n++;

  return n;
}


NAME:

count - counts the number of elements in the block satisfying the relation
to the given value

SYNOPSIS:

ptrdiff_t count(int (*relation)(TYPE*, TYPE*), 
		TYPE value, 
		TYPE *begin, 
		TYPE *end);

DESCRIPTION:

count returns the number of locations in the block that satisfy
relation with the pointer to value.

SEE ALSO:

other count, position

ASSUMPTIONS:

none

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N calls to relation are done.


IMPLEMENTATION:

ptrdiff_t count(register int (*relation)(TYPE*, TYPE*), 
		TYPE value, 
		register TYPE *begin, 
		register TYPE *end)
{
  register TYPE *temp = &value;
  register ptrdiff_t n = 0; 

  while (begin < end)
    if ((*relation)(begin++, temp))
      n++;

  return n;
}


NAME:

difference - collects those elements of two ordered blocks that are in the 
first, but not in the second

SYNOPSIS:

TYPE *difference(int (*relation)(TYPE*, TYPE*), 
		 TYPE *begin1, 
		 TYPE *end1, 
		 TYPE *begin2, 
		 TYPE *end2, 
		 TYPE *result);

DESCRIPTION:

difference puts elements from two ordered blocks with no repetitions
into a new ordered block with no repetitions so that every element
which is in the first block but not in the second will be placed in
the result The pointer after the last element of the new block is
returned.  relation is the name of the comparison function, which is
called with two arguments that point to the elements being compared.
As the function must return an integer less than, equal to, or greater
than zero, so must the first argument to be considered be less than,
equal to, or greater than the second.

NOTE:

If begin1 <= result < end1 or begin1 <= result + (end1 - begin1) <
end1 or begin2 <= result < end2 or begin2 <= result + (end2 - begin2)
< end2 then the effect of difference is not defined.

SEE ALSO:

intersection, merge, set_union, symmetric_difference, unique

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the blocks.  If N and M are the numbers of
locations in the blocks then at most N + M - 1 calls to relation and N
assignments are performed.


IMPLEMENTATION:

TYPE *difference(register int (*relation)(TYPE*, TYPE*), 
		 register TYPE *begin1, 
		 register TYPE *end1, 
		 register TYPE *begin2, 
		 register TYPE *end2, 
		 register TYPE *result)
{
  while (begin1 < end1 && begin2 < end2)
    {
      register int c = (*relation)(begin2, begin1);
      if (0 < c)
	*result++ = *begin1++;
      else 
	{
	  if (c == 0)
	    begin1++;
	  begin2++;
	}
    }

  while (begin1 < end1)
    *result++ = *begin1++;

  return result;
}


NAME:

difference - collects those elements of two ordered blocks that are in the 
first, but not in the second

SYNOPSIS:

TYPE *difference(TYPE *begin1, 
		 TYPE *end1, 
		 TYPE *begin2, 
		 TYPE *end2, 
		 TYPE *result);

DESCRIPTION:

difference puts elements from two ordered blocks with no repetitions
into a new ordered block with no repetitions so that every element
which is in the first block but not in the second will be placed in
the result The pointer after the last element of the new block is
returned.

NOTE:

If begin1 <= result < end1 or begin1 <= result + (end1 - begin1) <
end1 or begin2 <= result < end2 or begin2 <= result + (end2 - begin2)
< end2 then the effect of difference is not defined.

SEE ALSO:

intersection, merge, set_union, symmetric_difference

ASSUMPTIONS:

Less_than ("<") and assignment ("=") are defined for the TYPE

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the blocks.  If N and M are the numbers of
locations in the blocks then at most N + M - 1 less_than operations
and N assignments are performed.


IMPLEMENTATION:

TYPE *difference(register TYPE *begin1, 
		 register TYPE *end1, 
		 register TYPE *begin2, 
		 register TYPE *end2, 
		 register TYPE *result)
{
  while (begin1 < end1 && begin2 < end2)
    if (*begin1 < *begin2)
      *result++ = *begin1++;
    else if (!(*begin2++ < *begin1))
      begin1++;

  while (begin1 < end1)
    *result++ = *begin1++;

  return result;
}


NAME:

fill - assigns the same value to all locations in a block

SYNOPSIS:

void fill(TYPE value, 
          TYPE *begin, 
	  TYPE *end);

DESCRIPTION:

fill assigns value to every location between begin (inclusive) and end
(exclusive)

SEE ALSO:

for_each, generate

ASSUMPTIONS:

assignment ("=") is defined for the TYPE

DEPENDS ON:

nothing

COMPLEXITY: 

Linear in the size of the block.  If N is the number of locations in
the block exactly N assignments of TYPE are performed.


IMPLEMENTATION:


void fill(register TYPE value, 
	  register TYPE *begin, 
	  register TYPE *end)
{
  while (begin < end)
    *begin++ = value;
}


NAME:

for_each - applies the function to every location in the block

SYNOPSIS:

void for_each(void (*function)(TYPE*), 
	      TYPE *begin, 
	      TYPE *end);

DESCRIPTION:

for_each applies the function to every location in the block from the
leftmost to the rightmost.

SEE ALSO:

generate

ASSUMPTIONS:

none

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block then exactly N calls to the function are performed.


IMPLEMENTATION:

void for_each(register void (*function)(TYPE*), 
	      register TYPE *begin, 
	      register TYPE *end)
{
  while (begin < end)
    (*function)(begin++);
}


NAME:

generate - applies a function to every location in a block

SYNOPSIS:

void generate(void (*function)(ptrdiff_t, TYPE*), 
              TYPE *begin, TYPE *end);

DESCRIPTION:

For every location in a block generate applies a function to the
0-origin index of the location in the block and the pointer to the
location.

SEE ALSO:

fill, for_each

ASSUMPTIONS:

none

DEPENDS ON:

none

COMPLEXITY: 

Linear in the size of the block.  If N is the number of locations in
the block exactly N function calls to "function" are performed.

EXAMPLE:

It is possible to define a function that assigns a consecutive 
integer starting from 0 to every location in the block (similar to
APL iota) by doing:

void zap(ptrdiff_t n, ptrdiff_t *address)
{
  *address = n;
}

void iota(ptrdiff_t *begin, ptrdiff_t *end)
{
  generate(zap, begin, end);
}


IMPLEMENTATION:

void generate(register void (*function)(ptrdiff_t, TYPE*), 
	      register TYPE *begin, 
	      register TYPE *end)
{
  register TYPE *index = begin;

  for (; begin < end; begin++)
    (*function)(begin - index, begin);
}


NAME:

insert - inserts an element in an ordered block

SYNOPSIS:

TYPE *insert(TYPE value, 
	     TYPE *begin, 
	     TYPE *end);

DESCRIPTION:

insert assigns value to the location in the ordered block that
contains the leftmost element greater than value. Before the
assignment all the elements from that location to the end of the block
are moved one location to the right.

SEE ALSO:

binary_partition, binary_search, set_insert

ASSUMPTIONS:

Less_than ("<") and assignment ("=") are defined for the TYPE

DEPENDS ON:

TYPE *binary_partition(TYPE value, 
		       TYPE *begin, 
		       TYPE *end);

void copy(TYPE *begin, 
          TYPE *end, 
	  TYPE *result);

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block then at most N assignments and at most logN operations
less_than are performed.


IMPLEMENTATION:

TYPE *insert(TYPE value, 
	     TYPE *begin, 
	     TYPE *end)
{
  begin = binary_partition(value, begin, end);

  copy(begin, end, begin + 1);

  *begin = value;

  return begin;
}


NAME:

insert - inserts an element in an ordered block

SYNOPSIS:

TYPE *insert(int (*relation)(TYPE*, TYPE*), 
	     TYPE value, 
	     TYPE *begin, 
	     TYPE *end);

DESCRIPTION:

insert assigns value to the location in the ordered block that
contains the leftmost element greater than value. Before the
assignment all the elements from that location to the end of the block
are moved one location to the right.  relation is the name of the
comparison function, which is called with two arguments that point to
the elements being compared.  As the function must return an integer
less than, equal to, or greater than zero, so must the first argument
to be considered be less than, equal to, or greater than the second.

SEE ALSO:

binary_partition, binary_search, set_insert

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE

DEPENDS ON:

TYPE *binary_partition(int (*relation)(TYPE*, TYPE*), 
		       TYPE value, 
		       TYPE *begin, 
		       TYPE *end);

void copy(TYPE *begin, 
          TYPE *end, 
	  TYPE *result);

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block then at most N assignments and at most logN call to the
relation are performed.


IMPLEMENTATION:

TYPE *insert(int (*relation)(TYPE*, TYPE*), 
	     TYPE value, 
	     TYPE *begin, 
	     TYPE *end)
{
  begin = binary_partition(relation, value, begin, end);

  copy(begin, end, begin + 1);

  *begin = value;

  return begin;
}


NAME:

insertion_sort - sorts a block

SYNOPSIS:

void insertion_sort(TYPE *begin, 
                    TYPE *end);

DESCRIPTION:

insertion_sort sorts a block in place.  The sorting is stable, namely,
the relative order of equal elements is preserved. It is the sort of
choice when: 1) the size of the block is small; or 2) the number of
elements out of order is small; or 3) the average distance between
original position of an element and its final destination is small.
(By small we mean less than 16.)

SEE ALSO:

merge_sort, sort, stable_sort

ASSUMPTIONS:

Less_than ("<") and assignment ("=") are defined for the TYPE

DEPENDS ON:

TYPE *minimum(TYPE *begin, 
	      TYPE *end);

COMPLEXITY:

Quadratic in the size of the block.  If N is the number of locations
in the block then on the average N^2/4 less_than operations and same
number of assignments are performed.


IMPLEMENTATION:

void insertion_sort(register TYPE *begin, 
		    register TYPE *end)
{
  if (end - begin < 2)  /* size < 2 */
    return;

  TYPE *r = minimum(begin, end); /* create a sentinel */
  TYPE temp = *begin;          /* swap */
  *begin = *r;
  *r = temp;

  begin++; /* there is no need to insert the second element */
  
  while (++begin < end)
    {
      REGISTER TYPE value = *begin;
      register TYPE *index = begin;
      
      while (value < *--index)
	*(index + 1) = *index;
      
      *(index + 1) = value;
    }
}


NAME:

insertion_sort - sorts a block

SYNOPSIS:

void insertion_sort(int (*relation)(TYPE*, TYPE*), 
                    TYPE *begin, 
		    TYPE *end);

DESCRIPTION:

insertion_sort sorts a block in place.  The sorting is stable, namely,
the relative order of equal elements is preserved. It is the sort of
choice when: 1) the size of the block is small; or 2) the number of
elements out of order is small; or 3) the average distance between
original position of an element and its final destination is small.
(By small we mean less than 16.)  relation is the name of the
comparison function, which is called with two arguments that point to
the elements being compared.  As the function must return an integer
less than, equal to, or greater than zero, so must the first argument
to be considered be less than, equal to, or greater than the second.

SEE ALSO:

merge_sort, sort, stable_sort

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE

DEPENDS ON:

nothing

COMPLEXITY:

Quadratic in the size of the block.  If N is the number of locations
in the block then on the average N^2/4 less_than operations and same
number of assignments are performed.


IMPLEMENTATION:

void insertion_sort(register int (*relation)(TYPE*, TYPE*), 
		    register TYPE *begin, 
		    TYPE *end)
{
  register TYPE *index = begin;

  while (++index < end)
    {
      TYPE value = *index;
      register TYPE *temp = &value;
      register TYPE *current = index;

      for (; begin < current && (*relation)(temp , current - 1) < 0; current--)
	*current = *(current - 1);

      *current = value;
    }
}


NAME:

intersection - collects those elements of two ordered blocks that are in both

SYNOPSIS:

TYPE *intersection(int (*relation)(TYPE*, TYPE*), 
		   TYPE *begin1, 
		   TYPE *end1, 
		   TYPE *begin2, 
		   TYPE *end2, 
		   TYPE *result);

DESCRIPTION:

intersection puts elements from two ordered blocks with no repetitions
into a new ordered block with no repetitions so that for every element
which is in both blocks it will be placed in the result The pointer
after the last element of the new block is returned.  relation is the
name of the comparison function, which is called with two arguments
that point to the elements being compared.  As the function must
return an integer less than, equal to, or greater than zero, so must
the first argument to be considered be less than, equal to, or greater
than the second.

NOTE:

If begin1 <= result < end1 or begin1 <= result + (end1 - begin1) <
end1 or begin2 <= result < end2 or begin2 <= result + (end2 - begin2)
< end2 then the effect of intersection is not defined.

SEE ALSO:

difference, merge, set_union, symmetric_difference, unique

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the blocks.  If N and M are the numbers of
locations in the blocks then at most N + M - 1 calls to relation and
maximum(N, M) assignments are performed.


IMPLEMENTATION:

TYPE *intersection(register int (*relation)(TYPE*, TYPE*), 
		   register TYPE *begin1, 
		   register TYPE *end1, 
		   register TYPE *begin2, 
		   register TYPE *end2, 
		   register TYPE *result)
{
  while (begin1 < end1 && begin2 < end2)
    {
      register int c = (*relation)(begin2, begin1);

      if (c < 0)
	begin2++;
      else if (0 < c)
	begin1++;
      else
	{
	  *(result++) = *(begin1++);
	  begin2++;
	}
    }
  return result;
}


NAME:

intersection - collects those elements of two ordered blocks that are in both

SYNOPSIS:

TYPE *intersection(TYPE *begin1, 
		   TYPE *end1, 
		   TYPE *begin2, 
		   TYPE *end2, 
		   TYPE *result);

DESCRIPTION:

intersection puts elements from two ordered blocks with no repetitions
into a new ordered block with no repetitions so that for every element
which is in both blocks it will be placed in the result The pointer
after the last element of the new block is returned.

NOTE:

If begin1 <= result < end1 or begin1 <= result + (end1 - begin1) <
end1 or begin2 <= result < end2 or begin2 <= result + (end2 - begin2)
< end2 then the effect of intersection is not defined.

SEE ALSO:

difference, merge, set_union, symmetric_difference, unique

ASSUMPTIONS:

Less_than ("<") and assignment ("=") are defined for the TYPE

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the blocks.  If N and M are the numbers of
locations in the blocks then at most N + M - 1 less_than operations
and maximum(N, M) assignments are performed.


IMPLEMENTATION:

TYPE *intersection(register TYPE *begin1, 
		   register TYPE *end1, 
		   register TYPE *begin2, 
		   register TYPE *end2, 
		   register TYPE *result)
{
  while (begin1 < end1 && begin2 < end2)
    if (*begin2 < *begin1)
      begin2++;
    else if (*begin1 < *begin2)
      begin1++;
    else
      {
	*(result++) = *(begin1++);
	begin2++;
      }
  return result;
}


NAME:

merge - combines two ordered blocks into one

SYNOPSIS:

void merge(int (*relation)(TYPE*, TYPE*), 
	   TYPE *begin1, 
	   TYPE *end1, 
	   TYPE *begin2, 
	   TYPE *end2, 
	   TYPE *result);

DESCRIPTION:

merge combines two ordered blocks into one.  merge is stable. That is,
equal elements from the first block precede equal elements from the
second.  relation is the name of the comparison function, which is
called with two arguments that point to the elements being compared.
As the function must return an integer less than, equal to, or greater
than zero, so must the first argument to be considered be less than,
equal to, or greater than the second.

NOTE:

If begin1 <= result < end1 or begin1 <= result + (end1 - begin1) <
end1 or begin2 <= result < end2 or begin2 <= result + (end2 - begin2)
< end2 than the effect of merge is not defined.

SEE ALSO:

difference, intersection, symmetric_difference, union

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the blocks.  If N and M are the numbers of
locations in the blocks then at most N + M - 1 less_than operations
and N + M assignments are performed.


IMPLEMENTATION:

void merge(register int (*relation)(TYPE*, TYPE*), 
	   register TYPE *begin1, 
	   register TYPE *end1, 
	   register TYPE *begin2, 
	   register TYPE *end2, 
	   register TYPE *result)
{
  while (begin1 < end1 && begin2 < end2)
    *result++ = ((*relation)(begin2, begin1) < 0 ? *begin2++ : *begin1++);

  while (begin1 < end1)
    *result++ = *begin1++;
  
  while (begin2 < end2)
    *result++ = *begin2++;
}


NAME:

merge - combines two ordered blocks into one

SYNOPSIS:

void merge(TYPE *begin1, 
	   TYPE *end1, 
	   TYPE *begin2, 
	   TYPE *end2, 
	   TYPE *result);

DESCRIPTION:

merge combines two ordered blocks into one.  merge is stable. That is,
equal elements from the first block precede equal elements from the
second.

NOTE:

If begin1 <= result < end1 or begin1 <= result + (end1 - begin1) <
end1 or begin2 <= result < end2 or begin2 <= result + (end2 - begin2)
< end2 then the effect of merge is not defined.

SEE ALSO:

difference, intersection, symmetric_difference, union

ASSUMPTIONS:

Less_than ("<") and assignment ("=") are defined for the TYPE

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the blocks.  If N and M are the numbers of
locations in the blocks then at most N + M - 1 calls to relation and N
+ M assignments are performed.


IMPLEMENTATION:

void merge(register TYPE *begin1, 
	   register TYPE *end1, 
	   register TYPE *begin2, 
	   register TYPE *end2, 
	   register TYPE *result)
{
  while (begin1 < end1 && begin2 < end2)
    *result++ = (*begin2 < *begin1 ? *begin2++ : *begin1++);

  while (begin1 < end1)
    *result++ = *begin1++;
  
  while (begin2 < end2)
    *result++ = *begin2++;

}


NAME:

merge_sort - sorts a block

SYNOPSIS:

TYPE *merge_sort(TYPE *begin, 
                 TYPE *end, 
		 TYPE *result);

DESCRIPTION:

merge_sort sorts a block. It is stable, that is the relative order of
equal elements is preserved. It does require an auxiliary block of the
same size (the address of an auxiliary block is the third argument to
merge_sort). It returns the address of the original block or the
address of the auxiliary block depending on which one contains the
final result of the sort.

NOTE:

If begin <= result < end or begin <= result + (end - begin) < end then
the effect of merge_sort is not defined.

SEE ALSO:

insertion_sort, sort, stable_sort

ASSUMPTIONS:

Less_than ("<") and assignment ("=") are defined for the TYPE

DEPENDS ON:

void insertion_sort(TYPE *begin, 
                    TYPE *end);

void merge(TYPE *begin1, 
	   TYPE *end1, 
	   TYPE *begin2, 
	   TYPE *end2, 
	   TYPE *result);

COMPLEXITY:

O(NlogN) in the size of the block.  If N is the size of the block then
at most N*log(N) less_than operations and at most the same number of
assignments is performed.


IMPLEMENTATION:

static void merge_sort_step(ptrdiff_t number, 
			    TYPE *begin, 
			    TYPE *end, 
			    TYPE *result)
{
  ptrdiff_t m = 2 * number;

  while (begin + m < end)
    {
      merge(begin, begin + number, begin + number, begin + m, result);
      begin += m;
      result += m;
    }

  if (begin + number + 1 < end)
    merge(begin, begin + number, begin + number, end, result);
  else
    while (begin < end)
      *result++ = *begin++;
}

static void insertion_sort_chunks(ptrdiff_t number, 
				  TYPE *begin, 
				  TYPE *end)
{
  for (; begin + number < end; begin += number)
    insertion_sort(begin, begin + number);

  insertion_sort(begin, end);
}

TYPE *merge_sort(TYPE *begin, 
		 TYPE *end, 
		 TYPE *result)
{
  ptrdiff_t number = 8, length = end - begin;

  insertion_sort_chunks(number, begin, end);

  for (; number < length; 
       number += number, end = begin, begin = result, result = end)
    merge_sort_step(number, begin, begin + length, result);

  return begin;
}


NAME:

merge_sort - sorts a block

SYNOPSIS:

TYPE *merge_sort(int (*relation)(TYPE*, TYPE*), 
                 TYPE *begin, 
		 TYPE *end, 
		 TYPE *result);

DESCRIPTION:

merge_sort sorts a block. It is stable, that is the relative order of
equal elements is preserved. It does require an auxiliary block of the
same size (the address of an auxiliary block is the third argument to
merge_sort). It returns the address of the original block or the
address of the auxiliary block depending on which one contains the
final result of the sort.  relation is the name of the comparison
function, which is called with two arguments that point to the
elements being compared.  As the function must return an integer less
than, equal to, or greater than zero, so must the first argument to be
considered be less than, equal to, or greater than the second.

NOTE:

If begin <= result < end or begin <= result + (end - begin) < end then
the effect of merge_sort is not defined.

SEE ALSO:

insertion_sort, sort, stable_sort

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE

DEPENDS ON:

void insertion_sort(int (*relation)(TYPE*, TYPE*), 
                    TYPE *begin, 
		    TYPE *end);

void merge(int (*relation)(TYPE*, TYPE*), 
	   TYPE *begin1, 
	   TYPE *end1, 
	   TYPE *begin2, 
	   TYPE *end2, 
	   TYPE *result);

COMPLEXITY:

O(NlogN) in the size of the block.  If N is the size of the block then
at most N*log(N) calls to relation and at most the same number of
assignments is performed.


IMPLEMENTATION:

static void merge_sort_step(int (*relation)(TYPE*, TYPE*), 
			    ptrdiff_t number, 
			    TYPE *begin, 
			    TYPE *end, 
			    TYPE *result)
{
  ptrdiff_t m = 2 * number;

  while (begin + m < end)
    {
      merge(relation, begin, begin + number, begin + number, begin + m, 
	    result);
      begin += m;
      result += m;
    }

  if (begin + number + 1 < end)
    merge(relation, begin, begin + number, begin + number, end, result);
  else
    while (begin < end)
      *result++ = *begin++;
}

static void insertion_sort_chunks(int (*relation)(TYPE*, TYPE*), 
				  ptrdiff_t number, 
				  TYPE *begin, 
				  TYPE *end)
{
  for (; begin + number < end; begin += number)
    insertion_sort(relation, begin, begin + number);

  insertion_sort(relation, begin, end);
}

TYPE *merge_sort(int (*relation)(TYPE*, TYPE*), 
		 TYPE *begin, 
		 TYPE *end, 
		 TYPE *result)
{
  ptrdiff_t number = 8, length = end - begin;

  insertion_sort_chunks(relation, number, begin, end);

  for (; number < length; 
       number += number, end = begin, begin = result, result = end)
    merge_sort_step(relation, number, begin, begin + length, result);

  return begin;
}


NAME:

minimum - finds the smallest element in the block

SYNOPSIS:

TYPE *minimum(TYPE *begin, 
	      TYPE *end);

DESCRIPTION:

minimum returns a pointer to the leftmost smallest element in the
block

NOTE:

If the block is empty then begin is returned.

SEE ALSO:

select

ASSUMPTIONS:

Less_than ("<") is defined for the TYPE

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block then exactly N - 1 operation less_than are performed.


IMPLEMENTATION:

TYPE *minimum(register TYPE *begin, 
	      register TYPE *end)
{
  register TYPE *index = begin;

  while (++begin < end)
    if (*begin < *index)
      index = begin;

  return index;
}


NAME:

minimum - finds the smallest element in the block

SYNOPSIS:

TYPE *minimum(int (*relation)(TYPE*, TYPE*), 
	      TYPE *begin, 
	      TYPE *end);

DESCRIPTION:

minimum returns a pointer to the leftmost smallest element in the
block.  relation is the name of the comparison function, which is
called with two arguments that point to the elements being compared.
As the function must return an integer less than, equal to, or greater
than zero, so must the first argument to be considered be less than,
equal to, or greater than the second.

NOTE:

If the block is empty then begin is returned.

SEE ALSO:

select

ASSUMPTIONS:

none

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block then exactly N - 1 calls to the relation are performed.


IMPLEMENTATION:

TYPE *minimum(register int (*relation)(TYPE*, TYPE*), 
	      register TYPE *begin, 
	      register TYPE *end)
{
  register TYPE *index = begin;

  while (++begin < end)
    if ((*relation)(begin, index) < 0)
      index = begin;

  return index;
}


NAME:

mismatch - finds first mismatch among two blocks

SYNOPSIS:

TYPE *mismatch(TYPE *begin1, 
	       TYPE *end1, 
	       TYPE *begin2, 
	       TYPE *end2);

DESCRIPTION:

mismatch returns a pointer to the leftmost element within the first
block which is not equal to the corresponding element in the second
block. If such an element does not exist then the 0 pointer is
returned.

SEE ALSO:

other mismatch, search

ASSUMPTIONS:

Equality ("==") is defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the blocks.  If N and M are correspondingly the
numbers of locations in the first and second blocks then at most
minimum(N, M) equality operations on the TYPE are performed.


IMPLEMENTATION:

TYPE *mismatch(register TYPE *begin1, 
	       register TYPE *end1, 
	       register TYPE *begin2, 
	       register TYPE *end2)
{
  register ptrdiff_t len = 
    end1 - begin1 < end2 - begin2 ? end1 - begin1 : end2 - begin2;

  while (0 < len--)
    if (!(*begin1++ == *begin2++))
      return begin1;

  return 0;
}


NAME:

mismatch - finds first mismatch among two blocks

SYNOPSIS:

TYPE *mismatch(int (*relation)(TYPE*, TYPE*), 
	       TYPE *begin1, 
	       TYPE *end1, 
	       TYPE *begin2, 
	       TYPE *end2);

DESCRIPTION:

mismatch returns a leftmost location within the first block which does
not satisfy the relation with the corresponding location in the second
block. If such an element does not exist then the 0 pointer is
returned.

SEE ALSO:

other mismatch, search

ASSUMPTIONS:

none

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the blocks.  If N and M are correspondingly the
numbers of locations in the first and second blocks then at most
minimum(N, M) calls to the relation are performed.


IMPLEMENTATION:

TYPE *mismatch(register int (*relation)(TYPE*, TYPE*), 
	       register TYPE *begin1, 
	       register TYPE *end1, 
	       register TYPE *begin2, 
	       register TYPE *end2)
{
  register ptrdiff_t len = 
    end1 - begin1 < end2 - begin2 ? end1 - begin1 : end2 - begin2;

  while (0 < len--)
    if (!(*relation)(begin1++, begin2++))
      return begin1;

  return 0;
}


NAME:

partition - separates elements into those that satisfy the predicate and
those that do not

SYNOPSIS:

TYPE *partition(int (*predicate)(TYPE*), 
		TYPE *begin, 
		TYPE *end); 

DESCRIPTION:

partition moves elements in those locations of the block that do
satisfy the predicate to the left and those that do not satisfy the
predicate to the right and returns the pointer after the last
"satisfying" element.

NOTE:

partition does not preserve the relative order of elements in both
groups ("satisfying" and "not-satisfying") that is, it is not stable.
If stability is desired then stable_partition should be used.
(Actually, at present it is better to use stable_partition_copy - if
extra memory is available - and then copy the block back.)

SEE ALSO:

other partition, partition_copy, remove, remove_copy, 
stable_partition, stable_partition_copy, stable_remove, 
stable_remove_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N calls to predicate are done. If P is the number of
locations in the block that do satisfy the predicate then at most
3*min(P, N-P) assignments of TYPE are done.


IMPLEMENTATION:

TYPE *partition(register int (*predicate)(TYPE*), 
		register TYPE *begin, 
		register TYPE *end) 
{
  for (;;)
    {
      for (;;begin++) 
	if (begin >= end) 
	  return end;
	else if (!(*predicate)(begin))
	  break;

      for (;;) 
	if (begin >= --end)
	  return end;
	else if ((*predicate)(end))
	  break;

      {
	REGISTER TYPE temp = *begin;
	*begin++ = *end;
	*end = temp;
      }
    }
}


NAME:

partition - separates elements into those that are equal to the value and
those that are not

SYNOPSIS:

TYPE *partition(TYPE value, 
		TYPE *begin, 
		TYPE *end); 

DESCRIPTION:

partition moves elements in the block that are equal to the value to
the left and those that are not equal to the right and returns the
pointer after the last "equal" element.

NOTE:

partition does not preserve the relative order of elements in both
groups ("equal" and "not-equal") that is, it is not stable. If
stability is desired then stable_partition should be used. (Actually,
at present it is better to use stable_partition_copy - if extra memory
is available - and then copy the block back.)

SEE ALSO:

other partition, partition_copy, remove, remove_copy, 
stable_partition, stable_partition_copy, stable_remove, 
stable_remove_copy

ASSUMPTIONS:

Assignment ("=") and equality ("==") are defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N equality operations on TYPE are performed.  If P
is the number of elements in the block that are equal to the value
then at most 3*min(P, N-P) assignments of TYPE are done.


IMPLEMENTATION:

TYPE *partition(REGISTER TYPE value, 
		register TYPE *begin, 
		register TYPE *end) 
{
  for (;;)
    {
      for (;;begin++)
	if (begin >= end) 
	  return end;
	else if (!(*begin == value))
	  break;

      for (;;) 
	if (begin >= --end)
	  return end;
	else if (*end == value)
	  break;

      {
	REGISTER TYPE temp = *begin;
	*begin++ = *end;
	*end = temp;
      }
    }
}


NAME:

partition - separates elements into those that relate to the value and
those that are not

SYNOPSIS:

TYPE *partition(int (*relation)(TYPE*, TYPE*), 
		TYPE value, 
		TYPE *begin, 
		TYPE *end);

DESCRIPTION:

partition moves elements in those locations of the block that do
satisfy the relation with the pointer to the value to the left and
those that do not satisfy the relation to the right and returns the
pointer after the last "satisfying" element.

NOTE:

partition does not preserve the relative order of elements in both
groups ("satisfying" and "not-satisfying") that is, it is not stable.
If stability is desired then stable_partition should be used.
(Actually, at present it is better to use stable_partition_copy - if
extra memory is available - and then copy the block back.)

SEE ALSO:

other partition, partition_copy, remove, remove_copy, 
stable_partition, stable_partition_copy, stable_remove, 
stable_remove_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N equality operations on TYPE are performed.  If P
is the number of locations in the block that satisfy relation with the
pointer to the value then at most 3*min(P, N-P) assignments of TYPE
are done.


IMPLEMENTATION:

TYPE *partition(register int (*relation)(TYPE*, TYPE*), 
		TYPE value, 
		register TYPE *begin, 
		register TYPE *end)
{
  register TYPE *temp = &value;

  for (;;)
    {
      for (;;begin++) 
	if (begin >= end) 
	  return end;
	else if (!(*relation)(begin, temp))
	  break;

      for (;;) 
	if (begin >= --end)
	  return end;
	else if ((*relation)(end, temp))
	  break;

      {
	REGISTER TYPE temp = *begin;
	*begin++ = *end;
	*end = temp;
      }
    }
}


NAME:

partition_copy - copies elements satisfying the predicate before the elements
that do not

SYNOPSIS:

TYPE *partition_copy(int (*predicate)(TYPE*), 
		     TYPE *begin, 
		     TYPE *end, 
		     TYPE *result);

DESCRIPTION:

partition_copy first copies elements in those locations of the block
that do satisfy the predicate and then those that do not satisfy the
predicate and returns the pointer after the copy of the last
"satisfying" element.

NOTE:

1) partition_copy does not preserve the relative order of elements in
both groups ("satisfying" and "not-satisfying") that is, it is not
stable. If stability is desired then stable_partition_copy should be
used.  (Actually, the ordering of the "satisfying" group is stable,
and the ordering of the "not-satisfying" is the inverse of the
stable.)

2) If begin <= result < end or begin <= result + (end - begin) < end
then the effect of partition_copy is not defined.

SEE ALSO:

partition, other partition_copy, remove, remove_copy, 
stable_partition, stable_partition_copy, stable_remove, 
stable_remove_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N calls to the predicate and N assignments of TYPE
are done.


IMPLEMENTATION:

TYPE *partition_copy(register int (*predicate)(TYPE*), 
		     register TYPE *begin, 
		     register TYPE *end, 
		     register TYPE *result)
{
  register TYPE *last = result + (end - begin);

  for (; begin < end; begin++)
    if ((*predicate)(begin))
      *(result++) = *begin;
    else
      *--last = *begin;

  return last;
}


NAME:

partition_copy - copies elements equal to the value before those that are not

SYNOPSIS:

TYPE *partition_copy(TYPE value, 
		     TYPE *begin, 
		     TYPE *end, 
		     TYPE *result);

DESCRIPTION:

partition_copy first copies elements in the block that are equal to
the value and then those that are not and returns the pointer after
the copy of the last "equal" element.

NOTE:

1) partition_copy does not preserve the relative order of elements in
both groups ("equal" and "not-equal") that is, it is not stable. If
stability is desired then stable_partition_copy should be used.
(Actually, the ordering of the "equal" group is stable, and the
ordering of the "not-equal" is the inverse of the stable.)

2) If begin <= result < end or begin <= result + (end - begin) < end
then the effect of partition_copy is not defined.

SEE ALSO:

partition, other partition_copy, remove, remove_copy,
stable_partition, stable_partition_copy, stable_remove,
stable_remove_copy

ASSUMPTIONS:

Assignment ("=") and equality ("==") are defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N equalities of TYPE and N assignments of TYPE are
done.


IMPLEMENTATION:

TYPE *partition_copy(REGISTER TYPE value, 
		     TYPE *begin, 
		     register TYPE *end, 
		     register TYPE *result)
{
  register TYPE *last = result + (end - begin); 

  for (; begin < end; begin++)
    if (*begin == value)
      *(result++) = *begin;
    else
      *(--last) = *begin;

  return last;
}


NAME:

partition_copy - copies elements related to the value before 
those that are not

SYNOPSIS:

TYPE *partition_copy(int (*relation)(TYPE*, TYPE*), 
		     TYPE value, 
		     TYPE *begin, 
		     TYPE *end, 
		     TYPE *result);

DESCRIPTION:

partition_copy first copies those elements in the block locations of
which satisfy the relation with the pointer to the value and then
those that do not and returns the pointer after the copy of the last
"satisfying" element.

NOTE:

1) partition_copy does not preserve the relative order of elements in
both groups ("satisfying" and "not-satisfying") that is, it is not
stable. If stability is desired then stable_partition_copy should be
used.  (Actually, the ordering of the "satisfying" group is stable,
and the ordering of the "not-satisfying" is the inverse of the
stable.)

2) If begin <= result < end or begin <= result + (end - begin) < end
then the effect of partition_copy is not defined.

SEE ALSO:

partition, other partition_copy, remove, remove_copy, 
stable_partition, stable_partition_copy, stable_remove, 
stable_remove_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N calls to the relation and N assignments of TYPE
are done.


IMPLEMENTATION:

TYPE *partition_copy(register int (*relation)(TYPE*, TYPE*), 
		     TYPE value, 
		     register TYPE *begin, 
		     register TYPE *end, 
		     register TYPE *result)
{
  register TYPE *last = result + (end - begin);
  register TYPE *temp = &value;
 
  for (; begin < end; begin++)
    if ((*relation)(begin, temp))
      *(result++) = *begin;
    else
      *(--last) = *begin;

  return last;
}


NAME:

position - finds leftmost location in the block satisfying the predicate

SYNOPSIS:

TYPE *position(int (*predicate)(TYPE*), 
	       TYPE *begin, 
	       TYPE *end);

DESCRIPTION:

Position returns the leftmost pointer in the block that satisfies
predicate if such a pointer exists, or 0 if there is no such pointer.

SEE ALSO:

other position, right_position, search

ASSUMPTIONS:

none

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block at most N calls to predicate are done.


IMPLEMENTATION:

TYPE *position(register int (*predicate)(TYPE*), 
	       register TYPE *begin, 
	       register TYPE *end)
{
  while (begin < end)
    if ((*predicate)(begin++))
      return begin - 1;

  return 0;
}


NAME:

position - finds leftmost value in the block equal to the given value

SYNOPSIS:

TYPE *position(TYPE value, 
	       TYPE *begin, 
	       TYPE *end);

DESCRIPTION:

Position returns the leftmost pointer in the block that points to an
element equal to value if such a pointer exists, or 0 if there is no
such pointer.

SEE ALSO:

other position, right_position, search

ASSUMPTIONS:

Equality ("==") is defined for the TYPE.

DEPENDS ON:

Nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block at most N equalities of TYPE are performed.


IMPLEMENTATION:

TYPE *position(REGISTER TYPE value, 
	       register TYPE *begin, 
	       register TYPE *end)
{
  while (begin < end)
    if (*begin++ == value)
      return begin - 1;

  return 0;
}


NAME:

position - finds leftmost value in the block satisfying the relation
to the given value

SYNOPSIS:

TYPE *position(int (*relation)(TYPE*, TYPE*), 
	       TYPE value, 
	       TYPE *begin, 
	       TYPE *end);

DESCRIPTION:

position returns the leftmost pointer in the block that satisfies
relation with the pointer to value if such a pointer exists, or 0 if
there is no such pointer.

SEE ALSO:
Aother position, right_position, search

ASSUMPTIONS:

none

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block at most N calls to relation are done.


IMPLEMENTATION:

TYPE *position(register int (*relation)(TYPE*, TYPE*), 
	       TYPE value, 
	       register TYPE *begin, 
	       register TYPE *end)
{
  register TYPE *temp = &value;

  while (begin < end) 
    if ((*relation)(begin++, temp))
      return begin - 1;

  return 0;
}


NAME:

random - returns a random pointer to a location in a block


SYNOPSIS:

TYPE *random(TYPE *begin, 
             TYPE *end);

DESCRIPTION:

random returns a uniformly distributed random pointer between begin
(inclusive) and end (exclusive). Since random uses drand48 it is
important that the random number generator is initialized with
srand48, seed48, or lcong48 (see drand48(3C)) before random is used.
If begin is greater or equal than end 0 pointer is returned.

NOTE:

random uses drand48, which is UNIX System V specific. In the future,
it should be parameterized and use the appropriate random number
generator.

ASSUMPTIONS: 

none

DEPENDS ON:

double drand48(); (in <rand48.h>)

COMPLEXITY:

constant in the size of the block


IMPLEMENTATION:

#include <rand48.h>

TYPE *random(TYPE *begin, 
	     TYPE *end)
{

  if (begin < end) 
    return begin + (ptrdiff_t)(drand48() * (end - begin));
  else
    return 0;

}


NAME:

remove - removes elements satisfying the predicate

SYNOPSIS:

TYPE *remove(int (*predicate)(TYPE*), 
	     TYPE *begin, 
	     TYPE *end);

DESCRIPTION:

remove moves all the elements in the block locations of which do not
satisfy predicate to the left and returns the pointer pointing after
the last such element.

NOTE:

remove does not preserve the relative order of elements locations of
which do not satisfy the predicate, that is, it is not stable. If
stability is desired then stable_remove should be used.

SEE ALSO:

partition, partition_copy, remove_copy, 
stable_partition, stable_partition_copy, stable_remove, 
stable_remove_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N calls to predicate are done. If P is the number of
locations in the block that do not satisfy predicate then at most P
assignments of TYPE are done.


IMPLEMENTATION:

TYPE *remove(register int (*predicate)(TYPE*), 
	     register TYPE *begin, 
	     register TYPE *end)
{
  for (;;)
    {
      for (;;begin++) 
	if (begin >= end) 
	  return end;
	else if ((*predicate)(begin))
	  break;

      for (;;) 
	if (begin >= --end)
	  return end;
	else if (!(*predicate)(end))
	  break;

      *begin++ = *end;
    }
}


NAME:

remove - removes elements equal to the value

SYNOPSIS:

TYPE *remove(TYPE value, 
	     TYPE *begin, 
	     TYPE *end);

DESCRIPTION:

remove moves all the elements in the block which are not equal to
value to the left and returns the pointer pointing after the last such
element.

NOTE:

remove does not preserve the relative order of elements that are not
equal to the value, that is, it is not stable. If stability is desired
then stable_remove should be used.

SEE ALSO:

partition, partition_copy, other remove, remove_copy, 
stable_partition, stable_partition_copy, stable_remove, 
stable_remove_copy

ASSUMPTIONS:

Assignment ("=") and equality ("==") are defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N equality operations of the TYPE are performed. If
P is the number of locations in the block that are not equal to the
value then at most P assignments of TYPE are done.


IMPLEMENTATION:

TYPE *remove(REGISTER TYPE value, 
	     register TYPE *begin, 
	     register TYPE *end)
{
  for (;;)
    {
      for (;;begin++)
	if (begin >= end) 
	  return end;
	else if (*begin == value)
	  break;

      for (;;) 
	if (begin >= --end)
	  return end;
	else if (!(*end == value))
	  break;

      *begin++ = *end;
    }
}


NAME:

remove - removes elements satisfying the relation with the value


SYNOPSIS:

TYPE *remove(int (*relation)(TYPE*, TYPE*), 
	     TYPE value, 
	     TYPE *begin, 
	     TYPE *end);

DESCRIPTION:

remove moves all the elements in the block, locations of which do not
satisfy the relation with the pointer to the value, to the left and
returns the pointer pointing after the last such element.

NOTE:

remove does not preserve the relative order of elements locations of
which do not satisfy the relation with the pointer to the value, that
is, it is not stable. If stability is desired then stable_remove
should be used.

SEE ALSO:

partition, partition_copy, other remove, remove_copy, 
stable_partition, stable_partition_copy, stable_remove, 
stable_remove_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N calls to the relation are done. If P is the number
of locations in the block that do not satisfy the relation with the
value then at most P assignments of TYPE are done.


IMPLEMENTATION:

TYPE *remove(register int (*relation)(TYPE*, TYPE*), 
	     TYPE value, 
	     register TYPE *begin, 
	     register TYPE *end)
{
  register TYPE *temp = &value;
  for (;;)
    {
      for (;;begin++) 
	if (begin >= end) 
	  return end;
	else if ((*relation)(begin, temp))
	  break;

      for (;;) 
	if (begin >= --end)
	  return end;
	else if (!(*relation)(end, temp))
	  break;

      *begin++ = *end;
    }
}


NAME:

remove_copy - copies the elements not satisfying the predicate

SYNOPSIS:

TYPE *remove_copy(int (*predicate)(TYPE*), 
		  TYPE *begin, 
		  TYPE *end, 
		  TYPE *result);

DESCRIPTION:

remove_copy copies elements in those locations in the block that do
not satisfy the predicate in the consecutive locations starting with
result, and returns the pointer past the last of the copies.

NOTE:

1) The relative order of the elements not satisfying the predicate IS
preserved. (It IS stable.)

2) If begin <= result < end or begin <= result + (end - begin) < end
then the effect of remove_copy is not defined.

SEE ALSO:

partition, partition_copy, remove, other remove_copy, 
stable_partition, stable_partition_copy, stable_remove, 
stable_remove_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N calls to predicate are done. If P is the number of
locations in the block that do not satisfy predicate then exactly P
assignments of TYPE are done.


IMPLEMENTATION:

TYPE *remove_copy(register int (*predicate)(TYPE*), 
		  register TYPE *begin, 
		  register TYPE *end, 
		  register TYPE *result)
{
  for (; begin < end; begin++)
    if (!(*predicate)(begin))
      *result++ = *begin;

  return result;
}


NAME:

remove_copy - copies the elments not equal to the value

SYNOPSIS:

TYPE *remove_copy(TYPE value, 
		  TYPE *begin, 
		  TYPE *end, 
		  TYPE *result);

DESCRIPTION:

remove_copy copies those elements in the block, that are not equal to
the value, in the consecutive locations starting with result, and
returns the pointer past the last of the copies.

NOTE:

1) The relative order of the elements not satisfying the predicate IS
preserved. (It IS stable.)

2) If begin <= result < end or begin <= result + (end - begin) < end
then the effect of remove_copy is not defined.

SEE ALSO:

partition, partition_copy, remove, other remove_copy, 
stable_partition, stable_partition_copy, stable_remove, 
stable_remove_copy

ASSUMPTIONS:

Assignment ("=") and equality ("==") are defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N equality operations of the TYPE are performed. If
P is the number of locations in the block that are not equal to the
value then exactly P assignments of TYPE are done.


IMPLEMENTATION:

TYPE *remove_copy(REGISTER TYPE value, 
		  register TYPE *begin, 
		  register TYPE *end, 
		  register TYPE *result)
{
  for (; begin < end; begin++)
    if (!(*begin == value))
      *result++ = *begin;

  return result;
}


NAME:

remove_copy - copies elements that are not related to the value

SYNOPSIS:

TYPE *remove_copy(int (*relation)(TYPE*, TYPE*), 
		  TYPE value, 
		  TYPE *begin, 
		  TYPE *end, 
		  TYPE *result);

DESCRIPTION:

remove_copy copies those elements in the locations in the block, that
do not satisfy the relation with the pointer to the value, in the
consecutive locations starting with result, and returns the pointer
past the last of the copies.

NOTE:

1) The relative order of the elements not satisfying the predicate IS
preserved. (It IS stable.)

2) If begin <= result < end or begin <= result + (end - begin) < end
then the effect of remove_copy is not defined.

SEE ALSO:

partition, partition_copy, remove, other remove_copy, 
stable_partition, stable_partition_copy, stable_remove, 
stable_remove_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N calls to the relation are done. If P is the number
of locations in the block that do not satisfy the relation with the
value then exactly P assignments of TYPE are done.


IMPLEMENTATION:

TYPE *remove_copy(register int (*relation)(TYPE*, TYPE*), 
		  TYPE value, 
		  register TYPE *begin, 
		  register TYPE *end, 
		  register TYPE *result)
{
  register TYPE *temp = &value;

  for (; begin < end; begin++)
    if (!(*relation)(begin, temp))
      *result++ = *begin;

  return result;
}


NAME:

remove_duplicates - removes duplicate elements

SYNOPSIS:

TYPE *remove_duplicates(TYPE *begin, 
			TYPE *end);

DESCRIPTION:

remove_duplicates moves all unique (not equal to each other) elements
in the block to the left and returns the pointer after the last unique
elements. The relative order of the unique elements is preserved.

NOTE:

remove_duplicate is quadratic and should not be used with large (more
than a hundred or so elements) blocks. Large blocks should be first
sorted with sort or stable_sort and then passed through unique.

SEE ALSO:

other remove_duplicates, remove_duplicates_copy, unique, unique_copy

ASSUMPTIONS:

Assignment ("=") and equality ("==") are defined for the TYPE.

DEPENDS ON:

TYPE *position(TYPE value, 
	       TYPE *begin, 
	       TYPE *end);

COMPLEXITY:

Quadratic in the size of the block.  If N is the number of locations
in the block at most N^2/2 equality operations of TYPE and at most N -
2 assignments of TYPE are performed.


IMPLEMENTATION:

TYPE *remove_duplicates(register TYPE *begin, 
			register TYPE *end)
{
  register TYPE *index = begin;
  register TYPE *m;

  for(;index < end; index++)
    if (position(*index, begin, index) != index)
      break;

  m = index;

  while (++index < end)
    if (position(*index, begin, m) == m)
      *m++ = *index;

  return m;
}
      

NAME:

remove_duplicates - removes duplicate elements

SYNOPSIS:

TYPE *remove_duplicates(int (*relation)(TYPE*, TYPE*), 
			TYPE *begin, 
			TYPE *end);

DESCRIPTION:

remove_duplicates moves all unique (not satisfying the relation to
each other) elements in the block to the left and returns the pointer
after the last unique elements. The relative order of the unique
elements is preserved.

NOTE:

remove_duplicate is quadratic and should not be used with large (more
than a hundred or so elements) blocks. Large blocks should be first
sorted with sort or stable_sort and then passed through unique.

SEE ALSO:

other remove_duplicates, remove_duplicates_copy, unique, unique_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

TYPE *position(int (*relation)(TYPE*, TYPE*), 
               TYPE value, 
	       TYPE *begin, 
	       TYPE *end);

COMPLEXITY:

Quadratic in the size of the block.  If N is the number of locations
in the block at most N^2/2 calls to the relation and at most N - 2
assignments of TYPE are performed.


IMPLEMENTATION:

TYPE *remove_duplicates(int (*relation)(TYPE*, TYPE*), 
			register TYPE *begin, 
			register TYPE *end)
{
  register TYPE *index = begin;
  register TYPE *m;

  for(;index < end; index++)
    if (position(relation, *index, begin, index) != index)
      break;

  m = index;

  while (++index < end)
    if (!position(relation, *index, begin, m))
      *m++ = *index;

  return m;
}
      

NAME:

remove_duplicates_copy - copies all unique elements

SYNOPSIS:

TYPE *remove_duplicates_copy(TYPE *begin, 
			     TYPE *end, 
			     TYPE *result);

DESCRIPTION:

remove_duplicates_copy copies all unique (not equal to each other)
elements in the block and returns the pointer after the last copied
element. The relative order of the unique elements is preserved.

NOTE:

1) remove_duplicate_copy is quadratic and should not be used with
large (more than a hundred or so elements) blocks. Large blocks should
be first copied, then sorted with sort or stable_sort and then passed
through unique.

2) If begin <= result < end or begin <= result + (end - begin) < end
then the effect of remove_duplicates_copy is not defined.

SEE ALSO:

remove_duplicates, other remove_duplicates_copy, unique, unique_copy

ASSUMPTIONS:

Assignment ("=") and equality ("==") are defined for the TYPE.

DEPENDS ON:

TYPE *position(TYPE value, 
	       TYPE *begin, 
	       TYPE *end);

COMPLEXITY:

Quadratic in the size of the block.  If N is the number of locations
in the block at most N^2/2 equality operations of TYPE and at most N
assignments of TYPE are performed.


IMPLEMENTATION:

TYPE *remove_duplicates_copy(register TYPE *begin, 
			     register TYPE *end, 
			     register TYPE *result)
{
  register TYPE *m = result;

  for (; begin < end; begin++)
    if (!position(*begin, result, m))
      *m++ = *begin;

  return m;
}
      

NAME:

remove_duplicates_copy - copies all unique elements

SYNOPSIS:

TYPE *remove_duplicates_copy(int (*relation)(TYPE*, TYPE*), 
			     TYPE *begin, 
			     TYPE *end, 
			     TYPE *result);

DESCRIPTION:

remove_duplicates_copy copies all unique (not satisfying the relation
to each other) elements in the block and returns the pointer after the
last copied element. The relative order of the unique elements is
preserved.

NOTE:

1) remove_duplicate_copy is quadratic and should not be used with
large (more than a hundred or so elements) blocks. Large blocks should
be first copied, then sorted with sort or stable_sort and then passed
through unique.

2) If begin <= result < end or begin <= result + (end - begin) < end then
the effect of remove_duplicates_copy is not defined.

SEE ALSO:

remove_duplicates, other remove_duplicates_copy, unique, unique_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

TYPE *position(int (*relation)(TYPE*, TYPE*), 
               TYPE value, 
	       TYPE *begin, 
	       TYPE *end);

COMPLEXITY:

Quadratic in the size of the block.  If N is the number of locations
in the block at most N^2/2 calls to the relation and at most N
assignments of TYPE are performed.


IMPLEMENTATION:

TYPE *remove_duplicates_copy(int (*relation)(TYPE*, TYPE*), 
			     register TYPE *begin, 
			     register TYPE *end, 
			     register TYPE *result)
{
  register TYPE *m = result;

  for (; begin < end; begin++)
    if (position(relation, *begin, result, m) == m)
      *m++ = *begin;

  return m;
}
      

NAME: 

reverse - reverses a block in place

SYNOPSIS:

void reverse(TYPE *begin, 
	     TYPE *end);

DESCRIPTION:

Reverse reverses a block in place, namely, for every integer i, 0 <= i
< (end - begin), that after the reversal the location end - (i + 1)
has the same value as begin + i had before the reversal.

SEE ALSO:

reverse_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY: 

Linear in the size of the block.  If N is the number of locations in
the block exactly 3*floor(N/2) assignments of TYPE are performed.


IMPLEMENTATION:


void reverse(register TYPE *begin, 
	     register TYPE *end)
{
  while (begin < --end)
    {
      REGISTER TYPE temp = *begin;
      *begin++ = *end;
      *end = temp;
    }
}


NAME:

reverse_copy - copies a block in the reversed order

SYNOPSIS:

void reverse_copy(TYPE *begin, 
		  TYPE *end,
		  TYPE *result);

DESCRIPTION:

Reverse_copy moves every value in a block into a new location in the
reversed order, namely, for every integer i, 0 <= i < (end - begin),
that after the reversal the location result + i has the same value as
end - (i + 1) had before the reversal.

NOTE:

If begin <= result < end or begin <= result + (end - begin) < end then
the effect of reverse_copy is not defined.

SEE ALSO:

reverse

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY: 

Linear in the size of the block.  If N is the number of locations in
the block exactly N assignments of TYPE are performed.


IMPLEMENTATION:

void reverse_copy(register TYPE *begin, 
		  register TYPE *end, 
		  register TYPE *result)
{
  while (begin < end--)
    *result++ = *end;
}


NAME:

right_position - finds rightmost location in the block satisfying the predicate

SYNOPSIS:

TYPE *right_position(int (*predicate)(TYPE*), 
		     TYPE *begin, 
		     TYPE *end);

DESCRIPTION:

Right_position returns the rightmost pointer in the block that
satisfies predicate if such a pointer exists, or 0 if there is no such
pointer.

SEE ALSO:

position, other right_position, search

ASSUMPTIONS:

none

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block at most N calls to predicate are done.


IMPLEMENTATION:

TYPE *right_position(register int (*predicate)(TYPE*), 
		     register TYPE *begin, 
		     register TYPE *end)
{
  while (begin < end) 
    if ((*predicate)(--end))
      return end;

  return 0;
}


NAME:

right_position - finds rightmost value in the block equal to the given value

SYNOPSIS:

TYPE *right_position(TYPE value, 
		     TYPE *begin, 
		     TYPE *end);

DESCRIPTION:

Position returns the rightmost pointer in the block that points to an
element equal to value if such a pointer exists, or 0 if there is no
such pointer.

SEE ALSO:

position, other right_position, search

ASSUMPTIONS:

Equality ("==") is defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block at most N equalities of TYPE are performed.


IMPLEMENTATION:

TYPE *right_position(REGISTER TYPE value, 
		     register TYPE *begin, 
		     register TYPE *end)
{
  while (begin < end) 
    if (*--end == value)
      return end;

  return 0;
}


NAME:

right_position - finds rightmost value in the block satisfying relation
to the given value

SYNOPSIS:

TYPE *right_position(int (*relation)(TYPE*, TYPE*), 
		     TYPE value, 
		     TYPE *begin, 
		     TYPE *end);

DESCRIPTION:

Right_position returns the rightmost pointer in the block that
satisfies relation with the pointer to value if such a pointer exists,
or 0 if there is no such pointer.

SEE ALSO:

position, other right_position, search

ASSUMPTIONS:

none

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block at most N calls to relation are done.


IMPLEMENTATION:


TYPE *right_position(register int (*relation)(TYPE*, TYPE*), 
		     TYPE value, 
		     register TYPE *begin, 
		     register TYPE *end)
{
  register TYPE *temp = &value;

  while (begin < end) 
    if ((*relation)(--end, temp))
      return end;

  return 0;
}


NAME:

rotate - circularly rotates a block in place

SYNOPSIS:

void rotate(ptrdiff_t number, 
	    TYPE *begin, 
	    TYPE *end);

DESCRIPTION:

If number is non-negative then rotate circularly rotates a block to
the right.  If number is negative then rotate circularly rotates a
block to the left.  In both cases, for every i, 0 <= i < (end -
begin), the value at the location begin + i before the rotate is equal
to the value at the location begin + (i + number)(modulo (end -
begin)).

NOTE:

Rotate is implemented in the usual way with tree calls to reverse.  It
is possible to speed it up. Rotate_copy is at present almost three
times faster than rotate.

SEE ALSO:

rotate_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

void reverse(TYPE *begin, 
	     TYPE *end);

COMPLEXITY: 

Linear in the size of the block.  If N is the number of locations in
the block approximately 3N assignments of TYPE are performed.


IMPLEMENTATION:

void rotate(ptrdiff_t number, 
	    TYPE *begin, 
	    TYPE *end)
{
  if (begin >= end)
    return;

  number %= end - begin;

  if (number == 0)
    return;

  if (number < 0)
    number += (end - begin);

  reverse(begin, end);
  reverse(begin, begin + number);
  reverse(begin + number, end);
}


NAME:

rotate_copy - copies a block while circularly rotating it.

SYNOPSIS:

void rotate_copy(ptrdiff_t number, 
		 TYPE *begin, 
		 TYPE *end, 
		 TYPE *result);

DESCRIPTION:

If number is non-negative then rotate_copy copies a block circularly
rotating it to the right.  If number is negative then rotate_copy
copies a block circularly rotating it to the left.  In both cases, for
every i, 0 <= i < (end - begin), the value at the location begin + i
before the rotate is equal to the value at the location result + (i +
number)(modulo (end - begin)).

NOTE:

If begin <= result < end or begin <= result + (end - begin) < end then
the effect of rotate_copy is not defined.

SEE ALSO:

rotate

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

void copy(TYPE *begin, 
          TYPE *end, 
	  TYPE *result);

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N assignments of TYPE are performed.


IMPLEMENTATION:

void rotate_copy(ptrdiff_t number, 
		 TYPE *begin, 
		 TYPE *end, 
		 TYPE *result)
{
  if (begin >= end)
    return;

  number %= end - begin;

  if (number == 0)
    {
      copy(begin, end, result);
      return;
    }

  if (number < 0)
    number += (end - begin);

  copy(end - number, end, result);
  copy(begin, end - number, result + number);
}


NAME:

search - finds a matching subblock in a block

SYNOPSIS:

TYPE *search(TYPE *begin1, 
	     TYPE *end1, 
	     TYPE *begin2, 
	     TYPE *end2);

DESCRIPTION:

search returns a location in the first block such that such that a
subblock of it which starts with this location and is equal in size to
the second block such that every element in this subblock is equal to
the corresponding element of the second block. If such location does
not exist then the 0 pointer is returned.

NOTE:

At present search is quadratic in the worst case.  In the future it
may be replaced with a faster one.  However, it is quite fast on the
average in most practical cases.

SEE ALSO:

mismatch, other search

ASSUMPTIONS:

Equality ("==") is defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Quadratic in the size of the blocks.  If N and M are correspondingly
the numbers of locations in the first and second blocks then at most
N*M equality operations of TYPE are performed. (But see the note.)


IMPLEMENTATION:

TYPE *search(register TYPE *begin1, 
	     TYPE *end1, 
	     register TYPE *begin2, 
	     TYPE *end2)
{
  register ptrdiff_t d1, d2, k;

  if (begin1 >= end1)
    return begin2;

  d1 = end1 - begin1;
  d2 = end2 - begin2;

  if (d2 < d1)
    return 0;

  k = 0;

  while (k < d1)
    if (begin1[k] == begin2[k])
      k++;
    else if (d1 == d2)
      return 0;
    else
      {
	k = 0;
	begin2++;
	d2--;
      }

  return begin2;
}


NAME:

search - finds a matching subblock in a block

SYNOPSIS:

TYPE *search(int (*relation)(TYPE*, TYPE*), 
	     TYPE *begin1, 
	     TYPE *end1, 
	     TYPE *begin2, 
	     TYPE *end2);

DESCRIPTION:

search returns a location in the first block such that such that a
subblock of it which starts with this location and is equal in size to
the second block such that every element in this subblock is equal to
the corresponding element of the second block. If such location does
not exist then the 0 pointer is returned.

NOTE:

At present search is quadratic in the worst case.  In the future it
may be replaced with a faster one.  However, it is quite fast on the
average in most practical cases.

SEE ALSO:

mismatch, other search

ASSUMPTIONS:

none

DEPENDS ON:

nothing

COMPLEXITY:

Quadratic in the size of the blocks.  If N and M are correspondingly
the numbers of locations in the first and second blocks then at most
N*M calls to the relation are performed. (But see the note.)


IMPLEMENTATION:

TYPE *search(register int (*relation)(TYPE*, TYPE*), 
	     register TYPE *begin1, 
	     TYPE *end1, 
	     register TYPE *begin2, 
	     TYPE *end2)
{
  register ptrdiff_t d1, d2, k;

  if (begin1 >= end1)
    return begin2;

  d1 = end1 - begin1;
  d2 = end2 - begin2;

  if (d2 < d1)
    return 0;

  k = 0;

  while (k < d1)
    if ((*relation)(begin1 + k, begin2 + k))
      k++;
    else if (d1 == d2)
      return 0;
    else
      {
	k = 0;
	begin2++;
	d2--;
      }

  return begin2;
}


NAME:

select - finds the nth smallest element in the block

SYNOPSIS:

void select(ptrdiff_t nth, 
	    TYPE *begin, 
	    TYPE *end);

DESCRIPTION:

select puts the nth smallest element in the block in the location
begin + nth - 1. It also moves first n - 1 smallest elements to the
left of this location and the rest of the elements to the right.

NOTE:

if 0 <= nth <end - begin then nothing is done.

SEE ALSO:

minimum

ASSUMPTIONS:

Less_than ("<") and assignment ("=") are defined for the TYPE

DEPENDS ON:

void insertion_sort(TYPE *begin, 
                    TYPE *end);

TYPE *minimum(TYPE *begin, 
	      TYPE *end);

COMPLEXITY:

Linear on the average.  Quadratic in the worst case. (Which is highly
improbable.)


IMPLEMENTATION:

static TYPE *ordered_partition(register TYPE *begin, 
			       register TYPE *end);

/* see sort for the implementation of ordered_partition */

void select(ptrdiff_t nth, 
	    TYPE *begin, 
	    TYPE *end)
{
  if (begin >= end || nth <= 0 || end - begin < nth)
    return;

  for (;;)
    if (end - begin < 6)
      {
	insertion_sort(begin, end);
	return;
      }
    else if (nth < 4)
      {
	while (nth--)
	  {
	    register TYPE *r = minimum(begin, end);
	    REGISTER TYPE temp = *begin;
	    *begin = *r;
	    *r = temp;
	  }    
	return;
      }
    else
      {
	TYPE *index = ordered_partition(begin, end);

	if (index - begin >= nth)
	  end = index;
	else
	  {
	    nth -= index - begin;
	    begin = index;
	  }
      }
}


NAME:

select - finds the nth smallest element in the block

SYNOPSIS:

void select(int (*relation)(TYPE*, TYPE*), 
	    ptrdiff_t nth, 
	    TYPE *begin, 
	    TYPE *end);

DESCRIPTION:

select puts the nth smallest element in the block in the location
begin + nth - 1. It also moves first n - 1 smallest elements to the
left of this location and the rest of the elements to the right.
relation is the name of the comparison function, which is called with
two arguments that point to the elements being compared.  As the
function must return an integer less than, equal to, or greater than
zero, so must the first argument to be considered be less than, equal
to, or greater than the second.

NOTE:

if 0 <= nth <end - begin then nothing is done.

SEE ALSO:

minimum

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE

DEPENDS ON:

void insertion_sort(int (*relation)(TYPE*, TYPE*), 
                    TYPE *begin, 
		    TYPE *end);

TYPE *minimum(int (*relation)(TYPE*, TYPE*), 
	      TYPE *begin, 
	      TYPE *end);

COMPLEXITY:

Linear on the average.  Quadratic in the worst case. (Which is highly
improbable.)


IMPLEMENTATION:

static TYPE *ordered_partition(register int (*relation)(TYPE*, TYPE*), 
			       register TYPE *begin, 
			       register TYPE *end);

/* see sort for the implementation of ordered_partition */
void select(int (*relation)(TYPE*, TYPE*), 
	    ptrdiff_t nth, 
	    TYPE *begin, 
	    TYPE *end)
{
  if (begin >= end || nth <= 0 || end - begin < nth)
    return;

  for (;;)
    if (end - begin < 6)
      {
	insertion_sort(relation, begin, end);
	return;
      }
    else if (nth < 4)
      {
	while (nth--)
	  {
	    register TYPE *r = minimum(relation, begin, end);
	    REGISTER TYPE temp = *begin;
	    *begin++ = *r;
	    *r = temp;
	  }    
	return;
      }
    else
      {
	TYPE *index = ordered_partition(relation, begin, end);

	if (index - begin >= nth)
	  end = index;
	else
	  {
	    nth -= index - begin;
	    begin = index;
	  }
      }
}








NAME:

set_insert - inserts an element in an ordered block if it is not already in it

SYNOPSIS:

TYPE *set_insert(TYPE value, 
		 TYPE *begin, 
		 TYPE *end);

DESCRIPTION:

set_insert inserts a value into an ordered block if the block does not
contain an element equal to the value. If insertion is done then the
location at which insertion was done is returned. Otherwise the 0
pointer is returned.

SEE ALSO:

binary_partition, binary_search, insert, set_union

ASSUMPTIONS:

Less_than ("<") and assignment ("=") are defined for the TYPE

DEPENDS ON:

TYPE *binary_partition(TYPE value, 
		       TYPE *begin, 
		       TYPE *end);

void copy(TYPE *begin, 
          TYPE *end, 
	  TYPE *result);

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block then at most N assignments and at most logN operations
less_than are performed.


IMPLEMENTATION:

TYPE *set_insert(TYPE value, 
		 TYPE *begin, 
		 TYPE *end)
{
  TYPE *index = binary_partition(value, begin, end);

  if (begin < index && !(*(index - 1) < value))
    return 0;

  else
    {
      copy(index, end, index + 1);
      *index = value;
      return index;
    }
}


NAME:

set_insert - inserts an element in an ordered block if it is not already in it

SYNOPSIS:

TYPE *set_insert(int (*relation)(TYPE*, TYPE*), 
		 TYPE value, 
		 TYPE *begin, 
		 TYPE *end);

DESCRIPTION:

set_insert inserts a value into an ordered block if the block does not
contain an element equal to the value. If insertion is done then the
location at which insertion was done is returned. Otherwise the 0
pointer is returned.  relation is the name of the comparison function,
which is called with two arguments that point to the elements being
compared.  As the function must return an integer less than, equal to,
or greater than zero, so must the first argument to be considered be
less than, equal to, or greater than the second.

SEE ALSO:

binary_partition, binary_search, insert, set_union

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE

DEPENDS ON:

TYPE *binary_partition(int (*relation)(TYPE*, TYPE*), 
		       TYPE value, 
		       TYPE *begin, 
		       TYPE *end);

void copy(TYPE *begin, 
          TYPE *end, 
	  TYPE *result);

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block then at most N assignments and at most logN calls to the
relation are performed.


IMPLEMENTATION:

TYPE *set_insert(int (*relation)(TYPE*, TYPE*), 
		 TYPE value, 
		 TYPE *begin, 
		 TYPE *end)
{
  TYPE *index = binary_partition(relation, value, begin, end);

  if (begin < index && !((*relation)(index - 1, &value) < 0))
    return 0;

  else
    {
      copy(index, end, index + 1);
      *index = value;
      return index;
    }
}


NAME:

set_union - combines (with no repetitions) two ordered blocks into one

SYNOPSIS:

TYPE *set_union(int (*relation)(TYPE*, TYPE*), 
		TYPE *begin1, 
		TYPE *end1, 
		TYPE *begin2, 
		TYPE *end2, 
		TYPE *result);

DESCRIPTION:

set_union puts elements from two ordered blocks with no repetitions
into a new ordered block with no repetitions so that for every element
in the original blocks there is an element in the result that is equal
to it. The pointer after the last element of the new block is
returned.  relation is the name of the comparison function, which is
called with two arguments that point to the elements being compared.
As the function must return an integer less than, equal to, or greater
than zero, so must the first argument to be considered be less than,
equal to, or greater than the second.

NOTE:

If begin1 <= result < end1 or begin1 <= result + (end1 - begin1) <
end1 or begin2 <= result < end2 or begin2 <= result + (end2 - begin2)
< end2 then the effect of set_union is not defined.

SEE ALSO:

difference, intersection, merge, symmetric_difference, unique

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the blocks.  If N and M are the numbers of
locations in the blocks then at most N + M - 1 calls to relation and N
+ M assignments are performed.


IMPLEMENTATION:

TYPE *set_union(register int (*relation)(TYPE*, TYPE*), 
		register TYPE *begin1, 
		register TYPE *end1, 
		register TYPE *begin2, 
		register TYPE *end2, 
		register TYPE *result)
{
  while (begin1 < end1 && begin2 < end2)
    {
      register int c = (*relation)(begin2, begin1);

      if (c < 0)
	*result++ = *begin2++;
      else 
	{
	  *result++ = *begin1++;

	  if (c == 0)
	    begin2++;
	}
    }

  while (begin1 < end1)
    *result++ = *begin1++;

  while (begin2 < end2)
    *result++ = *begin2++;

  return result;
}


NAME:

set_union - combines (with no repetitions) two ordered blocks into one

SYNOPSIS:

TYPE *set_union(TYPE *begin1, 
		TYPE *end1, 
		TYPE *begin2, 
		TYPE *end2, 
		TYPE *result);

DESCRIPTION:

set_union puts elements from two ordered blocks with no repetitions
into a new ordered block with no repetitions so that for every element
in the original blocks there is an element in the result that is equal
to it. The pointer after the last element of the new block is
returned.

NOTE:

If begin1 <= result < end1 or begin1 <= result + (end1 - begin1) <
end1 or begin2 <= result < end2 or begin2 <= result + (end2 - begin2)
< end2 then the effect of set_union is not defined.

SEE ALSO:

difference, intersection, merge, symmetric_difference, unique

ASSUMPTIONS:

Less_than ("<") and assignment ("=") are defined for the TYPE

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the blocks.  If N and M are the numbers of
locations in the blocks then at most N + M - 1 less_than operations
and N + M assignments are performed.


IMPLEMENTATION:

TYPE *set_union(register TYPE *begin1, 
		register TYPE *end1, 
		register TYPE *begin2, 
		register TYPE *end2, 
		register TYPE *result)
{
  while (begin1 < end1 && begin2 < end2)
    if (*begin2 < *begin1)
      *result++ = *begin2++;
    else 
      {
	*result++ = *begin1++;
	if (!(*begin1 < *begin2))
	  begin2++;
      }

  while (begin1 < end1)
    *result++ = *begin1++;

  while (begin2 < end2)
    *result++ = *begin2++;

  return result;
}


NAME:

shuffle - shuffles a block

SYNOPSIS:

void shuffle(TYPE *begin, 
	     TYPE *end);

DESCRIPTION:

Shuffle randomly permutes a block in place.

SEE ALSO:

shuffle_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

TYPE *random(TYPE *begin, 
             TYPE *end);

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly 3*(N - 1) assignments of TYPE are performed.


IMPLEMENTATION:

void shuffle(register TYPE *begin, 
	     register TYPE *end)
{
  register TYPE *index = begin + 1;

  while (index < end)
    {
      register TYPE *r = random(begin, index + 1);
      REGISTER TYPE temp = *index;
      *index++ = *r;
      *r = temp;
    }    
}


NAME:

shuffle_copy - copies a block while shuffling it

SYNOPSIS:

void shuffle_copy(TYPE *begin, 
		  TYPE *end, 
		  TYPE *result);

DESCRIPTION:

Shuffle_copy copies a block to a different location while randomly
permuting it.

NOTE:

If begin <= result < end or begin <= result + (end - begin) < end then
the effect of shuffle_copy is not defined.

SEE ALSO:

shuffle

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

TYPE *random(TYPE *begin, 
             TYPE *end);

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly 2*N assignments of TYPE are performed.


IMPLEMENTATION:

void shuffle_copy(register TYPE *begin, 
		  register TYPE *end, 
		  register TYPE *result)
{
  register TYPE *result_end = result; 

  while (begin < end)
    {
      register TYPE *r = random(result, result_end + 1);
      *result_end++ = *r;
      *r = *begin++;
    }
}


NAME:

sort - sorts the block

SYNOPSIS:

void sort(TYPE *begin, 
	  TYPE *end);

DESCRIPTION:

sort sorts a block in place.

NOTE:

sort is not stable. That is, it does not preserve the relative order
of equal elements.

SEE ALSO:

insertion_sort, merge_sort, stable_sort

ASSUMPTIONS:

Less_than ("<") and assignment ("=") are defined for the TYPE

DEPENDS ON:

void insertion_sort(TYPE *begin, 
                    TYPE *end);

TYPE *random(TYPE *begin, 
             TYPE *end);

COMPLEXITY:

O(NlogN) on the average.  Quadratic in the worst case. (Which is
highly improbable.)


IMPLEMENTATION:

static TYPE *ordered_partition(register TYPE *begin, 
			       register TYPE *end) 
{
  TYPE *old_begin = begin;

  REGISTER TYPE value = *random(begin, end);

  begin--;

  for (;;)
    {
      while (*++begin < value);

      while (value < *--end);

      if (begin < end)
	{
	  REGISTER TYPE temp = *begin;
	  *begin = *end;
	  *end = temp;
	}
      else
	return (begin == old_begin) ? begin + 1 : begin;
    }
}

static void quicksort_loop(register TYPE *begin, 
			   register TYPE *end)
{
  while (10 < end - begin)
    {
      register TYPE *index = ordered_partition(begin, end);

      if (end - index < index - begin)
	{
	  quicksort_loop(index, end);
	  end = index;
	}
      else
	{
	  quicksort_loop(begin, index);
	  begin = index;
	}
    }
}

void sort(TYPE *begin, 
	  TYPE *end)
{
  quicksort_loop(begin, end);
  insertion_sort(begin, end);
}


NAME:

sort - sorts the block

SYNOPSIS:

void sort(int (*relation)(TYPE*, TYPE*), 
	  TYPE *begin, 
	  TYPE *end);

DESCRIPTION:

sort sorts a block in place.  relation is the name of the comparison
function, which is called with two arguments that point to the
elements being compared.  As the function must return an integer less
than, equal to, or greater than zero, so must the first argument to be
considered be less than, equal to, or greater than the second.

NOTE:

sort is not stable. That is, it does not preserve the relative order
of equal elements.

SEE ALSO:

insertion_sort, merge_sort, stable_sort

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE

DEPENDS ON:

void insertion_sort(int (*relation)(TYPE*, TYPE*), 
                    TYPE *begin, 
		    TYPE *end);

TYPE *random(TYPE *begin, 
             TYPE *end);

COMPLEXITY:

O(NlogN) on the average.  Quadratic in the worst case. (Which is
highly improbable.)


IMPLEMENTATION:

static TYPE *ordered_partition(register int (*relation)(TYPE*, TYPE*), 
			       register TYPE *begin, 
			       register TYPE *end)
{
  TYPE *old_begin = begin;

  TYPE value = *random(begin, end);

  register TYPE *temp = &value;

  begin--;

  for (;;)
    {
      while ((*relation)(++begin, temp) < 0);

      while ((*relation)(temp, --end) < 0);

      if (begin < end)
	{
	  REGISTER TYPE temp = *begin;
	  *begin = *end;
	  *end = temp;
	}
      else
	return (begin==old_begin) ? begin + 1 : begin;
    }
}

static void quicksort_loop(int (*relation)(TYPE*, TYPE*), 
			   TYPE *begin, 
			   TYPE *end)
{
  while (10 < end - begin)
    {
      TYPE *index = ordered_partition(relation, begin, end);

      if (end - index < index - begin)
	{
	  quicksort_loop(relation, index, end);
	  end = index;
	}
      else
	{
	  quicksort_loop(relation, begin, index);
	  begin = index;
	}
    }
}

void sort(int (*relation)(TYPE*, TYPE*), 
	  TYPE *begin, 
	  TYPE *end)
{
  quicksort_loop(relation, begin, end);
  insertion_sort(relation, begin, end);
}


NAME:

stable_partition - separates elements into those that satisfy the predicate and
those that do not

SYNOPSIS:

TYPE *stable_partition(int (*predicate)(TYPE*),  
		       TYPE *begin, 
		       TYPE *end); 

DESCRIPTION:

stable_partition moves elements in those locations of the block that
do satisfy the predicate to the left and those that do not satisfy the
predicate to the right and returns the pointer after the last
"satisfying" element.  The relative order of elements within both
groups is preserved.

NOTE:

The divide-and-conquer algorithm used in stable_partitioning can be
refined and in stead of descending all the way down use all available
memory to do those subproblem that can be fitted by using
stable_partition_copy and then copy the block back.

SEE ALSO:

partition, partition_copy, remove, remove_copy, 
other stable_partition, stable_partition_copy, stable_remove, 
stable_remove_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

void rotate(ptrdiff_t number, 
	    TYPE *begin, 
	    TYPE *end);

COMPLEXITY:

O(NlogN) in the size of the block.  If N is the number of locations in
the block exactly N calls to the predicate are done. At most 3*N*logN
assignments of TYPE are performed.


IMPLEMENTATION:


TYPE *stable_partition(int (*predicate)(TYPE*),  
		       TYPE *begin, 
		       TYPE *end) 
{
  if (end - begin > 1)
    {
      TYPE *middle = begin + ((end - begin) >> 1);
      TYPE *first_half = stable_partition(predicate, begin, middle);
      TYPE *second_half = stable_partition(predicate, middle, end);

      rotate(first_half - middle, first_half, second_half);

      return first_half + (second_half - middle);
    }

  else if (begin < end)

    return (*predicate)(begin) ? begin + 1 : begin;

  else

    return end;
}


NAME:

stable_partition - separates elements into those that are equal to the 
value and those that are not

SYNOPSIS:

TYPE *stable_partition(TYPE value,  
		       TYPE *begin, 
		       TYPE *end); 

DESCRIPTION:

stable_partition moves elements in the block that are equal to the
value to the left and those that are not equal to the value to the
right and returns the pointer after the last "equal" element.  The
relative order of elements within both groups is preserved.

NOTE:

The divide-and-conquer algorithm used in stable_partitioning can be
refined and in stead of descending all the way down use all available
memory to do those subproblem that can be fitted by using
stable_partition_copy and then copy the block back.

SEE ALSO:

partition, partition_copy, remove, remove_copy, 
other stable_partition, stable_partition_copy, stable_remove, 
stable_remove_copy

ASSUMPTIONS:

Assignment ("=") and equality ("==") are defined for the TYPE.

DEPENDS ON:

void rotate(ptrdiff_t number, 
	    TYPE *begin, 
	    TYPE *end);

COMPLEXITY:

O(NlogN) in the size of the block.  If N is the number of locations in
the block exactly N equality operations of TYPE are performed. At most
3*N*logN assignments of TYPE are performed.


IMPLEMENTATION:

TYPE *stable_partition(TYPE value,  
		       TYPE *begin, 
		       TYPE *end) 
{
  if (end - begin > 1)
    {
      TYPE *middle = begin + ((end - begin) >> 1);
      TYPE *first_half = stable_partition(value, begin, middle);
      TYPE *second_half = stable_partition(value, middle, end);

      rotate(first_half - middle, first_half, second_half);

      return first_half + (second_half - middle);
    }

  else if (begin < end)

    return *begin == value ? begin + 1 : begin;

  else

    return end;
}


NAME:

stable_partition - separates elements into those that relate to the value and
those that are not

SYNOPSIS:

TYPE *stable_partition(int (*relation)(TYPE*, TYPE*), 
		       TYPE value,  
		       TYPE *begin, 
		       TYPE *end); 

DESCRIPTION:

stable_partition moves elements in those locations of the block that
do satisfy the relation with the value to the left and those that do
not satisfy the relation to the right and returns the pointer after
the last "satisfying" element.  The relative order of elements within
both groups is preserved.

NOTE:

The divide-and-conquer algorithm used in stable_partitioning can be
refined and in stead of descending all the way down use all available
memory to do those subproblem that can be fitted by using
stable_partition_copy and then copy the block back.

SEE ALSO:

partition, partition_copy, remove, remove_copy, 
other stable_partition, stable_partition_copy, stable_remove, 
stable_remove_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

void rotate(ptrdiff_t number, 
	    TYPE *begin, 
	    TYPE *end);

COMPLEXITY:

O(NlogN) in the size of the block.  If N is the number of locations in
the block exactly N calls to the relation are done. At most 3*N*logN
assignments of TYPE are performed.


IMPLEMENTATION:

TYPE *stable_partition(int (*relation)(TYPE*, TYPE*), 
		       TYPE value,  
		       TYPE *begin, 
		       TYPE *end) 
{
  if (end - begin > 1)
    {
      TYPE *middle = begin + ((end - begin) >> 1);
      TYPE *first_half = stable_partition(relation, value, begin, middle);
      TYPE *second_half = stable_partition(relation, value, middle, end);

      rotate(first_half - middle, first_half, second_half);

      return first_half + (second_half - middle);
    }

  else if (begin < end)

    return (*relation)(begin, &value) ? begin + 1 : begin;

  else

    return end;
}


NAME:

stable_partition_copy - copies elements satisfying the predicate 
before the elements that do not

SYNOPSIS:

TYPE *stable_partition_copy(int (*predicate)(TYPE*), 
			    TYPE *begin, 
			    TYPE *end, 
			    TYPE *result);

DESCRIPTION:

stable_partition_copy first copies elements in those locations of the
block that do satisfy the predicate and then those that do not satisfy
the predicate and returns the pointer after the copy of the last
"satisfying" element. The relative order of elements in both groups
("satisfying" and "not-satisfying") is preserved.

NOTE:

If begin <= result < end or begin <= result + (end - begin) < end then
the effect of stable_partition_copy is not defined.

SEE ALSO:

partition, partition_copy, remove, remove_copy, 
stable_partition, other stable_partition_copy, stable_remove, 
stable_remove_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

TYPE *partition_copy(
   int (*predicate)(TYPE*), 
   TYPE *begin, 
   TYPE *end, 
   TYPE *result
   );

void reverse(
   TYPE *begin, 
   TYPE *end
   );

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N calls to predicate are done. If P is the number of
locations in the block that do not satisfy the predicate then exactly
N + 3*floor(P/2) assignments of TYPE are done.


IMPLEMENTATION:

TYPE *stable_partition_copy(int (*predicate)(TYPE*), 
			    TYPE *begin, 
			    TYPE *end, 
			    TYPE *result)
{

  TYPE *m = partition_copy(predicate, begin, end, result);
  reverse(m, result + (end - begin));
  return m;
}


NAME:

stable_partition_copy - copies elements equal to the value before those 
that are not

SYNOPSIS:

TYPE *stable_partition_copy(TYPE value, 
			    TYPE *begin, 
			    TYPE *end, 
			    TYPE *result);

DESCRIPTION:

stable_partition_copy first copies elements in the block that are
equal to the value and then those that are not and returns the pointer
after the copy of the last "equal" element.  The relative order of
elements in both groups ("equal" and "not-equal") is preserved.

NOTE:

If begin <= result < end or begin <= result + (end - begin) < end then
the effect of stable_partition_copy is not defined.

SEE ALSO:

partition, partition_copy, remove, remove_copy, 
stable_partition, other stable_partition_copy, stable_remove, 
stable_remove_copy

ASSUMPTIONS:

Assignment ("=") and equality ("==") are defined for the TYPE.

DEPENDS ON:

TYPE *partition_copy(
   TYPE value,
   TYPE *begin, 
   TYPE *end, 
   TYPE *result
   );

void reverse(
   TYPE *begin, 
   TYPE *end
   );

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N equality operations of TYPE are performed.  If P
is the number of locations in the block that are not equal to the
value then exactly N + 3*floor(P/2) assignments of TYPE are done.


IMPLEMENTATION:

TYPE *stable_partition_copy(TYPE value, 
			    TYPE *begin, 
			    TYPE *end, 
			    TYPE *result)
{
  TYPE *m = partition_copy(value, begin, end, result);
  reverse(m, result + (end - begin));
  return m;
}


NAME:

stable_partition_copy - copies elements related to the value before 
those that are not

SYNOPSIS:

TYPE *stable_partition_copy(int (*relation)(TYPE*, TYPE*), 
			    TYPE value, 
			    TYPE *begin, 
			    TYPE *end, 
			    TYPE *result);

DESCRIPTION:

stable_partition_copy first copies those elements in the block
locations of which satisfy the relation with the pointer to the value
and then those that do not and returns the pointer after the copy of
the last "satisfying" element. The relative order of elements in both
groups ("satisfying" and "not-satisfying") is preserved.

NOTE:

If begin <= result < end or begin <= result + (end - begin) < end then
the effect of stable_partition_copy is not defined.

SEE ALSO:

partition, partition_copy, remove, remove_copy, 
stable_partition, other stable_partition_copy, stable_remove, 
stable_remove_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

TYPE *partition_copy(int (*relation)(TYPE*, TYPE*), 
		     TYPE value, 
		     TYPE *begin, 
		     TYPE *end, 
		     TYPE *result);

void reverse(
   TYPE *begin, 
   TYPE *end
   );

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N calls to the relation are done. If P is the number
of locations in the block that do not satisfy the relation then
exactly N + 3*floor(P/2) assignments of TYPE are done.


IMPLEMENTATION:

TYPE *stable_partition_copy(int (*relation)(TYPE*, TYPE*), 
			    TYPE value, 
			    TYPE *begin, 
			    TYPE *end, 
			    TYPE *result)
{
  TYPE *m = partition_copy(relation, value, begin, end, result);
  reverse(m, result + (end - begin));
  return m;
}


NAME:

stable_remove - removes elements satisfying the predicate

SYNOPSIS:

TYPE *stable_remove(int (*predicate)(TYPE*), 
		    TYPE *begin, 
		    TYPE *end);

DESCRIPTION:

stable_remove moves all the elements in the block, locations of which
do not satisfy the predicate, to the left and returns the pointer
pointing after the last such element. The relative order of the
elements not satisfying the predicate is preserved.

SEE ALSO:

partition, partition_copy, remove, remove_copy, 
stable_partition, stable_partition_copy, other stable_remove, 
stable_remove_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N calls to predicate are done. If P is the number of
locations in the block that do not satisfy predicate then at most P
assignments of TYPE are done.


IMPLEMENTATION:

TYPE *stable_remove(register int (*predicate)(TYPE*), 
		    register TYPE *begin, 
		    register TYPE *end)
{
  register TYPE *m;

  while (begin < end && !(*predicate)(begin))
    begin++;

  if (begin >= end)
    return end;

  m = begin;

  while (++begin < end)
    if (!(*predicate)(begin))
      *m++ = *begin;

  return m;
}
  

NAME:

stable_remove - removes elements equal to the value

SYNOPSIS:

TYPE *stable_remove(TYPE value, 
		    TYPE *begin, 
		    TYPE *end);

DESCRIPTION:

stable_remove moves all the elements in the block which are not equal
to value to the left and returns the pointer pointing after the last
such element. The relative order of the elements not satisfying the
predicate is preserved.

SEE ALSO:

partition, partition_copy, remove, remove_copy, 
stable_partition, stable_partition_copy, other stable_remove, 
stable_remove_copy

ASSUMPTIONS:

Assignment ("=") and equality ("==") are defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N equality operations of the TYPE are performed. If
P is the number of locations in the block that are not equal to the
value then at most P assignments of TYPE are done.


IMPLEMENTATION:

TYPE *stable_remove(REGISTER TYPE value, 
		    register TYPE *begin, 
		    register TYPE *end)
{
  register TYPE *m;

  while (begin < end && !(*begin == value))
    begin++;

  if (begin >= end)
    return end;

  m = begin;

  while (++begin < end)
    if (!(*begin == value))
      *m++ = *begin;

  return m;
}


NAME:

stable_remove - removes elements satisfying the relation with the value

SYNOPSIS:

TYPE *stable_remove(int (*relation)(TYPE*, TYPE*), 
		    TYPE value, 
		    TYPE *begin, 
		    TYPE *end);

DESCRIPTION:

stable_remove moves all the elements in the block, locations of which
do not satisfy the relation with the pointer to the value, to the left
and returns the pointer pointing after the last such element. The
relative order of the elements not satisfying the predicate is
preserved.

SEE ALSO:

partition, partition_copy, other remove, remove_copy, 
stable_partition, stable_partition_copy, stable_remove, 
stable_remove_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N calls to the relation are done. If P is the number
of locations in the block that do not satisfy the relation with the
value then at most P assignments of TYPE are done.


IMPLEMENTATION:

TYPE *stable_remove(register int (*relation)(TYPE*, TYPE*), 
		    TYPE value, 
		    register TYPE *begin, 
		    register TYPE *end)
{
  register TYPE *temp = &value;
  register TYPE *m;

  while (begin < end && !(*relation)(begin, temp))
    begin++;

  if (begin >= end)
    return end;

  m = begin;

  while (++begin < end)
    if (!(*relation)(begin, temp))
      *m++ = *begin;

  return m;
}


NAME:

stable_remove_copy - copies the elements not satisfying the predicate

SYNOPSIS:

TYPE *stable_remove_copy(int (*predicate)(TYPE*), 
			 TYPE *begin, 
			 TYPE *end,  
			 TYPE *result);

DESCRIPTION:

stable_remove_copy copies elements in those locations in the block
that do not satisfy the predicate in the consecutive locations
starting with result, and returns the pointer past the last of the
copies.

NOTE:

1) Is the same as remove_copy.

2) If begin <= result < end or begin <= result + (end - begin) < end
then the effect of stable_remove_copy is not defined.

SEE ALSO:

partition, partition_copy, remove, remove_copy, 
stable_partition, stable_partition_copy, stable_remove, 
other stable_remove_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:
ATYPE *remove_copy(int (*predicate)(TYPE*), 
		  TYPE *begin, 
		  TYPE *end, 
		  TYPE *result);

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N calls to predicate are done. If P is the number of
locations in the block that do not satisfy predicate then exactly P
assignments of TYPE are done.


IMPLEMENTATION:

TYPE *stable_remove_copy(int (*predicate)(TYPE*), 
			 TYPE *begin, 
			 TYPE *end,  
			 TYPE *result)
{
  return remove_copy(predicate, begin, end, result);
}


NAME:

stable_remove_copy - copies the elments not equal to the value

SYNOPSIS:

TYPE *stable_remove_copy(TYPE value, 
			 TYPE *begin, 
			 TYPE *end, 
			 TYPE *result);

DESCRIPTION:

stable_remove_copy copies those elements in the block, that are not
equal to the value, in the consecutive locations starting with result,
and returns the pointer past the last of the copies.

NOTE:

1) Is the same as remove_copy.

2) If begin <= result < end or begin <= result + (end - begin) < end
then the effect of stable_remove_copy is not defined.

SEE ALSO:

partition, partition_copy, remove, remove_copy, 
stable_partition, stable_partition_copy, stable_remove, 
other stable_remove_copy

ASSUMPTIONS:

Assignment ("=") and equality ("==") are defined for the TYPE.

DEPENDS ON:

TYPE *remove_copy(TYPE value, 
		  TYPE *begin, 
		  TYPE *end, 
		  TYPE *result);

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N equality operations of the TYPE are performed. If
P is the number of locations in the block that are not equal to the
value then exactly P assignments of TYPE are done.


IMPLEMENTATION:

TYPE *stable_remove_copy(TYPE value, 
			 TYPE *begin, 
			 TYPE *end, 
			 TYPE *result)
{
  return remove_copy(value, begin, end, result);
}


NAME:

stable_remove_copy - copies elements that are not related to the value

SYNOPSIS:

TYPE *stable_remove_copy(int (*relation)(TYPE*, TYPE*), 
			 TYPE value, 
			 TYPE *begin, 
			 TYPE *end, 
			 TYPE *result);

DESCRIPTION:

stable_remove_copy copies those elements in the locations in the
block, that do not satisfy the relation with the pointer to the value,
in the consecutive locations starting with result, and returns the
pointer past the last of the copies.

NOTE:

1) Is the same as remove_copy.

2) If begin <= result < end or begin <= result + (end - begin) < end
then the effect of stable_remove_copy is not defined.

SEE ALSO:

partition, partition_copy, remove, remove_copy, 
stable_partition, stable_partition_copy, stable_remove, 
other stable_remove_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

TYPE *remove_copy(int (*relation)(TYPE*, TYPE*), 
		  TYPE value, 
		  TYPE *begin, 
		  TYPE *end, 
		  TYPE *result);

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block exactly N calls to the relation are done. If P is the number
of locations in the block that do not satisfy the relation with the
value then exactly P assignments of TYPE are done.


IMPLEMENTATION:

TYPE *stable_remove_copy(int (*relation)(TYPE*, TYPE*), 
			 TYPE value, 
			 TYPE *begin, 
			 TYPE *end, 
			 TYPE *result)
{
  return remove_copy(relation, value, begin, end, result);
}


NAME:

stable_sort - stably sorts a block

SYNOPSIS:

void stable_sort(int (*relation)(TYPE*, TYPE*), 
		 TYPE *begin, 
		 TYPE *end);

DESCRIPTION:

stable_sort sorts a block in place. It is stable, that is, the
relative order of equal elements is preserved.  relation is the name
of the comparison function, which is called with two arguments that
point to the elements being compared.  As the function must return an
integer less than, equal to, or greater than zero, so must the first
argument to be considered be less than, equal to, or greater than the
second.

NOTE:

At present stable_sort becomes quadratic if it cannot allocate an
auxiliary block. This will be fixed in the future.

SEE ALSO:

insertion_sort, merge_sort, sort

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE

DEPENDS ON:

void insertion_sort(int (*relation)(TYPE*, TYPE*), 
                    TYPE *begin, 
		    TYPE *end);

char *malloc(unsigned);

TYPE *merge_sort(int (*relation)(TYPE*, TYPE*), 
                 TYPE *begin, 
                 TYPE *end, 
		 TYPE *result);

COMPLEXITY:

O(NlogN) if it can obtain an extra memory, O(N^2) otherwise.


IMPLEMENTATION:

#include <malloc.h>

void stable_sort(int (*relation)(TYPE*, TYPE*), 
		 TYPE *begin, 
		 TYPE *end)
{
  TYPE *index = (TYPE*) malloc((unsigned)(sizeof(TYPE) * (end - begin)));

  if (index == 0)
    {
      insertion_sort(relation, begin, end);
      return;
    }

  if (merge_sort(relation, begin, end, index) == index)
    {
      TYPE *i = index;

      while (begin < end)
	*begin++ = *i++;
    }

  free((char*)index);

}


NAME:

stable_sort - stably sorts a block

SYNOPSIS:

void stable_sort(TYPE *begin, 
		 TYPE *end);

DESCRIPTION:

stable_sort sorts a block in place. It is stable, that is, the
relative order of equal elements is preserved.

NOTE:

At present stable_sort becomes quadratic if it cannot allocate an
auxiliary block. That will be fixed in the future.

SEE ALSO:

insertion_sort, merge_sort, sort

ASSUMPTIONS:

Less_than ("<") and assignment ("=") are defined for the TYPE

DEPENDS ON:

void insertion_sort(TYPE *begin, 
                    TYPE *end);

char *malloc(unsigned);

TYPE *merge_sort(TYPE *begin, 
                 TYPE *end, 
		 TYPE *result);

COMPLEXITY:

O(NlogN) if it can obtain an extra memory, O(N^2) otherwise.


IMPLEMENTATION:

#include <malloc.h>

void stable_sort(TYPE *begin, 
		 TYPE *end)
{
  TYPE *index = (TYPE*) malloc((unsigned)(sizeof(TYPE) * (end - begin)));

  if (index == 0)
    {
      insertion_sort(begin, end);
      return;
    }

  if (merge_sort(begin, end, index) == index)
    {
      TYPE *i = index;

      while (begin < end)
	*begin++ = *i++;
    }

  free((char*)index);
}


NAME:

substitute - substitutes value with new_value

SYNOPSIS:

void substitute(TYPE value, 
		TYPE new_value, 
		TYPE *begin, 
		TYPE *end);

DESCRIPTION:

substitute assigns new_value to every location in the block the
content of which is equal to value.

SEE ALSO:

other substitute, substitute_copy

ASSUMPTIONS:

Assignment ("=") and equality ("==") are defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block then exactly N equality operations of TYPE and at most N
assignments of TYPE are performed.


IMPLEMENTATION:

void substitute(REGISTER TYPE value, 
		REGISTER TYPE new_value, 
		register TYPE *begin, 
		register TYPE *end)
{
  for (; begin < end; begin++)
    if (*begin == value)
      *begin = new_value;
}


NAME:

substitute - substitutes value with new_value

SYNOPSIS:

void substitute(int (*relation)(TYPE*, TYPE*), 
		TYPE value, 
		TYPE new_value, 
		TYPE *begin, 
		TYPE *end);

DESCRIPTION:

substitute assigns new_value to every location in the block which
satisfies the relation with the location containing the value.

SEE ALSO:

other substitute, substitute_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block then exactly N calls to the relation and at most N
assignments of TYPE are performed.


IMPLEMENTATION:

void substitute(register int (*relation)(TYPE*, TYPE*), 
		TYPE value, 
		REGISTER TYPE new_value, 
		register TYPE *begin, 
		register TYPE *end)
{
  register TYPE *temp = &value;

  for (; begin < end; begin++)
    if ((*relation)(begin, temp))
      *begin = new_value;
}


NAME:

substitute_copy - copies while substituting

SYNOPSIS:

void substitute_copy(TYPE value, 
		     TYPE new_value, 
		     TYPE *begin, 
		     TYPE *end, 
		     TYPE *result);

DESCRIPTION:

substitute_copy copies the block while replacing every item equal to
value with new_value.

NOTE:

If begin <= result < end or begin <= result + (end - begin) < end then
the effect of substitute_copy is not defined.

SEE ALSO:

substitute, other substitute_copy

ASSUMPTIONS:

Assignment ("=") and equality ("==") are defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block then exactly N equality operations of TYPE and exactly N
assignments of TYPE are performed.


IMPLEMENTATION:

void substitute_copy(REGISTER TYPE value, 
		     REGISTER TYPE new_value, 
		     register TYPE *begin, 
		     register TYPE *end, 
		     register TYPE *result)
{
  for (; begin < end; begin++)
    *result++ = (*begin == value ? new_value : *begin);
}


NAME:

substitute_copy - copies while substituting

SYNOPSIS:

void substitute_copy(int (*relation)(TYPE*, TYPE*), 
		     TYPE value, 
		     TYPE new_value, 
		     TYPE *begin, 
		     TYPE *end, 
		     TYPE *result);

DESCRIPTION:

substitute_copy copies the block while replacing every item satisfying
the relation with value with new_value.

NOTE:

If begin <= result < end or begin <= result + (end - begin) < end then
the effect of substitute_copy is not defined.

SEE ALSO:

substitute, other substitute_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block then exactly N calls to the relation and exactly N
assignments of TYPE are performed.


IMPLEMENTATION:

void substitute_copy(register int (*relation)(TYPE*, TYPE*), 
		     TYPE value, 
		     REGISTER TYPE new_value, 
		     register TYPE *begin, 
		     register TYPE *end, 
		     register TYPE *result)
{
  register TYPE *temp = &value;

  for (; begin < end; begin++)
    *result++ = ((*relation)(begin, temp) ? new_value : *begin);
}


NAME:

symmetric_difference - collects those elements of two ordered blocks 
that are only in one of them

SYNOPSIS:

TYPE *symmetric_difference(int (*relation)(TYPE*, TYPE*), 
			   TYPE *begin1, 
			   TYPE *end1, 
			   TYPE *begin2, 
			   TYPE *end2, 
			   TYPE *result);

DESCRIPTION:

symmetric_difference puts elements from two ordered blocks with no
repetitions into a new ordered block with no repetitions so that for
every element which is in only in one of the original blocks it will
be placed in the result The pointer after the last element of the new
block is returned.  relation is the name of the comparison function,
which is called with two arguments that point to the elements being
compared.  As the function must return an integer less than, equal to,
or greater than zero, so must the first argument to be considered be
less than, equal to, or greater than the second.

NOTE:

If begin1 <= result < end1 or begin1 <= result + (end1 - begin1) <
end1 or begin2 <= result < end2 or begin2 <= result + (end2 - begin2)
< end2 then the effect of symmetric_difference is not defined.

SEE ALSO:

difference, intersection, merge, set_union, unique

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the blocks.  If N and M are the numbers of
locations in the blocks then at most N + M - 1 calls to relation and N
+ M assignments are performed.


IMPLEMENTATION:

TYPE *symmetric_difference(register int (*relation)(TYPE*, TYPE*), 
			   register TYPE *begin1, 
			   register TYPE *end1, 
			   register TYPE *begin2, 
			   register TYPE *end2, 
			   register TYPE *result)
{
  while (begin1 < end1 && begin2 < end2)
    {
      register int c = (*relation)(begin2, begin1);

      if (0 < c)
	*result++ = *begin1++;
      else if (c < 0)
	*result++ = *begin2++;
      else 
	begin1++, begin2++;
    }

  while (begin1 < end1)
    *result++ = *begin1++;

  while (begin2 < end2)
    *result++ = *begin2++;

  return result;
}


NAME:

symmetric_difference - collects those elements of two ordered blocks 
that are only in one of them

SYNOPSIS:

TYPE *symmetric_difference(TYPE *begin1, 
			   TYPE *end1, 
			   TYPE *begin2, 
			   TYPE *end2, 
			   TYPE *result);

DESCRIPTION:

symmetric_difference puts elements from two ordered blocks with no
repetitions into a new ordered block with no repetitions so that for
every element which is in only in one of the original blocks it will
be placed in the result The pointer after the last element of the new
block is returned.

NOTE:

If begin1 <= result < end1 or begin1 <= result + (end1 - begin1) <
end1 or begin2 <= result < end2 or begin2 <= result + (end2 - begin2)
< end2 then the effect of symmetric_difference is not defined.

SEE ALSO:

difference, intersection, merge, set_union, unique

ASSUMPTIONS:

Less_than ("<") and assignment ("=") are defined for the TYPE

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the blocks.  If N and M are the numbers of
locations in the blocks then at most N + M - 1 less_than operations
and maximum(N, M) assignments are performed.


IMPLEMENTATION:

TYPE *symmetric_difference(register TYPE *begin1, 
			   register TYPE *end1, 
			   register TYPE *begin2, 
			   register TYPE *end2, 
			   register TYPE *result)
{
  while (begin1 < end1 && begin2 < end2)
    if (*begin1 < *begin2)
      *result++ = *begin1++;
    else if (*begin2 < *begin1)
      *result++ = *begin2++;
    else 
      begin1++ ,begin2++;

  while (begin1 < end1)
    *result++ = *begin1++;

  while (begin2 < end2)
    *result++ = *begin2++;

  return result;
}


NAME:

unique - removes repeated elements

SYNOPSIS:

TYPE *unique(TYPE *begin, 
	     TYPE *end);

DESCRIPTION:

unique removes all but the first element from every consecutive group
of equal elements in the block.

SEE ALSO:

remove_duplicates, remove_duplicates_copy, other unique, unique_copy

ASSUMPTIONS:

Assignment ("=") and equality ("==") are defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block then exactly N - 1 equality operations of TYPE and at most N
- 2 assignments of TYPE are performed.


IMPLEMENTATION:

TYPE *unique(register TYPE *begin, 
	     register TYPE *end)
{
  register TYPE *m;

  if (begin >= end)
    return begin;

  while (++begin < end)
    if (*(begin - 1) == *begin)
      break;

  if (begin == end)
    return begin;

  m = begin - 1;

  while (++begin < end)
    if (!(*m == *begin))
      *++m = *begin;

  return m + 1;
}
      

NAME:

unique - removes repeated elements

SYNOPSIS:

TYPE *unique(int (*relation)(TYPE*, TYPE*), 
	     TYPE *begin, 
	     TYPE *end);

DESCRIPTION:

unique removes all but the first element from every consecutive group
of elements, that DO NOT mutually satisfy the relation.

NOTE:

unique assumes that the relation is non-reflexive (that is, like "!="
and not like "=="). It is done because unique is normally used with
sorted blocks and so the same relation may be used both for sorting
and removing repeated elements.

SEE ALSO:

remove_duplicates, remove_duplicates_copy, other unique, unique_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block then exactly N - 1 calls to the relation and at most N - 2
assignments of TYPE are performed.


IMPLEMENTATION:

TYPE *unique(register int (*relation)(TYPE*, TYPE*), 
	     register TYPE *begin, 
	     register TYPE *end)
{
  register TYPE *m;

  if (begin >= end)
    return begin;

  while (++begin < end)
    if (!(*relation)(begin - 1, begin))
      break;

  if (begin == end)
    return begin;

  m = begin - 1;

  while (++begin < end)
    if ((*relation)(m, begin))
      *++m = *begin;

  return m + 1;
}
      

NAME:

unique_copy - copies a block while removing repeated elements

SYNOPSIS:

TYPE *unique_copy(TYPE *begin, 
		  TYPE *end, 
		  TYPE *result);

DESCRIPTION:

unique_copy copies only the first element out of any consecutive group
of equal elements in the block.

NOTE:

If begin <= result < end or begin <= result + (end - begin) < end then
the effect of unique_copy is not defined.

SEE ALSO:

remove_duplicates, remove_duplicates_copy, unique, other unique_copy

ASSUMPTIONS:

Assignment ("=") and equality ("==") are defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block then exactly N - 1 equality operations of TYPE and at most N
- 2 assignments of TYPE are performed.


IMPLEMENTATION:

TYPE *unique_copy(register TYPE *begin, 
		  register TYPE *end, 
		  register TYPE *result)
{
  if (begin >= end)
    return result;

  *result = *begin; 

  while (++begin < end)
    if (!(*result == *begin))
      *++result = *begin;

  return result + 1;
}
      

NAME:

unique_copy - copies a block while removing repeated elements

SYNOPSIS:

TYPE *unique_copy(int (*relation)(TYPE*, TYPE*), 
		  TYPE *begin, 
		  TYPE *end, 
		  TYPE *result);

DESCRIPTION:

unique_copy copies only the first element out of any consecutive group
of elements, that DO NOT mutually satisfy the relation.

NOTE:

1) unique_copy assumes that the relation is non-reflexive (that is,
like "!=" and not like "=="). It is done because unique_copy is
normally used with sorted blocks and so the same relation may be used
both for sorting and removing repeated elements.

2) If begin <= result < end or begin <= result + (end - begin) < end
then the effect of unique_copy is not defined.

SEE ALSO:

remove_duplicates, remove_duplicates_copy, unique, other unique_copy

ASSUMPTIONS:

Assignment ("=") is defined for the TYPE.

DEPENDS ON:

nothing

COMPLEXITY:

Linear in the size of the block.  If N is the number of locations in
the block then exactly N - 1 calls to the relation and at most N
assignments of TYPE are performed.


IMPLEMENTATION:

TYPE *unique_copy(register int (*relation)(TYPE*, TYPE*), 
		  register TYPE *begin, 
		  register TYPE *end, 
		  register TYPE *result)
{
  if (begin >= end)
    return result;

  *result = *begin; 

  while (++begin < end)
    if ((*relation)(result, begin))
      *++result = *begin;

  return result + 1;
}