PPL  1.2
Public Member Functions | Public Attributes | Private Member Functions | Private Attributes | List of all members
Parma_Polyhedra_Library::CO_Tree::tree_iterator Class Reference

#include <CO_Tree_defs.hh>

Collaboration diagram for Parma_Polyhedra_Library::CO_Tree::tree_iterator:
Collaboration graph
[legend]

Public Member Functions

 tree_iterator (CO_Tree &tree)
 Constructs a tree_iterator pointing at the root node of the specified tree. More...
 
 tree_iterator (CO_Tree &tree, dimension_type i)
 Constructs a tree_iterator pointing at the specified node of the tree. More...
 
 tree_iterator (const iterator &itr, CO_Tree &tree)
 Constructs a tree_iterator from an iterator. More...
 
tree_iterator & operator= (const tree_iterator &itr)
 The assignment operator. More...
 
tree_iterator & operator= (const iterator &itr)
 The assignment operator from an iterator. More...
 
bool operator== (const tree_iterator &itr) const
 Compares *this with itr. More...
 
bool operator!= (const tree_iterator &itr) const
 Compares *this with itr. More...
 
void get_root ()
 Makes the iterator point to the root of tree. More...
 
void get_left_child ()
 Makes the iterator point to the left child of the current node. More...
 
void get_right_child ()
 Makes the iterator point to the right child of the current node. More...
 
void get_parent ()
 Makes the iterator point to the parent of the current node. More...
 
void go_down_searching_key (dimension_type key)
 Searches for an element with key key in the subtree rooted at *this. More...
 
void follow_left_children_with_value ()
 Follows left children with a value, until it arrives at a leaf or at a node with no value. More...
 
void follow_right_children_with_value ()
 Follows right children with a value, until it arrives at a leaf or at a node with no value. More...
 
bool is_root () const
 Returns true if the pointed node is the root node. More...
 
bool is_right_child () const
 Returns true if the pointed node has a parent and is its right child. More...
 
bool is_leaf () const
 Returns true if the pointed node is a leaf of the complete tree. More...
 
data_type & operator* ()
 Returns the key and value of the current node. More...
 
Coefficient_traits::const_reference operator* () const
 Returns the key and value of the current node. More...
 
dimension_type & index ()
 Returns a reference to the index of the element pointed to by *this. More...
 
dimension_type index () const
 Returns the index of the element pointed to by *this. More...
 
dimension_type key () const
 Returns the index of the node pointed to by *this. More...
 
dimension_type dfs_index () const
 Returns the index of the current node in the DFS layout of the complete tree. More...
 
dimension_type get_offset () const
 Returns 2^h, with h the height of the current node in the tree, counting from 0. More...
 
height_t depth () const
 Returns the depth of the current node in the complete tree. More...
 

Public Attributes

CO_Tree & tree
 The tree containing the element pointed to by this iterator. More...
 

Private Member Functions

bool OK () const
 Checks the internal invariant. More...
 

Private Attributes

dimension_type i
 The index of the current node in the DFS layout of the complete tree. More...
 
dimension_type offset
 This is 2^h, with h the height of the current node in the tree, counting from 0. More...
 

Detailed Description

Definition at line 1329 of file CO_Tree_defs.hh.

Constructor & Destructor Documentation

Parma_Polyhedra_Library::CO_Tree::tree_iterator::tree_iterator ( CO_Tree &  tree)
inlineexplicit

Constructs a tree_iterator pointing at the root node of the specified tree.

Parameters
treeThe tree to which the new iterator will point to. It must not be empty.

Definition at line 699 of file CO_Tree_inlines.hh.

References get_root(), OK(), Parma_Polyhedra_Library::CO_Tree::reserved_size, and tree.

700  : tree(tree1) {
701  PPL_ASSERT(tree.reserved_size != 0);
702  get_root();
703  PPL_ASSERT(OK());
704 }
Parma_Polyhedra_Library::CO_Tree::tree_iterator::OK
bool OK() const
Checks the internal invariant.
Definition: CO_Tree.cc:1401
Parma_Polyhedra_Library::CO_Tree::reserved_size
dimension_type reserved_size
The number of nodes in the complete tree.
Definition: CO_Tree_defs.hh:1323
Parma_Polyhedra_Library::CO_Tree::tree_iterator::tree
CO_Tree & tree
The tree containing the element pointed to by this iterator.
Definition: CO_Tree_defs.hh:1495
Parma_Polyhedra_Library::CO_Tree::tree_iterator::get_root
void get_root()
Makes the iterator point to the root of tree.
Definition: CO_Tree_inlines.hh:751
Parma_Polyhedra_Library::CO_Tree::tree_iterator::tree_iterator ( CO_Tree &  tree,
dimension_type  i 
)
inline

Constructs a tree_iterator pointing at the specified node of the tree.

Parameters
treeThe tree to which the new iterator will point to. It must not be empty.
iThe index of the element in tree to which the new iterator will point to.

