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"
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 60 of file WorkLists.h.
#include <frontend/BinaryFormats/WorkLists.h>
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... | |
| T | 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... | |
| T | pop () |
| Remove an item from the back of the work list. More... | |
| T | take () |
| Remove and return an item from the front of the work list. 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
|
inline |
Returns true if this work list is empty.
This is a constant time operation.
Definition at line 68 of file WorkLists.h.
Referenced by Rose::BinaryAnalysis::ControlFlow::fixup_fcall_fret().
|
inline |
Returns the number of items in the work list.
This is a constant time operation.
Definition at line 71 of file WorkLists.h.
|
inline |
Reset the list to an empty state.
Definition at line 74 of file WorkLists.h.
|
inline |
Return true if the specified item is already on the work list.
Time complexity is O(log(N)).
Definition at line 77 of file WorkLists.h.
| 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 164 of file WorkLists.h.
| 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 186 of file WorkLists.h.
| 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 232 of file WorkLists.h.
Referenced by Rose::BinaryAnalysis::ControlFlow::fixup_fcall_fret(), and WorkList< T, Compare >::take().
| 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 198 of file WorkLists.h.
Referenced by WorkList< T, Compare >::add(), and Rose::BinaryAnalysis::ControlFlow::fixup_fcall_fret().
| 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 220 of file WorkLists.h.
| 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 243 of file WorkLists.h.
| 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 254 of file WorkLists.h.
| 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 262 of file WorkLists.h.
|
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 122 of file WorkLists.h.
References WorkList< T, Compare >::push().
|
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().
|
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().
|
inline |
Remove and return an item from the front of the work list.
The list must not be empty.
Definition at line 128 of file WorkLists.h.
References WorkList< T, Compare >::shift().
The documentation for this class was generated from the following file:
