linked_list.hpp

Go to the documentation of this file.

#pragma once
#include "helpers/equator.hpp"
#include "../object_model/read_only_collection.hpp"
#include "icollection.hpp"
#include "linked_list_node.hpp"
#include "../../string.hpp"
#include "../../usize.hpp"
#include <list>

namespace xtd {
  namespace collections {
    namespace generic {
      template<typename type_t, typename allocator_t>
      class linked_list : public xtd::object, public xtd::collections::generic::icollection<type_t> {
      public:
        
        using value_type = typename icollection<type_t>::value_type;
        using base_type = std::list<value_type, allocator_t>;
        using size_type = xtd::usize;
        using reference = value_type&;
        using const_reference = const value_type&;
        
        
        linked_list() = default;
        linked_list(linked_list&& list) = default;
        linked_list(const linked_list & list) {*data_ = *list.data_;}
        linked_list(base_type&& list) {data_->items = std::move(list);}
        linked_list(const base_type& list) {data_->items = list;}
        linked_list(const xtd::collections::generic::ienumerable < type_t >& collection) {
          for (const auto& item : collection)
            add(item);
        }

        template<xtd::iterable iterable_t>
        linked_list(iterable_t&& items) {
          for (const auto& item : items)
            add(item);
        }

        linked_list(std::initializer_list < type_t > items) {
          for (const auto& item : items)
            add(item);
        }

        template < std::input_iterator input_iterator_t >
        linked_list(input_iterator_t first, input_iterator_t last) {
          for (auto iterator = first; iterator != last; ++iterator)
            add(*iterator);
        }

        
        
        [[nodiscard]] auto count() const noexcept -> size_type override {return data_->items.size();}
        
        [[nodiscard]] auto first() const noexcept -> xtd::optional<linked_list_node<type_t>> {return count() ? xtd::optional<linked_list_node<type_t>> {linked_list_node<type_t> {const_cast<linked_list&>(self_), data_->items.begin(), data_->version}} : xtd::nullopt;}
        [[nodiscard]] auto first() noexcept -> xtd::optional<linked_list_node<type_t>> {return count() ? xtd::optional<linked_list_node<type_t>> {linked_list_node<type_t> {self_, data_->items.begin(), data_->version}} : xtd::nullopt;}
        
        [[nodiscard]] auto items() const noexcept -> const base_type& {return data_->items;}
        [[nodiscard]] auto items() noexcept -> base_type& {return data_->items;}
        
        [[nodiscard]] auto last() const noexcept -> xtd::optional<linked_list_node<type_t>> {return count() ? xtd::optional<linked_list_node<type_t>> {linked_list_node<type_t> {const_cast<linked_list&>(self_), --data_->items.end(), data_->version}} : xtd::nullopt;}
        [[nodiscard]] auto last() noexcept -> xtd::optional<linked_list_node<type_t>> {return count() ? xtd::optional<linked_list_node<type_t>> {linked_list_node<type_t> {self_, --data_->items.end(), data_->version}} : xtd::nullopt;}
        
        
        auto add_after(const linked_list_node<type_t>& node, const type_t& value) -> linked_list_node<type_t> {
          auto new_node = linked_list_node {value};
          add_after(node, new_node);
          return new_node;
        }

        auto add_after(const linked_list_node<type_t>& node, linked_list_node<type_t>& new_node) -> void {
          if (node.data_->list != this) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation);
          if (new_node.data_->list || !new_node.data_->value.has_value()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation, "The linked_list node belongs to a linked_list.");
          if (node.data_->version != data_->version) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation, "Collection was modified; enumeration operation may not execute.");
          auto iterator = node.data_->iterator;
          if (iterator != data_->items.end()) ++iterator;
          auto result = data_->items.insert(iterator, std::move(*new_node.data_->value));
          ++data_->version;
          new_node = {self_, result, data_->version};
        }
        
        auto add_before(const linked_list_node<type_t>& node, const type_t& value) -> linked_list_node<type_t> {
          auto new_node = linked_list_node {value};
          add_before(node, new_node);
          return new_node;
        }

