DREAM::AVLTree< key_type, item_type > Class Template Reference

This class combines STL vectors and maps providing a fast implementation for find (), operator++ (), operator-- (), and operator[] () in a common class. More...

#include <AVLTree.h>

List of all members.

Public Types

typedef Iterator< AVLTreeNode<
key_type, item_type > > 
iterator
 iterator class for convenience.
typedef Const_Iterator< AVLTreeNode<
key_type, item_type > > 
const_iterator
 const_iterator class for convenience.

Public Member Functions

 AVLTree ()
 Constructor.
 ~AVLTree ()
 Destructor.
void assign (const AVLTreeNode< key_type, item_type > *begin_node, const AVLTreeNode< key_type, item_type > *end_node)
 Assign operator.
void assign (Iterator< AVLTreeNode< key_type, item_type > > &begin_iter, Iterator< AVLTreeNode< key_type, item_type > > &end_iter)
 Assign operator.
void assign (Const_Iterator< AVLTreeNode< key_type, item_type > > &begin_iter, Const_Iterator< AVLTreeNode< key_type, item_type > > &end_iter)
 Assign operator.
AVLTreeNode< key_type, item_type > * begin ()
 Returns a pointer to the smallest element in the AVLTree.
const AVLTreeNode< key_type,
item_type > * 
begin () const
 Returns a pointer to the smallest element in the AVLTree.
void clear ()
 Erases elements in the AVLTree.
void destroy ()
 Erases elements in the AVLTree, and calls delete on the item_type.
bool empty ()
 Returns true if the AVLTree is empty.
bool empty () const
 Returns true if the AVLTree is empty.
AVLTreeNode< key_type, item_type > * end ()
 Returns NULL.
const AVLTreeNode< key_type,
item_type > * 
end () const
 Returns NULL.
void erase (Iterator< AVLTreeNode< key_type, item_type > > &iter)
 Erase a node from the AVLTree.
void erase (key_type key)
 Erase a node from the AVLTree.
AVLTreeNode< key_type, item_type > * find (const key_type &key)
 Finds an AVLTree node in the AVLTree.
const AVLTreeNode< key_type,
item_type > * 
find (const key_type &key) const
 Finds an AVLTree node in the AVLTree.
void insert (key_type key, item_type item)
 Inserts an AVLTree node in the AVLTree.
AVLTreeNode< key_type, item_type > * last ()
 Returns an iterator to the last element of the AVLTree.
const AVLTreeNode< key_type,
item_type > * 
last () const
 Returns an iterator to the last element of the AVLTree.
item_type & operator[] (uint i)
 operator [].
const item_type & operator[] (uint i) const
 operator [].
uint size () const
 Return the number of items in the AVLTree.

Protected Member Functions

void balance (AVLTreeNode< key_type, item_type > *node_ptr)
 Balances the AVLTree from the given node if necessary.
void balance_left (AVLTreeNode< key_type, item_type > *node_ptr)
 Balances the AVLTree to the right from the given node.
void balance_right (AVLTreeNode< key_type, item_type > *node_ptr)
 Balances the AVLTree to the right from the given node.
AVLTreeNode< key_type, item_type > * get_smaller_node (AVLTreeNode< key_type, item_type > *node_ptr, AVLTreeNode< key_type, item_type > *left_ptr, AVLTreeNode< key_type, item_type > *right_ptr)
 Finds the next smaller node in the subtree of node_ptr, removes it, and reconstructs the tree.
AVLTreeNode< key_type, item_type > * get_larger_node (AVLTreeNode< key_type, item_type > *node_ptr, AVLTreeNode< key_type, item_type > *left_ptr, AVLTreeNode< key_type, item_type > *right_ptr)
 Finds the next larger node in the subtree of node_ptr, removes it, and reconstructs the tree.
void erase_leaf (AVLTreeNode< key_type, item_type > *node_ptr, AVLTreeNode< key_type, item_type > *parent_ptr)
 Erase a leaf from the AVLTree.
void erase_left_child (AVLTreeNode< key_type, item_type > *node_ptr, AVLTreeNode< key_type, item_type > *parent_ptr, AVLTreeNode< key_type, item_type > *left_ptr)
 Erase a node with only a left child from the AVLTree.
void erase_right_child (AVLTreeNode< key_type, item_type > *node_ptr, AVLTreeNode< key_type, item_type > *parent_ptr, AVLTreeNode< key_type, item_type > *right_ptr)
 Erase a node with only a right child from the AVLTree.
void erase (AVLTreeNode< key_type, item_type > *node_ptr, AVLTreeNode< key_type, item_type > *parent_ptr, AVLTreeNode< key_type, item_type > *left_ptr, AVLTreeNode< key_type, item_type > *right_ptr)
 Erase a node with both children present from the AVLTree.

Protected Attributes

AVLTreeNode< key_type, item_type > * root_ptr_
 Pointer to the root of the tree.
AVLTreeNode< key_type, item_type > * last_ptr_
 Pointer to the last element of the tree.
uint size_
 Stores the number of items in the AVLTree.

Friends

class Iterator< AVLTreeNode< key_type, item_type > >
 Allow iterators to manipulate protected members.
class Const_Iterator< AVLTreeNode< key_type, item_type > >
 Allow iterators to manipulate protected members.


Detailed Description

template<class key_type, class item_type>
class DREAM::AVLTree< key_type, item_type >

This class combines STL vectors and maps providing a fast implementation for find (), operator++ (), operator-- (), and operator[] () in a common class.

This is necessary since we want random access to elements in the tree, which requires a mix of STL maps and vectors. We prefer faster find and insert operations, therefore the underlying data structure is an AVL tree as it allows for the easy and efficient implementation of all these operators.

Definition at line 184 of file AVLTree.h.


Member Typedef Documentation

template<class key_type, class item_type>
typedef Iterator<AVLTreeNode <key_type, item_type> > DREAM::AVLTree< key_type, item_type >::iterator

iterator class for convenience.

Definition at line 302 of file AVLTree.h.

template<class key_type, class item_type>
typedef Const_Iterator<AVLTreeNode <key_type, item_type> > DREAM::AVLTree< key_type, item_type >::const_iterator

const_iterator class for convenience.

Definition at line 305 of file AVLTree.h.


Constructor & Destructor Documentation

template<class key_type, class item_type>
DREAM::AVLTree< key_type, item_type >::AVLTree (  ) 

Constructor.

Definition at line 313 of file AVLTree.cpp.

template<class key_type, class item_type>
DREAM::AVLTree< key_type, item_type >::~AVLTree (  ) 

Destructor.

Definition at line 317 of file AVLTree.cpp.


Member Function Documentation

template<class key_type, class item_type>
void DREAM::AVLTree< key_type, item_type >::balance ( AVLTreeNode< key_type, item_type > *  node_ptr  )  [protected]

Balances the AVLTree from the given node if necessary.

Definition at line 354 of file AVLTree.cpp.

template<class key_type, class item_type>
void DREAM::AVLTree< key_type, item_type >::balance_left ( AVLTreeNode< key_type, item_type > *  node_ptr  )  [protected]

Balances the AVLTree to the right from the given node.

Definition at line 379 of file AVLTree.cpp.

template<class key_type, class item_type>
void DREAM::AVLTree< key_type, item_type >::balance_right ( AVLTreeNode< key_type, item_type > *  node_ptr  )  [protected]

Balances the AVLTree to the right from the given node.

Definition at line 484 of file AVLTree.cpp.

References DREAM::AVLTreeNode< key_type, item_type >::left_, DREAM::AVLTreeNode< key_type, item_type >::parent_, and DREAM::AVLTreeNode< key_type, item_type >::right_.

template<class key_type, class item_type>
AVLTreeNode< key_type, item_type > * DREAM::AVLTree< key_type, item_type >::get_smaller_node ( AVLTreeNode< key_type, item_type > *  node_ptr,
AVLTreeNode< key_type, item_type > *  left_ptr,
AVLTreeNode< key_type, item_type > *  right_ptr 
) [protected]

Finds the next smaller node in the subtree of node_ptr, removes it, and reconstructs the tree.

Definition at line 883 of file AVLTree.cpp.

References DREAM::AVLTreeNode< key_type, item_type >::left_, and DREAM::AVLTreeNode< key_type, item_type >::parent_.

template<class key_type, class item_type>
AVLTreeNode< key_type, item_type > * DREAM::AVLTree< key_type, item_type >::get_larger_node ( AVLTreeNode< key_type, item_type > *  node_ptr,
AVLTreeNode< key_type, item_type > *  left_ptr,
AVLTreeNode< key_type, item_type > *  right_ptr 
) [protected]

Finds the next larger node in the subtree of node_ptr, removes it, and reconstructs the tree.

Definition at line 921 of file AVLTree.cpp.

References DREAM::AVLTreeNode< key_type, item_type >::parent_, and DREAM::AVLTreeNode< key_type, item_type >::right_.

template<class key_type, class item_type>
void DREAM::AVLTree< key_type, item_type >::erase_leaf ( AVLTreeNode< key_type, item_type > *  node_ptr,
AVLTreeNode< key_type, item_type > *  parent_ptr 
) [protected]

Erase a leaf from the AVLTree.

Definition at line 760 of file AVLTree.cpp.

template<class key_type, class item_type>
void DREAM::AVLTree< key_type, item_type >::erase_left_child ( AVLTreeNode< key_type, item_type > *  node_ptr,
AVLTreeNode< key_type, item_type > *  parent_ptr,
AVLTreeNode< key_type, item_type > *  left_ptr 
) [protected]

Erase a node with only a left child from the AVLTree.

Definition at line 785 of file AVLTree.cpp.

template<class key_type, class item_type>
void DREAM::AVLTree< key_type, item_type >::erase_right_child ( AVLTreeNode< key_type, item_type > *  node_ptr,
AVLTreeNode< key_type, item_type > *  parent_ptr,
AVLTreeNode< key_type, item_type > *  right_ptr 
) [protected]

Erase a node with only a right child from the AVLTree.

Definition at line 817 of file AVLTree.cpp.

template<class key_type, class item_type>
void DREAM::AVLTree< key_type, item_type >::erase ( AVLTreeNode< key_type, item_type > *  node_ptr,
AVLTreeNode< key_type, item_type > *  parent_ptr,
AVLTreeNode< key_type, item_type > *  left_ptr,
AVLTreeNode< key_type, item_type > *  right_ptr 
) [protected]

Erase a node with both children present from the AVLTree.

Definition at line 704 of file AVLTree.cpp.

References DREAM::AVLTreeNode< key_type, item_type >::calculate_depth(), and DREAM::AVLTreeNode< key_type, item_type >::parent_.

template<class key_type, class item_type>
void DREAM::AVLTree< key_type, item_type >::assign ( const AVLTreeNode< key_type, item_type > *  begin_node,
const AVLTreeNode< key_type, item_type > *  end_node 
)

Assign operator.

Definition at line 324 of file AVLTree.cpp.

Referenced by DREAM::PriorityInversionList::add().

template<class key_type, class item_type>
void DREAM::AVLTree< key_type, item_type >::assign ( Iterator< AVLTreeNode< key_type, item_type > > &  begin_iter,
Iterator< AVLTreeNode< key_type, item_type > > &  end_iter 
)

Assign operator.

Definition at line 336 of file AVLTree.cpp.

template<class key_type, class item_type>
void DREAM::AVLTree< key_type, item_type >::assign ( Const_Iterator< AVLTreeNode< key_type, item_type > > &  begin_iter,
Const_Iterator< AVLTreeNode< key_type, item_type > > &  end_iter 
)

Assign operator.

Definition at line 345 of file AVLTree.cpp.

template<class key_type, class item_type>
AVLTreeNode< key_type, item_type > * DREAM::AVLTree< key_type, item_type >::begin (  ) 

Returns a pointer to the smallest element in the AVLTree.

Definition at line 589 of file AVLTree.cpp.

References DREAM::AVLTreeNode< key_type, item_type >::left_.

Referenced by DREAM::PriorityInversionList::add(), DREAM::ModelCheck::branching_point(), DREAM::Solution::deterministic(), DREAM::PriorityInversionList::find(), DREAM::Solution::fitness(), DREAM::operator<<(), DREAM::Thread::recent(), DREAM::Solution::regenerate_priorities(), DREAM::FixedPriorityScheduler::schedule(), DREAM::ModelCheck::trace_based_model_check(), DREAM::Solution::visitor(), and DREAM::Task::visitor_update_task_avltree().

template<class key_type, class item_type>
const AVLTreeNode< key_type, item_type > * DREAM::AVLTree< key_type, item_type >::begin (  )  const

Returns a pointer to the smallest element in the AVLTree.

Definition at line 603 of file AVLTree.cpp.

References DREAM::AVLTreeNode< key_type, item_type >::left_.

template<class key_type, class item_type>
void DREAM::AVLTree< key_type, item_type >::clear (  )  [inline]

Erases elements in the AVLTree.

Definition at line 617 of file AVLTree.cpp.

Referenced by DREAM::Scheduler::reset().

template<class key_type, class item_type>
void DREAM::AVLTree< key_type, item_type >::destroy (  ) 

Erases elements in the AVLTree, and calls delete on the item_type.

Use this function whenever you would like to iterate through the AVLTree, and erase dynamically allocated data.

Definition at line 628 of file AVLTree.cpp.

Referenced by DREAM::Solution::~Solution().

template<class key_type, class item_type>
bool DREAM::AVLTree< key_type, item_type >::empty (  )  [inline]

Returns true if the AVLTree is empty.

Definition at line 643 of file AVLTree.cpp.

Referenced by DREAM::Solution::fitness().

template<class key_type, class item_type>
bool DREAM::AVLTree< key_type, item_type >::empty (  )  const [inline]

Returns true if the AVLTree is empty.

Definition at line 649 of file AVLTree.cpp.

template<class key_type, class item_type>
AVLTreeNode< key_type, item_type > * DREAM::AVLTree< key_type, item_type >::end (  )  [inline]

Returns NULL.

Definition at line 655 of file AVLTree.cpp.

Referenced by DREAM::ModelCheck::branching_point(), DREAM::Solution::deterministic(), DREAM::PriorityInversionList::find(), DREAM::Solution::fitness(), DREAM::operator<<(), DREAM::Thread::recent(), DREAM::Solution::regenerate_priorities(), DREAM::ModelCheck::trace_based_model_check(), DREAM::Solution::visitor(), and DREAM::Task::visitor_update_task_avltree().

template<class key_type, class item_type>
const AVLTreeNode< key_type, item_type > * DREAM::AVLTree< key_type, item_type >::end (  )  const [inline]

Returns NULL.

Definition at line 661 of file AVLTree.cpp.

template<class key_type, class item_type>
void DREAM::AVLTree< key_type, item_type >::erase ( Iterator< AVLTreeNode< key_type, item_type > > &  iter  ) 

Erase a node from the AVLTree.

Definition at line 673 of file AVLTree.cpp.

template<class key_type, class item_type>
void DREAM::AVLTree< key_type, item_type >::erase ( key_type  key  )  [inline]

Erase a node from the AVLTree.

Definition at line 667 of file AVLTree.cpp.

template<class key_type, class item_type>
AVLTreeNode< key_type, item_type > * DREAM::AVLTree< key_type, item_type >::find ( const key_type &  key  ) 

Finds an AVLTree node in the AVLTree.

Definition at line 849 of file AVLTree.cpp.

References DREAM::AVLTreeNode< key_type, item_type >::first, DREAM::AVLTreeNode< key_type, item_type >::left_, and DREAM::AVLTreeNode< key_type, item_type >::right_.

Referenced by DREAM::PriorityInversionList::increment().

template<class key_type, class item_type>
const AVLTreeNode< key_type, item_type > * DREAM::AVLTree< key_type, item_type >::find ( const key_type &  key  )  const

Finds an AVLTree node in the AVLTree.

Definition at line 866 of file AVLTree.cpp.

References DREAM::AVLTreeNode< key_type, item_type >::first, DREAM::AVLTreeNode< key_type, item_type >::left_, and DREAM::AVLTreeNode< key_type, item_type >::right_.

template<class key_type, class item_type>
void DREAM::AVLTree< key_type, item_type >::insert ( key_type  key,
item_type  item 
)

Inserts an AVLTree node in the AVLTree.

Definition at line 959 of file AVLTree.cpp.

References DREAM::AVLTreeNode< key_type, item_type >::first, DREAM::AVLTreeNode< key_type, item_type >::left_, DREAM::AVLTreeNode< key_type, item_type >::right_, and DREAM::AVLTreeNode< key_type, item_type >::second.

Referenced by DREAM::Scheduler::add_error(), DREAM::Thread::enqueue(), DREAM::Scheduler::qos_add(), DREAM::Solution::regenerate_priorities(), DREAM::FixedPriorityScheduler::schedule(), DREAM::ModelCheck::trace_based_model_check(), DREAM::Scheduler::visitor_error_avltree(), and DREAM::Task::visitor_task_avltree().

template<class key_type, class item_type>
AVLTreeNode< key_type, item_type > * DREAM::AVLTree< key_type, item_type >::last (  )  [inline]

Returns an iterator to the last element of the AVLTree.

Definition at line 1000 of file AVLTree.cpp.

template<class key_type, class item_type>
const AVLTreeNode< key_type, item_type > * DREAM::AVLTree< key_type, item_type >::last (  )  const [inline]

Returns an iterator to the last element of the AVLTree.

Definition at line 1006 of file AVLTree.cpp.

template<class key_type, class item_type>
item_type & DREAM::AVLTree< key_type, item_type >::operator[] ( uint  i  ) 

operator [].

Definition at line 1012 of file AVLTree.cpp.

template<class key_type, class item_type>
const item_type & DREAM::AVLTree< key_type, item_type >::operator[] ( uint  i  )  const

operator [].

Definition at line 1027 of file AVLTree.cpp.

template<class key_type, class item_type>
uint DREAM::AVLTree< key_type, item_type >::size (  )  const [inline]

Return the number of items in the AVLTree.

Definition at line 1042 of file AVLTree.cpp.

Referenced by DREAM::PriorityInversionList::find(), DREAM::GeneticOptimize::mutate(), DREAM::Thread::recent(), DREAM::Solution::regenerate_subpriorities(), DREAM::FixedPriorityScheduler::schedule(), and DREAM::ModelCheck::trace_based_model_check().


Friends And Related Function Documentation

template<class key_type, class item_type>
friend class Iterator< AVLTreeNode< key_type, item_type > > [friend]

Allow iterators to manipulate protected members.

Definition at line 308 of file AVLTree.h.

template<class key_type, class item_type>
friend class Const_Iterator< AVLTreeNode< key_type, item_type > > [friend]

Allow iterators to manipulate protected members.

Definition at line 311 of file AVLTree.h.


Member Data Documentation

template<class key_type, class item_type>
AVLTreeNode<key_type, item_type>* DREAM::AVLTree< key_type, item_type >::root_ptr_ [protected]

Pointer to the root of the tree.

Definition at line 221 of file AVLTree.h.

template<class key_type, class item_type>
AVLTreeNode<key_type, item_type>* DREAM::AVLTree< key_type, item_type >::last_ptr_ [protected]

Pointer to the last element of the tree.

Definition at line 224 of file AVLTree.h.

template<class key_type, class item_type>
uint DREAM::AVLTree< key_type, item_type >::size_ [protected]

Stores the number of items in the AVLTree.

Definition at line 227 of file AVLTree.h.


The documentation for this class was generated from the following files:
Generated on Fri Jul 27 18:30:04 2007 for DREAM by  doxygen 1.5.1