list.hpp

Go to the documentation of this file.

#pragma once
#include "helpers/allocator.hpp"
#include "helpers/equator.hpp"
#include "helpers/lesser.hpp"
#include "helpers/raw_array.hpp"
#include "comparer.hpp"
#include "enumerable.hpp"
#include "ilist.hpp"
#define __XTD_CORE_INTERNAL__
#include "../../internal/__list_definition.hpp"
#undef  __XTD_CORE_INTERNAL__
#include "../object_model/read_only_collection.hpp"
#include "../../action.hpp"
#include "../../comparison.hpp"
#include "../../converter.hpp"
#include "../../intptr.hpp"
#include "../../is.hpp"
#include "../../object.hpp"
#include "../../optional.hpp"
#include "../../new_ptr.hpp"
#include "../../predicate.hpp"
#include "../../raw_type.hpp"
#include "../../self.hpp"
#include "../../string.hpp"

namespace xtd {
  namespace collections {
    namespace generic {
      template<typename type_t, typename allocator_t>
      class list : public xtd::object, public xtd::collections::generic::ilist<type_t>, public xtd::iequatable<xtd::collections::generic::list<type_t, allocator_t >> {
      public:
        
        using value_type = typename ilist<type_t>::value_type;
        using base_type = typename xtd::collections::generic::helpers::raw_array<value_type>::base_type;
        using const_base_type = const base_type;
        using size_type = xtd::usize;
        using reference = value_type&;
        using const_reference = const value_type&;
        using pointer = value_type*;
        using const_pointer = const value_type*;
        using read_only_collection = xtd::collections::object_model::read_only_collection<value_type>;
        
        
        list() noexcept = default;
        explicit list(size_type capacity) {self_.capacity(capacity);}
        list(const xtd::collections::generic::ienumerable<type_t>& collection) requires std::copy_constructible<type_t> {add_range(collection);}
        list(const list& list) requires std::copy_constructible<type_t> {*data_ = *list.data_;}
        list(list&& list) {
          data_ = std::move(list.data_);
          list.data_ = new_ptr<list_data>();
        }

        list(const base_type& list) requires std::copy_constructible<type_t> {data_->items = list;}
        list(base_type&& list) {data_->items = std::move(list);}
        list(std::initializer_list<type_t> items) requires std::copy_constructible<type_t> {add_range(items);}
        template <std::input_iterator input_iterator_t>
        list(input_iterator_t first, input_iterator_t last) requires std::copy_constructible<type_t> {
          for (auto iterator = first; iterator != last; ++iterator)
            add(*iterator);
        }

        
        
        [[nodiscard]] auto capacity() const noexcept -> size_type {return data_->items.capacity();}
        auto capacity(size_type value) -> void {
          if (value > data_->items.max_size()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::out_of_memory);
          if (value < count()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::argument_out_of_range);
          if (value == capacity()) return;
          if (value < capacity()) data_->items.shrink_to_fit();
          data_->items.reserve(value);
        }
        
        [[nodiscard]] auto count() const noexcept -> size_type override {return data_->items.size();}
        
        [[nodiscard]] auto data() noexcept -> pointer {return reinterpret_cast<pointer>(data_->items.data());}
        [[nodiscard]] auto data() const noexcept -> const_pointer {return reinterpret_cast<const_pointer>(data_->items.data());}
        
        [[nodiscard]] const auto& items() const noexcept {return data_->items;}
        [[nodiscard]] auto& items() noexcept {return data_->items;}
        
        
        auto add(const type_t& item) -> void override {
          if constexpr (std::copy_constructible<type_t>) data_->items.push_back(item);
          else xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation, "value_type is not copy constructible.");
        }

        auto add(type_t&& item) -> void {data_->items.push_back(std::forward<type_t>(item));}
        
        auto add_range(const xtd::collections::generic::ienumerable<type_t>& enumerable) -> void requires std::copy_constructible<type_t> {insert_range(count(), enumerable);}
        
        auto add_range(std::initializer_list<type_t> il) -> void requires std::copy_constructible<type_t> {insert_range(count(), il);}
        
        template<typename enumerable_t>
        auto add_range(const enumerable_t& enumerable) -> void requires std::copy_constructible<type_t> {insert_range(count(), enumerable);}
        
        [[nodiscard]] auto as_read_only() const noexcept -> read_only_collection requires std::copy_constructible<type_t> {return read_only_collection {self_};}
        
        [[nodiscard]] auto binary_search(const type_t& item) const noexcept -> xtd::usize {return binary_search(0, count(), item, xtd::collections::generic::comparer<type_t>::default_comparer);}
        [[nodiscard]] auto binary_search(const type_t& item, const xtd::collections::generic::icomparer<type_t>& comparer) const noexcept -> xtd::usize {return binary_search(0, count(), item, comparer);}
        [[nodiscard]] auto binary_search(xtd::usize index, xtd::usize count, const type_t& item, const xtd::collections::generic::icomparer<type_t>& comparer) const -> xtd::usize {
          if (index + count > self_.count()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::argument_out_of_range);
          auto first = data_->items.begin();
          auto last = data_->items.begin();
          std::advance(first, index);
          std::advance(last, index + count);
          auto position = std::lower_bound(first, last, item, helpers::lesser<type_t> {comparer});
          
          if (position != data_->items.end() && !comparer.compare(item, *position))
            return std::distance(data_->items.begin(), position);
          return ~std::distance(data_->items.begin(), position);
        }
        
        auto clear() -> void override {data_->items.clear();}
        
        [[nodiscard]] auto contains(const type_t& value) const noexcept -> bool override {
          return index_of(value) != npos;
        }
        
        template<typename output_t, typename converter_t>
        [[nodiscard]] auto convert_all(converter_t converter) const -> list<output_t> {
          auto result = list<output_t> {};
          auto apply_converter = xtd::converter<output_t, const type_t&> {converter};
          for (const auto& item : self_)
            result.add(apply_converter(item));
          return result;
        }
        
        auto copy_to(xtd::array<type_t>& array) const -> void requires std::copy_constructible<type_t> {copy_to(0, array, 0, count());}
        auto copy_to(xtd::array<type_t>& array, size_type array_index) const -> void override {
          if constexpr (std::copy_constructible<type_t>) copy_to(0, array, array_index, count());
          else xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation, "value_type is not copy constructible.");
        }

        auto copy_to(size_type index, xtd::array<type_t>& array, size_type array_index, size_type count) const -> void requires std::copy_constructible<type_t> {
          if (index + count > self_.count() || array_index + count > array.length()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::argument_out_of_range);
          for (auto i = index; i < (index + count); ++i)
            array[array_index++] = self_[i];
        }
        
        auto ensure_capacity(xtd::usize capacity) -> xtd::usize {
          data_->items.reserve(capacity);
          return self_.capacity();
        }
        
        [[nodiscard]] auto equals(const object& obj) const noexcept -> bool override {return is<list<value_type>>(obj) && equals(static_cast<const list<value_type>& > (obj));}
        [[nodiscard]] auto equals(const list& obj) const noexcept -> bool override {
          if (count() != obj.count()) return false;
          for (size_type i = 0; i < count(); i++)
            if (!helpers::equator<type_t> {}(self_[i], obj[i])) return false;
          return true;
        }
        
        template<typename predicate_t>
        [[nodiscard]] auto exists(predicate_t match) const -> bool {
          return find_index(match) != npos;
        }
        
        template<typename predicate_t>
        [[nodiscard]] auto find(predicate_t match) const -> optional<type_t> {
          auto index = find_index(match);
          if (index == npos) return nullopt;
          return self_[index];
        }
        
        template<typename predicate_t>
        [[nodiscard]] auto find_all(predicate_t match) const -> list {
          auto predicate = xtd::predicate<const type_t&> {match};
          auto result = list {};
          for (const auto& item : self_)
            if (predicate(item)) result.add(item);
          return result;
        }
        
        template<typename predicate_t>
        [[nodiscard]] auto find_index(predicate_t match) const -> xtd::usize {return find_index(0, count(), match);}
        template<typename predicate_t>
        [[nodiscard]] auto find_index(xtd::usize start_index, predicate_t match) const -> xtd::usize {return find_index(start_index, count() - start_index, match);}
        template<typename predicate_t>
        [[nodiscard]] auto find_index(xtd::usize start_index, xtd::usize count, predicate_t match) const -> xtd::usize {
          if (start_index > self_.count() || start_index + count > self_.count()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::argument_out_of_range);
          auto predicate = xtd::predicate<const type_t&> {match};
          for (auto index = start_index; index < start_index + count; ++index)
            if (predicate(self_[index])) return index;
          return npos;
        }
        
