Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Classes | Public Member Functions | Private Attributes | List of all members
Aleph::HTList Class Reference

Single linked list of nodes. More...

#include <htlist.H>

Inheritance diagram for Aleph::HTList:
[legend]
Collaboration diagram for Aleph::HTList:
[legend]

Classes

class  Iterator
 Iterator on HTList. More...
 

Public Member Functions

 HTList () noexcept
 Initialize an empty list.
 
void reset () noexcept
 
constexpr bool is_empty () const noexcept
 Return true if list is empty.
 
bool is_unitarian () const noexcept
 Return true if the list contains exactly just one element.
 
bool is_unitarian_or_empty () const noexcept
 Return true if list contains one element or is empty.
 
Slinknc * get_head () const noexcept
 Return list head (first element)
 
Slinknc * get_tail () const noexcept
 Return list tail (last element)
 
Slinknc * get_first () const noexcept
 Return list first element.
 
Slinknc * get_last () const noexcept
 Return the last item of the list (nullptr if the list is empty)
 
HTList & swap (HTList &l) noexcept
 Exchange 'this' values with another list.
 
void insert (Slinknc *link) noexcept
 Insert link as first element.
 
void append (Slinknc *link) noexcept
 Insert link as last element.
 
void append (HTList &l) noexcept
 Join 'this' with 'l' through list end.
 
void put (Slinknc *link) noexcept
 Insert link as last element.
 
void concat (HTList &l) noexcept
 Concat to 'this' all 'l' list; 'l' becomes empty.
 
void concat_list (HTList &l) noexcept
 
void insert (HTList &l) noexcept
 Insert starting in link (contained in 'this' list) the 'list' list.
 
void insert (Slinknc *link, HTList &list) noexcept
 Insert a list into this after one of its items.
 
Slinknc * remove_head_ne () noexcept
 It deletes head element (first one).
 
Slinknc * remove_head ()
 
Slinknc * remove_first_ne () noexcept
 
Slinknc * remove_first ()
 
bool remove (Slinknc *link)
 Remove from the list the item pointed by link
 
void push (Slinknc *link) noexcept
 Insert link as first element.
 
Slinknc * pop ()
 
Slinknc * top () const
 
size_t split_list (HTList &l, HTList &r) noexcept
 It divides 'this' into two equal lists without modifying elements order.
 
size_t split_list_ne (HTList &l, HTList &r) noexcept
 
size_t split (HTList &l, HTList &r) noexcept
 
size_t reverse () noexcept
 It inverts all list elements.
 
size_t reverse_list () noexcept
 
void cut (Slinknc *link, HTList &list) noexcept
 It cuts 'this' over 'link' element and it puts all remaining elements.
 
void cut_list (Slinknc *link, HTList &list) noexcept
 
void remove_all_and_delete () noexcept
 Remove and free memory for all the items of list.
 
size_t size () const noexcept
 Count the number of elements of the list.
 
void rotate_left (size_t n)
 Rotate to left the list n positions.
 

Private Attributes

Slinknc * head
 
Slinknc * tail
 

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 <tt>tail</tt> 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

Definition at line 506 of file htlist.H.

Constructor & Destructor Documentation

◆ HTList()

Aleph::HTList::HTList ( )
inlinenoexcept

Initialize an empty list.

Definition at line 514 of file htlist.H.

Member Function Documentation

◆ append() [1/2]

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

Join 'this' with 'l' through list end.

Parameters
[in]lList that will be inserted through list end

Definition at line 638 of file htlist.H.

References head, is_empty(), l, NEXT, swap(), and tail.

◆ append() [2/2]

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

Insert link as last element.

Parameters
[in]linkNew element that will be inserted

Definition at line 613 of file htlist.H.

References head, Aleph::maps(), NEXT, and tail.

Referenced by List_of_25_nodes::List_of_25_nodes(), Aleph::DynList< T >::__append(), Aleph::DynList< T >::append(), Aleph::DynList< T >::append(), concat(), concat_list(), Aleph::insert_sorted(), put(), Aleph::quicksort(), rotate_left(), HTListInsertBugFixTest::SetUp(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ concat()

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

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

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

Definition at line 660 of file htlist.H.

References append(), and l.

Referenced by Aleph::QuickHull::operator()(), Aleph::QuickHull::quick_hull(), TEST_F(), and TEST_F().

◆ concat_list()

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

Definition at line 663 of file htlist.H.

References append(), and l.

Referenced by Aleph::GenLinearHashTable< Key, BucketType, Cmp >::contract(), Aleph::quicksort(), TEST(), TEST(), and TEST().

◆ cut()

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

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

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

Parameters
[in]linkElement where 'list' will be cut.
[in]listList that will be cut in link

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

Definition at line 1025 of file htlist.H.

References Aleph::maps(), NEXT, and tail.

Referenced by cut_list(), and TEST_F().

◆ cut_list()

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

Definition at line 1037 of file htlist.H.

References cut().

Referenced by TEST(), and TEST_F().

◆ get_first()

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

Return list first element.

Definition at line 547 of file htlist.H.

References get_head().

Referenced by Aleph::DynList< T >::empty(), Aleph::DynList< T >::get_first_ne(), Aleph::insert_sorted(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), and top().

◆ get_head()

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

Return list head (first element)

Definition at line 539 of file htlist.H.

References head.

Referenced by get_first(), and TEST().

◆ get_last()

Slinknc * Aleph::HTList::get_last ( ) const
inlinenoexcept

Return the last item of the list (nullptr if the list is empty)

Definition at line 550 of file htlist.H.

References get_tail().

Referenced by Aleph::DynList< T >::empty(), Aleph::DynList< T >::get_last_ne(), Aleph::insert_sorted(), TEST(), TEST(), TEST(), TEST(), and TEST_F().

◆ get_tail()

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

Return list tail (last element)

Definition at line 543 of file htlist.H.

References tail.

Referenced by get_last(), and TEST().

◆ insert() [1/3]

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

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

'list' becomes empty

Insert list l starting from this. After insertion, l becomes empty.

Parameters
[in,out]lList that will be inserted starting from this. After the call, l is empty.

Definition at line 683 of file htlist.H.

References Aleph::DynList< T >::append(), l, and swap().

◆ insert() [2/3]

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

Insert link as first element.

Parameters
[in]linkNew element that will be inserted

Definition at line 588 of file htlist.H.

References head, Aleph::maps(), NEXT, and tail.

Referenced by Aleph::DynList< T >::__insert(), Aleph::DynList< T >::insert(), Aleph::DynList< T >::insert(), Aleph::insert_sorted(), push(), TEST(), and TEST().

◆ 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]linkto the item after one wants to insert list
[in]listto be inserted after item pointed by link

Definition at line 742 of file htlist.H.

References Aleph::maps(), NEXT, and tail.

◆ is_empty()

constexpr bool Aleph::HTList::is_empty ( ) const
inlineconstexprnoexcept

Return true if list is empty.

Definition at line 523 of file htlist.H.

References head.

Referenced by Aleph::Dlink::Dlink(), Aleph::DynSlist< T >::DynSlist(), append(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_path(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::build_reverse_mappings(), Aleph::compute_bipartite(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::compute_min_paths_tree(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_partial_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::compute_partial_min_paths_tree(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_partial_path(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::contract(), Aleph::Dlink::cut_list(), demo_binary_heap(), demo_event_simulation(), demo_fibonacci_heap(), demo_max_heap(), demo_queue(), Aleph::Path< GT >::empty(), Aleph::DynList< T >::empty(), Aleph::DynListQueue< T >::empty(), Graph_Traverse< GT, Itor, Q, Show_Arc >::exec(), Aleph::GenLinearHashTable< Key, BucketType, Cmp >::expand(), Aleph::Directed_Find_Path< GT, Itor, SA >::find(), Aleph::Find_Eulerian_Path< GT, SN, SA >::find_node_sequence(), Aleph::generic_preflow_vertex_push_maximum_flow(), Aleph::DynList< T >::get_first(), Aleph::get_futures(), Aleph::get_futures(), Aleph::DynList< T >::get_last(), Aleph::QuickHull::get_right_points(), Aleph::Find_Eulerian_Path< GT, SN, SA >::hierholzer_directed(), Aleph::Find_Eulerian_Path< GT, SN, SA >::hierholzer_undirected(), Aleph::in_place_transpose(), Aleph::insert_sorted(), Aleph::Test_Eulerian< GT, SN, SA >::is_connected(), Aleph::DynListQueue< T >::is_empty(), Aleph::Path< GT >::is_empty(), Aleph::FlowPath< Net >::is_empty(), Aleph::HTList::Iterator::is_in_first(), Aleph::is_inversely_sorted(), Aleph::HTList::Iterator::is_last(), Aleph::is_sorted(), Aleph::Test_Eulerian< GT, SN, SA >::is_strongly_connected(), QuadTree::join(), Aleph::list_insertion_sort(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::map_copy_path_to_original(), Aleph::max_flow_min_cost_by_cycle_canceling(), Aleph::Fibonacci_Heap< T, Compare >::merge(), Aleph::merge_lists(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::operator()(), Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::operator()(), Graph_Traverse< GT, Itor, Q, Show_Arc >::operator()(), Graph_Traverse< GT, Itor, Q, Show_Arc >::operator()(), Polinomio::operator*(), Polinomio::operator+=(), Aleph::Dlink::operator=(), Aleph::DynSlist< T >::operator=(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::paint_min_paths_tree(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_partial_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::paint_partial_min_paths_tree(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::paint_partial_path(), pop(), Aleph::print(), Aleph::QuickHull::quick_hull(), Aleph::quicksort(), Aleph::Q_Topological_Sort< GT, Itor, SA >::ranks(), remove(), remove_all_and_delete(), remove_head(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_node(), Aleph::HTList::Iterator::reset_last(), reverse(), rotate_left(), QueueTheadsPool< T >::run_event(), Aleph::Find_Aumenting_Path< Net, Q >::search(), Aleph::search_extreme(), Aleph::search_inversion(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle(), QuadTree::split(), Aleph::DynDlist< T >::split_list(), split_list(), Aleph::Dlink::split_list_ne(), Aleph::Dlink::swap(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), test_ks_find_with_iterations(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::test_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::test_negative_cycle(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::test_negative_cycle(), Aleph::test_sorted(), top(), Aleph::transpose(), TYPED_TEST(), and Aleph::vertex_connectivity().

◆ is_unitarian()

bool Aleph::HTList::is_unitarian ( ) const
inlinenoexcept

Return true if the list contains exactly just one element.

Definition at line 528 of file htlist.H.

References head, Aleph::maps(), and tail.

Referenced by split_list(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), and TEST_F().

◆ is_unitarian_or_empty()

bool Aleph::HTList::is_unitarian_or_empty ( ) const
inlinenoexcept

Return true if list contains one element or is empty.

Definition at line 535 of file htlist.H.

References head, and tail.

Referenced by Aleph::Path< GT >::check(), Aleph::quicksort(), TEST(), TEST(), TEST(), and TEST().

◆ pop()

Slinknc * Aleph::HTList::pop ( )
inline

Definition at line 886 of file htlist.H.

References ah_underflow_error_if, is_empty(), and remove_head().

Referenced by TEST(), TEST(), and TEST().

◆ push()

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

Insert link as first element.

Definition at line 862 of file htlist.H.

References insert().

Referenced by TEST(), and TEST().

◆ put()

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

Insert link as last element.

Definition at line 656 of file htlist.H.

References append().

Referenced by TEST().

◆ 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]linkpointer to the item to be removed.
Returns
true if link was found and removed: false otherwise
Exceptions
underflow_errorif the list is empty

Definition at line 832 of file htlist.H.

References ah_underflow_error_if, head, is_empty(), NEXT, Aleph::Slinknc::reset(), and tail.

Referenced by TEST().

◆ 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.

Definition at line 1065 of file htlist.H.

References is_empty(), Aleph::maps(), and remove_head_ne().

Referenced by List_of_25_nodes::~List_of_25_nodes(), HTListInsertBugFixTest::TearDown(), HTListSplitTest::TearDown(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ remove_first()

Slinknc * Aleph::HTList::remove_first ( )
inline

Definition at line 803 of file htlist.H.

References remove_head().

Referenced by Aleph::HTList::Iterator::del_ne(), rotate_left(), and TEST().

◆ remove_first_ne()

Slinknc * Aleph::HTList::remove_first_ne ( )
inlinenoexcept

Definition at line 801 of file htlist.H.

References remove_head_ne().

Referenced by Aleph::quicksort(), and reverse().

◆ 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.

Returns
a pointer to the removed item
Exceptions
underflow_errorif 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.

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

Returns
a pointer to the removed item.
Exceptions
underflow_errorif the list is empty

Definition at line 777 of file htlist.H.

References ah_underflow_error_if, is_empty(), and remove_head_ne().

Referenced by Aleph::in_place_transpose(), pop(), Aleph::DynList< T >::remove(), and remove_first().

◆ remove_head_ne()

Slinknc * Aleph::HTList::remove_head_ne ( )
inlinenoexcept

It deletes head element (first one).

Return deleted element

Definition at line 760 of file htlist.H.

References head, Aleph::maps(), NEXT, reset(), and tail.

Referenced by remove_all_and_delete(), remove_first_ne(), remove_head(), and Aleph::DynList< T >::remove_ne().

◆ reset()

void Aleph::HTList::reset ( )
inlinenoexcept

Definition at line 516 of file htlist.H.

References head, and tail.

Referenced by Aleph::DynSlist< T >::DynSlist(), Aleph::__remove_by_pos_xt(), Aleph::HTList::Iterator::del_ne(), Aleph::DynList< T >::empty(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::extract_max_rb(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::extract_min_rb(), Aleph::GenBinHeap< NodeType, Key, Compare >::getMin_ne(), Aleph::Gen_Treap< NodeType, Key, Compare >::join(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join(), Aleph::BinTree_Operation< Node, Cmp >::join(), Aleph::join(), Aleph::Gen_Treap< NodeType, Key, Compare >::join_dup(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_dup(), Aleph::join_preorder(), Aleph::DynSlist< T >::operator=(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_join(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::random_remove(), GenTdSplayTreeRk< NodeType, Key, Compare >::remove(), GenTdSplayTree< NodeType, Key, Compare >::remove(), Aleph::Gen_Treap< NodeType, Key, Compare >::remove(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove(), Aleph::BinTree_Operation< Node, Cmp >::remove(), Aleph::Gen_Treap< NodeType, Key, Compare >::remove(), Aleph::remove_by_key_xt(), Aleph::remove_from_bst(), remove_head_ne(), Aleph::GenBinHeap< NodeType, Key, Compare >::remove_last(), Aleph::Slink::remove_next(), Aleph::Slink_Nc::remove_next(), Aleph::Slinknc::remove_next(), Aleph::HtdRbTreeRk< Key, Compare >::split_pos(), Aleph::ssp_shortest_path(), and TEST().

◆ reverse()

Aleph::HTList::reverse ( )
inlinenoexcept

It inverts all list elements.

It returns list size

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

Definition at line 985 of file htlist.H.

References Aleph::count(), Aleph::DynList< T >::insert(), is_empty(), Aleph::maps(), remove_first_ne(), and swap().

Referenced by reverse_list(), TEST(), TEST(), TEST(), and TEST_F().

◆ reverse_list()

size_t Aleph::HTList::reverse_list ( )
inlinenoexcept

Definition at line 1002 of file htlist.H.

References reverse().

Referenced by Aleph::DynList< T >::reverse(), TEST(), and TEST().

◆ 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]nthe number of position to be rotated
Exceptions
domain_errorif list is empty

Definition at line 1359 of file htlist.H.

References ah_domain_error, append(), is_empty(), and remove_first().

Referenced by TEST(), TEST(), TEST(), TEST(), and TEST_F().

◆ 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

Definition at line 1319 of file htlist.H.

References Aleph::count(), and Aleph::HTList::Iterator::has_curr().

Referenced by Aleph::Matrix< Trow, Tcol, NumType >::Matrix(), Aleph::Matrix< Trow, Tcol, NumType >::Matrix(), Aleph::Vector< T, NumType >::Vector(), Aleph::HashMap< Key, Data, HashMapTable, Cmp >::add(), adjust_nodes(), Aleph::align_text_to_left(), Aleph::Huffman_Encoder_Engine::append_code(), apply(), benchmark_comparison(), Aleph::binary_search_dup(), Aleph::bsearch_dup(), Aleph::check_baseball_elimination(), Aleph::stl_comb_detail::combinations_impl(), Aleph::complete_rows(), Aleph::Unconnected_Components< GT, SA >::compute_lists(), Aleph::compute_stats(), Aleph::Random_Graph< GT, Init_Node, Init_Arc >::connect(), Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::connect(), Random_Network_Flow< Net >::connect_ranks(), Aleph::MCF_Arc< Arc_Info, FT >::cost(), Aleph::Unconnected_Components< GT, SA >::count_components(), count_total_nodes(), RingFileCache< T >::create(), Random_Network_Flow< Net >::create_forward_arcs_in_rank(), Aleph::csv_filter_by_value(), Aleph::csv_find_by_value(), Aleph::csv_inner_join(), Aleph::csv_is_rectangular(), Aleph::csv_join_horizontal(), Aleph::csv_join_vertical(), Aleph::csv_num_columns(), Aleph::csv_read_all(), Aleph::csv_read_row(), Aleph::csv_select_columns(), Aleph::csv_sort_by_column(), Aleph::csv_sort_by_column_numeric(), Aleph::csv_transpose(), Aleph::csv_unique(), Aleph::csv_write_row(), Aleph::Huffman_Decoder_Engine::decode(), Aleph::decompose_flow(), demo_baseball_elimination(), demo_basic_operations(), demo_build(), demo_calculator(), demo_city_coordinates(), demo_collision_detection(), demo_command_autocomplete(), demo_connected(), demo_connected_components(), demo_convex_hull_cities(), demo_convex_hull_performance(), demo_coverage_area(), demo_cycle_detection(), demo_department_codes(), demo_dynlist(), demo_encoding_decoding(), demo_erdos_renyi(), demo_fibonacci_heap(), demo_find_sccs(), demo_functional(), demo_geographic_points(), demo_geometric_primitives(), demo_hash_dispatcher(), demo_hierholzer(), demo_integration(), demo_kruskal_simulation(), demo_length_checking(), demo_modifiable_mapping(), demo_move_semantics(), demo_network_analysis(), demo_network_connectivity(), demo_parameters(), demo_performance(), demo_practical(), demo_prefix_search(), demo_regions_menu(), demo_row_col_operations(), demo_set_operations(), demo_sieve_of_eratosthenes(), demo_spell_checker(), demo_splitting(), demo_strongly_connected(), demo_survey_design(), demo_text_processor(), demo_traversal(), demo_tree_backends(), demo_triangulation_basic(), demo_triangulation_complex(), demo_tuple_conversions(), demo_variadic_constructor(), demo_variadic_dispatcher(), demo_vector_dynarray(), demo_word_frequency(), demonstrate_basic_operations(), demonstrate_ranked_operations(), Aleph::design_survey(), Point::distance_with(), Aleph::Huffman_Encoder_Engine::encode(), Aleph::Huffman_Encoder_Engine::encode(), Aleph::ThreadPool::enqueue_bulk(), eval(), example_basic_parallel(), example_basic_sccs(), example_batch_processing(), example_dag(), example_lightweight_version(), example_parallel_filter(), example_parallel_map(), example_strongly_connected(), fill(), Aleph::MCF_Arc< Arc_Info, FT >::flow(), Aleph::generate_graphpic(), Aleph::generate_graphviz(), Aleph::generate_layered_network(), generate_split_lines(), Aleph::MCF_Graph< NodeT, ArcT >::get_commodity(), Aleph::QuickHull::get_fartest_point(), Aleph::matgraph_detail::get_node(), Aleph::matgraph_detail::get_node(), OhashCommon< HashTbl, Key >::Iterator::has_curr(), Aleph::in_place_multisort_arrays(), Aleph::in_place_transpose(), OhashCommon< HashTbl, Key >::Iterator::is_last(), is_min_heap(), Aleph::justify_text(), Aleph::FlowPath< Net >::length(), Aleph::load_digraph(), main(), main(), Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::make_eulerian(), HashDistributionTest::measureHashUniqueness(), Aleph::merge(), Aleph::min_cut(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::num_connected_components(), Aleph::FlowDecomposition< Net >::num_cycles(), Aleph::GraphCopyWithMapping< GT, Tree >::num_nodes(), Aleph::FlowDecomposition< Net >::num_paths(), Aleph::ThreadPool::num_threads(), Aleph::percentile(), Aleph::Topological_Sort< GT, Itor, SA >::perform(), print_bits(), print_dynlist(), print_matching(), print_nested(), Aleph::remove_spaces(), Aleph::remove_symbols(), Aleph::ThreadPool::resize(), run_full_benchmark(), run_legacy_example(), run_performance_comparison(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::scc_by_blocks(), scenario_construction(), scenario_construction(), scenario_parlay_betting(), scenario_probability(), scenario_sales_analytics(), scenario_sensor_monitoring(), scenario_sports_leaderboard(), scenario_xor_checksum(), Aleph::MCF_Arc< Arc_Info, FT >::set_cost(), Aleph::MCF_Arc< Arc_Info, FT >::set_flow(), Aleph::Path< GT >::size(), Fixed_Relation::size(), Aleph::skip_block_comment(), Aleph::solve_assignment(), Aleph::solve_circulation(), Aleph::solve_project_selection(), Aleph::solve_transportation(), Aleph::split_n(), Aleph::HtdRbTreeRk< Key, Compare >::split_pos(), Aleph::stl_concat(), Aleph::stl_group_by(), Aleph::stl_traverse_arrangements(), Aleph::stl_traverse_combinations(), Aleph::stl_unzip(), Aleph::stl_unzip_tuple(), Aleph::stl_zip_to_pairs(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), test_all_constructors_agree(), test_construct_all_identical(), test_construct_from_array(), test_construct_from_dynlist(), test_copy_constructor(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), test_move_constructor(), test_non_idempotent_correctness(), test_string_concatenation(), test_sw_empty_graph(), test_values_reconstruct(), test_values_reconstruction(), Aleph::Matrix< Trow, Tcol, NumType >::to_str(), Aleph::Topological_Sort< GT, Itor, SA >::topological_sort(), Aleph::MCF_Graph< NodeT, ArcT >::total_cost(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST(), TYPED_TEST_P(), verify_heap_property(), and visual_demonstration().

◆ split()

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

Definition at line 977 of file htlist.H.

References l, and split_list().

Referenced by TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ split_list()

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`

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

Definition at line 930 of file htlist.H.

References Aleph::count(), head, is_empty(), is_unitarian(), l, Aleph::maps(), NEXT, swap(), and tail.

Referenced by Aleph::mergeinsertsort(), Aleph::mergesort(), split(), split_list_ne(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ split_list_ne()

size_t Aleph::HTList::split_list_ne ( HTList &  l,
HTList &  r 
)
inlinenoexcept

Definition at line 971 of file htlist.H.

References l, and split_list().

Referenced by Aleph::mergesort(), and TEST().

◆ swap()

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

Exchange 'this' values with another list.

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

Parameters
[in]lNew list which elements will be exchanged

Definition at line 571 of file htlist.H.

References head, l, and tail.

Referenced by append(), insert(), reverse(), split_list(), and Aleph::DynList< T >::swap().

◆ top()

Slinknc * Aleph::HTList::top ( ) const
inline

Definition at line 893 of file htlist.H.

References ah_underflow_error_if, get_first(), and is_empty().

Referenced by TEST(), TEST(), and TEST().

Member Data Documentation

◆ head

Slinknc* Aleph::HTList::head
private

Definition at line 508 of file htlist.H.

Referenced by append(), append(), RingFileCache< T >::create(), Aleph::HTList::Iterator::del_ne(), get_head(), insert(), is_empty(), Aleph::HTList::Iterator::is_in_first(), is_unitarian(), is_unitarian_or_empty(), Aleph::HTList::Iterator::next_ne(), remove(), remove_head_ne(), reset(), Aleph::HTList::Iterator::reset(), split_list(), and swap().

◆ tail

Slinknc* Aleph::HTList::tail
private

Definition at line 509 of file htlist.H.

Referenced by append(), append(), RingFileCache< T >::create(), cut(), Aleph::HTList::Iterator::del_ne(), get_tail(), insert(), insert(), Aleph::HTList::Iterator::is_last(), is_unitarian(), is_unitarian_or_empty(), Aleph::HTList::Iterator::next_ne(), remove(), remove_head_ne(), reset(), split_list(), and swap().

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