Definition at line 707 of file CO_Tree_inlines.hh.

References i, Parma_Polyhedra_Library::least_significant_one_mask(), offset, OK(), Parma_Polyhedra_Library::CO_Tree::reserved_size, and tree.

708  : tree(tree1) {
709  PPL_ASSERT(tree.reserved_size != 0);
710  PPL_ASSERT(i1 <= tree.reserved_size + 1);
711  i = i1;
712  offset = least_significant_one_mask(i);
713  PPL_ASSERT(OK());
714 }
Parma_Polyhedra_Library::CO_Tree::tree_iterator::OK
bool OK() const
Checks the internal invariant.
Definition: CO_Tree.cc:1401
Parma_Polyhedra_Library::CO_Tree::reserved_size
dimension_type reserved_size
The number of nodes in the complete tree.
Definition: CO_Tree_defs.hh:1323
Parma_Polyhedra_Library::CO_Tree::tree_iterator::offset
dimension_type offset
This is 2^h, with h the height of the current node in the tree, counting from 0.
Definition: CO_Tree_defs.hh:1534
Parma_Polyhedra_Library::CO_Tree::tree_iterator::tree
CO_Tree & tree
The tree containing the element pointed to by this iterator.
Definition: CO_Tree_defs.hh:1495
Parma_Polyhedra_Library::least_significant_one_mask
dimension_type least_significant_one_mask(dimension_type i)
Definition: globals_inlines.hh:187
Parma_Polyhedra_Library::CO_Tree::tree_iterator::i
dimension_type i
The index of the current node in the DFS layout of the complete tree.
Definition: CO_Tree_defs.hh:1525
Parma_Polyhedra_Library::CO_Tree::tree_iterator::tree_iterator ( const iterator &  itr,
CO_Tree &  tree 
)
inline

Constructs a tree_iterator from an iterator.

Parameters
itrThe iterator that will be converted into a tree_iterator. It must not be end().
treeThe tree to which the new iterator will point to. It must not be empty.

Definition at line 717 of file CO_Tree_inlines.hh.

References OK(), Parma_Polyhedra_Library::CO_Tree::reserved_size, and tree.

718  : tree(tree1) {
719  PPL_ASSERT(tree.reserved_size != 0);
720  *this = itr;
721  PPL_ASSERT(OK());
722 }
Parma_Polyhedra_Library::CO_Tree::tree_iterator::OK
bool OK() const
Checks the internal invariant.
Definition: CO_Tree.cc:1401
Parma_Polyhedra_Library::CO_Tree::reserved_size
dimension_type reserved_size
The number of nodes in the complete tree.
Definition: CO_Tree_defs.hh:1323
Parma_Polyhedra_Library::CO_Tree::tree_iterator::tree
CO_Tree & tree
The tree containing the element pointed to by this iterator.
Definition: CO_Tree_defs.hh:1495

Member Function Documentation

CO_Tree::height_t Parma_Polyhedra_Library::CO_Tree::tree_iterator::depth ( ) const
inline

Returns the depth of the current node in the complete tree.

This method takes $O(\log n)$ time.

Definition at line 868 of file CO_Tree_inlines.hh.

References Parma_Polyhedra_Library::CO_Tree::integer_log2().

Referenced by Parma_Polyhedra_Library::CO_Tree::dump_subtree(), Parma_Polyhedra_Library::CO_Tree::insert(), and Parma_Polyhedra_Library::CO_Tree::rebalance().

868  {
869  return integer_log2((tree.reserved_size + 1) / offset);
870 }
Parma_Polyhedra_Library::CO_Tree::integer_log2
static unsigned integer_log2(dimension_type n)
Returns the floor of the base-2 logarithm of n .
Definition: CO_Tree.cc:787
Parma_Polyhedra_Library::CO_Tree::reserved_size
dimension_type reserved_size
The number of nodes in the complete tree.
Definition: CO_Tree_defs.hh:1323
Parma_Polyhedra_Library::CO_Tree::tree_iterator::offset
dimension_type offset
This is 2^h, with h the height of the current node in the tree, counting from 0.
Definition: CO_Tree_defs.hh:1534
Parma_Polyhedra_Library::CO_Tree::tree_iterator::tree
CO_Tree & tree
The tree containing the element pointed to by this iterator.
Definition: CO_Tree_defs.hh:1495
dimension_type Parma_Polyhedra_Library::CO_Tree::tree_iterator::dfs_index ( ) const
inline

Returns the index of the current node in the DFS layout of the complete tree.

Definition at line 858 of file CO_Tree_inlines.hh.

Referenced by Parma_Polyhedra_Library::CO_Tree::count_used_in_subtree(), Parma_Polyhedra_Library::CO_Tree::iterator::operator=(), operator=(), and Parma_Polyhedra_Library::CO_Tree::rebalance().

