From 595ce965ef6e07c554a91ebb8b41c8e1c06b8b32 Mon Sep 17 00:00:00 2001 From: "jan.reininghaus" Date: Tue, 14 May 2013 09:59:44 +0000 Subject: cleaned up pivot column source git-svn-id: https://phat.googlecode.com/svn/trunk@85 8e3bb3c2-eed4-f18f-5264-0b6c94e6926d --- .../phat/representations/abstract_pivot_column.h | 93 ++++++++-------------- .../phat/representations/bit_tree_pivot_column.h | 28 +++---- include/phat/representations/full_pivot_column.h | 28 +++---- include/phat/representations/sparse_pivot_column.h | 28 +++---- 4 files changed, 75 insertions(+), 102 deletions(-) (limited to 'include') diff --git a/include/phat/representations/abstract_pivot_column.h b/include/phat/representations/abstract_pivot_column.h index e3598aa..f441537 100644 --- a/include/phat/representations/abstract_pivot_column.h +++ b/include/phat/representations/abstract_pivot_column.h @@ -28,93 +28,70 @@ namespace phat { // make sense template< typename PivotColumn > class abstract_pivot_column : public vector_vector { - public: protected: typedef vector_vector Base; - typedef PivotColumn pivot_column; + typedef PivotColumn pivot_col; // 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; + mutable thread_local_storage< pivot_col > pivot_cols; + mutable thread_local_storage< index > idx_of_pivot_cols; - pivot_column& get_pivot_column() const { - return _pivot_columns(); + pivot_col& get_pivot_col() const { + return pivot_cols(); } - bool is_represented_by_pivot_column( index idx ) const { - return pos_of_pivot_columns() == idx; + bool is_pivot_col( index idx ) const { + return idx_of_pivot_cols() == 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 release_pivot_col() { + index idx = idx_of_pivot_cols(); + if( idx != -1 ) + pivot_cols().get_col_and_clear( this->matrix[ idx ] ); + idx_of_pivot_cols() = -1; } - void represent_by_pivot_column( index idx ) { - pos_of_pivot_columns() = idx; - get_pivot_column().add_column( matrix[ idx ] ); + 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_columns ) { + void _set_num_cols( index nr_of_cols ) { #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; + pivot_cols[ tid ].init( nr_of_cols ); + idx_of_pivot_cols[ 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 { - 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 - bool _is_empty( index idx ) const { - return is_represented_by_pivot_column( idx ) ? get_pivot_column().empty() : Base::_is_empty( idx ); + Base::_set_num_cols( nr_of_cols ); } - // largest row index of given column idx (new name for lowestOne()) - index _get_max_index( index idx ) const { - return is_represented_by_pivot_column( idx ) ? get_pivot_column().max_index() : 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 ) { - is_represented_by_pivot_column( idx ) ? get_pivot_column().clear() : Base::_clear( idx ); + if( !is_pivot_col( target ) ) + make_pivot_col( target ); + get_pivot_col().add_col( matrix[source] ); } - void _set_col( index idx, const column& 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 ) { - is_represented_by_pivot_column( idx ) ? get_pivot_column().remove_max() : Base::_remove_max( 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(); + 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 ); } }; } diff --git a/include/phat/representations/bit_tree_pivot_column.h b/include/phat/representations/bit_tree_pivot_column.h index f997434..e8746f8 100644 --- a/include/phat/representations/bit_tree_pivot_column.h +++ b/include/phat/representations/bit_tree_pivot_column.h @@ -69,7 +69,7 @@ namespace phat { data.resize(upper_blocks + bottom_blocks_needed, 0); } - index max_index() const + index get_max_index() const { if (!data[0]) return -1; @@ -95,7 +95,7 @@ namespace phat { return -1; } - bool empty() const + bool is_empty() const { return data[0] == 0; } @@ -127,12 +127,12 @@ namespace phat { } } - void get_column_and_clear(column &out) + void get_col_and_clear(column &out) { out.clear(); while(true) { - index mx = this->max_index(); + index mx = this->get_max_index(); if (mx == -1) break; out.push_back(mx); @@ -142,7 +142,7 @@ namespace phat { std::reverse(out.begin(), out.end()); } - void add_column(const column &col) + void add_col(const column &col) { for (size_t i = 0; i < col.size(); ++i) { @@ -150,14 +150,10 @@ namespace phat { } } - bool empty() { - return !data[0]; - } - void clear() { while(true) { - index mx = this->max_index(); + index mx = this->get_max_index(); if (mx == -1) break; add_index(mx); @@ -165,22 +161,22 @@ namespace phat { } void remove_max() { - add_index( max_index() ); + add_index( get_max_index() ); } void set_col( const column& col ) { clear(); - add_column( col ); + add_col( col ); } void get_col( column& col ) { col.clear(); - get_column_and_clear( col ); - add_column( col ); + get_col_and_clear( col ); + add_col( col ); } }; - const size_t bit_tree_column::debrujin_magic_table[64] = { + const size_t bit_tree_column::debrujin_magic_table[64] = { 63, 0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3, 61, 51, 37, 40, 49, 18, 28, 20, @@ -188,7 +184,7 @@ namespace phat { 62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21, 56, 45, 25, 31, 35, 16, 9, 12, - 44, 24, 15, 8, 23, 7, 6, 5}; + 44, 24, 15, 8, 23, 7, 6, 5 }; typedef abstract_pivot_column bit_tree_pivot_column; } diff --git a/include/phat/representations/full_pivot_column.h b/include/phat/representations/full_pivot_column.h index ce7b9f1..b83683f 100644 --- a/include/phat/representations/full_pivot_column.h +++ b/include/phat/representations/full_pivot_column.h @@ -35,7 +35,7 @@ namespace phat { m_isInHistory.resize( total_size, false ); } - void add_column( const column& col ) { + void add_col( const column& col ) { for( index idx = 0; idx < (index) col.size(); idx++ ) { add_index( col[ idx ] ); } @@ -49,7 +49,7 @@ namespace phat { m_data[ idx ] = !m_data[ idx ]; } - index max_index() { + index get_max_index() { while( m_history.size() > 0 ) { index topIndex = m_history.top(); if( m_data[ topIndex ] ) { @@ -63,37 +63,37 @@ namespace phat { return -1; } - void get_column_and_clear( column& col ) { + void get_col_and_clear( column& col ) { col.clear(); - while( !empty() ) { - col.push_back( max_index() ); - add_index( max_index() ); + while( !is_empty() ) { + col.push_back( get_max_index() ); + add_index( get_max_index() ); } std::reverse( col.begin(), col.end() ); } - bool empty() { - return (max_index() == -1); + bool is_empty() { + return (get_max_index() == -1); } void clear() { - while( !empty() ) - add_index( max_index() ); + while( !is_empty() ) + add_index( get_max_index() ); } void remove_max() { - add_index( max_index() ); + add_index( get_max_index() ); } void set_col( const column& col ) { clear(); - add_column( col ); + add_col( col ); } void get_col( column& col ) { col.clear(); - get_column_and_clear( col ); - add_column( col ); + get_col_and_clear( col ); + add_col( col ); } }; diff --git a/include/phat/representations/sparse_pivot_column.h b/include/phat/representations/sparse_pivot_column.h index f4eab8b..9e39950 100644 --- a/include/phat/representations/sparse_pivot_column.h +++ b/include/phat/representations/sparse_pivot_column.h @@ -27,33 +27,33 @@ namespace phat { protected: std::set< index > m_data; + 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 ); + } + public: void init( const index total_size ) { m_data.clear(); } - void add_column( const column& col ) { + void add_col( 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() { + index get_max_index() { return m_data.empty() ? -1 : *m_data.rbegin(); } - void get_column_and_clear( column& col ) { + void get_col_and_clear( column& col ) { col.clear(); col.assign( m_data.begin(), m_data.end() ); m_data.clear(); } - bool empty() { + bool is_empty() { return m_data.empty(); } @@ -62,18 +62,18 @@ namespace phat { } void remove_max() { - add_index( max_index() ); + add_index( get_max_index() ); } void set_col( const column& col ) { clear(); - add_column( col ); + add_col( col ); } void get_col( column& col ) { col.clear(); - get_column_and_clear( col ); - add_column( col ); + get_col_and_clear( col ); + add_col( col ); } }; -- cgit v1.2.3