ROSE 0.11.145.147
Public Types | Public Member Functions | List of all members
Sawyer::Container::DistinctList< T, Cmp > Class Template Reference

Description

template<class T, class Cmp = std::less<T>>
class Sawyer::Container::DistinctList< T, Cmp >

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>

Inheritance diagram for Sawyer::Container::DistinctList< T, Cmp >:
Inheritance graph
[legend]

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 >
DistinctListoperator= (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.
 

Member Typedef Documentation

◆ Item

template<class T , class Cmp = std::less<T>>
typedef T Sawyer::Container::DistinctList< T, Cmp >::Item

Definition at line 26 of file DistinctList.h.

◆ Comparator

template<class T , class Cmp = std::less<T>>
typedef Cmp Sawyer::Container::DistinctList< T, Cmp >::Comparator

Definition at line 27 of file DistinctList.h.

◆ Items

template<class T , class Cmp = std::less<T>>
typedef std::list<Item> Sawyer::Container::DistinctList< T, Cmp >::Items

Definition at line 28 of file DistinctList.h.

Constructor & Destructor Documentation

◆ DistinctList() [1/2]

template<class T , class Cmp = std::less<T>>
Sawyer::Container::DistinctList< T, Cmp >::DistinctList ( )
inline

Construct an empty list.

Definition at line 37 of file DistinctList.h.

◆ DistinctList() [2/2]

template<class T , class Cmp = std::less<T>>
template<class T2 , class Cmp2 >
Sawyer::Container::DistinctList< T, Cmp >::DistinctList ( const DistinctList< T2, Cmp2 > &  other)
inline

Member Function Documentation

◆ operator=()

template<class T , class Cmp = std::less<T>>
template<class T2 , class Cmp2 >
DistinctList & Sawyer::Container::DistinctList< T, Cmp >::operator= ( const DistinctList< T2, Cmp2 > &  other)
inline

◆ clear()

template<class T , class Cmp = std::less<T>>
void Sawyer::Container::DistinctList< T, Cmp >::clear ( )
inline

◆ isEmpty()

template<class T , class Cmp = std::less<T>>
bool Sawyer::Container::DistinctList< T, Cmp >::isEmpty ( ) const
inline

◆ size()

template<class T , class Cmp = std::less<T>>
size_t Sawyer::Container::DistinctList< T, Cmp >::size ( ) const
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().

◆ exists()

template<class T , class Cmp = std::less<T>>
bool Sawyer::Container::DistinctList< T, Cmp >::exists ( const Item &  item) const
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().

◆ position()

template<class T , class Cmp = std::less<T>>
size_t Sawyer::Container::DistinctList< T, Cmp >::position ( const Item &  item) const
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().

◆ front()

template<class T , class Cmp = std::less<T>>
const Item & Sawyer::Container::DistinctList< T, Cmp >::front ( ) const
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().

◆ back()

template<class T , class Cmp = std::less<T>>
const Item & Sawyer::Container::DistinctList< T, Cmp >::back ( ) const
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().

◆ pushFront()

template<class T , class Cmp = std::less<T>>
void Sawyer::Container::DistinctList< T, Cmp >::pushFront ( const Item &  item)
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().

◆ pushBack()

template<class T , class Cmp = std::less<T>>
void Sawyer::Container::DistinctList< T, Cmp >::pushBack ( const Item &  item)
inline

◆ popFront()

template<class T , class Cmp = std::less<T>>
Item Sawyer::Container::DistinctList< T, Cmp >::popFront ( )
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().

◆ popBack()

template<class T , class Cmp = std::less<T>>
Item Sawyer::Container::DistinctList< T, Cmp >::popBack ( )
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().

◆ erase()

template<class T , class Cmp = std::less<T>>
void Sawyer::Container::DistinctList< T, Cmp >::erase ( const Item &  item)
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().

◆ items()

template<class T , class Cmp = std::less<T>>
const Items & Sawyer::Container::DistinctList< T, Cmp >::items ( ) const
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().


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