858  {
859  return i;
860 }
Parma_Polyhedra_Library::CO_Tree::tree_iterator::i
dimension_type i
The index of the current node in the DFS layout of the complete tree.
Definition: CO_Tree_defs.hh:1525
void Parma_Polyhedra_Library::CO_Tree::tree_iterator::follow_left_children_with_value ( )
inline

Follows left children with a value, until it arrives at a leaf or at a node with no value.

This method takes $O(1)$ time.

Definition at line 786 of file CO_Tree_inlines.hh.

References Parma_Polyhedra_Library::least_significant_one_mask(), Parma_Polyhedra_Library::CO_Tree::OK(), and Parma_Polyhedra_Library::CO_Tree::unused_index.

Referenced by Parma_Polyhedra_Library::CO_Tree::erase().

786  {
787  PPL_ASSERT(index() != unused_index);
788  const dimension_type* p = tree.indexes;
789  p += i;
790  p -= (offset - 1);
791  while (*p == unused_index) {
792  ++p;
793  }
794  const std::ptrdiff_t distance = p - tree.indexes;
795  PPL_ASSERT(distance >= 0);
796  i = static_cast<dimension_type>(distance);
797  offset = least_significant_one_mask(i);
798  PPL_ASSERT(OK());
799 }
Parma_Polyhedra_Library::dimension_type
size_t dimension_type
An unsigned integral type for representing space dimensions.
Definition: globals_types.hh:22
Parma_Polyhedra_Library::CO_Tree::tree_iterator::OK
bool OK() const
Checks the internal invariant.
Definition: CO_Tree.cc:1401
Parma_Polyhedra_Library::CO_Tree::indexes
dimension_type * indexes
The vector that contains the keys in the tree.
Definition: CO_Tree_defs.hh:1302
Parma_Polyhedra_Library::CO_Tree::tree_iterator::offset
dimension_type offset
This is 2^h, with h the height of the current node in the tree, counting from 0.
Definition: CO_Tree_defs.hh:1534
Parma_Polyhedra_Library::CO_Tree::tree_iterator::tree
CO_Tree & tree
The tree containing the element pointed to by this iterator.
Definition: CO_Tree_defs.hh:1495
Parma_Polyhedra_Library::CO_Tree::tree_iterator::index
dimension_type & index()
Returns a reference to the index of the element pointed to by *this.
Definition: CO_Tree_inlines.hh:848
Parma_Polyhedra_Library::least_significant_one_mask
dimension_type least_significant_one_mask(dimension_type i)
Definition: globals_inlines.hh:187
Parma_Polyhedra_Library::CO_Tree::unused_index
static const dimension_type unused_index
An index used as a marker for unused nodes in the tree.
Definition: CO_Tree_defs.hh:1277
Parma_Polyhedra_Library::CO_Tree::tree_iterator::i
dimension_type i
The index of the current node in the DFS layout of the complete tree.
Definition: CO_Tree_defs.hh:1525
void Parma_Polyhedra_Library::CO_Tree::tree_iterator::follow_right_children_with_value ( )
inline

Follows right children with a value, until it arrives at a leaf or at a node with no value.

This method takes $O(1)$ time.

Definition at line 802 of file CO_Tree_inlines.hh.

References Parma_Polyhedra_Library::least_significant_one_mask(), Parma_Polyhedra_Library::CO_Tree::OK(), and Parma_Polyhedra_Library::CO_Tree::unused_index.

Referenced by Parma_Polyhedra_Library::CO_Tree::erase().

802  {
803  PPL_ASSERT(index() != unused_index);
804  const dimension_type* p = tree.indexes;
805  p += i;
806  p += (offset - 1);
807  while (*p == unused_index) {
808  --p;
809  }
810  const std::ptrdiff_t distance = p - tree.indexes;
811  PPL_ASSERT(distance >= 0);
812  i = static_cast<dimension_type>(distance);
813  offset = least_significant_one_mask(i);
814  PPL_ASSERT(OK());
815 }
Parma_Polyhedra_Library::dimension_type
size_t dimension_type
An unsigned integral type for representing space dimensions.
Definition: globals_types.hh:22
Parma_Polyhedra_Library::CO_Tree::tree_iterator::OK
bool OK() const
Checks the internal invariant.
Definition: CO_Tree.cc:1401
Parma_Polyhedra_Library::CO_Tree::indexes
dimension_type * indexes
The vector that contains the keys in the tree.
Definition: CO_Tree_defs.hh:1302
Parma_Polyhedra_Library::CO_Tree::tree_iterator::offset
dimension_type offset
This is 2^h, with h the height of the current node in the tree, counting from 0.
Definition: CO_Tree_defs.hh:1534
Parma_Polyhedra_Library::CO_Tree::tree_iterator::tree
CO_Tree & tree
The tree containing the element pointed to by this iterator.
Definition: CO_Tree_defs.hh:1495
Parma_Polyhedra_Library::CO_Tree::tree_iterator::index
dimension_type & index()
Returns a reference to the index of the element pointed to by *this.
Definition: CO_Tree_inlines.hh:848
Parma_Polyhedra_Library::least_significant_one_mask
dimension_type least_significant_one_mask(dimension_type i)
Definition: globals_inlines.hh:187
Parma_Polyhedra_Library::CO_Tree::unused_index
static const dimension_type unused_index
An index used as a marker for unused nodes in the tree.
Definition: CO_Tree_defs.hh:1277
Parma_Polyhedra_Library::CO_Tree::tree_iterator::i
dimension_type i
The index of the current node in the DFS layout of the complete tree.
Definition: CO_Tree_defs.hh:1525
void Parma_Polyhedra_Library::CO_Tree::tree_iterator::get_left_child ( )
inline

Makes the iterator point to the left child of the current node.

This method takes $O(1)$ time.

Definition at line 758 of file CO_Tree_inlines.hh.

References Parma_Polyhedra_Library::CO_Tree::OK().

Referenced by Parma_Polyhedra_Library::CO_Tree::CO_Tree(), Parma_Polyhedra_Library::CO_Tree::dump_subtree(), Parma_Polyhedra_Library::CO_Tree::erase(), Parma_Polyhedra_Library::CO_Tree::insert_precise_aux(), Parma_Polyhedra_Library::CO_Tree::move_data_from(), and Parma_Polyhedra_Library::CO_Tree::rebalance().

758  {
759  PPL_ASSERT(offset != 0);
760  PPL_ASSERT(offset != 1);
761  offset /= 2;
762  i -= offset;
763  PPL_ASSERT(OK());
764 }
Parma_Polyhedra_Library::CO_Tree::tree_iterator::OK
bool OK() const
Checks the internal invariant.
Definition: CO_Tree.cc:1401
Parma_Polyhedra_Library::CO_Tree::tree_iterator::offset
dimension_type offset
This is 2^h, with h the height of the current node in the tree, counting from 0.
Definition: CO_Tree_defs.hh:1534
Parma_Polyhedra_Library::CO_Tree::tree_iterator::i
dimension_type i
The index of the current node in the DFS layout of the complete tree.
Definition: CO_Tree_defs.hh:1525
dimension_type Parma_Polyhedra_Library::CO_Tree::tree_iterator::get_offset ( ) const
inline

Returns 2^h, with h the height of the current node in the tree, counting from 0.

Thus leaves have offset 1. This is faster than depth(), so it is useful to compare node depths.

This method takes $O(1)$ time.

Definition at line 863 of file CO_Tree_inlines.hh.

Referenced by Parma_Polyhedra_Library::CO_Tree::count_used_in_subtree(), Parma_Polyhedra_Library::CO_Tree::erase(), Parma_Polyhedra_Library::CO_Tree::insert(), and Parma_Polyhedra_Library::CO_Tree::rebalance().

863  {
864  return offset;
865 }
Parma_Polyhedra_Library::CO_Tree::tree_iterator::offset
dimension_type offset
This is 2^h, with h the height of the current node in the tree, counting from 0.
Definition: CO_Tree_defs.hh:1534
void Parma_Polyhedra_Library::CO_Tree::tree_iterator::get_parent ( )
inline

Makes the iterator point to the parent of the current node.

This method takes $O(1)$ time.

Definition at line 776 of file CO_Tree_inlines.hh.

References Parma_Polyhedra_Library::CO_Tree::OK().

Referenced by Parma_Polyhedra_Library::CO_Tree::CO_Tree(), Parma_Polyhedra_Library::CO_Tree::dump_subtree(), Parma_Polyhedra_Library::CO_Tree::erase(), Parma_Polyhedra_Library::CO_Tree::move_data_from(), and Parma_Polyhedra_Library::CO_Tree::rebalance().

776  {
777  PPL_ASSERT(!is_root());
778  PPL_ASSERT(offset != 0);
779  i &= ~offset;
780  offset *= 2;
781  i |= offset;
782  PPL_ASSERT(OK());
783 }
Parma_Polyhedra_Library::CO_Tree::tree_iterator::is_root
bool is_root() const
Returns true if the pointed node is the root node.
Definition: CO_Tree_inlines.hh:818
Parma_Polyhedra_Library::CO_Tree::tree_iterator::OK
bool OK() const
Checks the internal invariant.
Definition: CO_Tree.cc:1401
Parma_Polyhedra_Library::CO_Tree::tree_iterator::offset
dimension_type offset
This is 2^h, with h the height of the current node in the tree, counting from 0.
Definition: CO_Tree_defs.hh:1534
Parma_Polyhedra_Library::CO_Tree::tree_iterator::i
dimension_type i
The index of the current node in the DFS layout of the complete tree.
Definition: CO_Tree_defs.hh:1525
void Parma_Polyhedra_Library::CO_Tree::tree_iterator::get_right_child ( )
inline

