#include <CO_Tree.defs.hh>

Collaboration diagram for Parma_Polyhedra_Library::CO_Tree::tree_iterator:

Public Member Functions
	tree_iterator (CO_Tree &tree)
	Constructs a tree_iterator pointing at the root node of the specified tree.
	tree_iterator (CO_Tree &tree, dimension_type i)
	Constructs a tree_iterator pointing at the specified node of the tree.
	tree_iterator (const iterator &itr, CO_Tree &tree)
	Constructs a tree_iterator from an iterator.
tree_iterator &	operator= (const tree_iterator &itr)
	The assignment operator.
tree_iterator &	operator= (const iterator &itr)
	The assignment operator from an iterator.
bool	operator== (const tree_iterator &itr) const
	Compares *this with `itr`.
bool	operator!= (const tree_iterator &itr) const
	Compares *this with `itr`.
void	get_root ()
	Makes the iterator point to the root of `tree`.
void	get_left_child ()
	Makes the iterator point to the left child of the current node.
void	get_right_child ()
	Makes the iterator point to the right child of the current node.
void	get_parent ()
	Makes the iterator point to the parent of the current node.
void	go_down_searching_key (dimension_type key)
	Searches for an element with key `key` in the subtree rooted at `*this`.
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.
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.
bool	is_root () const
	Returns true if the pointed node is the root node.
bool	is_right_child () const
	Returns true if the pointed node has a parent and is its right child.
bool	is_leaf () const
	Returns true if the pointed node is a leaf of the complete tree.
data_type &	operator* ()
	Returns the key and value of the current node.
Coefficient_traits::const_reference	operator* () const
	Returns the key and value of the current node.
dimension_type &	index ()
	Returns a reference to the index of the element pointed to by `*this`.
dimension_type	index () const
	Returns the index of the element pointed to by `*this`.
dimension_type	key () const
	Returns the index of the node pointed to by `*this`.
dimension_type	dfs_index () const
	Returns the index of the current node in the DFS layout of the complete tree.
dimension_type	get_offset () const
	Returns 2^h, with h the height of the current node in the tree, counting from 0.
height_t	depth () const
	Returns the depth of the current node in the complete tree.
Public Attributes
CO_Tree &	tree
	The tree containing the element pointed to by this iterator.
Private Member Functions
bool	OK () const
	Checks the internal invariant.
Private Attributes
dimension_type	i
	The index of the current node in the DFS layout of the complete tree.
dimension_type	offset
	This is 2^h, with h the height of the current node in the tree, counting from 0.

Detailed Description

Definition at line 1308 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:

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

Definition at line 669 of file CO_Tree.inlines.hh.

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

  : tree(tree1) {
  PPL_ASSERT(tree.reserved_size != 0);
  get_root();
  PPL_ASSERT(OK());
}

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:

tree	The tree to which the new iterator will point to. It must not be empty.
i	The index of the element in `tree` to which the new iterator will point to.

Definition at line 677 of file CO_Tree.inlines.hh.

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

  : tree(tree1) {
  PPL_ASSERT(tree.reserved_size != 0);
  PPL_ASSERT(i1 <= tree.reserved_size + 1);
  i = i1;
  offset = least_significant_one_mask(i);
  PPL_ASSERT(OK());
}

Parma_Polyhedra_Library::CO_Tree::tree_iterator::tree_iterator	(	const iterator &	itr,
		CO_Tree &	tree
	)

inline

Constructs a tree_iterator from an iterator.

Parameters:

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

Definition at line 687 of file CO_Tree.inlines.hh.

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

  : tree(tree1) {
  PPL_ASSERT(tree.reserved_size != 0);
  *this = itr;
  PPL_ASSERT(OK());
}

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 835 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().

                                  {
  return integer_log2((tree.reserved_size + 1) / offset);
}

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 825 of file CO_Tree.inlines.hh.

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

                                      {
  return i;
}

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 756 of file CO_Tree.inlines.hh.

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

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

                                                      {
  PPL_ASSERT(index() != unused_index);
  dimension_type* p = tree.indexes;
  p += i;
  p -= (offset - 1);
  while (*p == unused_index)
    ++p;
  ptrdiff_t distance = p - tree.indexes;
  PPL_ASSERT(distance >= 0);
  i = static_cast<dimension_type>(distance);
  offset = least_significant_one_mask(i);
  PPL_ASSERT(OK());
}

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 771 of file CO_Tree.inlines.hh.

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

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

                                                       {
  PPL_ASSERT(index() != unused_index);
  dimension_type* p = tree.indexes;
  p += i;
  p += (offset - 1);
  while (*p == unused_index)
    --p;
  ptrdiff_t distance = p - tree.indexes;
  PPL_ASSERT(distance >= 0);
  i = static_cast<dimension_type>(distance);
  offset = least_significant_one_mask(i);
  PPL_ASSERT(OK());
}

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 728 of file CO_Tree.inlines.hh.

References Parma_Polyhedra_Library::CO_Tree::OK(), and PPL_ASSERT.

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(), Parma_Polyhedra_Library::CO_Tree::move_data_from(), and Parma_Polyhedra_Library::CO_Tree::rebalance().

                                     {
  PPL_ASSERT(offset != 0);
  PPL_ASSERT(offset != 1);
  offset /= 2;
  i -= offset;
  PPL_ASSERT(OK());
}

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 830 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().

                                       {
  return offset;
}

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 746 of file CO_Tree.inlines.hh.

References Parma_Polyhedra_Library::CO_Tree::OK(), and PPL_ASSERT.

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().

                                 {
  PPL_ASSERT(!is_root());
  PPL_ASSERT(offset != 0);
  i &= ~offset;
  offset *= 2;
  i |= offset;
  PPL_ASSERT(OK());
}

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 737 of file CO_Tree.inlines.hh.

References Parma_Polyhedra_Library::CO_Tree::OK(), and PPL_ASSERT.

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(), Parma_Polyhedra_Library::CO_Tree::move_data_from(), and Parma_Polyhedra_Library::CO_Tree::rebalance().

                                      {
  PPL_ASSERT(offset != 0);
  PPL_ASSERT(offset != 1);
  offset /= 2;
  i += offset;
  PPL_ASSERT(OK());
}

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 721 of file CO_Tree.inlines.hh.

References Parma_Polyhedra_Library::CO_Tree::OK(), and PPL_ASSERT.

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

                               {
  i = tree.reserved_size / 2 + 1;
  offset = i;
  PPL_ASSERT(OK());
}

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:

key	The 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 1223 of file CO_Tree.cc.

References PPL_ASSERT.

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

                                                                 {
  // *this points to a node, so the tree is not empty.
  PPL_ASSERT(!tree.empty());
  PPL_ASSERT(key != unused_index);
  PPL_ASSERT(index() != unused_index);
  while (!is_leaf()) {
    if (key == index())
      break;
    if (key < index()) {
      get_left_child();
      if (index() == unused_index) {
        get_parent();
        break;
      }
    } else {
      get_right_child();
      if (index() == unused_index) {
        get_parent();
        break;
      }
    }
  }
}

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 815 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::move_data_from(), Parma_Polyhedra_Library::CO_Tree::rebalance(), and Parma_Polyhedra_Library::CO_Tree::structure_OK().

                            {
  return tree.indexes[i];
}

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 820 of file CO_Tree.inlines.hh.

                                  {
  return tree.indexes[i];
}

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 800 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(), and Parma_Polyhedra_Library::CO_Tree::rebalance().

                                    {
  return offset == 1;
}

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 793 of file CO_Tree.inlines.hh.

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

                                           {
  if (is_root())
    return false;
  return (i & (2*offset)) != 0;
}

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 786 of file CO_Tree.inlines.hh.

References PPL_ASSERT.

                                    {
  // This is implied by OK(), it is here for reference only.
  PPL_ASSERT(offset <= (tree.reserved_size / 2 + 1));
  return offset == (tree.reserved_size / 2 + 1);
}

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 1209 of file CO_Tree.cc.

Referenced by tree_iterator().

                                  {
  if (i == 0 || i > tree.reserved_size)
    return false;

  // This assumes two's complement encoding.
  dimension_type correct_offset = i & -i;

  if (offset != correct_offset)
    return false;

  return true;
}

bool Parma_Polyhedra_Library::CO_Tree::tree_iterator::operator!= ( const tree_iterator & itr ) const

inline

Compares *this with itr.

Parameters:

itr	The iterator that will compared with *this.

Definition at line 716 of file CO_Tree.inlines.hh.

                                                               {
  return !(*this == itr);
}

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 805 of file CO_Tree.inlines.hh.

                                {
  return tree.data[i];
}

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 810 of file CO_Tree.inlines.hh.

                                      {
  return tree.data[i];
}

CO_Tree::tree_iterator & Parma_Polyhedra_Library::CO_Tree::tree_iterator::operator= ( const tree_iterator & itr )

inline

The assignment operator.

Parameters:

itr	The iterator that will be assigned into *this.

Definition at line 695 of file CO_Tree.inlines.hh.

References i, offset, PPL_ASSERT, and tree.

                                                        {
  PPL_ASSERT(&tree == &(itr.tree));
  i = itr.i;
  offset = itr.offset;
  return *this;
}

CO_Tree::tree_iterator & Parma_Polyhedra_Library::CO_Tree::tree_iterator::operator= ( const iterator & itr )

inline

The assignment operator from an iterator.

Parameters:

itr	The iterator that will be assigned into *this.

Definition at line 703 of file CO_Tree.inlines.hh.

References Parma_Polyhedra_Library::least_significant_one_mask(), and PPL_ASSERT.

                                                   {
  PPL_ASSERT(itr != tree.end());
  i = tree.dfs_index(itr);
  offset = least_significant_one_mask(i);
  return *this;
}

bool Parma_Polyhedra_Library::CO_Tree::tree_iterator::operator== ( const tree_iterator & itr ) const

inline

Compares *this with itr.

Parameters:

itr	The iterator that will compared with *this.

Definition at line 711 of file CO_Tree.inlines.hh.

References i.

                                                               {
  return i == itr.i;
}

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 1504 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 1513 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 1474 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:

Public Member Functions

Public Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation