- Generated by
1.9.8
|
Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
|
Single linked list of nodes. More...
#include <htlist.H>
Classes | |
| class | Iterator |
Public Member Functions | |
| HTList () noexcept | |
| void | reset () noexcept |
| constexpr bool | is_empty () const noexcept |
| bool | is_unitarian () const noexcept |
| Return true if the list contains exactly just one. | |
| bool | is_unitarian_or_empty () const noexcept |
| Return true if list contains one element or is empty. | |
| 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 |
| 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 |
| 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. | |
| 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). Return deleted. | |
| Slinknc * | remove_head () |
| Slinknc * | remove_first_ne () noexcept |
| Slinknc * | remove_first () |
| bool | remove (Slinknc *link) |
| void | push (Slinknc *link) noexcept |
| Slinknc * | pop () |
| Slinknc * | top () const |
| size_t | split_list (HTList &l, HTList &r) noexcept |
| It divides 'this' into two equal lists without modifying. | |
| 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. It returns list size. | |
| size_t | reverse_list () noexcept |
| void | cut (Slinknc *link, HTList &list) noexcept |
| It cuts 'this' over 'link' element and it puts all. | |
| void | cut_list (Slinknc *link, HTList &list) noexcept |
| void | remove_all_and_delete () noexcept |
| 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 |
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.
| [in] | link | New element that will be inserted |
Definition at line 495 of file htlist.H.
References Aleph::and, Aleph::divide_and_conquer_partition_dp(), head, 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(), main(), put(), Aleph::quicksort(), rotate_left(), HTListInsertBugFixTest::SetUp(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), and TEST_F().
|
inlinenoexcept |
It cuts 'this' over 'link' element and it puts all.
list
\brief It makes reference to is_empty(). <br>
Referenced by cut_list().
| [in] | link | Element where 'list' will be cut. |
| [in] | list | List 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 820 of file htlist.H.
References Aleph::divide_and_conquer_partition_dp(), NEXT, and tail.
Referenced by cut_list(), main(), and TEST_F().
|
inlinenoexcept |
Definition at line 443 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(), and top().
|
inlinenoexcept |
|
inlinenoexcept |
Return the last item of the list (nullptr if the list is empty)
Definition at line 446 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(), and TEST().
|
inlinenoexcept |
Insert starting in link (contained in 'this' list) the.
Insert list `l` starting from `this`. After insertion, `l` becomes empty.
| [in,out] | l | List that will be inserted starting from this. After the call, l is empty. |
Definition at line 555 of file htlist.H.
References Aleph::DynList< T >::append(), l, and swap().
| [in] | link | New element that will be inserted |
Definition at line 473 of file htlist.H.
References Aleph::divide_and_conquer_partition_dp(), head, NEXT, and tail.
Referenced by Aleph::DynList< T >::__insert(), Aleph::DynList< T >::insert(), Aleph::DynList< T >::insert(), Aleph::insert_sorted(), main(), push(), reverse(), TEST(), and TEST().
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
| [in] | link | to the item after one wants to insert list |
| [in] | list | to be inserted after item pointed by link |
Definition at line 588 of file htlist.H.
References Aleph::divide_and_conquer_partition_dp(), NEXT, and tail.
Definition at line 419 of file htlist.H.
References head.
Referenced by Aleph::Dlink::Dlink(), append(), Aleph::DynList< T >::empty(), Aleph::DynListQueue< T >::empty(), Aleph::Find_Eulerian_Path< GT, SN, SA >::find_node_sequence(), Aleph::ShortestPathInPolygon::find_sleeve(), Aleph::DynList< T >::get_first(), Aleph::DynList< T >::get_last(), 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::AdversarialTraceCollector< Move, Score >::is_empty(), Aleph::DynListQueue< T >::is_empty(), Aleph::FlowPath< Net >::is_empty(), Aleph::HTList::Iterator::is_in_first(), Aleph::HTList::Iterator::is_last(), Aleph::Test_Eulerian< GT, SN, SA >::is_strongly_connected(), QuadTree::join(), main(), Aleph::merge_lists(), Aleph::Dlink::operator=(), pop(), Aleph::quicksort(), Aleph::sort_utils_detail::radix_sort_impl(), remove(), remove_all_and_delete(), remove_head(), Aleph::HTList::Iterator::reset_last(), reverse(), rotate_left(), Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::run_dial(), Aleph::search_extreme(), Aleph::search_extreme(), QuadTree::split(), Aleph::DynDlist< T >::split_list(), split_list(), Aleph::Dlink::split_list_ne(), Aleph::detail::spp_find_sleeve(), Aleph::k_shortest_paths_detail::state_to_path(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), 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_ks_find_with_iterations(), top(), and Aleph::transpose().
|
inlinenoexcept |
|
inlinenoexcept |
Return true if list contains one element or is empty.
Definition at line 431 of file htlist.H.
Referenced by Aleph::Path< GT >::check(), Aleph::quicksort(), TEST(), TEST(), TEST(), and TEST().
|
inline |
Definition at line 700 of file htlist.H.
References ah_underflow_error_if, is_empty(), and remove_head().
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.
| [in] | link | pointer to the item to be removed. |
true if link was found and removed: false otherwise | underflow_error | if the list is empty |
Definition at line 657 of file htlist.H.
References ah_underflow_error_if, head, is_empty(), NEXT, Aleph::Slinknc::reset(), and tail.
Referenced by TEST().
|
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.
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 847 of file htlist.H.
References Aleph::divide_and_conquer_partition_dp(), is_empty(), and remove_head_ne().
Referenced by List_of_25_nodes::~List_of_25_nodes(), main(), HTListInsertBugFixTest::TearDown(), HTListSplitTest::TearDown(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), and TEST_F().
|
inline |
Definition at line 641 of file htlist.H.
References remove_head().
Referenced by Aleph::HTList::Iterator::del_ne(), main(), rotate_left(), and TEST().
|
inlinenoexcept |
Definition at line 639 of file htlist.H.
References remove_head_ne().
Referenced by Aleph::quicksort(), and reverse().
|
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.
| 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.
| underflow_error | if the list is empty |
Definition at line 623 of file htlist.H.
References ah_underflow_error_if, is_empty(), and remove_head_ne().
Referenced by pop(), Aleph::DynList< T >::remove(), and remove_first().
|
inlinenoexcept |
It deletes head element (first one). Return deleted.
Definition at line 606 of file htlist.H.
References Aleph::divide_and_conquer_partition_dp(), head, NEXT, Aleph::Slinknc::reset(), and tail.
Referenced by remove_all_and_delete(), remove_first_ne(), remove_head(), and Aleph::DynList< T >::remove_ne().
|
inlinenoexcept |
Definition at line 412 of file htlist.H.
Referenced by Aleph::DynList< T >::empty().
|
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 786 of file htlist.H.
References Aleph::count(), Aleph::divide_and_conquer_partition_dp(), insert(), is_empty(), remove_first_ne(), and swap().
Referenced by main(), reverse_list(), TEST(), TEST(), and TEST().
|
inlinenoexcept |
|
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
| [in] | n | the number of position to be rotated |
| domain_error | if list is empty |
Definition at line 1090 of file htlist.H.
References ah_domain_error, append(), is_empty(), and remove_first().
|
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.
Definition at line 1065 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::binary_search_dup(), Aleph::bsearch_dup(), Aleph::chromatic_number(), Aleph::complete_rows(), Aleph::Unconnected_Components< GT, SA >::compute_lists(), Aleph::Random_Graph< GT, Init_Node, Init_Arc >::connect(), Aleph::sort_utils_detail::counting_sort_impl(), Aleph::decompose_flow(), demo_coverage_area(), demo_dynlist(), demo_find_sccs(), demo_practical(), demo_triangulation_basic(), demo_triangulation_complex(), Aleph::Gen_MultiPolynomial< Coefficient, MonomOrder >::factor_recombination(), Aleph::generate_layered_network(), imprime(), Aleph::in_place_transpose(), Aleph::FlowPath< Net >::length(), Aleph::k_shortest_paths_detail::make_path_snapshot(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::num_connected_components(), print_dynlist(), Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::query(), Aleph::Gen_Cartesian_Tree_RMQ< T, Comp >::query_idx(), Aleph::sort_utils_detail::radix_sort_impl(), Aleph::k_shortest_paths_detail::same_path_sequence(), scenario_construction(), Aleph::AdversarialTraceCollector< Move, Score >::size(), Aleph::split_n(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), test_construct_all_identical(), test_copy_constructor(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), test_non_idempotent_correctness(), test_string_concatenation(), test_sw_empty_graph(), Aleph::MonotonePolygonTriangulation::triangulate_monotone(), TYPED_TEST_P(), and Aleph::Tikz_Scene::visualize_convex_hull().
It divides 'this' into two equal lists without modifying.
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.
| [out] | l | list containg the first n/2 first items |
| [out] | r | list containg the last n/2 first items |
thisThis is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
Definition at line 731 of file htlist.H.
References Aleph::and, Aleph::count(), Aleph::divide_and_conquer_partition_dp(), head, is_empty(), is_unitarian(), l, NEXT, r, swap(), and tail.
Referenced by main(), Aleph::mergeinsertsort(), Aleph::mergesort(), split(), split_list_ne(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().
Definition at line 772 of file htlist.H.
References l, r, and split_list().
Referenced by Aleph::mergesort(), and TEST().
\brief Swap in constant time (very fast) 'this' elements with 'l'
list elements
Referenced by append(), insert(), reverse() and split_list().
| [in] | l | New list which elements will be exchanged |
Definition at line 459 of file htlist.H.
Referenced by append(), insert(), reverse(), split_list(), Aleph::DynList< T >::swap(), and TEST_F().
|
inline |
Definition at line 707 of file htlist.H.
References ah_underflow_error_if, get_first(), and is_empty().
|
private |
Definition at line 404 of file htlist.H.
Referenced by append(), append(), 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().
|
private |
Definition at line 405 of file htlist.H.
Referenced by append(), append(), 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().
1.9.8