        template<typename predicate_t>
        [[nodiscard]] auto find_last(predicate_t match) const -> optional<type_t> {
          auto index = find_last_index(match);
          if (index == npos) return nullopt;
          return self_[index];
        }
        
        template<typename predicate_t>
        [[nodiscard]] auto find_last_index(predicate_t match) const -> xtd::usize {return find_last_index(count() - 1, count(), match);}
        template<typename predicate_t>
        [[nodiscard]] auto find_last_index(xtd::usize start_index, predicate_t match) const -> xtd::usize {return find_last_index(start_index, start_index + 1, match);}
        template<typename predicate_t>
        [[nodiscard]] auto find_last_index(xtd::usize start_index, xtd::usize count, predicate_t match) const -> xtd::usize {
          if (start_index >= self_.count() || count > start_index + 1) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::argument_out_of_range);
          auto predicate = xtd::predicate<const type_t&> {match};
          auto end_index = start_index + 1 - count;
          for (auto index = start_index; ; --index) {
            if (predicate(self_[index])) return index;
            if (index == end_index) break;
          }
          return npos;
        }
        
        template<typename action_t>
        auto for_each(action_t action) -> void {
          auto apply_action = xtd::action<const type_t&> {action};
          for (const auto& item : self_)
            apply_action(item);
        }
        
        [[nodiscard]] enumerator<value_type> get_enumerator() const noexcept override {
          struct list_enumerator : public ienumerator<value_type> {
            explicit list_enumerator(const list& items, xtd::usize version) : items_(items), version_(version) {}
            
            [[nodiscard]] const value_type& current() const override {
              if (index_ >= items_.count()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation);
              if (version_ != items_.data_->items.version()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation, "Collection was modified; enumeration operation may not execute.");
              return items_[index_];
            }
            
            [[nodiscard]] bool move_next() override {
              if (version_ != items_.data_->items.version()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation, "Collection was modified; enumeration operation may not execute.");
              return ++index_ < items_.count();
            }
            
            void reset() override {
              version_ = items_.data_->items.version();
              index_ = list::npos;
            }
            
          private:
            size_type index_ = list::npos;
            const list& items_;
            size_type version_ = 0;
          };
          
          return {new_ptr<list_enumerator>(self_, data_->items.version())};
        }
        
        [[nodiscard]] auto get_range(size_type index, size_type count) -> list {
          if (index + count > self_.count()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::argument_out_of_range);
          return list<type_t> {data_->items.begin() + index, data_->items.begin() + index + count};
        }
        
        [[nodiscard]] auto index_of(const type_t& value) const noexcept -> size_type override {
          if (count() == 0)  return npos;
          return index_of(value, 0, count());
        }

        [[nodiscard]] auto index_of(const type_t& value, size_type index) const -> size_type {return index_of(value, index, count() - index);}
        [[nodiscard]] auto index_of(const type_t& value, size_type index, size_type count) const -> size_type {
          return find_index(index, count, delegate_(const auto& n) {return helpers::equator<type_t> {}(n, value);});
        }
        
