SparseLibrary  Version 1.6.0
MinCRS.hpp
1 /*
2  * Copyright (c) 2007-2014, A. N. Yzelman, Utrecht University 2007-2011;
3  * KU Leuven 2011-2014.
4  * R. H. Bisseling, Utrecht University 2007-2014.
5  *
6  * This file is part of the Sparse Library.
7  *
8  * This library was developed under supervision of Prof. dr. Rob H. Bisseling at
9  * Utrecht University, from 2007 until 2011. From 2011-2014, development continued
10  * at KU Leuven, where Prof. dr. Dirk Roose contributed significantly to the ideas
11  * behind the newer parts of the library code.
12  *
13  * The Sparse Library is free software: you can redistribute it and/or modify
14  * it under the terms of the GNU General Public License as published by the
15  * Free Software Foundation, either version 3 of the License, or (at your
16  * option) any later version.
17  *
18  * The Sparse Library is distributed in the hope that it will be useful, but
19  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
20  * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
21  * for more details.
22  *
23  * You should have received a copy of the GNU General Public License along
24  * with the Sparse Library. If not, see <http://www.gnu.org/licenses/>.
25  */
26 
27 
28 /*
29  * File created by:
30  * A. N. Yzelman, Dept. of Mathematics, Utrecht University, 2010.
31  */
32 
33 
34 #ifndef _H_MINCRS
35 #define _H_MINCRS
36 
37 #include "BlockOrderer.hpp"
38 
40 template< typename T >
41 class MinCRS: public BlockOrderer< T > {
42  protected:
43 
45  virtual void pre_readout ( const unsigned long int index ) {
46  //switch between internal nodes and external nodes
47  if( this->tree->isLeaf( index ) ) {
48  //immediately add everything in range
49  this->output->push_back( this->items[ index ] );
50  if( this->datatype != NULL )
51  this->datatype->push_back( NORMAL_DS );
52  } else {
53  //initialise
54  typename std::vector< Triplet< T > >::iterator it = this->items[ index ].begin();
55  std::vector< Triplet< T > > cur;
56  std::vector< Triplet< T > > rep;
57  //loop over this node's triplets
58  for( ; it != this->items[ index ].end(); ++it ) {
59  //left horizontal separator first
60  if( this->upper_vertical( index, *it ) )
61  cur.push_back( *it );
62  else
63  rep.push_back( *it );
64  }
65  if( cur.size() > 0 )
66  this->items[ index ] = rep; //replace with smaller vector
67  this->output->push_back( cur );
68  if( this->datatype != NULL )
69  this->datatype->push_back( VERTICAL_DS );
70  }
71  }
72 
74  virtual void in_readout ( const unsigned long int index ) {
75  //skip leaf node
76  if( this->tree->isLeaf( index ) ) return;
77  //initialise
78  typename std::vector< Triplet< T > >::iterator it = this->items[ index ].begin();
79  std::vector< Triplet< T > > cur1;
80  std::vector< Triplet< T > > cur2;
81  std::vector< Triplet< T > > cur3;
82  std::vector< Triplet< T > > rep;
83  //loop over this node's triplets
84  for( ; it != this->items[ index ].end(); ++it ) {
85  //now the 3 vertical separators (incl middle) in row order
86  if( this->left_horizontal( index, *it ) )
87  cur1.push_back( *it );
88  else if( this->middle( index, *it ) )
89  cur2.push_back( *it );
90  else if( this->right_horizontal( index, *it ) )
91  cur3.push_back( *it );
92  else
93  rep.push_back( *it );
94  }
95  if( cur1.size() + cur2.size() + cur3.size() > 0 )
96  this->items[ index ] = rep; //replace with smaller vector
97  this->output->push_back( cur1 );
98  this->output->push_back( cur2 );
99  this->output->push_back( cur3 );
100  if( this->datatype != NULL ) {
101  this->datatype->push_back( HORIZONTAL_DS );
102  this->datatype->push_back( NORMAL_DS );
103  this->datatype->push_back( HORIZONTAL_DS );
104  }
105  }
106 
108  virtual void post_readout( const unsigned long int index ) {
109  //skip leaf node
110  if( this->tree->isLeaf( index ) ) return;
111  //initialise
112  typename std::vector< Triplet< T > >::iterator it = this->items[ index ].begin();
113  std::vector< Triplet< T > > cur;
114  std::vector< Triplet< T > > rep;
115  //loop over this node's triplets
116  for( ; it != this->items[ index ].end(); ++it ) {
117  //right horizontal separator last
118  if( this->lower_vertical( index, *it ) )
119  cur.push_back( *it );
120  else
121  rep.push_back( *it );
122  }
123  if( cur.size() > 0 )
124  this->items[ index ] = rep; //replace with smaller vector
125  assert( rep.size() == 0 );
126  this->output->push_back( cur );
127  if( this->datatype != NULL )
128  this->datatype->push_back( VERTICAL_DS );
129  }
130 
131  public:
132 
133  virtual ~MinCRS() {}
134 
135 };
136 
137 #endif
138 
Induces a block order by fully traversing an SBDTree.
Definition: BlockOrderer.hpp:48
virtual void pre_readout(const unsigned long int index)
Prefix operations during SBD tree traversal.
Definition: MinCRS.hpp:45
SBDTree * tree
The SBD tree to order the blocks of.
Definition: BlockOrderer.hpp:53
char isLeaf(const unsigned long int index)
Whether the given node is a leaf node.
Definition: SBDTree.cpp:214
bool left_horizontal(const unsigned long int index, const Triplet< T > triplet)
Helper function for determining place of a nonzero within a separator cross.
Definition: BlockOrderer.hpp:203
bool upper_vertical(const unsigned long int index, const Triplet< T > triplet)
Helper function for determining place of a nonzero within a separator cross.
Definition: BlockOrderer.hpp:221
virtual void post_readout(const unsigned long int index)
Postfix operations during SBD tree traversal.
Definition: MinCRS.hpp:108
bool right_horizontal(const unsigned long int index, const Triplet< T > triplet)
Helper function for determining place of a nonzero within a separator cross.
Definition: BlockOrderer.hpp:212
bool lower_vertical(const unsigned long int index, const Triplet< T > triplet)
Helper function for determining place of a nonzero within a separator cross.
Definition: BlockOrderer.hpp:230
std::vector< std::vector< Triplet< T > > > * output
Output structure after SBD readout (series of blocks in the correct order).
Definition: BlockOrderer.hpp:197
virtual void in_readout(const unsigned long int index)
Infix operations during SBD tree traversal.
Definition: MinCRS.hpp:74
bool middle(const unsigned long int index, const Triplet< T > triplet)
Helper function for determining place of a nonzero within a separator cross.
Definition: BlockOrderer.hpp:239
std::vector< signed char > * datatype
The data type of each block.
Definition: BlockOrderer.hpp:200
Codes the Minimal CRS block order.
Definition: MinCRS.hpp:41
std::vector< Triplet< T > > * items
Nonzero storage at each node.
Definition: BlockOrderer.hpp:194