From de97fb40e2a75226578616201f3ee680e88b809e Mon Sep 17 00:00:00 2001 From: "jan.reininghaus" Date: Fri, 12 Apr 2013 11:18:34 +0000 Subject: converted tabs to spaces git-svn-id: https://phat.googlecode.com/svn/trunk@31 8e3bb3c2-eed4-f18f-5264-0b6c94e6926d --- .../phat/representations/bit_tree_pivot_column.h | 280 ++++++++++----------- src/phat.cpp | 16 +- 2 files changed, 148 insertions(+), 148 deletions(-) diff --git a/include/phat/representations/bit_tree_pivot_column.h b/include/phat/representations/bit_tree_pivot_column.h index b33e786..f9904c5 100644 --- a/include/phat/representations/bit_tree_pivot_column.h +++ b/include/phat/representations/bit_tree_pivot_column.h @@ -23,147 +23,147 @@ namespace phat { - // This is a bitset indexed with a 64-ary tree. Each node in the index - // has 64 bits; i-th bit says that the i-th subtree is non-empty. - // Supports practically O(1), inplace, zero-allocation: insert, remove, max_element - // and clear in O(number of ones in the bitset). - // 'add_index' is still the real bottleneck in practice. - class bit_tree_column - { - size_t offset; // data[i + offset] = ith block of the data-bitset - typedef uint64_t block_type; - std::vector< block_type > data; - - // this static is not a problem with OMP, it's initialized just after program starts - static const size_t debrujin_magic_table[64]; - - enum { block_size_in_bits = 64 }; - enum { block_shift = 6 }; - - // Some magic: http://graphics.stanford.edu/~seander/bithacks.html - // Gets the position of the rightmost bit of 'x'. 0 means the most significant bit. - // (-x)&x isolates the rightmost bit. - // The whole method is much faster than calling log2i, and very comparable to using ScanBitForward/Reverse intrinsic, - // which should be one CPU instruction, but is not portable. - inline size_t rightmost_pos(const block_type value) const - { - return 64 - 1 - debrujin_magic_table[((value & (-value))*0x07EDD5E59A4E28C2) >> 58]; - } - - public: - - void init(index num_cols) - { - int64_t n = 1; // in case of overflow - size_t bottom_blocks_needed = (num_cols+block_size_in_bits-1)/block_size_in_bits; - size_t upper_blocks = 1; - - // How many blocks/nodes of index needed to index the whole bitset? - while(n * block_size_in_bits < bottom_blocks_needed) - { - n *= block_size_in_bits; - upper_blocks += n; - } - - offset = upper_blocks; - data.resize(upper_blocks + bottom_blocks_needed, 0); - } - - inline index max_index() const - { - if (!data[0]) - return -1; - - const size_t size = data.size(); - size_t n = 0; - - while(true) - { - const block_type val = data[n]; - const size_t index = rightmost_pos(val); - const size_t newn = (n << block_shift) + index + 1; - - if (newn >= size) - { - const size_t bottom_index = n - offset; - return (bottom_index << block_shift) + index; - } - - n = newn; - } - - return -1; - } - - inline bool empty() const - { - return data[0] == 0; - } - - inline void add_index(const size_t entry) - { - const block_type ONE = 1; - const block_type block_modulo_mask = ((ONE << block_shift) - 1); - size_t index_in_level = entry >> block_shift; - size_t address = index_in_level + offset; - size_t index_in_block = entry & block_modulo_mask; - - block_type mask = (ONE << (block_size_in_bits - index_in_block - 1)); - - while(true) - { - data[address]^=mask; - - // First we check if we reached the root. - // Also, if anyone else was in this block, we don't need to update the path up. - if (!address || (data[address] & ~mask)) - return; - - index_in_block = index_in_level & block_modulo_mask; - index_in_level >>= block_shift; - --address; - address >>= block_shift; - mask = (ONE << (block_size_in_bits - index_in_block - 1)); - } - } - - void get_column_and_clear(column &out) - { - out.clear(); - while(true) - { - index mx = this->max_index(); - if (mx == -1) - break; - out.push_back(mx); - add_index(mx); - } - - std::reverse(out.begin(), out.end()); - } - - void add_column(const column &col) - { - for (size_t i = 0; i < col.size(); ++i) - { - add_index(col[i]); - } - } + // This is a bitset indexed with a 64-ary tree. Each node in the index + // has 64 bits; i-th bit says that the i-th subtree is non-empty. + // Supports practically O(1), inplace, zero-allocation: insert, remove, max_element + // and clear in O(number of ones in the bitset). + // 'add_index' is still the real bottleneck in practice. + class bit_tree_column + { + size_t offset; // data[i + offset] = ith block of the data-bitset + typedef uint64_t block_type; + std::vector< block_type > data; + + // this static is not a problem with OMP, it's initialized just after program starts + static const size_t debrujin_magic_table[64]; + + enum { block_size_in_bits = 64 }; + enum { block_shift = 6 }; + + // Some magic: http://graphics.stanford.edu/~seander/bithacks.html + // Gets the position of the rightmost bit of 'x'. 0 means the most significant bit. + // (-x)&x isolates the rightmost bit. + // The whole method is much faster than calling log2i, and very comparable to using ScanBitForward/Reverse intrinsic, + // which should be one CPU instruction, but is not portable. + inline size_t rightmost_pos(const block_type value) const + { + return 64 - 1 - debrujin_magic_table[((value & (-value))*0x07EDD5E59A4E28C2) >> 58]; + } + + public: + + void init(index num_cols) + { + int64_t n = 1; // in case of overflow + size_t bottom_blocks_needed = (num_cols+block_size_in_bits-1)/block_size_in_bits; + size_t upper_blocks = 1; + + // How many blocks/nodes of index needed to index the whole bitset? + while(n * block_size_in_bits < bottom_blocks_needed) + { + n *= block_size_in_bits; + upper_blocks += n; + } + + offset = upper_blocks; + data.resize(upper_blocks + bottom_blocks_needed, 0); + } + + inline index max_index() const + { + if (!data[0]) + return -1; + + const size_t size = data.size(); + size_t n = 0; + + while(true) + { + const block_type val = data[n]; + const size_t index = rightmost_pos(val); + const size_t newn = (n << block_shift) + index + 1; + + if (newn >= size) + { + const size_t bottom_index = n - offset; + return (bottom_index << block_shift) + index; + } + + n = newn; + } + + return -1; + } + + inline bool empty() const + { + return data[0] == 0; + } + + inline void add_index(const size_t entry) + { + const block_type ONE = 1; + const block_type block_modulo_mask = ((ONE << block_shift) - 1); + size_t index_in_level = entry >> block_shift; + size_t address = index_in_level + offset; + size_t index_in_block = entry & block_modulo_mask; + + block_type mask = (ONE << (block_size_in_bits - index_in_block - 1)); + + while(true) + { + data[address]^=mask; + + // First we check if we reached the root. + // Also, if anyone else was in this block, we don't need to update the path up. + if (!address || (data[address] & ~mask)) + return; + + index_in_block = index_in_level & block_modulo_mask; + index_in_level >>= block_shift; + --address; + address >>= block_shift; + mask = (ONE << (block_size_in_bits - index_in_block - 1)); + } + } + + void get_column_and_clear(column &out) + { + out.clear(); + while(true) + { + index mx = this->max_index(); + if (mx == -1) + break; + out.push_back(mx); + add_index(mx); + } + + std::reverse(out.begin(), out.end()); + } + + void add_column(const column &col) + { + for (size_t i = 0; i < col.size(); ++i) + { + add_index(col[i]); + } + } inline bool empty() { - return !data[0]; + return !data[0]; } - }; - - 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, - 55, 30, 34, 11, 43, 14, 22, 4, - 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}; - - typedef abstract_pivot_column bit_tree_pivot_column; + }; + + 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, + 55, 30, 34, 11, 43, 14, 22, 4, + 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}; + + typedef abstract_pivot_column bit_tree_pivot_column; } diff --git a/src/phat.cpp b/src/phat.cpp index 43ebedc..2b48088 100644 --- a/src/phat.cpp +++ b/src/phat.cpp @@ -69,7 +69,7 @@ void parse_command_line( int argc, char** argv, bool& use_binary, Representation else if( option == "--vector_vector" ) rep_type = VECTOR_VECTOR; else if( option == "--vector_set" ) rep_type = VECTOR_SET; else if( option == "--full_pivot_column" ) rep_type = FULL_PIVOT_COLUMN; - else if( option == "--bit_tree_pivot_column" ) rep_type = BIT_TREE_PIVOT_COLUMN; + else if( option == "--bit_tree_pivot_column" ) rep_type = BIT_TREE_PIVOT_COLUMN; else if( option == "--sparse_pivot_column" ) rep_type = SPARSE_PIVOT_COLUMN; else if( option == "--standard" ) reduction = STANDARD; else if( option == "--twist" ) reduction = TWIST; @@ -86,8 +86,8 @@ void parse_command_line( int argc, char** argv, bool& use_binary, Representation template void generic_compute_pairing( std::string input_filename, std::string output_filename, - bool use_binary, - bool verbose, + bool use_binary, + bool verbose, bool dualize ) { phat::boundary_matrix< Representation > matrix; @@ -95,7 +95,7 @@ void generic_compute_pairing( std::string input_filename, double read_timer = omp_get_wtime(); if( use_binary ) { - LOG( "Reading input file " << input_filename << " in binary mode" ) + LOG( "Reading input file " << input_filename << " in binary mode" ) read_successful = matrix.load_binary( input_filename ); } else { LOG( "Reading input file " << input_filename << " in ascii mode" ) @@ -134,8 +134,8 @@ void generic_compute_pairing( std::string input_filename, int main( int argc, char** argv ) { bool use_binary = true; // interpret input as binary or ascii file - Representation_type rep_type = BIT_TREE_PIVOT_COLUMN; // representation class - Algorithm_type reduction = CHUNK; // reduction algorithm + Representation_type rep_type = BIT_TREE_PIVOT_COLUMN; // representation class + Algorithm_type reduction = CHUNK; // reduction algorithm std::string input_filename; // name of file that contains the boundary matrix std::string output_filename; // name of file that will contain the persistence pairs bool verbose = false; // print timings / info @@ -165,8 +165,8 @@ int main( int argc, char** argv ) case CHUNK: CALL_GENERIC_CODE(phat::full_pivot_column, phat::chunk_reduction) break; } break; - case BIT_TREE_PIVOT_COLUMN: switch( reduction ) { - case STANDARD: CALL_GENERIC_CODE(phat::bit_tree_pivot_column, phat::standard_reduction) break; + case BIT_TREE_PIVOT_COLUMN: switch( reduction ) { + case STANDARD: CALL_GENERIC_CODE(phat::bit_tree_pivot_column, phat::standard_reduction) break; case TWIST: CALL_GENERIC_CODE(phat::bit_tree_pivot_column, phat::twist_reduction) break; case ROW: CALL_GENERIC_CODE(phat::bit_tree_pivot_column, phat::row_reduction) break; case CHUNK: CALL_GENERIC_CODE(phat::bit_tree_pivot_column, phat::chunk_reduction) break; -- cgit v1.2.3