        auto insert(size_type index, const type_t& value) -> void override {
          if constexpr (std::copy_constructible<type_t>) {
            if (index > count()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::argument_out_of_range);
            data_->items.insert(data_->items.begin() + index, value);
          } else xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation, "value_type is not copy constructible.");
        }

        auto insert(size_type index, type_t&& value) -> void {
          if (index > count()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::argument_out_of_range);
          data_->items.insert(data_->items.begin() + index, std::forward<type_t>(value));
        }
        
        auto insert_range(size_type index, const xtd::collections::generic::ienumerable<type_t>& enumerable) -> void {
          if (index > count()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::argument_out_of_range);
          
          // If the collection is this instance, it must be copied to avoid an infinite loop.
          if (static_cast<const void*>(&enumerable) == static_cast<const void*>(this)) {
            insert_range(index, list(enumerable));
            return;
          }
          
          data_->items.insert(data_->items.begin() + index, enumerable.begin(), enumerable.end());
        }

        auto insert_range(size_type index, const std::initializer_list<type_t>& items) -> void {
          if (index > count()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::argument_out_of_range);
          data_->items.insert(data_->items.begin() + index, items.begin(), items.end());
        }
        
        template<typename collection_t>
        auto insert_range(size_type index, const collection_t& items) -> void {
          if (index > count()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::argument_out_of_range);
          
          // If the collection is this instance, it must be copied to avoid an infinite loop.
          if (static_cast<const void*>(&items) == static_cast<const void*>(this)) {
            insert_range(index, list(items));
            return;
          }
          
          data_->items.insert(data_->items.begin() + index, items.begin(), items.end());
        }
        
        [[nodiscard]] auto last_index_of(const type_t& value) const noexcept -> size_type {
          if (count() == 0) return npos;
          return last_index_of(value, count() - 1, count());
        }

        [[nodiscard]] auto last_index_of(const type_t& value, size_type index) const -> size_type {
          return last_index_of(value, index, index + 1);
        }
        [[nodiscard]] auto last_index_of(const type_t& value, size_type index, size_type count) const -> size_type {
          return find_last_index(index, count, delegate_(const auto& n) {return helpers::equator<type_t> {}(n, value);});
        }
        
        auto remove(const type_t& item) noexcept -> bool override {
          auto index = index_of(item);
          if (index == npos) return false;
          remove_at(index);
          return true;
        }
        
        template<typename predicate_t>
        auto remove_all(predicate_t match) -> xtd::usize {
          auto predicate = xtd::predicate<const type_t&> {match};
          auto count = xtd::usize {0};
          auto iterator = data_->items.begin();
          while (iterator != data_->items.end())
            if (!predicate(*iterator)) iterator++;
            else {
              iterator = data_->items.erase(iterator);
              ++count;
            }
          return count;
        }
        
        auto remove_at(size_type index) -> void override {
          if (index >= count()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::argument_out_of_range);
          data_->items.erase(data_->items.begin() + index);
        }
        
        auto remove_range(size_type index, size_type count) -> void {
          if (index + count > self_.count()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::argument_out_of_range);
          data_->items.erase(data_->items.begin() + index, data_->items.begin() + index + count);
        }
        
        virtual auto resize(size_type count) -> void {
          if constexpr (std::copy_constructible<type_t>) {
            resize(count, value_type {});
          } else xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation, "value_type is not copy constructible.");
        }
        virtual auto resize(size_type count, const value_type& value) -> void {
          if constexpr (std::copy_constructible<type_t>) {
            if (count > data_->items.max_size()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::out_of_memory);;
            if (count == self_.count()) return;
            data_->items.resize(count, value);
          } else xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::invalid_operation, "value_type is not copy constructible.");
        }
        
        auto reverse() -> list<type_t>& {return reverse(0, count());}
        auto reverse(size_type index, size_type count) -> list<type_t>& {
          if (index + count > self_.count()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::argument_out_of_range);
          data_->items.increment_version();
          std::reverse(data_->items.begin() + index, data_->items.begin() + index + count);
          return self_;
        }
        
        [[nodiscard]] auto slice(size_type start, size_type length) const -> list<type_t> requires std::copy_constructible<type_t> {
          if (start + length > count()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::argument_out_of_range);
          return list<type_t> {data_->items.begin() + start, data_->items.begin() + start + length};
        }
        
        auto sort() -> list<type_t>& {return sort(xtd::collections::generic::comparer<type_t>::default_comparer);}
        
        auto sort(xtd::comparison<const type_t&> comparison) -> list<type_t>& {
          data_->items.increment_version();
          std::sort(data_->items.begin(), data_->items.end(), [&](const type_t& x, const type_t& y) {return comparison(x, y) < 0;});
          return self_;
        }
        
        auto sort(const xtd::collections::generic::icomparer<type_t>& comparer) -> list<type_t>& {
          return sort(0, count(), comparer);
        }
        
        auto sort(xtd::usize index, xtd::usize count, const xtd::collections::generic::icomparer<type_t>& comparer) -> list<type_t>&  {
          if (index + count > self_.count()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::argument_out_of_range);
          data_->items.increment_version();
          std::sort(data_->items.begin() + index, data_->items.begin() + index + count, helpers::lesser<type_t> {comparer});
          return self_;
        }
        
        [[nodiscard]] auto to_array() const noexcept -> xtd::array<value_type> requires std::copy_constructible<type_t> {return count() ? xtd::array<value_type>(data_->items.begin(), data_->items.end()) : xtd::array<value_type> {};}
        
        [[nodiscard]] auto to_string() const noexcept -> xtd::string override {return xtd::string::format("[{}]", xtd::string::join(", ", self_));}
        
        auto trim_excess() -> void {data_->items.shrink_to_fit();}
        
        template<typename prediacate_t>
        [[nodiscard]] auto true_for_all(prediacate_t match) const -> bool {
          auto predicate = xtd::predicate<const type_t&> {match};
          for (const auto& item : self_)
            if (!predicate(item)) return false;
          return true;
        }

        
        
        auto operator =(const list& other) -> list& requires std::copy_constructible<type_t> = default;
        auto operator =(list&& other) noexcept -> list& {
          data_->items = std::move(other.data_->items);
          return self_;
        }

        auto operator =(const std::initializer_list<type_t>& items) -> list& requires std::copy_constructible<type_t> {
          data_->items = items;
          return self_;
        }
        
        auto operator [](size_type index) const -> const_reference override {
          if ((index >= count() && index <= ~count() - 1) || index == npos) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::index_out_of_range);
          return data_->items[index];
        }

        auto operator [](size_type index) -> reference override {
          if ((index >= count() && index <= ~count() - 1) || index == npos) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::index_out_of_range);
          return data_->items[index];
        }
        
        operator const_base_type& () const noexcept {return data_->items;}
        operator base_type& () noexcept {return data_->items;}
        
      private:
        auto is_fixed_size() const noexcept -> bool override {return false;}
        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 list_data {
          xtd::collections::generic::helpers::raw_array<value_type, allocator_t> items;
          xtd::object sync_root;
        };
        
        xtd::ptr<list_data> data_ = xtd::new_ptr<list_data>();
      };
      
      // Deduction guides for xtd::collections::generic::list
      // {
      template<typename type_t>
      list(std::initializer_list<type_t>) -> list<type_t>;
      
      template<typename type_t>
      list(const ienumerable<type_t>&) -> list<type_t>;
      
      template<typename type_t>
      list(const ilist<type_t>&) -> list<type_t>;
      
      template<typename type_t>
      list(const std::vector<type_t>&) -> list<type_t>;
      
      template<typename type_t, typename allocator_t = helpers::allocator<type_t>>
      list(const list<type_t, allocator_t>&) -> list<type_t, allocator_t>;
      
      template<typename type_t>
      list(std::vector<type_t>&&) -> list<type_t>;
      
      template<typename type_t, typename allocator_t = helpers::allocator<type_t>>
      list(list<type_t, allocator_t>&&) -> list<type_t, allocator_t>;
      
      template<typename input_iterator_t>
      list(input_iterator_t, input_iterator_t) -> list<std::iter_value_t<input_iterator_t>>;
      // }
    }
  }
}