Makes the iterator point to the right child of the current node.

This method takes $O(1)$ time.

Definition at line 767 of file CO_Tree_inlines.hh.

References Parma_Polyhedra_Library::CO_Tree::OK().

Referenced by Parma_Polyhedra_Library::CO_Tree::CO_Tree(), Parma_Polyhedra_Library::CO_Tree::dump_subtree(), Parma_Polyhedra_Library::CO_Tree::erase(), Parma_Polyhedra_Library::CO_Tree::insert_precise_aux(), Parma_Polyhedra_Library::CO_Tree::move_data_from(), and Parma_Polyhedra_Library::CO_Tree::rebalance().

767  {
768  PPL_ASSERT(offset != 0);
769  PPL_ASSERT(offset != 1);
770  offset /= 2;
771  i += offset;
772  PPL_ASSERT(OK());
773 }
Parma_Polyhedra_Library::CO_Tree::tree_iterator::OK
bool OK() const
Checks the internal invariant.
Definition: CO_Tree.cc:1401
Parma_Polyhedra_Library::CO_Tree::tree_iterator::offset
dimension_type offset
This is 2^h, with h the height of the current node in the tree, counting from 0.
Definition: CO_Tree_defs.hh:1534
Parma_Polyhedra_Library::CO_Tree::tree_iterator::i
dimension_type i
The index of the current node in the DFS layout of the complete tree.
Definition: CO_Tree_defs.hh:1525
void Parma_Polyhedra_Library::CO_Tree::tree_iterator::get_root ( )
inline

Makes the iterator point to the root of tree.

The values of all fields (beside tree) are overwritten.

This method takes $O(1)$ time.

Definition at line 751 of file CO_Tree_inlines.hh.

References Parma_Polyhedra_Library::CO_Tree::OK().

Referenced by Parma_Polyhedra_Library::CO_Tree::erase(), Parma_Polyhedra_Library::CO_Tree::insert_precise_aux(), and tree_iterator().

751  {
752  i = tree.reserved_size / 2 + 1;
753  offset = i;
754  PPL_ASSERT(OK());
755 }
Parma_Polyhedra_Library::CO_Tree::tree_iterator::OK
bool OK() const
Checks the internal invariant.
Definition: CO_Tree.cc:1401
Parma_Polyhedra_Library::CO_Tree::reserved_size
dimension_type reserved_size
The number of nodes in the complete tree.
Definition: CO_Tree_defs.hh:1323
Parma_Polyhedra_Library::CO_Tree::tree_iterator::offset
dimension_type offset
This is 2^h, with h the height of the current node in the tree, counting from 0.
Definition: CO_Tree_defs.hh:1534
Parma_Polyhedra_Library::CO_Tree::tree_iterator::tree
CO_Tree & tree
The tree containing the element pointed to by this iterator.
Definition: CO_Tree_defs.hh:1495
Parma_Polyhedra_Library::CO_Tree::tree_iterator::i
dimension_type i
The index of the current node in the DFS layout of the complete tree.
Definition: CO_Tree_defs.hh:1525
void Parma_Polyhedra_Library::CO_Tree::tree_iterator::go_down_searching_key ( dimension_type  key)

Searches for an element with key key in the subtree rooted at *this.

Parameters
keyThe searched for key.

After this method, *this points to the found node (if it exists) or to the node that would be his parent (otherwise).

This method takes $O(\log n)$ time.

Definition at line 1417 of file CO_Tree.cc.

Referenced by Parma_Polyhedra_Library::CO_Tree::erase(), Parma_Polyhedra_Library::CO_Tree::insert(), Parma_Polyhedra_Library::CO_Tree::insert_precise(), and Parma_Polyhedra_Library::CO_Tree::insert_precise_aux().

