summaryrefslogtreecommitdiff
path: root/include
diff options
context:
space:
mode:
authorjan.reininghaus@gmail.com <jan.reininghaus@gmail.com@8e3bb3c2-eed4-f18f-5264-0b6c94e6926d>2013-05-12 20:42:59 +0000
committerjan.reininghaus@gmail.com <jan.reininghaus@gmail.com@8e3bb3c2-eed4-f18f-5264-0b6c94e6926d>2013-05-12 20:42:59 +0000
commitfb02e45712d44f217dfbd71910ea533894c065e6 (patch)
tree77928bd2a11345ced14cec6ca9b07086e09948ce /include
parent7569a4005dc119d7a62990aeb4abe263716617a5 (diff)
simplified pivot column representations
git-svn-id: https://phat.googlecode.com/svn/trunk@84 8e3bb3c2-eed4-f18f-5264-0b6c94e6926d
Diffstat (limited to 'include')
-rw-r--r--include/phat/representations/abstract_pivot_column.h47
-rw-r--r--include/phat/representations/bit_tree_pivot_column.h25
-rw-r--r--include/phat/representations/full_pivot_column.h20
-rw-r--r--include/phat/representations/sparse_pivot_column.h19
-rw-r--r--include/phat/representations/vector_list.h189
-rw-r--r--include/phat/representations/vector_set.h22
6 files changed, 171 insertions, 151 deletions
diff --git a/include/phat/representations/abstract_pivot_column.h b/include/phat/representations/abstract_pivot_column.h
index a84e013..e3598aa 100644
--- a/include/phat/representations/abstract_pivot_column.h
+++ b/include/phat/representations/abstract_pivot_column.h
@@ -71,14 +71,7 @@ namespace phat {
}
// replaces(!) content of 'col' with boundary of given index
void _get_col( index idx, column& col ) const {
- col.clear();
- if( is_represented_by_pivot_column( idx ) ) {
- pivot_column& pivot_column = get_pivot_column();
- pivot_column.get_column_and_clear( col );
- pivot_column.add_column( col );
- } else {
- Base::_get_col( idx, col );
- }
+ is_represented_by_pivot_column( idx ) ? get_pivot_column().get_col( col ) : Base::_get_col( idx, col );
}
// true iff boundary of given idx is empty
@@ -88,16 +81,7 @@ namespace phat {
// largest row index of given column idx (new name for lowestOne())
index _get_max_index( index idx ) const {
- if( is_represented_by_pivot_column( idx ) ) {
- pivot_column& pivot_column = get_pivot_column();
- if( pivot_column.empty() ) {
- return -1;
- } else {
- return pivot_column.max_index();
- }
- } else {
- return Base::_get_max_index( idx );
- }
+ return is_represented_by_pivot_column( idx ) ? get_pivot_column().max_index() : Base::_get_max_index( idx );
}
// adds column 'source' to column 'target'
@@ -111,37 +95,16 @@ namespace phat {
// clears given column
void _clear( index idx ) {
- if( is_represented_by_pivot_column( idx ) ) {
- column dummy;
- get_pivot_column().get_column_and_clear(dummy);
- } else {
- Base::_clear( idx );
- }
+ is_represented_by_pivot_column( idx ) ? get_pivot_column().clear() : Base::_clear( idx );
}
void _set_col( index idx, const column& col ) {
- if( is_represented_by_pivot_column( idx ) ) {
- column dummy;
- pivot_column& pivot_column = get_pivot_column();
- pivot_column.get_column_and_clear( dummy );
- pivot_column.add_column( col );
- } else {
- Base::_set_col( idx, col );
- }
+ is_represented_by_pivot_column( idx ) ? get_pivot_column().set_col( col ) : Base::_set_col( idx, col );
}
// removes the maximal index of a column
void _remove_max( index idx ) {
- _toggle( idx, _get_max_index( idx ) );
- }
-
- //// toggles given index pair
- void _toggle( index col_idx, index row_idx ) {
- if( !is_represented_by_pivot_column( col_idx ) ) {
- unset_pos_of_pivot_column();
- represent_by_pivot_column( col_idx );
- }
- get_pivot_column().add_index( row_idx );
+ is_represented_by_pivot_column( idx ) ? get_pivot_column().remove_max() : Base::_remove_max( idx );
}
// syncronizes all data structures (essential for openmp stuff)
diff --git a/include/phat/representations/bit_tree_pivot_column.h b/include/phat/representations/bit_tree_pivot_column.h
index 9e72530..f997434 100644
--- a/include/phat/representations/bit_tree_pivot_column.h
+++ b/include/phat/representations/bit_tree_pivot_column.h
@@ -153,6 +153,31 @@ namespace phat {
bool empty() {
return !data[0];
}
+
+ void clear() {
+ while(true)
+ {
+ index mx = this->max_index();
+ if (mx == -1)
+ break;
+ add_index(mx);
+ }
+ }
+
+ void remove_max() {
+ add_index( max_index() );
+ }
+
+ void set_col( const column& col ) {
+ clear();
+ add_column( col );
+ }
+
+ void get_col( column& col ) {
+ col.clear();
+ get_column_and_clear( col );
+ add_column( col );
+ }
};
const size_t bit_tree_column::debrujin_magic_table[64] = {
diff --git a/include/phat/representations/full_pivot_column.h b/include/phat/representations/full_pivot_column.h
index 9e0c348..ce7b9f1 100644
--- a/include/phat/representations/full_pivot_column.h
+++ b/include/phat/representations/full_pivot_column.h
@@ -75,6 +75,26 @@ namespace phat {
bool empty() {
return (max_index() == -1);
}
+
+ void clear() {
+ while( !empty() )
+ add_index( max_index() );
+ }
+
+ void remove_max() {
+ add_index( max_index() );
+ }
+
+ void set_col( const column& col ) {
+ clear();
+ add_column( col );
+ }
+
+ void get_col( column& col ) {
+ col.clear();
+ get_column_and_clear( col );
+ add_column( col );
+ }
};
typedef abstract_pivot_column< full_column > full_pivot_column;
diff --git a/include/phat/representations/sparse_pivot_column.h b/include/phat/representations/sparse_pivot_column.h
index c851a2b..f4eab8b 100644
--- a/include/phat/representations/sparse_pivot_column.h
+++ b/include/phat/representations/sparse_pivot_column.h
@@ -56,6 +56,25 @@ namespace phat {
bool empty() {
return m_data.empty();
}
+
+ void clear() {
+ m_data.clear();
+ }
+
+ void remove_max() {
+ add_index( max_index() );
+ }
+
+ void set_col( const column& col ) {
+ clear();
+ add_column( col );
+ }
+
+ void get_col( column& col ) {
+ col.clear();
+ get_column_and_clear( col );
+ add_column( col );
+ }
};
typedef abstract_pivot_column< sparse_column > sparse_pivot_column;
diff --git a/include/phat/representations/vector_list.h b/include/phat/representations/vector_list.h
index 38e3090..fdd5818 100644
--- a/include/phat/representations/vector_list.h
+++ b/include/phat/representations/vector_list.h
@@ -1,98 +1,97 @@
-/* Copyright 2013 IST Austria
- Contributed by: Jan Reininghaus
-
- This file is part of PHAT.
-
- PHAT is free software: you can redistribute it and/or modify
- it under the terms of the GNU Lesser General Public License as published by
- the Free Software Foundation, either version 3 of the License, or
- (at your option) any later version.
-
- PHAT 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 Lesser General Public License for more details.
-
- You should have received a copy of the GNU Lesser General Public License
- along with PHAT. If not, see <http://www.gnu.org/licenses/>. */
-
-#pragma once
-
-#include <phat/helpers/misc.h>
-
-namespace phat {
- class vector_list {
-
- protected:
- typedef std::list< index > internal_column;
- std::vector< dimension > dims;
- std::vector< internal_column > matrix;
-
- public:
- // overall number of cells in boundary_matrix
- index _get_num_cols() const {
- return (index)matrix.size();
- }
- void _set_num_cols( index nr_of_columns ) {
- dims.resize( nr_of_columns );
- matrix.resize( nr_of_columns );
- }
-
- // dimension of given index
- dimension _get_dim( index idx ) const {
- return dims[ idx ];
- }
- void _set_dim( index idx, dimension dim ) {
- dims[ idx ] = dim;
- }
-
- // replaces(!) content of 'col' with boundary of given index
- void _get_col( index idx, column& col ) const {
- col.clear();
- col.reserve( matrix[idx].size() );
- std::copy (matrix[idx].begin(), matrix[idx].end(), std::back_inserter(col) );
- }
-
- void _set_col( index idx, const column& col ) {
- matrix[ idx ].clear();
- matrix[ idx ].resize( col.size() );
- std::copy (col.begin(), col.end(), matrix[ idx ].begin() );
- }
-
- // true iff boundary of given idx is empty
- bool _is_empty( index idx ) const {
- return matrix[ idx ].empty();
- }
-
- // largest row index of given column idx (new name for lowestOne())
- index _get_max_index( index idx ) const {
- return matrix[ idx ].empty() ? -1 : *matrix[ idx ].rbegin();
- }
-
- // removes the maximal index of a column
- void _remove_max( index idx ) {
- internal_column::iterator it = matrix[ idx ].end();
- it--;
- matrix[ idx ].erase( it );
- }
-
- // clears given column
- void _clear( index idx ) {
- matrix[ idx ].clear();
- }
-
- // syncronizes all data structures (essential for openmp stuff)
- void _sync() {}
-
- // adds column 'source' to column 'target'
- void _add_to( index source, index target ) {
- internal_column& source_col = matrix[ source ];
- internal_column& target_col = matrix[ target ];
- internal_column temp_col;
+/* Copyright 2013 IST Austria
+ Contributed by: Jan Reininghaus
+
+ This file is part of PHAT.
+
+ PHAT is free software: you can redistribute it and/or modify
+ it under the terms of the GNU Lesser General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ PHAT 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 Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with PHAT. If not, see <http://www.gnu.org/licenses/>. */
+
+#pragma once
+
+#include <phat/helpers/misc.h>
+
+namespace phat {
+ class vector_list {
+
+ protected:
+ std::vector< dimension > dims;
+ std::vector< std::list< index > > matrix;
+
+ public:
+ // overall number of cells in boundary_matrix
+ index _get_num_cols() const {
+ return (index)matrix.size();
+ }
+ void _set_num_cols( index nr_of_columns ) {
+ dims.resize( nr_of_columns );
+ matrix.resize( nr_of_columns );
+ }
+
+ // dimension of given index
+ dimension _get_dim( index idx ) const {
+ return dims[ idx ];
+ }
+ void _set_dim( index idx, dimension dim ) {
+ dims[ idx ] = dim;
+ }
+
+ // replaces(!) content of 'col' with boundary of given index
+ void _get_col( index idx, column& col ) const {
+ col.clear();
+ col.reserve( matrix[idx].size() );
+ std::copy (matrix[idx].begin(), matrix[idx].end(), std::back_inserter(col) );
+ }
+
+ void _set_col( index idx, const column& col ) {
+ matrix[ idx ].clear();
+ matrix[ idx ].resize( col.size() );
+ std::copy (col.begin(), col.end(), matrix[ idx ].begin() );
+ }
+
+ // true iff boundary of given idx is empty
+ bool _is_empty( index idx ) const {
+ return matrix[ idx ].empty();
+ }
+
+ // largest row index of given column idx (new name for lowestOne())
+ index _get_max_index( index idx ) const {
+ return matrix[ idx ].empty() ? -1 : *matrix[ idx ].rbegin();
+ }
+
+ // removes the maximal index of a column
+ void _remove_max( index idx ) {
+ std::list< index >::iterator it = matrix[ idx ].end();
+ it--;
+ matrix[ idx ].erase( it );
+ }
+
+ // clears given column
+ void _clear( index idx ) {
+ matrix[ idx ].clear();
+ }
+
+ // syncronizes all data structures (essential for openmp stuff)
+ void _sync() {}
+
+ // adds column 'source' to column 'target'
+ void _add_to( index source, index target ) {
+ std::list< index >& source_col = matrix[ source ];
+ std::list< index >& target_col = matrix[ target ];
+ std::list< index > temp_col;
target_col.swap( temp_col );
std::set_symmetric_difference( temp_col.begin(), temp_col.end(),
source_col.begin(), source_col.end(),
- std::back_inserter( target_col ) );
- }
- };
-}
+ std::back_inserter( target_col ) );
+ }
+ };
+}
diff --git a/include/phat/representations/vector_set.h b/include/phat/representations/vector_set.h
index dadf1b3..ea6df09 100644
--- a/include/phat/representations/vector_set.h
+++ b/include/phat/representations/vector_set.h
@@ -24,9 +24,8 @@ namespace phat {
class vector_set {
protected:
- typedef std::set< index > internal_column;
std::vector< dimension > dims;
- std::vector< internal_column > matrix;
+ std::vector< std::set< index > > matrix;
public:
// overall number of cells in boundary_matrix
@@ -69,7 +68,7 @@ namespace phat {
// removes the maximal index of a column
void _remove_max( index idx ) {
- internal_column::iterator it = matrix[ idx ].end();
+ std::set< index >::iterator it = matrix[ idx ].end();
it--;
matrix[ idx ].erase( it );
}
@@ -84,17 +83,12 @@ namespace phat {
// adds column 'source' to column 'target'
void _add_to( index source, index target ) {
- for( internal_column::iterator it = matrix[ source ].begin(); it != matrix[ source ].end(); it++ )
- _toggle( target, *it );
- }
-
- //// toggles given index pair
- void _toggle( index col_idx, index row_idx ) {
- internal_column& col = matrix[ col_idx ];
- std::pair< internal_column::iterator, bool > result = col.insert( row_idx );
- if( !result.second ) {
- col.erase( result.first );
- }
+ for( std::set< index >::iterator it = matrix[ source ].begin(); it != matrix[ source ].end(); it++ ) {
+ std::set< index >& col = matrix[ target ];
+ std::pair< std::set< index >::iterator, bool > result = col.insert( *it );
+ if( !result.second )
+ col.erase( result.first );
+ }
}
};
}