namespace xtd::collections::generic::extensions {
  template<typename source_t, typename enumerable_t>
  inline auto enumerable<source_t, enumerable_t>::to_list() const -> xtd::collections::generic::list<source_t> {
    return xtd::linq::enumerable::to_list(self());
  }
}
 
template<xtd::iterable source_t>
auto xtd::linq::enumerable::as_enumerable(source_t&& source) noexcept {
  if constexpr(xtd::collections::generic::enumerable<source_t>) return std::move(source);
  else return xtd::collections::generic::list<xtd::iterable_value_type<source_t>>(std::move(source));
}
 
template<typename key_t, xtd::iterable source_t, xtd::callable<key_t, xtd::iterable_value_type<source_t>> key_selector_t, xtd::callable<bool, key_t, key_t> key_equater_t>
auto xtd::linq::enumerable::count_by(const source_t& source, key_selector_t&& key_selector, key_equater_t&& key_equater) noexcept -> xtd::collections::generic::enumerable_generator<xtd::collections::generic::key_value_pair<key_t, xtd::usize>> {
  auto result = list<key_value_pair<key_t, xtd::usize>> {};
  auto keys = list<key_t> {};
  auto enumerator = source.get_enumerator();
  while (enumerator.move_next()) {
    auto key = key_selector(enumerator.current());
    auto index = xtd::usize {0};
    for (; index < keys.count(); ++index)
      if (key_equater(keys[index], key)) break;
    if (index < keys.count()) result[index] = {key, result[index].value() + 1};
    else {
      keys.add(key);
      result.add({key, 1});
    }
  }
  
  for (const auto& item : result)
    co_yield item;
}
 
template<typename value_t>
inline auto xtd::linq::enumerable::to_list(const xtd::collections::generic::ienumerable<value_t>& source) {
  return xtd::collections::generic::list<value_t> {source};
}