Sharing of my labs carried out during the TDDE18 course at Linköping University
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

sorted_list.cc 4.1KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175
  1. #include "sorted_list.h"
  2. #include <stdexcept>
  3. #include <iostream>
  4. /* Lab 3 - TDDE18 - Sorted list lab - Source file */
  5. ////////////////////////////////
  6. /// Special member functions ///
  7. ////////////////////////////////
  8. /// Default constructor
  9. Sorted_List::Sorted_List(): first{nullptr}
  10. {
  11. }
  12. /// Copy constructor
  13. Sorted_List::Sorted_List(Sorted_List const& other) {
  14. Node* current = other.first;
  15. while (current) {
  16. insert(current->value);
  17. current = current->next;
  18. }
  19. }
  20. /// "Nice" constructor
  21. Sorted_List::Sorted_List(std::initializer_list<int> list) {
  22. for (int i : list) {
  23. insert(i);
  24. }
  25. }
  26. /// Move constructor
  27. Sorted_List::Sorted_List(Sorted_List&& other) : first{other.first} {
  28. other.first = nullptr;
  29. }
  30. /// Move assignment
  31. Sorted_List& Sorted_List::operator=(Sorted_List&& other) {
  32. Sorted_List tmp{};
  33. std::swap(tmp.first, first);
  34. std::swap(first, other.first);
  35. return *this;
  36. }
  37. /// Destructor
  38. Sorted_List::~Sorted_List() {
  39. Node* tmp{first};
  40. // We browse the list and delete nodes one by one
  41. while (tmp){
  42. Node* next{tmp->next};
  43. delete tmp;
  44. tmp = next;
  45. }
  46. }
  47. /// Copy assignment operator
  48. Sorted_List& Sorted_List::operator=(Sorted_List const& other){
  49. Sorted_List tmp(other);
  50. std::swap(tmp.first, this->first);
  51. return *this;
  52. }
  53. ///////////////
  54. /// Methods ///
  55. ///////////////
  56. /* Public insert function calling the private one
  57. We have created two list to be able to have a
  58. recursive insert function. */
  59. void Sorted_List::insert(int val) {
  60. insert(first, val);
  61. }
  62. /* Private insert function, taking a reference to a
  63. pointer and the value to insert. */
  64. void Sorted_List::insert(Node*& first, int val) {
  65. // If the list is empty
  66. if (!first){
  67. first = new Node{val, nullptr};
  68. }
  69. // Else if the next node is greater than the value
  70. // i.e. we have to insert between two nodes
  71. else if (first->value > val) {
  72. first = new Node{val, first};
  73. }
  74. // Else if we are at the end of the list
  75. else if (!first->next) {
  76. first->next = new Node{val, nullptr};
  77. }
  78. // Else we must insert later in the list
  79. else {
  80. insert(first->next, val);
  81. }
  82. }
  83. /// Iterative remove function
  84. void Sorted_List::remove(int val) {
  85. /* Keeping in memory the current
  86. node and its predecessor. */
  87. Node* current = first;
  88. Node* previous = first;
  89. // We browse the list
  90. while (current) {
  91. // If the node has the sought value
  92. if (current->value == val) {
  93. // If it is the first one we must do otherwise to avoid memory leaks
  94. if (current == first){
  95. Node* tmp{first};
  96. first = current->next;
  97. delete tmp;
  98. return;
  99. }
  100. else {
  101. previous->next = current->next;
  102. delete current;
  103. return;
  104. }
  105. }
  106. /* If we find a value greater than the sought value, that's
  107. means that the value isn't in the list. We stop here. */
  108. else if (current->value > val)
  109. {
  110. break;
  111. }
  112. previous = current;
  113. current = current->next;
  114. }
  115. // If we exit the loop with no value found, we raise a error.
  116. throw std::logic_error{"Remove(): The searched item is not in the list."};
  117. }
  118. bool Sorted_List::is_empty() const {
  119. return first == nullptr;
  120. }
  121. int Sorted_List::size() const {
  122. int count{0};
  123. Node* current = first;
  124. while (current){
  125. count++;
  126. current = current->next;
  127. }
  128. return count;
  129. }
  130. int Sorted_List::at(int pos) const {
  131. if (is_empty()) {
  132. throw std::logic_error{"At(): The given list is empty."};
  133. }
  134. Node* tmp{first};
  135. while (pos > 0){
  136. if (! tmp->next) {
  137. throw std::logic_error{"At(): The given index value is too large."};
  138. }
  139. --pos;
  140. tmp = tmp->next;
  141. }
  142. return tmp->value;
  143. }
  144. std::string Sorted_List::to_string() const {
  145. std::string str{"[ "};
  146. Node* tmp{first};
  147. while (tmp){
  148. str += std::to_string(tmp->value) + " ";
  149. tmp = tmp->next;
  150. }
  151. return str + "]";
  152. }