.\" ident	@(#)Array_alg:man/part.3	3.2
.\"
.\" C++ Standard Components, Release 3.0.
.\"
.\" Copyright (c) 1991, 1992 AT&T and UNIX System Laboratories, Inc.
.\" Copyright (c) 1988, 1989, 1990 AT&T.  All Rights Reserved.
.\"
.\" THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T and UNIX System
.\" Laboratories, Inc.  The copyright notice above does not evidence
.\" any actual or intended publication of such source code.
.\" 
.TH \f3part\fP \f3Array_alg(3C++)\fP " "
.SH NAME
part \- partition an array into two groups of elements
.SH SYNOPSIS OF Array_alg.h
.Bf

    template <class \*(gt>
    \*(gt* part(const \*(gt& val,\*(gt* b,\*(gt* e);
    template <class \*(gt>
    \*(gt* part_c(const \*(gt& val,\*(gt* b1,\*(gt* e1,\*(gt* b2);
    template <class \*(gt>
    \*(gt* part_p(int (*pred)(const \*(gt*),\*(gt* b,\*(gt* e);
    template <class \*(gt>
    \*(gt* part_pc(int (*pred)(const \*(gt*),\*(gt* b1,\*(gt* e1,\*(gt* b2);
    template <class \*(gt>
    \*(gt* part_ps(int (*pred)(const \*(gt*),\*(gt* b,\*(gt* e);
    template <class \*(gt>
    \*(gt* part_psc(int (*pred)(const \*(gt*),\*(gt* b1,\*(gt* e1,\*(gt* b2);
    template <class \*(gt>
    \*(gt* part_r(int (*pred)(const \*(gt*),const \*(gt& val,\*(gt* b,\*(gt* e);
    template <class \*(gt>
    \*(gt* part_rc(
        int (*rel)(const \*(gt*,const \*(gt*),
	const \*(gt& val,
	\*(gt* b1,
	\*(gt* e1,
	\*(gt* b2
    );
    template <class \*(gt>
    \*(gt* part_rs(int (*rel)(const \*(gt*,const \*(gt*),const \*(gt& val,\*(gt* b,\*(gt* e);
    template <class \*(gt>
    \*(gt* part_rsc(
        int (*rel)(const \*(gt*,const \*(gt*),
	const \*(gt& val,
	\*(gt* b1,
	\*(gt* e1,
	\*(gt* b2
    );
    template <class \*(gt>
    \*(gt* part_s(const \*(gt& val,\*(gt* b,\*(gt* e);
    template <class \*(gt>
    \*(gt* part_sc(const \*(gt& val,\*(gt* b1,\*(gt* e1,\*(gt* b2);
.Be
.SH ASSUMPTIONS
.PP
(1) For non-predicate and non-relational versions,
\*(gt\f4::operator==\f1 defines an equivalence
relation on \*(gt
.br
(2) For relational versions, \f4rel\f1 
defines an equivalence relation on \*(gt
.br
(3) For copy versions, the output array does not overlap 
the input array
.br
(4) For copy versions, the output array has at
least as many cells as the input array
.br
(5) \*(gt has \f4operator=\f1
.SH DESCRIPTION
.PP
These functions partition an array into two groups 
such that the elements in the left group satisfy a 
given criterion and those in the right group do not.
They return a pointer to the cell just beyond the 
last element in the left group.
.sp 0.5v
.IP "\f4template <class \*(gt>\f1"
.IC "\f4\*(gt* part(const \*(gt& val,\*(gt* b,\*(gt* e);\f1"
Uses equality with \f4val\f1
as the partitioning criterion, 
with \f4\*(gt::operator==\f1 used for the equality 
test.  That is,
if \f4p\f1 is a pointer into the array,
then \f4*p\f1 will be in the left group if
\f4*p==val\f1 and in the right group otherwise.
The algorithm is not stable; that is, it does 
not preserve the relative order of 
elements in both groups.  
If stability is required then \f4part_s\f1 
should be used.  
If extra memory is available, it is even better
to use \f4part_sc\f1 and then copy the result array 
back into place.
.IP "\f4template <class \*(gt>\f1"
.IC "\f4\*(gt* part_c(const \*(gt& val,\*(gt* b1,\*(gt* e1,\*(gt* b2);\f1"
Like \f4part\f1 except that the input array is
preserved and the result written to a new array
beginning at location \f4b2\f1.
.IP "\f4template <class \*(gt>\f1"
.IC "\f4\*(gt* part_p(int (*pred)(const \*(gt*),\*(gt* b,\*(gt* e);\f1"
Like \f4part\f1 except that
it uses satisfaction of \f4pred\f1
as the criterion for partitioning.  
That is, if \f4p\f1 is a pointer into the array,
then \f4*p\f1 will be in the left group if
\f4pred(p)\f1 is true and in the right group
if \f4pred(p)\f1 is false.
.IP "\f4template <class \*(gt>\f1"
.IC "\f4\*(gt* part_pc(int (*pred)(const \*(gt*),\*(gt* b1,\*(gt* e1,\*(gt* b2);\f1"
Like \f4part_p\f1 except that the input array is
preserved and the result written to a new array
beginning at location \f4b2\f1.
.IP "\f4template <class \*(gt>\f1"
.IC "\f4\*(gt* part_ps(int (*pred)(const \*(gt*),\*(gt* b,\*(gt* e);\f1"
Like \f4part_p\f1 except that it uses a
stable algorithm.  That is, the relative order 
of elements within both groups is preserved.
.IP "\f4template <class \*(gt>\f1"
.IC "\f4\*(gt* part_psc(int (*pred)(const \*(gt*),\*(gt* b1,\*(gt* e1,\*(gt* b2);\f1"
Like \f4part_ps\f1 except that the input array is
preserved and the result written to a new array
beginning at location \f4b2\f1.
.IP "\f4template <class \*(gt>\f1"
.IC "\f4\*(gt* part_r(int (*rel)(const \*(gt*,const \*(gt*),const \*(gt& val,\*(gt* b,\*(gt* e);\f1"
Like \f4part\f1 except that it 
uses \f4rel\f1 to test for equality.
That is, if \f4p\f1 is a pointer into the array,
then \f4*p\f1 will be in the left group if
\f4rel(p,&val)==0\f1 and in the right group
otherwise.
.IP "\f4template <class \*(gt>\f1"
.IC "\f4\*(gt* part_rc(\f1"
.IC "\f4    int (*rel)(const \*(gt*,const \*(gt*),\f1" 
.IC "\f4    const \*(gt& val,\f1" 
.IC "\f4    \*(gt* b1,\f1" 
.IC "\f4    \*(gt* e1,\f1"
.IC "\f4    \*(gt* b2\f1"
.IC "\f4);\f1"
Like \f4part_r\f1 except that the input array is
preserved and the result written to a new array
beginning at location \f4b2\f1.
.IP "\f4template <class \*(gt>\f1"
.IC "\f4\*(gt* part_rs(int (*rel)(const \*(gt*,const \*(gt*),const \*(gt& val,\*(gt* b,\*(gt* e);\f1"
Like \f4part_r\f1 except that it uses a
stable algorithm.  That is, the relative order 
of elements within both groups is preserved.
.IP "\f4template <class \*(gt>\f1"
.IC "\f4\*(gt* part_rsc(\f1"
.IC "\f4    int (*rel)(const \*(gt*,const \*(gt*),\f1" 
.IC "\f4    const \*(gt& val,\f1" 
.IC "\f4    \*(gt* b1,\f1" 
.IC "\f4    \*(gt* e1,\f1" 
.IC "\f4    \*(gt* b2\f1"
.IC "\f4);\f1"
Like \f4part_rs\f1 except that the input array is
preserved and the result written to a new array
beginning at location \f4b2\f1.
.IP "\f4template <class \*(gt>\f1"
.IC "\f4\*(gt* part_s(const \*(gt& val,\*(gt* b,\*(gt* e);\f1"
Like \f4part\f1 except that it uses a
stable algorithm.  That is, the relative order 
of elements within both groups is preserved.
.IP "\f4\*(gt* part_sc(const \*(gt& val,\*(gt* b1,\*(gt* e1,\*(gt* b2);\f1"
Like \f4part_s\f1 except that the input array is
preserved and the result written to a new array
beginning at location \f4b2\f1.
.SH COMPLEXITY
.IP "\f4part\f1, \f4part_p\f1, \f4part_r\f1"
If \f2N\f1 is the size of the array, 
then the complexity is \f2O(N)\f1.  
Exactly \f2N\f1 tests of the criterion are made. 
If \f2P\f1 is the number of elements in the array 
that satisfy the criterion, then at most 
\f23*min(P, N\-P)\f1 assignments are done.
.IP "\f4part_c\f1, \f4part_pc\f1, \f4part_rc\f1"
If \f2N\f1 is the size of the array, 
then the complexity is \f2O(N)\f1.  
Exactly \f2N\f1 tests of the criterion and 
\f2N\f1 assignments are done.
.IP "\f4part_ps\f1, \f4part_rs\f1, \f4part_s\f1"
If \f2N\f1 is the size of the array, 
then complexity is \f2O(NlgN)\f1.
Exactly \f2N\f1 tests of the criterion
and at most \f23NlgN\f1 assignments are done.
.IP "\f4part_psc\f1, \f4part_rsc\f1, \f4part_sc\f1"
If \f2N\f1 is the size of the array,
then complexity \f2O(N)\f1.
Exactly \f2N\f1 tests of the criterion are made.
If \f2P\f1 is the number of locations in the array that 
do not satisfy the criterion, then exactly
\f2N + 3floor(P/2)\f1 assignments are done.
.SH NOTES
Because a Block (see \f3Block(3C++)\f1)
can always be used wherever an array is called for,
Array Algorithms can also be used with Blocks.
In fact, these two components were actually designed 
to be used together.
.SH SEE ALSO
.Bf
\f3intro(.)\f1
\f3Block(3C++)\f1
.Be