From fb02e45712d44f217dfbd71910ea533894c065e6 Mon Sep 17 00:00:00 2001 From: "jan.reininghaus@gmail.com" Date: Sun, 12 May 2013 20:42:59 +0000 Subject: simplified pivot column representations git-svn-id: https://phat.googlecode.com/svn/trunk@84 8e3bb3c2-eed4-f18f-5264-0b6c94e6926d --- .../phat/representations/abstract_pivot_column.h | 47 +---- .../phat/representations/bit_tree_pivot_column.h | 25 +++ include/phat/representations/full_pivot_column.h | 20 +++ include/phat/representations/sparse_pivot_column.h | 19 +++ include/phat/representations/vector_list.h | 189 ++++++++++----------- include/phat/representations/vector_set.h | 22 +-- 6 files changed, 171 insertions(+), 151 deletions(-) (limited to 'include') 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 @@ -152,6 +152,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 ); } }; 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 @@ -74,6 +74,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 ); } }; 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 @@ -55,6 +55,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 ); } }; 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 . */ - -#pragma once - -#include - -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 . */ + +#pragma once + +#include + +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 ); + } } }; } -- cgit v1.2.3