/usr/include/rheolef/csr-algo-trans.h is in librheolef-dev 5.93-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 | # ifndef _SKIT_CSR_ALGO_TRANS_H
# define _SKIT_CSR_ALGO_TRANS_H
///
/// This file is part of Rheolef.
///
/// Copyright (C) 2000-2009 Pierre Saramito <Pierre.Saramito@imag.fr>
///
/// Rheolef is free software; you can redistribute it and/or modify
/// it under the terms of the GNU General Public License as published by
/// the Free Software Foundation; either version 2 of the License, or
/// (at your option) any later version.
///
/// Rheolef is distributed in the hope that it will be useful,
/// but WITHOUT ANY WARRANTY; without even the implied warranty of
/// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
/// GNU General Public License for more details.
///
/// You should have received a copy of the GNU General Public License
/// along with Rheolef; if not, write to the Free Software
/// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
///
/// =========================================================================
//
// CSR: Compressed Sparse Row format
//
// transposition algorithms
//
// author: Pierre.Saramito@imag.fr
//
// date: 24 september 1997
//
//@!\vfill\listofalgorithms
/*@!
\vfill \pagebreak \mbox{} \vfill \begin{algorithm}[h]
\caption{{\tt sort}: sort rows by increasing column order}
\begin{algorithmic}
\INPUT {the matrix in CSR format}
ia(0:nrow), ja(0:nnz-1), a(0:nnz-1)
\ENDINPUT
\OUTPUT {the sorted CSR matrix}
iao(0:nrow), jao(0:nnzl-1), ao(0:nnzl-1)
\ENDOUTPUT
\BEGIN
{\em first: reset iao} \\
\FORTO {i := 0} {nrow}
iao(i) := 0;
\ENDFOR
{\em second: compute lengths from pointers} \\
\FORTO {i := 0} {nrow-1}
\FORTO {p := ia(i)} {ia(i+1)-1}
iao (ja(p)+1)++;
\ENDFOR
\ENDFOR
{\em third: compute pointers from lengths} \\
\FORTO {i := 0} {nrow-1}
iao(i+1) += iao(i)
\ENDFOR
{\em fourth: copy values} \\
\FORTO {i := 0} {nrow-1}
\FORTO {p := ia(i)} {ia(i+1)-1}
j := ja(p) \\
q := iao(j) \\
jao(q) := i \\
ao(q) := a(p) \\
iao (j)++
\ENDFOR
\ENDFOR
{\em fiveth: reshift pointers} \\
\FORTOSTEP {i := nrow-1} {0} {-1}
iao(i+1) := iao(i);
\ENDFOR
iao(0) := 0
\END
\end{algorithmic} \end{algorithm}
\vfill \pagebreak \mbox{} \vfill
*/
namespace rheolef {
// second: compute lengths from pointers
template<
class InputIterator1,
class InputIterator2,
class MutableRandomAcessIterator,
class Size>
void
column_length(
InputIterator1 iter_ib,
InputIterator1 last_ib,
InputIterator2 iter_jb,
MutableRandomAcessIterator rand_ia,
Size nrow_a)
{
InputIterator2 first_jb = iter_jb;
iter_ib++;
while (iter_ib != last_ib) {
InputIterator2 endl_jb = first_jb + (*iter_ib);
while (iter_jb != endl_jb) {
rand_ia [(*iter_jb)+1]++;
assert_macro (*iter_jb < nrow_a, "trans(csr&): column number "
<< *iter_jb
<< " out of range 0.."
<< nrow_a-1);
iter_jb++;
}
++iter_ib;
}
}
// third pass: compute pointers from lengths
template <class InputIterator>
void
pointer_from_length (InputIterator iter_ia, InputIterator last_ia)
{
InputIterator prec_ia = iter_ia;
++iter_ia;
while (iter_ia != last_ia) {
(*iter_ia) += (*prec_ia);
prec_ia = iter_ia;
++iter_ia;
}
}
// fourth pass: store values
template <
class InputIterator1,
class InputIterator2,
class InputIterator3,
class MutableRandomAccessIterator1,
class MutableRandomAccessIterator2,
class MutableRandomAccessIterator3,
class Size>
void
trans_copy_values(
InputIterator1 iter_ib,
InputIterator1 last_ib,
InputIterator2 iter_jb,
InputIterator3 iter_b,
MutableRandomAccessIterator1 rand_ia,
MutableRandomAccessIterator2 rand_ja,
MutableRandomAccessIterator3 rand_a,
Size size_type_tag)
{
Size i_b = 0;
iter_ib++;
InputIterator2 first_jb = iter_jb;
while (iter_ib != last_ib) {
InputIterator2 endl_jb = first_jb + (*iter_ib);
while (iter_jb != endl_jb) {
Size i_a = *iter_jb;
Size q = rand_ia [i_a];
rand_ja [q] = i_b;
rand_a [q] = *iter_b++;
rand_ia [i_a]++;
++iter_jb;
}
++iter_ib;
++i_b;
}
}
// fiveth pass: reshift ia
template <
class InputIterator,
class T>
void
right_shift (
InputIterator iter_ia,
InputIterator last_ia,
T last_value)
{
InputIterator prec_ia = iter_ia;
iter_ia++;
while (iter_ia != last_ia) {
*prec_ia = *iter_ia;
prec_ia = iter_ia;
iter_ia++;
}
*prec_ia = last_value;
}
//@!\vfill
}// namespace rheolef
# endif // _SKIT_CSR_ALGO_TRANS_H
|