1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2%%
3%%  sort_vector.tex       LiDIA documentation
4%%
5%%  This file contains the documentation of the vector classes
6%%
7%%  Copyright   (c)   1995   by  LiDIA-Group
8%%
9%%  Authors: Frank Lehmann, Markus Maurer
10%%           Patrick Theobald, Stefan Neis
11%%
12
13\newcommand{\DEF}{\textcode{\itshape DEF}}
14
15
16%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
17
18\NAME
19
20\CLASS{sort_vector< T >} \dotfill vectors with sort functions
21
22
23%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
24
25\ABSTRACT
26
27Class \code{sort_vector< T >} contains \code{base_vector< T >} as a base class.  It supports any
28member and friend function of that class.  Additionally it provides functions for sorting and
29searching, inserting and deleting.  \code{T} can be either a built-in type or a class.
30
31
32%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
33
34\DESCRIPTION
35
36A variable of type \code{sort_vector< T >} contains the same components as a variable of type
37\code{base_vector< T >}.  In addition there is a character \code{sort_dir} and a function
38pointer \code{*el_cmp}.
39
40A vector of type \code{sort_vector< T >} can be sorted according to a certain sort direction.
41This class provides two standard directions \code{SORT_VECTOR_UP} and \code{SORT_VECTOR_DOWN} to
42sort the elements of a vector in ascending or descending order, respectively.  Furthermore,
43specific compare functions may be used to define a relation of elements of type \code{T}.  These
44functions define a new sort relation for a vector.
45
46Any compare function used must have a prototye like
47\begin{quote}
48  \code{int cmp ( const T & $a$, const T & $b$ ) }.
49\end{quote}
50The data type for pointers to functions of that type will be called \code{CMP_FUNC} in the
51sequel.  The return value of a comparison shall be as follows:
52\begin{center}
53  \begin{tabular}{rl}
54    $ < 0 $ & if \code{(a, b)} is in correct order \\
55    $ = 0 $ & if \code{a, b}  are identical      \\
56    $ > 0 $ & if \code{(a, b)} is in inverted order
57  \end{tabular}
58\end{center}
59Any vector $v$ of type \code{sort_vector< T >} contains a default sort direction according to
60which it will be sorted if the function \code{$v$.sort()} is applied.  This default sort
61direction will be set to \code{SORT_VECTOR_UP} by any constructor in this class; i.e. vector $v$
62will be sorted in ascending order by default.  This default value may later be changed for a
63vector $v$ by using the function \code{$v$.set_sort_direction()}.
64
65
66%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
67
68\CONS
69
70Each of the following constructors can get an additional parameter (\code{FIXED} or
71\code{EXPAND}) to indicate the mode of the \code{sort_vector}.
72
73\begin{fcode}{ct}{sort_vector< T >}{}
74  constructs a vector with capacity 0.
75\end{fcode}
76
77\begin{fcode}{ct}{sort_vector< T >}{lidia_size_t $c$}
78  constructs a vector with capacity $c$ initialized with values generated by the default
79  constructor for type \code{T}.
80\end{fcode}
81
82\begin{fcode}{ct}{sort_vector< T >}{lidia_size_t $c$, lidia_size_t $s$}
83  constructs a vector with capacity $c$ and size $s$ initialized with values generated by the
84  default constructor for type \code{T}.
85\end{fcode}
86
87\begin{fcode}{ct}{sort_vector< T >}{const sort_vector< T > & $w$}
88  constructs a vector with capacity $w.size$ initialized with the elements of $w$.
89\end{fcode}
90
91\begin{fcode}{ct}{sort_vector< T >}{const T * $a$, lidia_size_t $l$}
92  constructs a vector with capacity $l$ and size $l$ initialized with the first $l$ elements of
93  the array $a$.
94\end{fcode}
95
96\begin{fcode}{dt}{~sort_vector< T >}{}
97\end{fcode}
98
99
100%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
101
102\STITLE{Sort direction}
103
104\begin{cfcode}{char}{$v$.sort_direction}{}
105  returns the default sort direction of vector $v$.  The return value will be one of the
106  predefined constants \code{SORT_VECTOR_UP}, \code{SORT_VECTOR_UP} or \code{SORT_VECTOR_CMP}.
107  The latter indicates that the sort direction of $v$ has been set to a certain compare
108  function.
109\end{cfcode}
110
111\begin{cfcode}{char}{$v$.get_sort_direction}{}
112  returns the default sort direction of vector $v$.  The return value will be one of the
113  predefined constants \code{SORT_VECTOR_UP}, \code{SORT_VECTOR_DOWN} or \code{SORT_VECTOR_CMP}.
114  The latter indicates that the sort direction of $v$ has been set to a certain compare
115  function.
116\end{cfcode}
117
118\begin{fcode}{void}{$v$.set_sort_direction}{char $\mathit{dir}$}
119  sets the default sort-direction for $v$ to $\mathit{dir}$.  The value of $\mathit{dir}$ may be
120  either one of the two predefined constants \code{SORT_VECTOR_UP} or \code{SORT_VECTOR_DOWN}.
121  If $\mathit{dir}$ is invalid, the standard sort direction of $v$ will be left unchanged and
122  the \LEH will be invoked.
123\end{fcode}
124
125\begin{fcode}{void}{$v$.set_sort_direction}{int (*cmp) (const T & $a$, const T & $b$)}
126  sets the default sort direction for $v$ in a way that function \code{cmp()} will be used to
127  compare the entries of $v$.
128\end{fcode}
129
130
131%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
132
133\STITLE{Sort Functions}
134
135Class \code{sort_vector< T >} provides a sort function, which allows to sort a vector in various
136ways.  There are three different prototypes for this sort routine that allow a variety of calls
137of the functions.  Some of the parameters of function \code{sort()} can obtain default values if
138they are not specified in a call.  These default values will be indicated by ''\DEF''.
139
140It is possible to restrict the sort routine to a part of a vector by explicitly passing on the
141starting and ending indices to this function.  Whenever these values are invalid, the \LEH will
142be invoked.
143
144\begin{fcode}{void}{$v$.sort}{char sort_dir = \DEF, int $l$ = \DEF, int $r$ = \DEF}
145  sorts the elements $v[l], \dots, v[r]$ according to the direction \code{$v$.sort_dir}.  Any other
146  element in $v$ will remain in its position.  The value of \code{$v$.sort_dir} has to be either one of
147  the two constants \code{SORT_VECTOR_UP} or \code{SORT_VECTOR_DOWN}.  If it differs from these
148  values, the \LEH will be invoked.  If no values for $l$ and $r$ are given, the entire vector
149  will be sorted.  If \code{$v$.sort_dir} is not specified either, the default sort direction for $v$
150  will be used.
151\end{fcode}
152
153\begin{fcode}{void}{$v$.sort}{CMP_FUNC cmp, int $l$ = \DEF, int $r$ = \DEF}
154  sorts the elements $v[l], \dots, v[r]$ according to the compare function \code{(*cmp)()}.  Any
155  other element in $v$ will remain in its position.  The function \code{(*cmp)()} must be of
156  correct type \code{CMP_FUNC}.  If no values for $l$ and $r$ are given, the entire vector will
157  be sorted.
158\end{fcode}
159
160\begin{fcode}{void}{$v$.sort}{int $l$, int $r$}
161  sorts the elements $v[l], \dots, v[r]$ according to the default sort direction of $v$.
162\end{fcode}
163
164
165%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
166
167\STITLE{Search Functions}
168
169As a second feature the class \code{sort_vector< T >} provides functions for linear and binary
170search in a vector.
171
172\begin{cfcode}{bool}{$v$.linear_search}{const T & $x$, int & $\mathit{pos}$}
173  searches $x$ in vector $v$.  If $x$ can be found, this function will return \TRUE and
174  $\mathit{pos}$ will hold the index of its first occurence in $v$.  Otherwise, the return value
175  will be \FALSE.
176\end{cfcode}
177
178The function \code{bin_search()} searches for an element $x$ in a vector using a binary search
179strategy.  (Beware of the fact, that this routine can work successfully only if the elements of
180the vector are sorted in an appropriate way.) Its return value will be \TRUE if it succeeds, and
181\FALSE otherwise.  If $x$ can be found in a vector, $\mathit{pos}$ will hold the index of its
182\emph{first} occurence or else, $\mathit{pos}$ will be the index, where $x$ can be inserted
183according to the corresponding sort direction.
184
185Some of the parameters of function \code{bin_search()} can obtain default values if they are not
186specified in a call.  These default values will be indicated by ''\DEF''.
187
188It is possible to restrict the search to a part of a vector by explicitly passing on the
189starting and ending indices to this function.  Whenever these values are invalid, the \LEH will
190be invoked.
191
192\begin{cfcode}{bool}{$v$.bin_search}{const T & $x$, int & $\mathit{pos}$, char sort_dir = \DEF,
193    int $l$ = \DEF, int $r$ = \DEF}%
194  searches for $x$ among the elements $v[l], \dots, v[r]$ using the sort direction
195  \code{$v$.sort_dir}.  Its value must be either of the two constants \code{SORT_VECTOR_UP} or
196  \code{SORT_VECTOR_DOWN}.  If \code{$v$.sort_dir} differs from these values, the \LEH will be
197  invoked.  If no values for $l$ and $r$ are given, the search will be carried out on the entire
198  vector.  If \code{$v$.sort_dir} is not specified either, the default sort-direction for $v$
199  will be used.
200\end{cfcode}
201
202\begin{cfcode}{bool}{$v$.bin_search}{const T & $x$, int & $\mathit{pos}$, CMP_FUNC cmp, int $l$ = \DEF, int $r$ = \DEF}
203  searches for $x$ among the elements $v[l], \dots, v[r]$ using function \code{(*cmp)()} to
204  compare these entries.  The function \code{(*cmp)()} must be of correct type \code{CMP_FUNC}.
205  If no values for $l$ and $r$ are given, the search will be carried out on the entire vector.
206  If \code{$v$.sort_dir} is not specified either, the default sort direction for $v$ will be
207  used.
208\end{cfcode}
209
210\begin{cfcode}{bool}{$v$.bin_search}{const T & $x$, int & $\mathit{pos}$, int $l$, int $r$}
211  searches for $x$ among the elements $v[l], \dots, v[r]$ using the default sort direction of $v$.
212\end{cfcode}
213
214
215%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
216
217\STITLE{Insert Functions}
218
219The class \code{sort_vector< T >} also supports several functions to insert a new element into a
220vector.  These use the member function \code{$v$.set_size()} to extend the size of a vector $v$ by
2211.  If this cannot successfully be done, the vector will be left unchanged.  In that case, the
222\LEH will be invoked.
223
224An element $x$ can either be inserted at a specified position (using the function
225\code{insert_at()} of class \code{base_vector< T >}) or it can also be automatically inserted at
226its \emph{correct} position according to the vector's sort direction.
227
228The function \code{insert()} provides several prototypes that allow to optionally specify a sort
229direction or a part of the vector in a call to it.  If these parameters are missing, $insert()$
230will refer to the vector default sort direction or consider the entire vector, respectively.
231
232Note, that a vector must have been sorted before using the function \code{insert()}.  The sort
233direction used in the sort procedure must correspond to the one specified here.
234
235\begin{fcode}{void}{$v$.insert}{const T & $x$, char sort_dir = \DEF, int $l$ = \DEF, int $r$ = \DEF}
236  uses the function \code{bin_search()} to determine the correct position of $x$ in $v$
237  according to the specified sort direction.  If $l$ and $r$ are specified, the search for $x$
238  will be restricted to the part $v[l], \dots, v[r]$.  After $x$ is inserted at the corresponding
239  position, every succeeding element in $v$ will be moved one place to the right.  The value of
240  \code{$v$.sort_dir} must be either one of the two constants \code{SORT_VECTOR_UP} or
241  \code{SORT_VECTOR_DOWN}.  If \code{$v$.sort_dir} differs from these values, the \LEH will be
242  invoked.
243
244  If no values are given for $l$, $r$ or \code{sort_dir}, the default values will be passed on
245  to the function \code{bin_search()}, i.e. the search for $x$ will be carried out on the entire
246  vector and according to its default sort direction.
247\end{fcode}
248
249\begin{fcode}{void}{$v$.insert}{const T & $x$, CMP_FUNC cmp, int $l$ = \DEF, int $r$ = \DEF}
250  uses the function \code{bin_search()} to determine the correct position of $x$ in $v$
251  according to the compare function \code{(*cmp)()}.  If $l$ and $r$ are specified, the search
252  for $x$ will be restricted to the part $v[l], \dots, v[r]$.  After $x$ is inserted at the
253  corresponding position, every succeeding element in $v$ will be moved one place to the right.
254
255  If no values are given for $l$ and $r$, the default values will be passed on to the function
256  \code{bin_search()}, i.e. the search for $x$ will be carried out on the entire vector.
257\end{fcode}
258
259\begin{fcode}{void}{$v$.insert}{const T & $x$, int $l$, int $r$}
260  uses the function \code{bin_search()} to determine the correct position of $x$ in $v$
261  according to the default sort direction of $v$.  The search for $x$ will be restricted to the
262  part $v[l], \dots, v[r]$.  After $x$ is inserted at the corresponding position, every succeeding
263  element in $v$ will be moved one place to the right.
264\end{fcode}
265
266
267%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
268
269\STITLE{Remove Functions}
270
271Furthermore, the class \code{sort_vector< T >} supports functions to remove elements from a
272vector.  These functions use \code{$v$.set_size()} to deminish the size of the vector after the
273removal.
274
275The function \code{remove()} initiates \code{bin_search()} first to find a given element $x$ in
276a vector.  If this search was successfully done, $one$ occurrence of $x$ will be removed from
277$v$.  Any element in $v$ succeeding $x$ will be moved one position to the left and the size of
278the vector will be diminished by 1.  If $x$ cannot be found in the vector, $v$ will be left
279unchanged and the return value will be \FALSE.
280
281The function \code{remove()} also provides several prototypes that allow to optionally specify a
282sort direction or a part of the vector.  If these parameters are missing, \code{remove()} will
283refer to the vector default sort direction and consider the entire vector, respectively.
284
285\begin{fcode}{bool}{$v$.remove}{const T & $x$, char sort_dir = \DEF, int $l$ = \DEF, int $r$ = \DEF}
286  uses the function \code{bin_search()} to find $x$ in $v$ using the specified sort direction.
287  If $l$ and $r$ are specified, the search for $x$ will be restricted to the part
288  $v[l], \dots, v[r]$.  If $x$ can be found in the vector, its first occurence will be deleted.
289  The value of \code{$v$.sort_dir} must be one either of the two constants \code{SORT_VECTOR_UP}
290  or \code{SORT_VECTOR_DOWN}.  If \code{$v$.sort_dir} differs from these values, the \LEH will be
291  invoked.
292
293  If no values are given for $l$, $r$ or \code{$v$.sort_dir}, the default values will be passed on
294  to the function \code{bin_search()}, i.e. the search for $x$ will be carried out on the entire
295  vector and according to its default sort direction.
296\end{fcode}
297
298\begin{fcode}{bool}{$v$.remove}{const T & $x$, CMP_FUNC cmp, int $l$ = \DEF, int $r$ = \DEF}
299  uses the function \code{$v$.bin_search()} to find $x$ in $v$ using the compare function
300  \code{(*cmp)()}.  If $l$ and $r$ are specified, the search for $x$ will be restricted to the
301  part $v[l], \dots, v[r]$.  If $x$ can be found in the vector, its first occurence will be
302  deleted.
303
304  If no values are given for $l$ and $r$, the default values will be passed on to the function
305  \code{bin_search()}, i.e. the search for $x$ will be carried out on the entire vector.
306\end{fcode}
307
308\begin{fcode}{bool}{$v$.remove}{const T & $x$, int $l$, int $r$}
309  uses the function \code{bin_search()} to find $x$ in $v$ using the default sort-direction of
310  $v$.  The search for $x$ will be restricted to the part $v[l], \dots, v[r]$.  If $x$ can be
311  found in the vector, its first occurence will be deleted.
312\end{fcode}
313
314
315%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
316
317\SEEALSO
318
319\SEE{base_vector}, \SEE{file_vector},
320\SEE{math_vector}
321
322
323%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
324
325\NOTES
326
327As described in the template introduction (see page \pageref{template_introduction}) for using
328an instance of type \code{sort_vector< T >} the type $T$ has to have at least
329\begin{itemize}
330\item a swap function \code{void swap(T &, T&)},
331\item the input operator \code{>>},
332\item the output operator \code{<<},
333\item the assignment operator \code{=} and
334\item the compare operators \code{<} and \code{>}.
335\end{itemize}
336
337
338%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
339
340\EXAMPLES
341
342\begin{quote}
343\begin{verbatim}
344#include <LiDIA/sort_vector.h>
345
346int main()
347{
348    sort_vector < double > w ;
349
350    cout << " w = " ;
351    cin >> w ;
352
353    w.sort();
354
355    cout << w << flush;
356}
357\end{verbatim}
358\end{quote}
359
360For further examples please refer to \path{LiDIA/src/templates/vector/vector_appl.cc}
361
362
363%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
364
365\AUTHOR
366
367Frank Lehmann, Markus Maurer, Stefan Neis, Thomas Papanikolaou, Patrick
368Theobald
369