ROSE 0.11.145.147
|
A doubly-linked list of distinct items.
Each item on the list is unequal to any other item on the list. Most operations take O(log N) time.
Definition at line 24 of file DistinctList.h.
#include <Sawyer/DistinctList.h>
Public Types | |
typedef T | Item |
typedef Cmp | Comparator |
typedef std::list< Item > | Items |
Public Member Functions | |
DistinctList () | |
Construct an empty list. | |
template<class T2 , class Cmp2 > | |
DistinctList (const DistinctList< T2, Cmp2 > &other) | |
Copy-construct a list. | |
template<class T2 , class Cmp2 > | |
DistinctList & | operator= (const DistinctList< T2, Cmp2 > &other) |
Assign one list to another. | |
void | clear () |
Clear the list. | |
bool | isEmpty () const |
Determines whether list is empty. | |
size_t | size () const |
Number of items in list. | |
bool | exists (const Item &item) const |
Determine if an item exists. | |
size_t | position (const Item &item) const |
Determine the position of an item. | |
const Item & | front () const |
Reference to item at front of list. | |
const Item & | back () const |
Reference to item at back of list. | |
void | pushFront (const Item &item) |
Insert item at front of list if distinct. | |
void | pushBack (const Item &item) |
Insert item at back of list if distinct. | |
Item | popFront () |
Return and erase item at front of list. | |
Item | popBack () |
Return and erase item at back of list. | |
void | erase (const Item &item) |
Erase an item from the list. | |
const Items & | items () const |
Return all items as a list. | |
typedef T Sawyer::Container::DistinctList< T, Cmp >::Item |
Definition at line 26 of file DistinctList.h.
typedef Cmp Sawyer::Container::DistinctList< T, Cmp >::Comparator |
Definition at line 27 of file DistinctList.h.
typedef std::list<Item> Sawyer::Container::DistinctList< T, Cmp >::Items |
Definition at line 28 of file DistinctList.h.
|
inline |
Construct an empty list.
Definition at line 37 of file DistinctList.h.
|
inline |
Copy-construct a list.
Definition at line 41 of file DistinctList.h.
References Sawyer::Container::DistinctList< T, Cmp >::items(), and Sawyer::Container::DistinctList< T, Cmp >::pushBack().
|
inline |
Assign one list to another.
Definition at line 48 of file DistinctList.h.
References Sawyer::Container::DistinctList< T, Cmp >::clear(), Sawyer::Container::DistinctList< T, Cmp >::items(), and Sawyer::Container::DistinctList< T, Cmp >::pushBack().
|
inline |
Clear the list.
Erase all items from the list making the list empty.
Definition at line 58 of file DistinctList.h.
References Sawyer::Container::Map< K, T, Cmp, Alloc >::clear().
Referenced by Sawyer::Container::DistinctList< T, Cmp >::operator=(), and Rose::BinaryAnalysis::DataFlow::Engine< Cfg_, State_, TransferFunction_, MergeFunction_, PathFeasibility_ >::reset().
|
inline |
Determines whether list is empty.
Returns true if the list is empty, false if it contains anything. Time complexity is constant.
Definition at line 66 of file DistinctList.h.
References Sawyer::Container::Map< K, T, Cmp, Alloc >::isEmpty().
Referenced by Sawyer::Container::DistinctList< T, Cmp >::back(), Sawyer::Container::DistinctList< T, Cmp >::front(), Sawyer::Container::DistinctList< T, Cmp >::popBack(), Sawyer::Container::DistinctList< T, Cmp >::popFront(), and Rose::BinaryAnalysis::DataFlow::Engine< Cfg_, State_, TransferFunction_, MergeFunction_, PathFeasibility_ >::runOneIteration().
|
inline |
Number of items in list.
Returns the total number of items in the list in constant time.
Definition at line 73 of file DistinctList.h.
References Sawyer::Container::Map< K, T, Cmp, Alloc >::size().
Referenced by Sawyer::Container::DistinctList< T, Cmp >::position().
|
inline |
Determine if an item exists.
Returns true if the specified item exists in the list, false if not.
Definition at line 80 of file DistinctList.h.
References Sawyer::Container::Map< K, T, Cmp, Alloc >::exists().
|
inline |
Determine the position of an item.
Returns the position of an item from the beginning of the list. This is an O(n) operation.
Definition at line 87 of file DistinctList.h.
References Sawyer::Container::Map< K, T, Cmp, Alloc >::exists(), and Sawyer::Container::DistinctList< T, Cmp >::size().
|
inline |
Reference to item at front of list.
Returns a const reference to the item at the front of the list, or throws an std::runtime_error
if the list is empty.
Definition at line 103 of file DistinctList.h.
References Sawyer::Container::DistinctList< T, Cmp >::isEmpty().
|
inline |
Reference to item at back of list.
Returns a const reference to the item at the back of the list, or throws an std::runtime_error
if the list is empty.
Definition at line 113 of file DistinctList.h.
References Sawyer::Container::DistinctList< T, Cmp >::isEmpty().
|
inline |
Insert item at front of list if distinct.
If item
does not exist in the list then insert a copy at the front of the list. If the item exists then do nothing.
Definition at line 122 of file DistinctList.h.
References Sawyer::Container::Map< K, T, Cmp, Alloc >::find(), Sawyer::Container::Map< K, T, Cmp, Alloc >::insert(), and Sawyer::Container::Map< K, T, Cmp, Alloc >::nodes().
|
inline |
Insert item at back of list if distinct.
If item
does not exist in the list then insert a copy at the back of the list. If the item exists then do nothing.
Definition at line 133 of file DistinctList.h.
References Sawyer::Container::Map< K, T, Cmp, Alloc >::find(), Sawyer::Container::Map< K, T, Cmp, Alloc >::insert(), and Sawyer::Container::Map< K, T, Cmp, Alloc >::nodes().
Referenced by Sawyer::Container::DistinctList< T, Cmp >::DistinctList(), Rose::BinaryAnalysis::DataFlow::Engine< Cfg_, State_, TransferFunction_, MergeFunction_, PathFeasibility_ >::insertStartingVertex(), Sawyer::Container::DistinctList< T, Cmp >::operator=(), and Rose::BinaryAnalysis::DataFlow::Engine< Cfg_, State_, TransferFunction_, MergeFunction_, PathFeasibility_ >::runOneIteration().
|
inline |
Return and erase item at front of list.
Returns a copy of the item at the front of the list and that item is removed from the list. Throws an std::runtime_error
if the list is empty.
Definition at line 145 of file DistinctList.h.
References Sawyer::Container::Map< K, T, Cmp, Alloc >::erase(), and Sawyer::Container::DistinctList< T, Cmp >::isEmpty().
Referenced by Rose::BinaryAnalysis::DataFlow::Engine< Cfg_, State_, TransferFunction_, MergeFunction_, PathFeasibility_ >::runOneIteration().
|
inline |
Return and erase item at back of list.
Returns a copy of the item at the back of the list and that item is removed from the list. Throws an std::runtime_error
if the list is empty.
Definition at line 158 of file DistinctList.h.
References Sawyer::Container::Map< K, T, Cmp, Alloc >::erase(), and Sawyer::Container::DistinctList< T, Cmp >::isEmpty().
|
inline |
Erase an item from the list.
Erases the item equal to item
from the list if it exists, does nothing otherwise.
Definition at line 170 of file DistinctList.h.
References Sawyer::Container::Map< K, T, Cmp, Alloc >::eraseAt(), Sawyer::Container::Map< K, T, Cmp, Alloc >::find(), Sawyer::Container::Map< K, T, Cmp, Alloc >::nodes(), and Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::value().
|
inline |
Return all items as a list.
Returns all items as a list. The list is const since it should only be modified through this API.
Definition at line 181 of file DistinctList.h.
Referenced by Sawyer::Container::DistinctList< T, Cmp >::DistinctList(), Sawyer::Container::DistinctList< T, Cmp >::operator=(), and Rose::BinaryAnalysis::DataFlow::Engine< Cfg_, State_, TransferFunction_, MergeFunction_, PathFeasibility_ >::runOneIteration().