#include <htlist.H>

Inheritance diagram for Aleph::HTList:

Classes
class	Iterator

Public Member Functions
	HTList () noexcept
	Initialize an empty list.

void	reset ()

bool	is_empty () const noexcept

bool	is_unitarian () const noexcept

bool	is_unitarian_or_empty () const noexcept

Slinknc *	get_head () const noexcept

Slinknc *	get_tail () const noexcept

Slinknc *	get_first () const noexcept

Slinknc *	get_last () const noexcept
	Return the last item of the list (`nullptr` if the list is empty)

HTList &	swap (HTList &l) noexcept
	Swap in constant time (very fast) 'this' elements with 'l' list elements Referenced by append(), insert(), reverse() and split_list(). More...

void	insert (Slinknc *link) noexcept

void	append (Slinknc *link) noexcept

void	append (HTList &l) noexcept

void	put (Slinknc *link) noexcept

void	concat (HTList &l) noexcept

void	concat_list (HTList &l) noexcept

void	insert (HTList &l) noexcept

void	insert (Slinknc *link, HTList &list) noexcept

Slinknc *	remove_head_ne () noexcept

Slinknc *	remove_head ()

Slinknc *	remove_first_ne () noexcept

Slinknc *	remove_first ()

bool	remove (Slinknc *link)

void	push (Slinknc *link) noexcept

Slinknc *	pop ()

Slinknc *	top ()

size_t	split_list (HTList &l, HTList &r) noexcept

size_t	split_list_ne (HTList &l, HTList &r) noexcept

size_t	split (HTList &l, HTList &r) noexcept

size_t	reverse () noexcept

size_t	reverse_list () noexcept

void	cut (Slinknc *link, HTList &list) noexcept
	It makes reference to is_empty(). Referenced by cut_list(). More...

void	cut_list (Slinknc *link, HTList &list) noexcept

void	remove_all_and_delete () noexcept

size_t	size () const noexcept

void	rotate_left (size_t n)

Detailed Description

Single linked list of nodes.

