Implements a guarded, doubly linked list structure. More...

#include <doubly_linked_list.h>

Classes
class	iterator
	iterators allow the list to be traversed. More...

Public Member Functions
	doubly_linked_list ()
	constructs a blank list. More...

	~doubly_linked_list ()
	invalidates all contents of the list and destroys all child nodes. More...

int	elements () const
	returns the number of items currently in the list. More...

bool	empty () const
	returns true if the list is empty. More...

iterator	head () const
	returns an iterator located at the head of the list. More...

iterator	tail () const
	returns an iterator located at the tail of the list. More...

int	index (const iterator &it) const
	returns the zero-based index of the cursor's position from the head. More...

bool	set_index (iterator &to_set, int new_index)
	positions the iterator "to_set" at the index specified. More...

void	append (iterator &where, node *new_node)
	adds a "new_node" into the list immediately after "where". More...

void	insert (iterator &where, node *new_node)
	places a "new_node" immediately before the current node in the list. More...

node *	remove (iterator &where)
	extracts the current item from "where" and repairs the hole. More...

void	zap (iterator &where)
	wipes out the item at "where", including its contents. More...

void	zap_all ()
	destroys all the list elements and makes the list empty. More...

bool	forward (iterator &where, int count)
	moves the list pointer "count" items towards the tail. More...

bool	backward (iterator &where, int count)
	moves the list pointer "count" items towards the head. More...

int	items_from_head (const iterator &where) const
	Returns the number of elements between the current item and the head. More...

int	items_from_tail (const iterator &where) const
	Returns the number of elements between the current item and the tail. More...

Friends
class	iterator

Detailed Description

Implements a guarded, doubly linked list structure.

The list is viewed one element at a time, through the monocular of an iterator, which keeps track of the current position in the list. the iterator's cursor can be shifted around at will. nodes can be added to the list before or after the cursor, and the node pointed at by the cursor can be queried or modified. Using multiple iterators is fine as long as you guarantee that they either are all just reading the list or that you have a valid access pattern of reads and writes such that no iterator's cursor is affected. Note that this list is not thread safe.

Definition at line 40 of file doubly_linked_list.h.

Constructor & Destructor Documentation

◆ doubly_linked_list()

nodes::doubly_linked_list::doubly_linked_list ( )

constructs a blank list.

Definition at line 95 of file doubly_linked_list.cpp.

References nodes::NEXT, nodes::PREVIOUS, and nodes::node::set_link().

◆ ~doubly_linked_list()

nodes::doubly_linked_list::~doubly_linked_list ( )

invalidates all contents of the list and destroys all child nodes.

Definition at line 104 of file doubly_linked_list.cpp.

References empty(), head(), basis::WHACK(), and zap().

Member Function Documentation

◆ append()

void nodes::doubly_linked_list::append	(	iterator &	where,
		node *	new_node
	)

adds a "new_node" into the list immediately after "where".

the nodes previously following the current node (if any) will follow after the "new_node". this does not change the current position. ownership of "new_node" is taken over by the list.

Definition at line 223 of file doubly_linked_list.cpp.

References empty(), nodes::node::get_link(), nodes::node::insert_link(), nodes::node::links(), nodes::NEXT, NULL_POINTER, nodes::PREVIOUS, and nodes::node::set_link().

◆ backward()

bool nodes::doubly_linked_list::backward	(	iterator &	where,
		int	count
	)

moves the list pointer "count" items towards the head.

Definition at line 142 of file doubly_linked_list.cpp.

References nodes::doubly_linked_list::iterator::is_tail(), items_from_head(), and nodes::doubly_linked_list::iterator::previous().

◆ elements()

int nodes::doubly_linked_list::elements ( ) const

returns the number of items currently in the list.

this is a costly operation.

Definition at line 152 of file doubly_linked_list.cpp.

References empty(), nodes::node::get_link(), and nodes::NEXT.

◆ empty()

bool nodes::doubly_linked_list::empty ( ) const

returns true if the list is empty.

this is really quick compared to checking the number of elements.

Definition at line 113 of file doubly_linked_list.cpp.

References nodes::node::get_link(), and nodes::NEXT.

Referenced by append(), elements(), insert(), remove(), set_index(), zap_all(), and ~doubly_linked_list().

◆ forward()

bool nodes::doubly_linked_list::forward	(	iterator &	where,
		int	count
	)

moves the list pointer "count" items towards the tail.

Note: forward and backward operate on elements; the head and tail guard are not included in the count. Also, negative values of "count" are ignored.

Definition at line 132 of file doubly_linked_list.cpp.