        auto add_before(const linked_list_node<type_t>& node, linked_list_node<type_t>& new_node) -> void {
          if (node.data_->list != this) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation);
          if (new_node.data_->list || !new_node.data_->value.has_value()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation, "The linked_list node belongs to a linked_list.");
          if (node.data_->version != data_->version) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation, "Collection was modified; enumeration operation may not execute.");
          auto iterator = node.data_->iterator;
          auto result = data_->items.insert(iterator, std::move(*new_node.data_->value));
          ++data_->version;
          new_node = {self_, result, data_->version};
        }
        
        auto add_first(const type_t& value) -> linked_list_node<type_t> {
          auto new_node = linked_list_node {value};
          add_first(new_node);
          return new_node;
        }

        auto add_first(linked_list_node<type_t>& node) -> void {
          if (node.data_->list || !node.data_->value.has_value()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation, "The linked_list node belongs to a linked_list.");
          data_->items.push_front(node.data_->value.value());
          ++data_->version;
          node = {self_, data_->items.begin(), data_->version};
        }
        
        auto add_last(const type_t& value) -> linked_list_node<type_t> {
          auto new_node = linked_list_node {value};
          add_last(new_node);
          return new_node;
        }

        auto add_last(linked_list_node<type_t>& node) -> void {
          if (node.data_->list || !node.data_->value.has_value()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation, "The linked_list node belongs to a linked_list.");
          data_->items.push_back(node.data_->value.value());
          ++data_->version;
          auto tmp = data_->items.end();
          node = {self_, --tmp, data_->version};
        }
        
        auto clear() -> void override {
          data_->items.clear();
          ++data_->version;
        }
        
        [[nodiscard]] auto contains(const type_t& value) const noexcept -> bool override {
          for (const auto& item : data_->items)
            if (xtd::collections::generic::helpers::equator<type_t> {}(item, value)) return true;
          return false;
        }
        
        auto copy_to(xtd::array < type_t >& array, size_type array_index) const -> void override {
          if (array_index + count() > array.length()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::argument_out_of_range);
          for (const auto& item : data_->items)
            array[array_index++] = item;
        }
        
        [[nodiscard]] auto find(const type_t value) const noexcept -> xtd::optional<linked_list_node<type_t>> {
          for (auto node = first(); node; node = node->next())
            if (xtd::collections::generic::helpers::equator<type_t> {}(node->value(), value)) return node;
          return xtd::nullopt;
        }
        
        [[nodiscard]] auto find_last(const type_t value) const noexcept -> xtd::optional<linked_list_node<type_t>> {
          for (auto node = last(); node; node = node->previous())
            if (xtd::collections::generic::helpers::equator<type_t> {}(node->value(), value)) return node;
          return xtd::nullopt;
        }
        
        [[nodiscard]] enumerator<value_type> get_enumerator() const noexcept override {
          struct linked_list_enumerator : public ienumerator < value_type > {
            explicit linked_list_enumerator(const linked_list & items, xtd::usize version) : items_(items), version_(version) {}
            
            [[nodiscard]] const value_type& current() const override {
              if (iterator_ == items_.data_->items.cend()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation);
              if (version_ != items_.data_->version) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation, "Collection was modified; enumeration operation may not execute.");
              return *iterator_;
            }
            
            [[nodiscard]] bool move_next() override {
              if (version_ != items_.data_->version) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation, "Collection was modified; enumeration operation may not execute.");
              if (index_++ && iterator_ != items_.data_->items.cend()) ++iterator_;
              else iterator_ = items_.data_->items.cbegin();
              return iterator_ != items_.data_->items.cend();
            }
            
            void reset() override {
              index_ = 0;
              version_ = items_.data_->version;
              iterator_ = items_.data_->items.cend();
            }
            
          private:
            size_type index_ = 0;
            const linked_list& items_;
            typename base_type::const_iterator iterator_ = items_.data_->items.cend();
            size_type version_ = 0;
          };
          return {new_ptr < linked_list_enumerator > (self_, data_->version)};
        }
        
        auto remove(const type_t& item) noexcept -> bool override {
          auto node = find(item);
          if (node == nullopt) return false;
          remove(*node);
          return true;
        }

        auto remove(linked_list_node<type_t>& node) -> void {
          if (!count()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation);
          if (node.data_->list != this) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation);
          if (node.data_->version != data_->version) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation, "Collection was modified; enumeration operation may not execute.");
          node.data_->value = *node.data_->iterator;
          data_->items.erase(node.data_->iterator);
          ++data_->version;
          node.data_->list = null;
        }
        
        auto remove_first() -> void {
          if (!count()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation);
          data_->items.erase(data_->items.begin());
          ++data_->version;
        }
        
        auto remove_last() -> void {
          if (!count()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation);
          data_->items.erase(--data_->items.end());
          ++data_->version;
        }
        
        [[nodiscard]] auto to_string() const noexcept -> xtd::string override {return xtd::string::format("[{}]", xtd::string::join(", ", self_));}
        
        
        auto operator =(const linked_list & other) -> linked_list& = default;
        auto operator =(linked_list&& other) noexcept -> linked_list& {
          data_->items = std::move(other.data_->items);
          return self_;
        }

        auto operator =(const std::initializer_list < type_t >& items) -> linked_list& {
          data_->items = items;
          return self_;
        }
        
        operator const base_type& () const noexcept {return data_->items;}
        operator base_type& () noexcept {return data_->items;}
        
      private:
        friend class linked_list_node<type_t>;
        auto add(const type_t& item) -> void override {add_last(item);}
        auto is_read_only() const noexcept -> bool override {return false;}
        auto is_synchronized() const noexcept -> bool override {return false;}
        const xtd::object& sync_root() const noexcept override {return data_->sync_root;}
        
        struct linked_list_data {
          base_type items;
          xtd::object sync_root;
          xtd::usize version = 0;
        };
        
        xtd::ptr < linked_list_data > data_ = xtd::new_ptr < linked_list_data > ();
      };
      
      // Deduction guides for xtd::collections::generic::linked_list
      // {
      template < class type_t, typename allocator_t = xtd::collections::generic::helpers::allocator < type_t>>
      linked_list(linked_list < type_t, allocator_t >&&) -> linked_list < type_t, allocator_t >;
      
      template < class type_t, typename allocator_t = xtd::collections::generic::helpers::allocator < type_t>>
      linked_list(const list < type_t, allocator_t >&) -> linked_list < type_t, allocator_t >;
      
      template < class type_t>
      linked_list(const std::list < type_t >&) -> linked_list < type_t >;
      
      template < class type_t>
      linked_list(std::list < type_t >&&) -> linked_list < type_t >;
      
      template < class type_t>
      linked_list(const ienumerable < type_t >&) -> linked_list < type_t >;
 
      template <xtd::iterable iterable_t>
      linked_list(iterable_t&&) -> linked_list<xtd::iterable_value_type<iterable_t>>;
 
      template < class type_t>
      linked_list(std::initializer_list < type_t >) -> linked_list < type_t >;
      
      template<typename input_iterator_t>
      linked_list(input_iterator_t, input_iterator_t) -> linked_list<std::iter_value_t<input_iterator_t>>;
      // }
    }
  }
}