From c817c81d9d79fe77b0729216b7db5a7eab56a23c Mon Sep 17 00:00:00 2001 From: "ulrich.bauer@gmail.com" Date: Thu, 28 Feb 2013 19:31:04 +0000 Subject: initial checkin git-svn-id: https://phat.googlecode.com/svn/trunk@2 8e3bb3c2-eed4-f18f-5264-0b6c94e6926d --- .../phat/representations/abstract_pivot_column.h | 158 +++++++++++++++++++++ include/phat/representations/full_pivot_column.h | 81 +++++++++++ include/phat/representations/sparse_pivot_column.h | 62 ++++++++ include/phat/representations/vector_set.h | 104 ++++++++++++++ include/phat/representations/vector_vector.h | 90 ++++++++++++ 5 files changed, 495 insertions(+) create mode 100644 include/phat/representations/abstract_pivot_column.h create mode 100644 include/phat/representations/full_pivot_column.h create mode 100644 include/phat/representations/sparse_pivot_column.h create mode 100644 include/phat/representations/vector_set.h create mode 100644 include/phat/representations/vector_vector.h (limited to 'include/phat/representations') diff --git a/include/phat/representations/abstract_pivot_column.h b/include/phat/representations/abstract_pivot_column.h new file mode 100644 index 0000000..a84e013 --- /dev/null +++ b/include/phat/representations/abstract_pivot_column.h @@ -0,0 +1,158 @@ +/* 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 . */ + +#pragma once + +#include +#include + +namespace phat { + + // Note: We could even make the rep generic in the underlying Const representation + // But I cannot imagine that anything else than vector> would + // make sense + template< typename PivotColumn > + class abstract_pivot_column : public vector_vector { + public: + + protected: + typedef vector_vector Base; + typedef PivotColumn pivot_column; + + // For parallization purposes, it could be more than one full column + mutable thread_local_storage< pivot_column > _pivot_columns; + mutable thread_local_storage< index > pos_of_pivot_columns; + + pivot_column& get_pivot_column() const { + return _pivot_columns(); + } + + bool is_represented_by_pivot_column( index idx ) const { + return pos_of_pivot_columns() == idx; + } + + void unset_pos_of_pivot_column() { + index idx = pos_of_pivot_columns(); + if( idx != -1 ) { + _pivot_columns().get_column_and_clear( this->matrix[ idx ] ); + } + pos_of_pivot_columns() = -1; + } + + void represent_by_pivot_column( index idx ) { + pos_of_pivot_columns() = idx; + get_pivot_column().add_column( matrix[ idx ] ); + } + + public: + + void _set_num_cols( index nr_of_columns ) { + #pragma omp parallel for + for( int tid = 0; tid < omp_get_num_threads(); tid++ ) { + _pivot_columns[ tid ].init( nr_of_columns ); + pos_of_pivot_columns[ tid ] = -1; + } + Base::_set_num_cols( nr_of_columns ); + } + // 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 ); + } + } + + // true iff boundary of given idx is empty + bool _is_empty( index idx ) const { + return is_represented_by_pivot_column( idx ) ? get_pivot_column().empty() : Base::_is_empty( idx ); + } + + // 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 ); + } + } + + // adds column 'source' to column 'target' + void _add_to( index source, index target ) { + if( !is_represented_by_pivot_column( target ) ) { + unset_pos_of_pivot_column(); + represent_by_pivot_column( target ); + } + get_pivot_column().add_column( matrix[source] ); + } + + // 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 ); + } + } + + 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 ); + } + } + + // 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 ); + } + + // syncronizes all data structures (essential for openmp stuff) + // has to be called before and after any multithreaded access! + void _sync() { + #pragma omp parallel for + for( int tid = 0; tid < omp_get_num_threads(); tid++ ) + unset_pos_of_pivot_column(); + } + + }; +} + + diff --git a/include/phat/representations/full_pivot_column.h b/include/phat/representations/full_pivot_column.h new file mode 100644 index 0000000..9e0c348 --- /dev/null +++ b/include/phat/representations/full_pivot_column.h @@ -0,0 +1,81 @@ +/* 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 . */ + +#pragma once + +#include +#include + +namespace phat { + class full_column { + + protected: + std::priority_queue< index > m_history; + std::vector< char > m_isInHistory; + std::vector< char > m_data; + + public: + void init( const index total_size ) { + m_data.resize( total_size, false ); + m_isInHistory.resize( total_size, false ); + } + + void add_column( const column& col ) { + for( index idx = 0; idx < (index) col.size(); idx++ ) { + add_index( col[ idx ] ); + } + } + void add_index( const index idx ) { + if( !m_isInHistory[ idx ] ) { + m_history.push( idx ); + m_isInHistory[ idx ] = true; + } + + m_data[ idx ] = !m_data[ idx ]; + } + + index max_index() { + while( m_history.size() > 0 ) { + index topIndex = m_history.top(); + if( m_data[ topIndex ] ) { + return topIndex; + } else { + m_history.pop(); + m_isInHistory[ topIndex ] = false; + } + } + + return -1; + } + + void get_column_and_clear( column& col ) { + col.clear(); + while( !empty() ) { + col.push_back( max_index() ); + add_index( max_index() ); + } + std::reverse( col.begin(), col.end() ); + } + + bool empty() { + return (max_index() == -1); + } + }; + + 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 new file mode 100644 index 0000000..c851a2b --- /dev/null +++ b/include/phat/representations/sparse_pivot_column.h @@ -0,0 +1,62 @@ +/* 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 . */ + +#pragma once + +#include +#include + +namespace phat { + class sparse_column { + + protected: + std::set< index > m_data; + + public: + void init( const index total_size ) { + m_data.clear(); + } + + void add_column( const column& col ) { + for( index idx = 0; idx < (index) col.size(); idx++ ) + add_index( col[ idx ] ); + } + + void add_index( const index idx ) { + std::pair< std::set< index >::iterator, bool > result = m_data.insert( idx ); + if( result.second == false ) + m_data.erase( result.first ); + } + + index max_index() { + return m_data.empty() ? -1 : *m_data.rbegin(); + } + + void get_column_and_clear( column& col ) { + col.clear(); + col.assign( m_data.begin(), m_data.end() ); + m_data.clear(); + } + + bool empty() { + return m_data.empty(); + } + }; + + typedef abstract_pivot_column< sparse_column > sparse_pivot_column; +} diff --git a/include/phat/representations/vector_set.h b/include/phat/representations/vector_set.h new file mode 100644 index 0000000..2ce0c56 --- /dev/null +++ b/include/phat/representations/vector_set.h @@ -0,0 +1,104 @@ +/* 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 . */ + +#pragma once + +#include + +namespace phat { + class vector_set { + + protected: + typedef std::set< 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) ); + std::sort( col.begin(), col.end() ); + } + 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 ) { + 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 ]; + for( internal_column::const_iterator source_it = source_col.begin(); + source_it != source_col.end(); source_it++ ) { + _toggle(target, *source_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 ); + } + } + }; +} diff --git a/include/phat/representations/vector_vector.h b/include/phat/representations/vector_vector.h new file mode 100644 index 0000000..c313c20 --- /dev/null +++ b/include/phat/representations/vector_vector.h @@ -0,0 +1,90 @@ +/* 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 . */ + +#pragma once + +#include + +namespace phat { + class vector_vector { + + protected: + std::vector< dimension > dims; + std::vector< 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 = 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 = target_col; + target_col.clear(); + std::set_symmetric_difference( temp_col.begin(), temp_col.end(), + source_col.begin(), source_col.end(), + std::back_inserter( target_col ) ); + } + }; +} -- cgit v1.2.3