1417  {
1418  // *this points to a node, so the tree is not empty.
1419  PPL_ASSERT(!tree.empty());
1420  PPL_ASSERT(key != unused_index);
1421  PPL_ASSERT(index() != unused_index);
1422  while (!is_leaf()) {
1423  if (key == index()) {
1424  break;
1425  }
1426  if (key < index()) {
1427  get_left_child();
1428  if (index() == unused_index) {
1429  get_parent();
1430  break;
1431  }
1432  }
1433  else {
1434  get_right_child();
1435  if (index() == unused_index) {
1436  get_parent();
1437  break;
1438  }
1439  }
1440  }
1441 }
Parma_Polyhedra_Library::CO_Tree::tree_iterator::key
dimension_type key() const
Returns the index of the node pointed to by *this.
Parma_Polyhedra_Library::CO_Tree::tree_iterator::get_parent
void get_parent()
Makes the iterator point to the parent of the current node.
Definition: CO_Tree_inlines.hh:776
Parma_Polyhedra_Library::CO_Tree::tree_iterator::is_leaf
bool is_leaf() const
Returns true if the pointed node is a leaf of the complete tree.
Definition: CO_Tree_inlines.hh:833
Parma_Polyhedra_Library::CO_Tree::tree_iterator::get_left_child
void get_left_child()
Makes the iterator point to the left child of the current node.
Definition: CO_Tree_inlines.hh:758
Parma_Polyhedra_Library::CO_Tree::empty
bool empty() const
Returns true if the tree has no elements.
Definition: CO_Tree_inlines.hh:86
Parma_Polyhedra_Library::CO_Tree::tree_iterator::tree
CO_Tree & tree
The tree containing the element pointed to by this iterator.
Definition: CO_Tree_defs.hh:1495
Parma_Polyhedra_Library::CO_Tree::tree_iterator::index
dimension_type & index()
Returns a reference to the index of the element pointed to by *this.
Definition: CO_Tree_inlines.hh:848
Parma_Polyhedra_Library::CO_Tree::unused_index
static const dimension_type unused_index
An index used as a marker for unused nodes in the tree.
Definition: CO_Tree_defs.hh:1277
Parma_Polyhedra_Library::CO_Tree::tree_iterator::get_right_child
void get_right_child()
Makes the iterator point to the right child of the current node.
Definition: CO_Tree_inlines.hh:767
dimension_type & Parma_Polyhedra_Library::CO_Tree::tree_iterator::index ( )
inline

Returns a reference to the index of the element pointed to by *this.

Returns
a reference to the index of the element pointed to by *this.

Definition at line 848 of file CO_Tree_inlines.hh.

Referenced by Parma_Polyhedra_Library::CO_Tree::CO_Tree(), Parma_Polyhedra_Library::CO_Tree::dump_subtree(), Parma_Polyhedra_Library::CO_Tree::erase(), Parma_Polyhedra_Library::CO_Tree::insert(), Parma_Polyhedra_Library::CO_Tree::insert_in_empty_tree(), Parma_Polyhedra_Library::CO_Tree::insert_precise(), Parma_Polyhedra_Library::CO_Tree::insert_precise_aux(), Parma_Polyhedra_Library::CO_Tree::move_data_from(), Parma_Polyhedra_Library::CO_Tree::rebalance(), and Parma_Polyhedra_Library::CO_Tree::structure_OK().

848  {
849  return tree.indexes[i];
850 }
Parma_Polyhedra_Library::CO_Tree::indexes
dimension_type * indexes
The vector that contains the keys in the tree.
Definition: CO_Tree_defs.hh:1302
Parma_Polyhedra_Library::CO_Tree::tree_iterator::tree
CO_Tree & tree
The tree containing the element pointed to by this iterator.
Definition: CO_Tree_defs.hh:1495
Parma_Polyhedra_Library::CO_Tree::tree_iterator::i
dimension_type i
The index of the current node in the DFS layout of the complete tree.
Definition: CO_Tree_defs.hh:1525
dimension_type Parma_Polyhedra_Library::CO_Tree::tree_iterator::index ( ) const
inline

Returns the index of the element pointed to by *this.

Returns
the index of the element pointed to by *this.

Definition at line 853 of file CO_Tree_inlines.hh.

853  {
854  return tree.indexes[i];
855 }
Parma_Polyhedra_Library::CO_Tree::indexes
dimension_type * indexes
The vector that contains the keys in the tree.
Definition: CO_Tree_defs.hh:1302
Parma_Polyhedra_Library::CO_Tree::tree_iterator::tree
CO_Tree & tree
The tree containing the element pointed to by this iterator.
Definition: CO_Tree_defs.hh:1495
Parma_Polyhedra_Library::CO_Tree::tree_iterator::i
dimension_type i
The index of the current node in the DFS layout of the complete tree.
Definition: CO_Tree_defs.hh:1525
bool Parma_Polyhedra_Library::CO_Tree::tree_iterator::is_leaf ( ) const
inline

Returns true if the pointed node is a leaf of the complete tree.

This method takes $O(1)$ time.

Definition at line 833 of file CO_Tree_inlines.hh.

Referenced by Parma_Polyhedra_Library::CO_Tree::dump_subtree(), Parma_Polyhedra_Library::CO_Tree::erase(), Parma_Polyhedra_Library::CO_Tree::insert_precise_aux(), and Parma_Polyhedra_Library::CO_Tree::rebalance().

833  {
834  return offset == 1;
835 }
Parma_Polyhedra_Library::CO_Tree::tree_iterator::offset
dimension_type offset
This is 2^h, with h the height of the current node in the tree, counting from 0.
Definition: CO_Tree_defs.hh:1534
bool Parma_Polyhedra_Library::CO_Tree::tree_iterator::is_right_child ( ) const
inline

Returns true if the pointed node has a parent and is its right child.

This method takes $O(1)$ time.

Definition at line 825 of file CO_Tree_inlines.hh.

Referenced by Parma_Polyhedra_Library::CO_Tree::rebalance().

