operations_research::DenseDoublyLinkedList Class Reference

#include <dense_doubly_linked_list.h>

Public Member Functions
template<class T >
	DenseDoublyLinkedList (const T &sorted_elements)
int	Size () const
int	Next (int i) const
	Inline implementations (forced inline for the speed).
int	Prev (int i) const
void	Remove (int i)
	You must not call Remove() twice with the same element.

Detailed Description

Specialized doubly-linked list that initially holds [0..n-1] in an arbitrary (user-specified) and fixed order. It then supports O(1) removal and access to the next and previous element of a given (non-removed) element.

It is very fast and compact: it uses exactly 8*n bytes of memory.

Definition at line 29 of file dense_doubly_linked_list.h.

Constructor & Destructor Documentation

DenseDoublyLinkedList()

template<class T >

operations_research::DenseDoublyLinkedList::DenseDoublyLinkedList ( const T & sorted_elements )

explicit

You can construct a DenseDoublyLinkedList with any range-iterable class that also has a size() method. The order of the elements is given by the user and will never change (modulo the removal of elements).

Definition at line 77 of file dense_doubly_linked_list.h.

Member Function Documentation

Next()

int operations_research::DenseDoublyLinkedList::Next ( int i ) const

inline

Inline implementations (forced inline for the speed).

Next() (resp. Prev()) must be called on elements that haven't yet been removed. They will return -1 if called on the last (resp. first) element.

Definition at line 54 of file dense_doubly_linked_list.h.

Prev()

int operations_research::DenseDoublyLinkedList::Prev ( int i ) const

inline

Definition at line 61 of file dense_doubly_linked_list.h.

Remove()

void operations_research::DenseDoublyLinkedList::Remove ( int i )

inline

You must not call Remove() twice with the same element.

Definition at line 68 of file dense_doubly_linked_list.h.

Size()

int operations_research::DenseDoublyLinkedList::Size ( ) const

inline

Definition at line 37 of file dense_doubly_linked_list.h.

---

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

• ortools/algorithms/dense_doubly_linked_list.h