diff options
Diffstat (limited to 'include/phat/representations')
17 files changed, 806 insertions, 587 deletions
diff --git a/include/phat/representations/Container_traits.h b/include/phat/representations/Container_traits.h new file mode 100644 index 0000000..9ab4b5c --- /dev/null +++ b/include/phat/representations/Container_traits.h @@ -0,0 +1,75 @@ +/* Copyright 2013 IST Austria + Contributed by: Ulrich Bauer, Michael Kerber, 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 + +namespace phat { + +template<typename ColumnContainer> + class Column_container_traits { + + public: + + typedef ColumnContainer Column_container; + typedef typename Column_container::value_type Column_type; + + Column_type& col_at(Column_container& data, index idx) const { + return data[ idx ]; + } + + const Column_type& col_at(const Column_container& data, index idx) const { + return data[ idx ]; + } + + index get_size(const Column_container& data) const { + return data.size(); + } + + void resize(Column_container& data, index nr_of_columns) const { + data.resize(nr_of_columns); + } + +}; + +template<typename DimensionContainer> + class Dimension_container_traits { + + public: + + typedef DimensionContainer Dimension_container; + + index& dim_at(Dimension_container& data, index idx) const { + return data[ idx ]; + } + + const index& dim_at(const Dimension_container& data, index idx) const { + return data[ idx ]; + } + + index get_size(const Dimension_container& data) const { + return data.size(); + } + + void resize(Dimension_container& data, index nr_of_columns) const { + data.resize(nr_of_columns); + } + +}; + + +} // namespace phat diff --git a/include/phat/representations/Pivot_representation.h b/include/phat/representations/Pivot_representation.h new file mode 100644 index 0000000..324c888 --- /dev/null +++ b/include/phat/representations/Pivot_representation.h @@ -0,0 +1,118 @@ +/* Copyright 2013 IST Austria + Contributed by: Ulrich Bauer, Michael Kerber, 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/representations/Container_traits.h> + +namespace phat{ + +template<typename BaseRepresentation, typename PivotColumn> + class Pivot_representation : public BaseRepresentation { + + public: + + typedef BaseRepresentation Base; + typedef PivotColumn Pivot_column; + + protected: + + // For parallization purposes, it could be more than one full column + mutable thread_local_storage< Pivot_column > pivot_cols; + mutable thread_local_storage< index > idx_of_pivot_cols; + + Pivot_column& get_pivot_col() const { + return pivot_cols(); + } + + bool is_pivot_col( index idx ) const { + return idx_of_pivot_cols() == idx; + } + + void release_pivot_col() { + index idx = idx_of_pivot_cols(); + if( idx != -1 ) { + Base::_clear(idx); + column col; + pivot_cols().get_col_and_clear( col ); + Base::_set_col(idx, col); + } + idx_of_pivot_cols() = -1; + } + + void make_pivot_col( index idx ) { + release_pivot_col(); + idx_of_pivot_cols() = idx; + // Remark: Converting the column to a vector first gives a huge performance + // penalty, due to the fact that data is copied around + //column col; + //Base::_get_col( idx, col ); + + get_pivot_col().add_col( Base::col_traits.col_at(Base::matrix,idx).begin(), + Base::col_traits.col_at(Base::matrix,idx).end()); + + //get_pivot_col().add_col( Base::matrix[idx]); + } + + public: + + void _set_num_cols( index nr_of_cols ) { + #pragma omp parallel for + for( int tid = 0; tid < omp_get_num_threads(); tid++ ) { + pivot_cols[ tid ].init( nr_of_cols ); + idx_of_pivot_cols[ tid ] = -1; + } + Base::_set_num_cols( nr_of_cols ); + } + + void _add_to( index source, index target ) { + if( !is_pivot_col( target ) ) + make_pivot_col( target ); + //column col; + //Base::_get_col(source,col); + + get_pivot_col().add_col( Base::col_traits.col_at(Base::matrix,source).begin(), + Base::col_traits.col_at(Base::matrix,source).end() ); + + //get_pivot_col().add_col(Base::matrix[source]); + } + + void _sync() { + #pragma omp parallel for + for( int tid = 0; tid < omp_get_num_threads(); tid++ ) + release_pivot_col(); + } + + void _get_col( index idx, column& col ) const { is_pivot_col( idx ) ? get_pivot_col().get_col( col ) : Base::_get_col( idx, col ); } + + bool _is_empty( index idx ) const { return is_pivot_col( idx ) ? get_pivot_col().is_empty() : Base::_is_empty( idx ); } + + index _get_max_index( index idx ) const { return is_pivot_col( idx ) ? get_pivot_col().get_max_index() : Base::_get_max_index( idx ); } + + void _clear( index idx ) { is_pivot_col( idx ) ? get_pivot_col().clear() : Base::_clear( idx ); } + + void _set_col( index idx, const column& col ) { is_pivot_col( idx ) ? get_pivot_col().set_col( col ) : Base::_set_col( idx, col ); } + + void _remove_max( index idx ) { is_pivot_col( idx ) ? get_pivot_col().remove_max() : Base::_remove_max( idx ); } + + void finalize( index idx ) { Base::_finalize( idx ); } + +}; + + +} diff --git a/include/phat/representations/Uniform_representation.h b/include/phat/representations/Uniform_representation.h new file mode 100644 index 0000000..ccbf6a3 --- /dev/null +++ b/include/phat/representations/Uniform_representation.h @@ -0,0 +1,112 @@ +/* Copyright 2013 IST Austria + Contributed by: Ulrich Bauer, Michael Kerber, 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/representations/Container_traits.h> + +namespace phat { + +template<class ColumnContainer, class DimensionContainer> +class Uniform_representation { + + public: + + typedef ColumnContainer Column_container; + typedef DimensionContainer Dimension_container; + + typedef Column_container_traits<Column_container> Column_traits; + typedef Dimension_container_traits<Dimension_container> Dimension_traits; + + + typedef typename Column_traits::Column_type Column_type; + + protected: + + // We need to label them mutable, since we have no control whether + // the representations are manipulated by the traits class + mutable Dimension_container dims; + mutable Column_container matrix; + + Column_traits col_traits; + Dimension_traits dim_traits; + + thread_local_storage< column > temp_column_buffer; + + public: + + index _get_num_cols() const { + return col_traits.get_size(matrix); + } + + void _set_num_cols(index nr_of_columns) { + col_traits.resize(matrix, nr_of_columns); + for(index idx = 0;idx < nr_of_columns;idx++) { + col_traits.col_at(matrix,idx).offer_thread_local_storage(&temp_column_buffer); + } + dim_traits.resize(dims, nr_of_columns); + } + + dimension _get_dim( index idx ) const { + return dim_traits.dim_at(dims, idx ); + } + + void _set_dim( index idx, dimension dim ) { + dim_traits.dim_at(dims,idx) = dim; + } + + void _get_col( index idx, column& col ) const { + col_traits.col_at(matrix, idx)._get_col( col ); + } + + void _set_col( index idx, const column& col ) { + //col_traits.col_at(matrix, idx)._set_col( col ); + matrix[idx]._set_col(col); + } + + bool _is_empty( index idx ) const { + return col_traits.col_at(matrix, idx)._is_empty(); + } + + index _get_max_index( index idx ) const { + return col_traits.col_at(matrix, idx)._get_max_index(); + } + + void _remove_max( index idx ) { + return col_traits.col_at(matrix, idx)._remove_max(); + } + + void _add_to( index source, index target ) { + Column_type& source_col = col_traits.col_at(matrix, source); + Column_type& target_col = col_traits.col_at(matrix, target); + target_col._add_to( source_col ); + } + + void _clear( index idx ) { + col_traits.col_at(matrix, idx)._clear(); + } + + void _finalize( index idx ) { + col_traits.col_at(matrix, idx)._finalize(); + } + + void _sync() {} + +}; + +} diff --git a/include/phat/representations/Unordered_map_container_traits.h b/include/phat/representations/Unordered_map_container_traits.h new file mode 100644 index 0000000..0e54be6 --- /dev/null +++ b/include/phat/representations/Unordered_map_container_traits.h @@ -0,0 +1,120 @@ +/* Copyright 2013 IST Austria + Contributed by: Ulrich Bauer, Michael Kerber, 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 + +// This file requires c++11 + +#include<phat/representations/Container_traits.h> + +#include<unordered_map> +#include<mutex> + +namespace phat{ + +template<class ColumnType> + class Column_container_traits< std::unordered_map<index,ColumnType> > { + + protected: + + index _size; + + mutable std::mutex _mutex; + + public: + + typedef std::unordered_map<index,ColumnType> Column_container; + + typedef ColumnType Column_type; + + Column_type& col_at(Column_container& data, index idx) const { + _mutex.lock(); + typename Column_container::iterator it = data.find(idx); + if(it==data.end()) { + std::pair<typename Column_container::iterator, bool> result + = data.insert(std::make_pair(idx,Column_type())); + it = result.first; + } + _mutex.unlock(); + return it->second; + } + + /* + const Column_type& col_at(const Column_container& data, index idx) const { + if(data.find(idx)==data.end()) { + data.insert(std::make_pair(idx,Column_type())); + } + return data.at(idx); + } + */ + + index get_size(const Column_container& data) const { + return _size; + } + + void resize(Column_container& data, index nr_of_columns) { + _size = nr_of_columns; + } + + }; + +template<> + class Dimension_container_traits< std::unordered_map<index,index> > { + + protected: + + index _size; + + mutable std::mutex _mutex; + + public: + + typedef std::unordered_map<index,index> Dimension_container; + + index& dim_at(Dimension_container& data, index idx) const { + _mutex.lock(); + typename Dimension_container::iterator it = data.find(idx); + if(it==data.end()) { + std::pair<typename Dimension_container::iterator, bool> result + = data.insert(std::make_pair(idx,0)); + it = result.first; + } + _mutex.unlock(); + return it->second; + } + + /* + const index& dim_at(Dimension_container& data, index idx) const { + if(data.find(idx)==data.end()) { + data.insert(std::make_pair(idx,0)); + } + return data.at(idx); + } + */ + + index get_size(const Dimension_container& data) const { + return _size; + } + + void resize(Dimension_container& data, index nr_of_columns) { + _size = nr_of_columns; + } + + }; + +} // of namespace phat diff --git a/include/phat/representations/abstract_pivot_column.h b/include/phat/representations/abstract_pivot_column.h deleted file mode 100644 index e16d7a5..0000000 --- a/include/phat/representations/abstract_pivot_column.h +++ /dev/null @@ -1,102 +0,0 @@ -/* Copyright 2013 IST Austria
- Contributed by: Ulrich Bauer, Michael Kerber, 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>
-#include <phat/representations/vector_vector.h>
-
-namespace phat {
-
- // Note: We could even make the rep generic in the underlying Const representation
- // But I cannot imagine that anything else than vector<vector<index>> would
- // make sense
- template< typename PivotColumn >
- class abstract_pivot_column : public vector_vector {
-
- protected:
- typedef vector_vector Base;
- typedef PivotColumn pivot_col;
-
- // For parallization purposes, it could be more than one full column
- mutable thread_local_storage< pivot_col > pivot_cols;
- mutable thread_local_storage< index > idx_of_pivot_cols;
-
- pivot_col& get_pivot_col() const {
- return pivot_cols();
- }
-
- bool is_pivot_col( index idx ) const {
- return idx_of_pivot_cols() == idx;
- }
-
- void release_pivot_col() {
- index idx = idx_of_pivot_cols();
- if( idx != -1 ) {
- this->matrix[ idx ].clear();
- pivot_cols().get_col_and_clear( this->matrix[ idx ] );
- }
- idx_of_pivot_cols() = -1;
- }
-
- void make_pivot_col( index idx ) {
- release_pivot_col();
- idx_of_pivot_cols() = idx;
- get_pivot_col().add_col( matrix[ idx ] );
- }
-
- public:
-
- void _set_num_cols( index nr_of_cols ) {
- #pragma omp parallel for
- for( int tid = 0; tid < omp_get_num_threads(); tid++ ) {
- pivot_cols[ tid ].init( nr_of_cols );
- idx_of_pivot_cols[ tid ] = -1;
- }
- Base::_set_num_cols( nr_of_cols );
- }
-
- void _add_to( index source, index target ) {
- if( !is_pivot_col( target ) )
- make_pivot_col( target );
- get_pivot_col().add_col( matrix[source] );
- }
-
- void _sync() {
- #pragma omp parallel for
- for( int tid = 0; tid < omp_get_num_threads(); tid++ )
- release_pivot_col();
- }
-
- void _get_col( index idx, column& col ) const { is_pivot_col( idx ) ? get_pivot_col().get_col( col ) : Base::_get_col( idx, col ); }
-
- bool _is_empty( index idx ) const { return is_pivot_col( idx ) ? get_pivot_col().is_empty() : Base::_is_empty( idx ); }
-
- index _get_max_index( index idx ) const { return is_pivot_col( idx ) ? get_pivot_col().get_max_index() : Base::_get_max_index( idx ); }
-
- void _clear( index idx ) { is_pivot_col( idx ) ? get_pivot_col().clear() : Base::_clear( idx ); }
-
- void _set_col( index idx, const column& col ) { is_pivot_col( idx ) ? get_pivot_col().set_col( col ) : Base::_set_col( idx, col ); }
-
- void _remove_max( index idx ) { is_pivot_col( idx ) ? get_pivot_col().remove_max() : Base::_remove_max( idx ); }
-
- void finalize( index idx ) { Base::_finalize( idx ); }
- };
-}
-
-
diff --git a/include/phat/representations/bit_tree_pivot_column.h b/include/phat/representations/bit_tree_pivot_column.h index 4d48e88..4779d70 100644 --- a/include/phat/representations/bit_tree_pivot_column.h +++ b/include/phat/representations/bit_tree_pivot_column.h @@ -19,7 +19,6 @@ #pragma once
#include <phat/helpers/misc.h>
-#include <phat/representations/abstract_pivot_column.h>
namespace phat {
@@ -133,6 +132,15 @@ namespace phat { std::reverse( out.begin(), out.end() );
}
+
+ template<typename InputIterator>
+ void add_col(InputIterator begin, InputIterator end) {
+ for(InputIterator it=begin;it!=end;it++) {
+ add_index(*it);
+ }
+ }
+
+
void add_col(const column &col) {
for( size_t i = 0; i < col.size(); ++i )
add_index(col[i]);
@@ -161,5 +169,4 @@ namespace phat { }
};
- typedef abstract_pivot_column<bit_tree_column> bit_tree_pivot_column;
}
diff --git a/include/phat/representations/default_representations.h b/include/phat/representations/default_representations.h new file mode 100644 index 0000000..a0f618f --- /dev/null +++ b/include/phat/representations/default_representations.h @@ -0,0 +1,47 @@ +/* Copyright 2013 IST Austria + Contributed by: Ulrich Bauer, Michael Kerber, 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> +#include <phat/representations/Uniform_representation.h> +#include <phat/representations/Pivot_representation.h> + +#include <phat/representations/sparse_pivot_column.h> +#include <phat/representations/full_pivot_column.h> +#include <phat/representations/heap_pivot_column.h> +#include <phat/representations/bit_tree_pivot_column.h> +#include <phat/representations/vector_column_rep.h> +#include <phat/representations/list_column_rep.h> +#include <phat/representations/set_column_rep.h> +#include <phat/representations/heap_column_rep.h> + + +namespace phat { + + // typedef Uniform_representation< std::unordered_map<index,phat::vector_column_rep>, std::unordered_map<index,index> > hash_vector; + typedef Uniform_representation< std::vector<phat::vector_column_rep>, std::vector<index> > vector_vector; + typedef Uniform_representation< std::vector<phat::set_column_rep>, std::vector<index> > vector_set; + typedef Uniform_representation< std::vector<phat::heap_column_rep>, std::vector<index> > vector_heap; + typedef Uniform_representation< std::vector<phat::list_column_rep>, std::vector<index> > vector_list; + typedef Pivot_representation< vector_vector, full_column > full_pivot_column; + typedef Pivot_representation< vector_vector, heap_column > heap_pivot_column; + typedef Pivot_representation< vector_vector, sparse_column > sparse_pivot_column; + typedef Pivot_representation< vector_vector, bit_tree_column > bit_tree_pivot_column; + +} diff --git a/include/phat/representations/full_pivot_column.h b/include/phat/representations/full_pivot_column.h index c2e9e3c..a6a09d1 100644 --- a/include/phat/representations/full_pivot_column.h +++ b/include/phat/representations/full_pivot_column.h @@ -19,7 +19,6 @@ #pragma once
#include <phat/helpers/misc.h>
-#include <phat/representations/abstract_pivot_column.h>
namespace phat {
class full_column {
@@ -35,6 +34,15 @@ namespace phat { is_in_history.resize( total_size, false );
}
+
+ template<typename InputIterator>
+ void add_col(InputIterator begin, InputIterator end) {
+ for(InputIterator it=begin;it!=end;it++) {
+ add_index(*it);
+ }
+ }
+
+
void add_col( const column& col ) {
for( index idx = 0; idx < (index) col.size(); idx++ ) {
add_index( col[ idx ] );
@@ -96,5 +104,4 @@ namespace phat { }
};
- typedef abstract_pivot_column< full_column > full_pivot_column;
}
diff --git a/include/phat/representations/heap_pivot_column.h b/include/phat/representations/heap_pivot_column.h index 33cd07b..c5e4313 100644 --- a/include/phat/representations/heap_pivot_column.h +++ b/include/phat/representations/heap_pivot_column.h @@ -19,7 +19,6 @@ #pragma once
#include <phat/helpers/misc.h>
-#include <phat/representations/abstract_pivot_column.h>
namespace phat {
class heap_column {
@@ -71,6 +70,18 @@ namespace phat { clear();
}
+
+ template<typename InputIterator>
+ void add_col(InputIterator begin, InputIterator end) {
+ for(InputIterator it=begin;it!=end;it++) {
+ data.push(*it);
+ inserts_since_last_prune++;
+ }
+ if( 2 * inserts_since_last_prune >( index ) data.size( ) )
+ prune();
+ }
+
+
void add_col( const column& col ) {
for( index idx = 0; idx < (index) col.size(); idx++ )
data.push( col[ idx ] );
@@ -122,5 +133,4 @@ namespace phat { }
};
- typedef abstract_pivot_column< heap_column > heap_pivot_column;
}
diff --git a/include/phat/representations/list_column_rep.h b/include/phat/representations/list_column_rep.h new file mode 100644 index 0000000..5de2652 --- /dev/null +++ b/include/phat/representations/list_column_rep.h @@ -0,0 +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 list_column_rep {
+
+ protected:
+ std::list< index > indices;
+
+ public:
+
+ typedef list_column_rep Self;
+
+ std::list<index>::const_iterator begin() const {
+ return indices.begin();
+ }
+
+ std::list<index>::const_iterator end() const {
+ return indices.end();
+ }
+
+ void offer_thread_local_storage(thread_local_storage< column >* tls) {
+ }
+
+ // replaces(!) content of 'col' with boundary of given index
+ void _get_col( column& col ) const {
+ col.clear();
+ col.reserve( indices.size() );
+ std::copy (indices.begin(), indices.end(), std::back_inserter(col) );
+ }
+
+ void _set_col( const column& col ) {
+ indices.clear();
+ indices.resize( col.size() );
+ std::copy (col.begin(), col.end(), indices.begin() );
+ }
+
+ // true iff boundary of given idx is empty
+ bool _is_empty() const {
+ return indices.empty();
+ }
+
+ // largest row index of given column idx (new name for lowestOne())
+ index _get_max_index() const {
+ return indices.empty() ? -1 : *indices.rbegin();
+ }
+
+ // removes the maximal index of a column
+ void _remove_max() {
+ std::list< index >::iterator it = indices.end();
+ it--;
+ indices.erase( it );
+ }
+
+ // clears given column
+ void _clear() {
+ indices.clear();
+ }
+
+ // syncronizes all data structures (essential for openmp stuff)
+ void _sync() {}
+
+ // adds column 'source' to column 'target'
+ void _add_to( Self& source) {
+ std::list< index >& source_col = source.indices;
+ std::list< index >& target_col = this->indices;
+ 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 ) );
+ }
+
+ // finalizes given column
+ void _finalize() {
+ }
+ };
+}
diff --git a/include/phat/representations/set_column_rep.h b/include/phat/representations/set_column_rep.h new file mode 100644 index 0000000..c43b74e --- /dev/null +++ b/include/phat/representations/set_column_rep.h @@ -0,0 +1,96 @@ +/* Copyright 2013 IST Austria + Contributed by: Ulrich Bauer, Michael Kerber, 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 set_column_rep { + + protected: + std::set< index > indices; + + public: + + typedef set_column_rep Self; + + std::set<index>::const_iterator begin() const { + return indices.begin(); + } + + std::set<index>::const_iterator end() const { + return indices.end(); + } + + void offer_thread_local_storage(thread_local_storage< column >* tls) { + } + + // replaces(!) content of 'col' with boundary of given index + void _get_col( column& col ) const { + col.clear(); + col.reserve( indices.size() ); + std::copy (indices.begin(), indices.end(), std::back_inserter(col) ); + } + void _set_col( const column& col ) { + indices.clear(); + indices.insert( col.begin(), col.end() ); + } + + // true iff boundary of given idx is empty + bool _is_empty() const { + return indices.empty(); + } + + // largest row index of given column idx (new name for lowestOne()) + index _get_max_index() const { + return indices.empty() ? -1 : *indices.rbegin(); + } + + // removes the maximal index of a column + void _remove_max() { + std::set< index >::iterator it = indices.end(); + it--; + indices.erase( it ); + } + + // clears given column + void _clear() { + indices.clear(); + } + + // syncronizes all data structures (essential for openmp stuff) + void _sync() {} + + // adds column 'source' to column 'target' + void _add_to( Self& source) { + + std::set< index >& col = this->indices; + for( std::set< index >::iterator it = source.indices.begin(); it != source.indices.end(); it++ ) { + std::pair< std::set< index >::iterator, bool > result = col.insert( *it ); + if( !result.second ) + col.erase( result.first ); + } + } + + // finalizes given column + void _finalize() { + } + + }; +} diff --git a/include/phat/representations/sparse_pivot_column.h b/include/phat/representations/sparse_pivot_column.h index 390fd91..bbaf98c 100644 --- a/include/phat/representations/sparse_pivot_column.h +++ b/include/phat/representations/sparse_pivot_column.h @@ -19,7 +19,6 @@ #pragma once
#include <phat/helpers/misc.h>
-#include <phat/representations/abstract_pivot_column.h>
namespace phat {
class sparse_column {
@@ -37,6 +36,15 @@ namespace phat { void init( const index total_size ) {
data.clear();
}
+
+
+ template<typename InputIterator>
+ void add_col(InputIterator begin, InputIterator end) {
+ for(InputIterator it=begin;it!=end;it++) {
+ add_index(*it);
+ }
+ }
+
void add_col( const column& col ) {
for( index idx = 0; idx < (index) col.size(); idx++ )
@@ -75,5 +83,4 @@ namespace phat { }
};
- typedef abstract_pivot_column< sparse_column > sparse_pivot_column;
}
diff --git a/include/phat/representations/vector_column_rep.h b/include/phat/representations/vector_column_rep.h new file mode 100644 index 0000000..22c37ef --- /dev/null +++ b/include/phat/representations/vector_column_rep.h @@ -0,0 +1,102 @@ +/* Copyright 2013 IST Austria + Contributed by: Ulrich Bauer, Michael Kerber, 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_column_rep { + + protected: + + std::vector<index> indices; + + thread_local_storage< column >* temp_column_buffer; + + public: + + typedef vector_column_rep Self; + + void offer_thread_local_storage(thread_local_storage< column >* tls) { + temp_column_buffer=tls; + } + + std::vector<index>::const_iterator begin() const { + return indices.begin(); + } + + std::vector<index>::const_iterator end() const { + return indices.end(); + } + + // replaces(!) content of 'col' with boundary of given index + void _get_col( column& col ) const { + col.clear(); + col = indices; + } + void _set_col( const column& col ) { + indices = col; + } + + // true iff boundary of given idx is empty + bool _is_empty() const { + return indices.empty(); + } + + // largest row index of given column idx (new name for lowestOne()) + index _get_max_index() const { + return indices.empty() ? -1 : indices.back(); + } + + // removes the maximal index of a column + void _remove_max() { + indices.pop_back(); + } + + // clears given column + void _clear() { + indices.clear(); + } + + // syncronizes all data structures (essential for openmp stuff) + void _sync() {} + + // adds column 'source' to column 'target' + void _add_to( const Self& source_col ) { + column& temp_col = (*temp_column_buffer)(); + + size_t new_size = source_col.indices.size() + this->indices.size(); + + if (new_size > temp_col.size()) temp_col.resize(new_size); + + std::vector<index>::iterator col_end = std::set_symmetric_difference( this->indices.begin(), this->indices.end(), + source_col.indices.begin(), source_col.indices.end(), + temp_col.begin() ); + temp_col.erase(col_end, temp_col.end()); + + + this->indices.swap(temp_col); + } + + // finalizes given column + void _finalize() { + column(indices.begin(), indices.end()).swap(indices); + } + }; +} diff --git a/include/phat/representations/vector_heap.h b/include/phat/representations/vector_heap.h deleted file mode 100644 index db0420f..0000000 --- a/include/phat/representations/vector_heap.h +++ /dev/null @@ -1,170 +0,0 @@ -/* 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_heap {
-
- protected:
- std::vector< dimension > dims;
- std::vector< column > matrix;
-
- std::vector< index > inserts_since_last_prune;
-
- mutable thread_local_storage< column > temp_column_buffer;
-
- protected:
- void _prune( index idx )
- {
- column& col = matrix[ idx ];
- column& temp_col = temp_column_buffer();
- temp_col.clear();
- index max_index = _pop_max_index( col );
- while( max_index != -1 ) {
- temp_col.push_back( max_index );
- max_index = _pop_max_index( col );
- }
- col = temp_col;
- std::reverse( col.begin( ), col.end( ) );
- std::make_heap( col.begin( ), col.end( ) );
- inserts_since_last_prune[ idx ] = 0;
- }
-
- index _pop_max_index( index idx )
- {
- return _pop_max_index( matrix[ idx ] );
- }
-
- index _pop_max_index( column& col ) const
- {
- if( col.empty( ) )
- return -1;
- else {
- index max_element = col.front( );
- std::pop_heap( col.begin( ), col.end( ) );
- col.pop_back( );
- while( !col.empty( ) && col.front( ) == max_element ) {
- std::pop_heap( col.begin( ), col.end( ) );
- col.pop_back( );
- if( col.empty( ) )
- return -1;
- else {
- max_element = col.front( );
- std::pop_heap( col.begin( ), col.end( ) );
- col.pop_back( );
- }
- }
- return max_element;
- }
- }
-
- 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 );
- inserts_since_last_prune.assign( nr_of_columns, 0 );
- }
-
- // 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
- {
- temp_column_buffer( ) = matrix[ idx ];
-
- index max_index = _pop_max_index( temp_column_buffer() );
- while( max_index != -1 ) {
- col.push_back( max_index );
- max_index = _pop_max_index( temp_column_buffer( ) );
- }
- std::reverse( col.begin( ), col.end( ) );
- }
- void _set_col( index idx, const column& col )
- {
- matrix[ idx ] = col;
- std::make_heap( matrix[ idx ].begin( ), matrix[ idx ].end( ) );
- }
-
- // true iff boundary of given idx is empty
- bool _is_empty( index idx ) const
- {
- return _get_max_index( idx ) == -1;
- }
-
- // largest row index of given column idx (new name for lowestOne())
- index _get_max_index( index idx ) const
- {
- column& col = const_cast< column& >( matrix[ idx ] );
- index max_element = _pop_max_index( col );
- col.push_back( max_element );
- std::push_heap( col.begin( ), col.end( ) );
- return max_element;
- }
-
- // removes the maximal index of a column
- void _remove_max( index idx )
- {
- _pop_max_index( idx );
- }
-
- // 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 )
- {
- for( index idx = 0; idx < (index)matrix[ source ].size( ); idx++ ) {
- matrix[ target ].push_back( matrix[ source ][ idx ] );
- std::push_heap( matrix[ target ].begin(), matrix[ target ].end() );
- }
- inserts_since_last_prune[ target ] += matrix[ source ].size();
-
- if( 2 * inserts_since_last_prune[ target ] > ( index )matrix[ target ].size() )
- _prune( target );
- }
-
- // finalizes given column
- void _finalize( index idx ) {
- _prune( idx );
- }
-
- };
-}
diff --git a/include/phat/representations/vector_list.h b/include/phat/representations/vector_list.h deleted file mode 100644 index ca0b5b8..0000000 --- a/include/phat/representations/vector_list.h +++ /dev/null @@ -1,101 +0,0 @@ -/* 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 ) );
- }
-
- // finalizes given column
- void _finalize( index idx ) {
- }
- };
-}
diff --git a/include/phat/representations/vector_set.h b/include/phat/representations/vector_set.h deleted file mode 100644 index 6878a27..0000000 --- a/include/phat/representations/vector_set.h +++ /dev/null @@ -1,99 +0,0 @@ -/* Copyright 2013 IST Austria - Contributed by: Ulrich Bauer, Michael Kerber, 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_set { - - protected: - std::vector< dimension > dims; - std::vector< std::set< 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 ].insert( col.begin(), col.end() ); - } - - // 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::set< 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 ) { - 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 ); - } - } - - // finalizes given column - void _finalize( index idx ) { - } - - }; -} diff --git a/include/phat/representations/vector_vector.h b/include/phat/representations/vector_vector.h deleted file mode 100644 index f111d6b..0000000 --- a/include/phat/representations/vector_vector.h +++ /dev/null @@ -1,107 +0,0 @@ -/* Copyright 2013 IST Austria
- Contributed by: Ulrich Bauer, Michael Kerber, 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_vector {
-
- protected:
- std::vector< dimension > dims;
- std::vector< column > matrix;
-
- thread_local_storage< column > temp_column_buffer;
-
- 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 = matrix[ idx ];
- }
- void _set_col( index idx, const column& col ) {
- matrix[ idx ] = col;
- }
-
- // 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 ].back();
- }
-
- // removes the maximal index of a column
- void _remove_max( index idx ) {
- matrix[ idx ].pop_back();
- }
-
- // 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 ) {
- column& source_col = matrix[ source ];
- column& target_col = matrix[ target ];
- column& temp_col = temp_column_buffer();
-
-
- size_t new_size = source_col.size() + target_col.size();
-
- if (new_size > temp_col.size()) temp_col.resize(new_size);
-
- std::vector<index>::iterator col_end = std::set_symmetric_difference( target_col.begin(), target_col.end(),
- source_col.begin(), source_col.end(),
- temp_col.begin() );
- temp_col.erase(col_end, temp_col.end());
-
-
- target_col.swap(temp_col);
- }
-
- // finalizes given column
- void _finalize( index idx ) {
- column& col = matrix[ idx ];
- column(col.begin(), col.end()).swap(col);
- }
- };
-}
|