Module: ppl/ppl Branch: sparse_matrices Commit: 6d75380ef8478339ba0145cae153f096f8111ff0 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6d75380ef8478... Author: Marco Poletti <poletti.marco@gmail.com> Date: Fri May 7 17:32:36 2010 +0200 CO_Tree: use height_t instead of dimension_type for node heights and depths. --- src/CO_Tree.cc | 18 +++++++++--------- src/CO_Tree.defs.hh | 20 ++++++++++---------- src/CO_Tree.inlines.hh | 14 +++++++------- 3 files changed, 26 insertions(+), 26 deletions(-) diff --git a/src/CO_Tree.cc b/src/CO_Tree.cc index afc2807..d33e9a1 100644 --- a/src/CO_Tree.cc +++ b/src/CO_Tree.cc @@ -165,7 +165,7 @@ PPL::CO_Tree::init(dimension_type reserved_size1) { return; } - dimension_type l = 0; + height_t l = 0; if (reserved_size1 == 0) reserved_size1 = 1; @@ -504,8 +504,8 @@ PPL::CO_Tree::rebalance(inorder_iterator& itr, dimension_type key, PPL_ASSERT(!itr.get_right_child_value()); } #endif - dimension_type itr_depth_minus_1 = itr.depth() - 1; - dimension_type height = max_depth - itr_depth_minus_1; + height_t itr_depth_minus_1 = itr.depth() - 1; + height_t height = max_depth - itr_depth_minus_1; dimension_type subtree_size; const bool deleting = itr->first == unused_index; PPL_ASSERT(deleting || key != unused_index); @@ -641,7 +641,7 @@ PPL::CO_Tree::count_used_in_subtree(inorder_iterator& itr) { dimension_type n = 0; #ifdef USE_PPL_CO_TREE_VEB_LAYOUT - const dimension_type depth = itr.depth(); + const height_t depth = itr.depth(); #ifndef NDEBUG const dimension_type root_index = itr->first; @@ -711,7 +711,7 @@ PPL::CO_Tree::count_used_in_subtree(inorder_const_iterator& itr) { dimension_type n = 0; #ifdef USE_PPL_CO_TREE_VEB_LAYOUT - const dimension_type depth = itr.depth(); + const height_t depth = itr.depth(); #ifndef NDEBUG const dimension_type root_index = itr->first; @@ -833,7 +833,7 @@ PPL::CO_Tree #endif #ifdef USE_PPL_CO_TREE_VEB_LAYOUT - const dimension_type depth = root.depth(); + const height_t depth = root.depth(); #endif // defined(USE_PPL_CO_TREE_DFS_LAYOUT) while (root.get_right_child_value()) @@ -995,7 +995,7 @@ PPL::CO_Tree #ifdef USE_PPL_CO_TREE_VEB_LAYOUT const PPL::CO_Tree::level_data* -PPL::CO_Tree::Level_Data_Cache::get_level_data(dimension_type height) { +PPL::CO_Tree::Level_Data_Cache::get_level_data(height_t height) { PPL_ASSERT(height >= 2); if (cache[height] == NULL) { cache[height] = new level_data[height]; @@ -1007,12 +1007,12 @@ PPL::CO_Tree::Level_Data_Cache::get_level_data(dimension_type height) { void PPL::CO_Tree::Level_Data_Cache ::fill_level_data(level_data* p, - dimension_type min_depth, dimension_type max_depth) { + height_t min_depth, height_t max_depth) { PPL_ASSERT(p != NULL); if (min_depth == max_depth) return; - dimension_type d0 = (min_depth + max_depth) / 2; + height_t d0 = (min_depth + max_depth) / 2; p[d0].depth_of_root_of_top_tree = min_depth; p[d0].bottom_tree_size = ((dimension_type)1 << (max_depth - d0)) - 1; diff --git a/src/CO_Tree.defs.hh b/src/CO_Tree.defs.hh index ebbba0f..0960519 100644 --- a/src/CO_Tree.defs.hh +++ b/src/CO_Tree.defs.hh @@ -266,7 +266,7 @@ private: struct level_data { dimension_type bottom_tree_size; dimension_type top_tree_size; - dimension_type depth_of_root_of_top_tree; + height_t depth_of_root_of_top_tree; }; #ifdef USE_PPL_CO_TREE_VEB_LAYOUT @@ -274,14 +274,14 @@ private: public: - static const level_data* get_level_data(dimension_type height); + static const level_data* get_level_data(height_t height); private: - static const dimension_type max_depth = sizeof(dimension_type)*CHAR_BIT; + static const height_t max_depth = sizeof(dimension_type)*CHAR_BIT; - static void fill_level_data(level_data* p, dimension_type min_depth, - dimension_type max_depth); + static void fill_level_data(level_data* p, height_t min_depth, + height_t max_depth); //! cache[0] and cache[1] are not used. //! cache[i] contains NULL if get_level_data(i) has not been called yet, @@ -410,7 +410,7 @@ private: #endif // defined(USE_PPL_CO_TREE_VEB_LAYOUT) //! The depth of the leaves in the static tree. - dimension_type max_depth; + height_t max_depth; //! The vector that contains the keys in the tree. //! If a pair has \p unused_index as first element, it means it is not used. @@ -530,14 +530,14 @@ public: bool is_before_begin() const; //! Returns the depth of the current node. - dimension_type depth() const; + height_t depth() const; const CO_Tree* get_tree() const; private: #ifdef USE_PPL_CO_TREE_VEB_LAYOUT //! The depth of the current node in the vEB layout. - dimension_type d; + height_t d; //! Position of the node in a BFS layout. dimension_type i; @@ -685,7 +685,7 @@ public: bool is_before_begin() const; //! Returns the depth of the current node. - dimension_type depth() const; + height_t depth() const; CO_Tree* get_tree(); @@ -694,7 +694,7 @@ public: private: #ifdef USE_PPL_CO_TREE_VEB_LAYOUT //! The depth of the current node in the vEB layout. - dimension_type d; + height_t d; //! Position of the node in a BFS layout. dimension_type i; diff --git a/src/CO_Tree.inlines.hh b/src/CO_Tree.inlines.hh index 8de94c1..b27aa3e 100644 --- a/src/CO_Tree.inlines.hh +++ b/src/CO_Tree.inlines.hh @@ -837,7 +837,7 @@ CO_Tree::inorder_iterator::is_before_begin() const { #endif // defined(USE_PPL_CO_TREE_DFS_LAYOUT) } -inline dimension_type +inline CO_Tree::height_t CO_Tree::inorder_iterator::depth() const { PPL_ASSERT(tree != 0); @@ -847,7 +847,7 @@ CO_Tree::inorder_iterator::depth() const { #ifdef USE_PPL_CO_TREE_BFS_LAYOUT dimension_type n = i; - dimension_type d = 0; + height_t d = 0; while (n != 0) { n /= 2; ++d; @@ -857,7 +857,7 @@ CO_Tree::inorder_iterator::depth() const { #ifdef USE_PPL_CO_TREE_DFS_LAYOUT dimension_type n = i; - dimension_type d = 0; + height_t d = 0; while ((n & (dimension_type)0x01U) == 0) { n /= 2; ++d; @@ -1112,7 +1112,7 @@ CO_Tree::inorder_iterator::operator=(const inorder_iterator& itr2) { if (!is_at_end() && !is_before_begin()) { d = itr2.d; i = itr2.i; - for (dimension_type i = 1; i <= itr2.d; ++i) + for (height_t i = 1; i <= itr2.d; ++i) pos[i] = itr2.pos[i]; } #endif // defined(USE_PPL_CO_TREE_VEB_LAYOUT) @@ -1492,7 +1492,7 @@ CO_Tree::inorder_const_iterator::is_before_begin() const { #endif // defined(USE_PPL_CO_TREE_DFS_LAYOUT) } -inline dimension_type +inline CO_Tree::height_t CO_Tree::inorder_const_iterator::depth() const { PPL_ASSERT(tree != 0); PPL_ASSERT(tree->reserved_size != 0); @@ -1503,7 +1503,7 @@ CO_Tree::inorder_const_iterator::depth() const { #ifdef USE_PPL_CO_TREE_BFS_LAYOUT dimension_type n = i; - dimension_type d = 0; + height_t d = 0; while (n != 0) { n /= 2; ++d; @@ -1513,7 +1513,7 @@ CO_Tree::inorder_const_iterator::depth() const { #ifdef USE_PPL_CO_TREE_DFS_LAYOUT dimension_type n = i; - dimension_type d = 0; + height_t d = 0; while ((n & (dimension_type)0x01U) == 0) { n /= 2; ++d;