123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175 |
- #include "sorted_list.h"
- #include <stdexcept>
- #include <iostream>
-
- /* Lab 3 - TDDE18 - Sorted list lab - Source file */
-
-
- ////////////////////////////////
- /// Special member functions ///
- ////////////////////////////////
-
- /// Default constructor
- Sorted_List::Sorted_List(): first{nullptr}
- {
- }
-
- /// Copy constructor
- Sorted_List::Sorted_List(Sorted_List const& other) {
- Node* current = other.first;
-
- while (current) {
- insert(current->value);
- current = current->next;
- }
- }
-
- /// "Nice" constructor
- Sorted_List::Sorted_List(std::initializer_list<int> list) {
- for (int i : list) {
- insert(i);
- }
- }
-
- /// Move constructor
- Sorted_List::Sorted_List(Sorted_List&& other) : first{other.first} {
- other.first = nullptr;
- }
-
- /// Move assignment
- Sorted_List& Sorted_List::operator=(Sorted_List&& other) {
- Sorted_List tmp{};
- std::swap(tmp.first, first);
- std::swap(first, other.first);
- return *this;
- }
-
- /// Destructor
- Sorted_List::~Sorted_List() {
- Node* tmp{first};
-
- // We browse the list and delete nodes one by one
- while (tmp){
- Node* next{tmp->next};
- delete tmp;
- tmp = next;
- }
- }
-
- /// Copy assignment operator
- Sorted_List& Sorted_List::operator=(Sorted_List const& other){
- Sorted_List tmp(other);
- std::swap(tmp.first, this->first);
- return *this;
- }
-
-
- ///////////////
- /// Methods ///
- ///////////////
-
- /* Public insert function calling the private one
- We have created two list to be able to have a
- recursive insert function. */
- void Sorted_List::insert(int val) {
- insert(first, val);
- }
-
- /* Private insert function, taking a reference to a
- pointer and the value to insert. */
- void Sorted_List::insert(Node*& first, int val) {
- // If the list is empty
- if (!first){
- first = new Node{val, nullptr};
- }
- // Else if the next node is greater than the value
- // i.e. we have to insert between two nodes
- else if (first->value > val) {
- first = new Node{val, first};
- }
- // Else if we are at the end of the list
- else if (!first->next) {
- first->next = new Node{val, nullptr};
- }
- // Else we must insert later in the list
- else {
- insert(first->next, val);
- }
- }
-
- /// Iterative remove function
- void Sorted_List::remove(int val) {
- /* Keeping in memory the current
- node and its predecessor. */
- Node* current = first;
- Node* previous = first;
-
- // We browse the list
- while (current) {
- // If the node has the sought value
- if (current->value == val) {
- // If it is the first one we must do otherwise to avoid memory leaks
- if (current == first){
- Node* tmp{first};
- first = current->next;
- delete tmp;
- return;
- }
- else {
- previous->next = current->next;
- delete current;
- return;
- }
- }
- /* If we find a value greater than the sought value, that's
- means that the value isn't in the list. We stop here. */
- else if (current->value > val)
- {
- break;
- }
- previous = current;
- current = current->next;
- }
- // If we exit the loop with no value found, we raise a error.
- throw std::logic_error{"Remove(): The searched item is not in the list."};
- }
-
- bool Sorted_List::is_empty() const {
- return first == nullptr;
- }
-
- int Sorted_List::size() const {
- int count{0};
- Node* current = first;
-
- while (current){
- count++;
- current = current->next;
- }
- return count;
- }
-
- int Sorted_List::at(int pos) const {
- if (is_empty()) {
- throw std::logic_error{"At(): The given list is empty."};
- }
- Node* tmp{first};
- while (pos > 0){
- if (! tmp->next) {
- throw std::logic_error{"At(): The given index value is too large."};
- }
- --pos;
- tmp = tmp->next;
- }
- return tmp->value;
- }
-
- std::string Sorted_List::to_string() const {
- std::string str{"[ "};
- Node* tmp{first};
- while (tmp){
- str += std::to_string(tmp->value) + " ";
- tmp = tmp->next;
- }
- return str + "]";
- }
|