825  {
826  if (is_root()) {
827  return false;
828  }
829  return (i & (2*offset)) != 0;
830 }
Parma_Polyhedra_Library::CO_Tree::tree_iterator::is_root
bool is_root() const
Returns true if the pointed node is the root node.
Definition: CO_Tree_inlines.hh:818
Parma_Polyhedra_Library::CO_Tree::tree_iterator::offset
dimension_type offset
This is 2^h, with h the height of the current node in the tree, counting from 0.
Definition: CO_Tree_defs.hh:1534
Parma_Polyhedra_Library::CO_Tree::tree_iterator::i
dimension_type i
The index of the current node in the DFS layout of the complete tree.
Definition: CO_Tree_defs.hh:1525
bool Parma_Polyhedra_Library::CO_Tree::tree_iterator::is_root ( ) const
inline

Returns true if the pointed node is the root node.

This method takes $O(1)$ time.

Definition at line 818 of file CO_Tree_inlines.hh.

818  {
819  // This is implied by OK(), it is here for reference only.
820  PPL_ASSERT(offset <= (tree.reserved_size / 2 + 1));
821  return offset == (tree.reserved_size / 2 + 1);
822 }
Parma_Polyhedra_Library::CO_Tree::reserved_size
dimension_type reserved_size
The number of nodes in the complete tree.
Definition: CO_Tree_defs.hh:1323
Parma_Polyhedra_Library::CO_Tree::tree_iterator::offset
dimension_type offset
This is 2^h, with h the height of the current node in the tree, counting from 0.
Definition: CO_Tree_defs.hh:1534
Parma_Polyhedra_Library::CO_Tree::tree_iterator::tree
CO_Tree & tree
The tree containing the element pointed to by this iterator.
Definition: CO_Tree_defs.hh:1495
dimension_type Parma_Polyhedra_Library::CO_Tree::tree_iterator::key ( ) const

Returns the index of the node pointed to by *this.

Returns
the key of the node pointed to by *this, or unused_index if the current node does not contain a valid element.
bool Parma_Polyhedra_Library::CO_Tree::tree_iterator::OK ( ) const
private

Checks the internal invariant.

Definition at line 1401 of file CO_Tree.cc.

Referenced by tree_iterator().

1401  {
1402  if (i == 0 || i > tree.reserved_size) {
1403  return false;
1404  }
1405 
1406  // This assumes two's complement encoding.
1407  const dimension_type correct_offset = i & -i;
1408 
1409  if (offset != correct_offset) {
1410  return false;
1411  }
1412 
1413  return true;
1414 }
Parma_Polyhedra_Library::dimension_type
size_t dimension_type
An unsigned integral type for representing space dimensions.
Definition: globals_types.hh:22
Parma_Polyhedra_Library::CO_Tree::reserved_size
dimension_type reserved_size
The number of nodes in the complete tree.
Definition: CO_Tree_defs.hh:1323
Parma_Polyhedra_Library::CO_Tree::tree_iterator::offset
dimension_type offset
This is 2^h, with h the height of the current node in the tree, counting from 0.
Definition: CO_Tree_defs.hh:1534
Parma_Polyhedra_Library::CO_Tree::tree_iterator::tree
CO_Tree & tree
The tree containing the element pointed to by this iterator.
Definition: CO_Tree_defs.hh:1495
Parma_Polyhedra_Library::CO_Tree::tree_iterator::i
dimension_type i
The index of the current node in the DFS layout of the complete tree.
Definition: CO_Tree_defs.hh:1525
bool Parma_Polyhedra_Library::CO_Tree::tree_iterator::operator!= ( const tree_iterator &  itr) const
inline

Compares *this with itr.

Parameters
itrThe iterator that will compared with *this.

Definition at line 746 of file CO_Tree_inlines.hh.

746  {
747  return !(*this == itr);
748 }
CO_Tree::data_type & Parma_Polyhedra_Library::CO_Tree::tree_iterator::operator* ( )
inline

Returns the key and value of the current node.

Definition at line 838 of file CO_Tree_inlines.hh.

838  {
839  return tree.data[i];
840 }
Parma_Polyhedra_Library::CO_Tree::data
data_type * data
The vector that contains the data of the keys in the tree.
Definition: CO_Tree_defs.hh:1316
Parma_Polyhedra_Library::CO_Tree::tree_iterator::tree
CO_Tree & tree
The tree containing the element pointed to by this iterator.
Definition: CO_Tree_defs.hh:1495
Parma_Polyhedra_Library::CO_Tree::tree_iterator::i
dimension_type i
The index of the current node in the DFS layout of the complete tree.
Definition: CO_Tree_defs.hh:1525
Coefficient_traits::const_reference Parma_Polyhedra_Library::CO_Tree::tree_iterator::operator* ( ) const
inline

Returns the key and value of the current node.

Definition at line 843 of file CO_Tree_inlines.hh.