HTList models a list of nodes of type Slinknc. A Slinknc object is a link that could be contained inside any data structure. The possibility for belonging to a HTList is defined for the owner of one o more objects of typeSlinknc`.

A HTlist object maintains two references. The first one is called head" and corresponds to the first node. The second one is called tail and corresponds to last node.

Take in account that this class does not manage memory neither access to the data that could be stored in the nodes. Slinknc y Snodenc. However, since this class is inherited by other more sophisticated classes, we will use the term "item" instead of node for referring an element of this list of nodes.

See also: Slinknc Snodenc DynList

Author: Alejandro Mujica; Leandro Rabindranath LeÃ³n

Member Function Documentation

◆ append() [1/2]

void Aleph::HTList::append ( Slinknc * link )

inlinenoexcept

Insert link as last element

Parameters

[in] link New element that will be inserted

Here is the caller graph for this function:

◆ append() [2/2]

void Aleph::HTList::append ( HTList & l )

inlinenoexcept

Join 'this' with 'l' through list end

Parameters

[in] l List that will be inserted through list end

Here is the call graph for this function:

◆ concat()

void Aleph::HTList::concat ( HTList & l )

inlinenoexcept

Concat to 'this' all 'l' list; 'l' becomes empty

◆ concat_list()

void Aleph::HTList::concat_list ( HTList & l )

inlinenoexcept

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ cut()

void Aleph::HTList::cut	(	Slinknc *	link,
		HTList &	list
	)

inlinenoexcept

It makes reference to is_empty().
Referenced by cut_list().

It cuts 'this' over 'link' element and it puts all remaining elements

Parameters

[in]	link	Element where 'list' will be cut.
[in]	list	List that will be cut in link

◆ cut_list()

void Aleph::HTList::cut_list	(	Slinknc *	link,
		HTList &	list
	)

inlinenoexcept

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ get_first()

Slinknc* Aleph::HTList::get_first ( ) const

inlinenoexcept

Return list first element

Here is the caller graph for this function:

◆ get_head()

Slinknc* Aleph::HTList::get_head ( ) const

inlinenoexcept

Return list head (first element)

◆ get_tail()

Slinknc* Aleph::HTList::get_tail ( ) const

inlinenoexcept

Return list tail (first element)

◆ insert() [1/3]

void Aleph::HTList::insert ( Slinknc * link )

inlinenoexcept

Insert link as first element

Parameters

[in] link New element that will be inserted

Here is the caller graph for this function:

◆ insert() [2/3]

void Aleph::HTList::insert ( HTList & l )

inlinenoexcept

Insert starting in link (contained in 'this' list) the 'list' list. 'list' becomes empty

Parameters

[in]	link	Element where 'list' will start
[in]	list	List that will be inserted after link

◆ insert() [3/3]

void Aleph::HTList::insert	(	Slinknc *	link,
		HTList &	list
	)

inlinenoexcept

Insert a list into this after one of its items.

insert(link, list) assumes that link points to a item of this and inserts in constant time list just after the item pointed by link. The order of list is not altered. but list becomes empty after insertion.

Suppose the following situation

this-->t1-->t2-->t3-->t4-->t5-->t6-->t7-->t8
                ^

| link

l–>l1–>l2–>l3–>l4

Then insert(link, list) produces:

this-->t1-->t2-->t3-->t4-->l1-->l2-->l3-->l4-->t5-->t6-->t7-->t8

l becomes empty

Parameters

[in]	link	to the item after one wants to insert `list`
[in]	list	to be inserted after item pointed by `link`

◆ is_empty()

bool Aleph::HTList::is_empty ( ) const

inlinenoexcept

Return true if list is empty

Here is the caller graph for this function:

◆ is_unitarian()

bool Aleph::HTList::is_unitarian ( ) const

inlinenoexcept

Return true if the list contains exactly just one element

◆ is_unitarian_or_empty()

bool Aleph::HTList::is_unitarian_or_empty ( ) const

inlinenoexcept

Return true if list contains one element or is empty

◆ push()

void Aleph::HTList::push ( Slinknc * link )

inlinenoexcept

Insert link as first element

Here is the call graph for this function:

◆ put()

void Aleph::HTList::put ( Slinknc * link )

inlinenoexcept

Insert link as last element

◆ remove()

bool Aleph::HTList::remove ( Slinknc * link )

inline

Remove from the list the item pointed by link

remove(link) perform a sequential traversal of this until find link. Then link is removed.

This method has a complexity of $O(n)$ for worst and average case.

Parameters

[in] link pointer to the item to be removed.

Returns: true if link was found and removed: false otherwise

Exceptions

underflow_error if the list is empty

Here is the call graph for this function:

◆ remove_all_and_delete()

void Aleph::HTList::remove_all_and_delete ( )

inlinenoexcept

Remove and free memory for all the items of list.

remove_all_and_delete() remove each item of the list and call to delete operator on the removed item. At the end of call, all the items were removed, all the memory freed qand the list emptied.

Warning: This method only has sense if the items of list were dynamically allocated with new. Although That is very frequently the case, there are some exceptions. So, be sure that the items were allocated with new operator.

Here is the call graph for this function:

◆ remove_head()

Aleph::HTList::remove_head ( )

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Remove the header item from the list.

Returns: a pointer to the removed item

Exceptions

underflow_error if the list is empty

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Remove the first item of this.

This synonym is adequate when this is dealed as a stack.

Returns: a pointer to the removed item.

Exceptions

underflow_error if the list is empty

Here is the call graph for this function:

Here is the caller graph for this function:

◆ remove_head_ne()

Slinknc* Aleph::HTList::remove_head_ne ( )

inlinenoexcept

It deletes head element (first one). Return deleted element

Here is the caller graph for this function:

◆ reverse()

size_t Aleph::HTList::reverse ( )

inlinenoexcept

It inverts all list elements. It returns list size

◆ reverse_list()

size_t Aleph::HTList::reverse_list ( )

inlinenoexcept

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ rotate_left()

void Aleph::HTList::rotate_left ( size_t n )

inline

Rotate to left the list n positions.

rotate_left(n) rotates the items to left n positions. For example, if the list is as follows:

l0, l1, l2, l3, l4, l5, l6, l7, l8, l9

Then rotate_left(4) produces the following state:

l4, l5, l6, l7, l8, l9, l0, l1, l2, l3

Parameters

[in] n the number of position to be rotated

Exceptions

domain_error if list is empty

Here is the call graph for this function:

◆ size()

size_t Aleph::HTList::size ( ) const

inlinenoexcept

Count the number of elements of the list.

This method counts, it does not retrieve, the number of elements stored in the list.

So it is complexity is $O(n)$ . This is some polemic because one could maintain an internal counter and retrieve it in constant time. It possible that this feauture is put in next versions. We do not maintain this counter because it is possible to add or remove items from a given node. So these operations would require access to the full list's context, what it often not the case.

Returns: the number of items of list

Here is the call graph for this function:

Here is the caller graph for this function:

◆ split()

size_t Aleph::HTList::split	(	HTList &	l,
		HTList &	r
	)

inlinenoexcept

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

◆ split_list()

size_t Aleph::HTList::split_list	(	HTList &	l,
		HTList &	r
	)

inlinenoexcept

It divides 'this' into two equal lists without modifying elements order

Split the list in two.

This method takes the first n/2 items of `this` and puts them, in
the same order, in list `l`. The remainder items are put in list
`r`. After operation `this` becomes empty. The order of items is
preserved through `l` and `r`.

\param[out] l list containg the first n/2 first items
\param[out] r list containg the last n/2 first items
\return the total of items that has `this`

Here is the call graph for this function:

◆ swap()

HTList& Aleph::HTList::swap ( HTList & l )

inlinenoexcept

Swap in constant time (very fast) 'this' elements with 'l' list elements
Referenced by append(), insert(), reverse() and split_list().

Exchange 'this' values with another list

Parameters

[in] l New list which elements will be exchanged

Here is the caller graph for this function:

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

htlist.H

Classes

Public Member Functions

Detailed Description

Member Function Documentation

◆ append() [1/2]

◆ append() [2/2]

◆ concat()

◆ concat_list()

◆ cut()

◆ cut_list()

◆ get_first()

◆ get_head()

◆ get_tail()

◆ insert() [1/3]

◆ insert() [2/3]

◆ insert() [3/3]

◆ is_empty()

◆ is_unitarian()

◆ is_unitarian_or_empty()

◆ push()

◆ put()

◆ remove()

◆ remove_all_and_delete()

◆ remove_head()

◆ remove_head_ne()

◆ reverse()

◆ reverse_list()

◆ rotate_left()

◆ size()

◆ split()

◆ split_list()

◆ swap()