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