References nodes::doubly_linked_list::iterator::is_head(), items_from_tail(), and nodes::doubly_linked_list::iterator::next().

◆ head()

iterator nodes::doubly_linked_list::head ( ) const

inline

returns an iterator located at the head of the list.

Definition at line 115 of file doubly_linked_list.h.

References iterator.

Referenced by zap_all(), and ~doubly_linked_list().

◆ index()

int nodes::doubly_linked_list::index ( const iterator & it ) const

inline

returns the zero-based index of the cursor's position from the head.

this is a synonym for items_from_head().

Definition at line 120 of file doubly_linked_list.h.

References items_from_head().

Referenced by items_from_head(), and items_from_tail().

◆ insert()

void nodes::doubly_linked_list::insert	(	iterator &	where,
		node *	new_node
	)

places a "new_node" immediately before the current node in the list.

the "new_node" will follow the prior precursor to the current node. this does not change the current position. ownership of "new_node" is taken over by the list. after the call, the iterator points at the new node.

Definition at line 239 of file doubly_linked_list.cpp.

References empty(), nodes::node::get_link(), nodes::node::insert_link(), nodes::node::links(), nodes::NEXT, NULL_POINTER, nodes::PREVIOUS, and nodes::node::set_link().

◆ items_from_head()

int nodes::doubly_linked_list::items_from_head ( const iterator & where ) const

Returns the number of elements between the current item and the head.

zero is returned if this is at the first element or the head.

Definition at line 164 of file doubly_linked_list.cpp.

References nodes::node::get_link(), index(), nodes::doubly_linked_list::iterator::is_head(), and nodes::NEXT.

Referenced by backward(), and index().

◆ items_from_tail()

int nodes::doubly_linked_list::items_from_tail ( const iterator & where ) const

Returns the number of elements between the current item and the tail.

zero is returned if this is at the last element or the tail.

Definition at line 177 of file doubly_linked_list.cpp.

References nodes::node::get_link(), index(), nodes::doubly_linked_list::iterator::is_tail(), and nodes::PREVIOUS.

Referenced by forward().

◆ remove()

node * nodes::doubly_linked_list::remove ( iterator & where )

extracts the current item from "where" and repairs the hole.

NULL_POINTER is returned if the list was empty. the current position is set to the node that used to be after the node that has been removed. after the call, the iterator points at the new node.

Definition at line 202 of file doubly_linked_list.cpp.

References empty(), nodes::node::get_link(), nodes::NEXT, NULL_POINTER, nodes::PREVIOUS, and nodes::node::set_link().

Referenced by zap().

◆ set_index()

bool nodes::doubly_linked_list::set_index	(	iterator &	to_set,
		int	new_index
	)

positions the iterator "to_set" at the index specified.

Definition at line 119 of file doubly_linked_list.cpp.

References empty(), nodes::node::get_link(), and nodes::NEXT.

◆ tail()

iterator nodes::doubly_linked_list::tail ( ) const

inline

returns an iterator located at the tail of the list.

Definition at line 117 of file doubly_linked_list.h.

References iterator.

◆ zap()

void nodes::doubly_linked_list::zap ( iterator & where )

wipes out the item at "where", including its contents.

the current position is reset to the item after the now defunct item (or the tail).

Definition at line 221 of file doubly_linked_list.cpp.

References remove().

Referenced by zap_all(), and ~doubly_linked_list().

◆ zap_all()

void nodes::doubly_linked_list::zap_all ( )

destroys all the list elements and makes the list empty.

any existing iterators will be invalidated by this.

Definition at line 255 of file doubly_linked_list.cpp.

References empty(), head(), and zap().

Friends And Related Function Documentation

◆ iterator

friend class iterator

friend

Definition at line 178 of file doubly_linked_list.h.

Referenced by head(), and tail().

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

/opt/feistymeow.org/feisty_meow/nucleus/library/nodes/doubly_linked_list.h
/opt/feistymeow.org/feisty_meow/nucleus/library/nodes/doubly_linked_list.cpp

Classes

Public Member Functions

Friends

Detailed Description

Constructor & Destructor Documentation

◆ doubly_linked_list()

◆ ~doubly_linked_list()

Member Function Documentation

◆ append()

◆ backward()

◆ elements()

◆ empty()

◆ forward()

◆ head()

◆ index()

◆ insert()

◆ items_from_head()

◆ items_from_tail()

◆ remove()

◆ set_index()

◆ tail()

◆ zap()

◆ zap_all()

Friends And Related Function Documentation

◆ iterator