843  {
844  return tree.data[i];
845 }
Parma_Polyhedra_Library::CO_Tree::data
data_type * data
The vector that contains the data of the keys in the tree.
Definition: CO_Tree_defs.hh:1316
Parma_Polyhedra_Library::CO_Tree::tree_iterator::tree
CO_Tree & tree
The tree containing the element pointed to by this iterator.
Definition: CO_Tree_defs.hh:1495
Parma_Polyhedra_Library::CO_Tree::tree_iterator::i
dimension_type i
The index of the current node in the DFS layout of the complete tree.
Definition: CO_Tree_defs.hh:1525
CO_Tree::tree_iterator & Parma_Polyhedra_Library::CO_Tree::tree_iterator::operator= ( const tree_iterator &  itr)
inline

The assignment operator.

Parameters
itrThe iterator that will be assigned into *this.

Definition at line 725 of file CO_Tree_inlines.hh.

References i, offset, and tree.

725  {
726  PPL_ASSERT(&tree == &(itr.tree));
727  i = itr.i;
728  offset = itr.offset;
729  return *this;
730 }
Parma_Polyhedra_Library::CO_Tree::tree_iterator::offset
dimension_type offset
This is 2^h, with h the height of the current node in the tree, counting from 0.
Definition: CO_Tree_defs.hh:1534
Parma_Polyhedra_Library::CO_Tree::tree_iterator::tree
CO_Tree & tree
The tree containing the element pointed to by this iterator.
Definition: CO_Tree_defs.hh:1495
Parma_Polyhedra_Library::CO_Tree::tree_iterator::i
dimension_type i
The index of the current node in the DFS layout of the complete tree.
Definition: CO_Tree_defs.hh:1525
CO_Tree::tree_iterator & Parma_Polyhedra_Library::CO_Tree::tree_iterator::operator= ( const iterator &  itr)
inline

The assignment operator from an iterator.

Parameters
itrThe iterator that will be assigned into *this.

Definition at line 733 of file CO_Tree_inlines.hh.

References dfs_index(), and Parma_Polyhedra_Library::least_significant_one_mask().

733  {
734  PPL_ASSERT(itr != tree.end());
735  i = tree.dfs_index(itr);
736  offset = least_significant_one_mask(i);
737  return *this;
738 }
Parma_Polyhedra_Library::CO_Tree::end
const iterator & end()
Returns an iterator that points after the last element.
Definition: CO_Tree_inlines.hh:201
Parma_Polyhedra_Library::CO_Tree::tree_iterator::offset
dimension_type offset
This is 2^h, with h the height of the current node in the tree, counting from 0.
Definition: CO_Tree_defs.hh:1534
Parma_Polyhedra_Library::CO_Tree::dfs_index
dimension_type dfs_index(const_iterator itr) const
Definition: CO_Tree_inlines.hh:32
Parma_Polyhedra_Library::CO_Tree::tree_iterator::tree
CO_Tree & tree
The tree containing the element pointed to by this iterator.
Definition: CO_Tree_defs.hh:1495
Parma_Polyhedra_Library::least_significant_one_mask
dimension_type least_significant_one_mask(dimension_type i)
Definition: globals_inlines.hh:187
Parma_Polyhedra_Library::CO_Tree::tree_iterator::i
dimension_type i
The index of the current node in the DFS layout of the complete tree.
Definition: CO_Tree_defs.hh:1525
bool Parma_Polyhedra_Library::CO_Tree::tree_iterator::operator== ( const tree_iterator &  itr) const
inline

Compares *this with itr.

Parameters
itrThe iterator that will compared with *this.

Definition at line 741 of file CO_Tree_inlines.hh.

References i.

741  {
742  return i == itr.i;
743 }
Parma_Polyhedra_Library::CO_Tree::tree_iterator::i
dimension_type i
The index of the current node in the DFS layout of the complete tree.
Definition: CO_Tree_defs.hh:1525

Member Data Documentation

dimension_type Parma_Polyhedra_Library::CO_Tree::tree_iterator::i
private

The index of the current node in the DFS layout of the complete tree.

Definition at line 1525 of file CO_Tree_defs.hh.

Referenced by operator=(), operator==(), and tree_iterator().

dimension_type Parma_Polyhedra_Library::CO_Tree::tree_iterator::offset
private

This is 2^h, with h the height of the current node in the tree, counting from 0.

Thus leaves have offset 1. This is equal to (i & -i), and is only stored to increase performance.

Definition at line 1534 of file CO_Tree_defs.hh.

Referenced by operator=(), and tree_iterator().

CO_Tree& Parma_Polyhedra_Library::CO_Tree::tree_iterator::tree

The tree containing the element pointed to by this iterator.

Definition at line 1495 of file CO_Tree_defs.hh.

Referenced by Parma_Polyhedra_Library::CO_Tree::count_used_in_subtree(), Parma_Polyhedra_Library::CO_Tree::iterator::operator=(), operator=(), and tree_iterator().

The documentation for this class was generated from the following files: