ROSE  0.9.10.54
Public Types | Public Member Functions | List of all members
WorkList< T, Compare > Class Template Reference

Description

template<typename T, class Compare = std::less<T>>
class WorkList< T, Compare >

List of things to work on.

A WorkList is an ordered list of items of user-defined type. Items are inserted (and copied) onto either the front or back of the list and are removed from either the front or back, allowing the WorkList to be used as a queue, stack, or combination. The modifier method names (push, pop, unshift, shift) are the same as for lists in Perl, and the worklist operates in a similar manner: push/pop operate on one end of the list while unshift/shift operate on the other end of the list.

Methods that insert items can optionally check that the item to be inserted is not already in the list, and skip the insertion if it is. Their behavior in this regard is controlled by an optional Boolean (actually, boost::tribool) argument that that enables or disables the uniqueness check. If the argument is indeterminate (the default) then the uniqueness check depends on whether uniqueness checking was enabled or disabled when the list was constructed. The optional argument allows a list that was constructed one way to be used a different way, although doing so may be less efficient.

Subclasses WorkListUnique and WorkListNonUnique are convenient ways to create a worklist and provide better documentation as to the default setting for uniqueness checking.

Time and space complexity

Lists that are constructed to perform uniqueness checks store two copies of their elements: the extra copy is an std::map that's used for its ability to do O(log(N)) lookups for the uniqueness checks. Insertion is O(log N) regardless of whether uniqueness is checked at the time of insertion. Removal and existance are also O(log N).

Lists that are constructed to not perform uniqueness checks store only one copy of each element. Insertion and removal are constant time operations, but existance is linear.

Size is always a constant time operation even if the list is implemented with std::list.

Examples

The following code prints "7123456789"

static int tail[3] = {7, 8, 9}, head[3] = {3, 2, 1};
worklist.push(5);
worklist.unshift(4);
worklist.push(5); //no-op for WorkListUnique
worklist.push(6);
worklist.push(tail+0, tail+3);
worklist.unshift(head+0, head+3);
worklist.unshift(6, true); //no-op
worklist.unshift(7, false); //disable uniqueness check
while (!worklist.empty())
std::cout <<worklist.shift();

If we change the worklist to a WorkListNonUnique, then it would print "71234556789" instead (the only difference is that the second push(5) defaulted to non-unique insertion).

Definition at line 58 of file WorkLists.h.

#include <WorkLists.h>

Inheritance diagram for WorkList< T, Compare >:
Inheritance graph
[legend]

Public Types

typedef T value_type
 
typedef Compare key_compare
 

Public Member Functions

 WorkList (bool check_uniqueness=false)
 
bool empty () const
 Returns true if this work list is empty. More...
 
size_t size () const
 Returns the number of items in the work list. More...
 
void clear ()
 Reset the list to an empty state. More...
 
bool exists (const T &item) const
 Return true if the specified item is already on the work list. More...
 
bool unshift (const T &, boost::tribool check_uniqueness=boost::indeterminate)
 Add an item to the front of the work list. More...
 
template<class Iterator >
size_t unshift (const Iterator &begin, const Iterator &end, boost::tribool check_uniqueness=boost::indeterminate)
 Adds multiple items to the front of the work list. More...
 
shift ()
 Remove and return the item from the front of the work list. More...
 
bool push (const T &, boost::tribool check_uniqueness=boost::logic::indeterminate)
 Add an item to the back of the work list. More...
 
template<class Iterator >
size_t push (const Iterator &begin, const Iterator &end, boost::tribool check_uniqueness=boost::indeterminate)
 Adds multiple items to the back of the work list. More...
 
pop ()
 Remove an item from the back of the work list. More...
 
bool isEmpty () const ROSE_DEPRECATED("use empty instead")
 An alias for empty(). More...
 
take ()
 Remove and return an item from the front of the work list. More...
 
const T & examine () const ROSE_DEPRECATED("use front instead")
 Alias for front(). More...
 
const T & front () const
 Returns the object at the front/back of the list without removing it. More...
 
const T & back () const
 Returns the object at the front/back of the list without removing it. More...
 
void add (const T &item)
 Adds an item(s) to the end of the queue. More...
 
void add (const std::vector< T > &items)
 Adds an item(s) to the end of the queue. More...
 
void add (const std::set< T > &items)
 Adds an item(s) to the end of the queue. More...
 

Member Function Documentation

template<typename T, class Compare = std::less<T>>
bool WorkList< T, Compare >::empty ( ) const
inline
template<typename T, class Compare = std::less<T>>
size_t WorkList< T, Compare >::size ( void  ) const
inline

Returns the number of items in the work list.

This is a constant time operation.

Definition at line 69 of file WorkLists.h.

template<typename T, class Compare = std::less<T>>
void WorkList< T, Compare >::clear ( )
inline

Reset the list to an empty state.

Definition at line 72 of file WorkLists.h.

template<typename T, class Compare = std::less<T>>
bool WorkList< T, Compare >::exists ( const T &  item) const
inline

Return true if the specified item is already on the work list.

Time complexity is O(log(N)).

Definition at line 75 of file WorkLists.h.

template<typename T , class Compare >
bool WorkList< T, Compare >::unshift ( const T &  item,
boost::tribool  check_uniqueness = boost::indeterminate 
)

Add an item to the front of the work list.

If unique is true (the default) then the item is added to the list only if it's not already on the list. Returns true if the item was added to the list. Time complexity is O(log(N)).

Definition at line 168 of file WorkLists.h.

Referenced by WorkList< T, Compare >::unshift().

template<typename T , class Compare >
template<class Iterator >
size_t WorkList< T, Compare >::unshift ( const Iterator &  begin,
const Iterator &  end,
boost::tribool  check_uniqueness = boost::indeterminate 
)

Adds multiple items to the front of the work list.

If unique is true (the default) then an item is added to the list only if it's not already on the list. Returns the number of items that were added to the list. Time complexity is O(M log(N+M)) where M is the number of items being inserted.

Definition at line 190 of file WorkLists.h.

References WorkList< T, Compare >::unshift().

template<typename T , class Compare >
T WorkList< T, Compare >::shift ( )

Remove and return the item from the front of the work list.

The list must not be empty. Time complexity is O(log(N)).

Definition at line 236 of file WorkLists.h.

References WorkList< T, Compare >::empty().

Referenced by Rose::BinaryAnalysis::ControlFlow::fixup_fcall_fret(), and WorkList< T, Compare >::take().

template<typename T , class Compare >
bool WorkList< T, Compare >::push ( const T &  item,
boost::tribool  check_uniqueness = boost::logic::indeterminate 
)

Add an item to the back of the work list.

If unique is true (the default) then the item is added to the list only if it's not already on the list. Returns true if the item was added to the list. Time complexity is O(log(N)).

Definition at line 202 of file WorkLists.h.

Referenced by WorkList< T, Compare >::add(), Rose::BinaryAnalysis::ControlFlow::fixup_fcall_fret(), and WorkList< T, Compare >::push().

template<typename T , class Compare >
template<class Iterator >
size_t WorkList< T, Compare >::push ( const Iterator &  begin,
const Iterator &  end,
boost::tribool  check_uniqueness = boost::indeterminate 
)

Adds multiple items to the back of the work list.

If unique is true (the default) then an item is added to the list only if it's not already on the list. Returns the number of items that were added to the list. Time complexity is O(M log(N+M)) where M is the number of items being inserted.

Definition at line 224 of file WorkLists.h.

References WorkList< T, Compare >::push().

template<typename T , class Compare >
T WorkList< T, Compare >::pop ( )

Remove an item from the back of the work list.

The list must not be empty. Time complexity is O(log(N)).

Definition at line 247 of file WorkLists.h.

References WorkList< T, Compare >::empty().

template<typename T , class Compare >
const T & WorkList< T, Compare >::front ( ) const

Returns the object at the front/back of the list without removing it.

The list must not be empty. Items are returned by const reference because changing their value could change their sort order. If you need to change the value of the front or back element then do so by a shift-modify-unshift or pop-modify-push sequence. Time complexity is O(1).

Definition at line 258 of file WorkLists.h.

References WorkList< T, Compare >::empty().

Referenced by WorkList< T, Compare >::examine().

template<typename T , class Compare >
const T & WorkList< T, Compare >::back ( ) const

Returns the object at the front/back of the list without removing it.

The list must not be empty. Items are returned by const reference because changing their value could change their sort order. If you need to change the value of the front or back element then do so by a shift-modify-unshift or pop-modify-push sequence. Time complexity is O(1).

Definition at line 266 of file WorkLists.h.

References WorkList< T, Compare >::empty().

template<typename T , class Compare >
bool WorkList< T, Compare >::isEmpty ( ) const

An alias for empty().

This is deprecated; use empty() instead, which is the naming convention used by the STL.

Definition at line 291 of file WorkLists.h.

References WorkList< T, Compare >::empty().

template<typename T, class Compare = std::less<T>>
void WorkList< T, Compare >::add ( const T &  item)
inline

Adds an item(s) to the end of the queue.

The item is not added if the list was constructed to check for duplicates and the item being inserted is already in the list.

Definition at line 123 of file WorkLists.h.

References WorkList< T, Compare >::push().

template<typename T, class Compare = std::less<T>>
void WorkList< T, Compare >::add ( const std::vector< T > &  items)
inline

Adds an item(s) to the end of the queue.

The item is not added if the list was constructed to check for duplicates and the item being inserted is already in the list.

Definition at line 124 of file WorkLists.h.

References WorkList< T, Compare >::push().

template<typename T, class Compare = std::less<T>>
void WorkList< T, Compare >::add ( const std::set< T > &  items)
inline

Adds an item(s) to the end of the queue.

The item is not added if the list was constructed to check for duplicates and the item being inserted is already in the list.

Definition at line 125 of file WorkLists.h.

References WorkList< T, Compare >::push().

template<typename T, class Compare = std::less<T>>
T WorkList< T, Compare >::take ( )
inline

Remove and return an item from the front of the work list.

The list must not be empty.

Definition at line 129 of file WorkLists.h.

References WorkList< T, Compare >::shift().

template<typename T , class Compare >
const T & WorkList< T, Compare >::examine ( ) const

Alias for front().

Definition at line 299 of file WorkLists.h.

References WorkList< T, Compare >::front().


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