list.hpp

Go to the documentation of this file.

#pragma once
#include "helpers/allocator.hpp"
#include "helpers/equator.hpp"
#include "comparer.hpp"
#include "ilist.hpp"
#define __XTD_CORE_INTERNAL__
#include "../../internal/__list_definition.hpp"
#include "../../internal/__xtd_raw_array_data.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 "../../self.hpp"
#include "../../string.hpp"

namespace xtd {
  namespace collections {
    namespace generic {
      template<class type_t, class 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 >> {
        struct __comparer__ {
          __comparer__(const xtd::collections::generic::icomparer<type_t>& comparer) : comparer_(comparer) {}
          bool operator()(const type_t& e1, const type_t& e2) const {return comparer_.compare(e1, e2) < 0;}
          const xtd::collections::generic::icomparer<type_t>& comparer_;
        };
        
        struct __comparison_comparer__ {
          __comparison_comparer__(xtd::comparison<const type_t&> comparison) : comparison_(comparison) {}
          bool operator()(const type_t& e1, const type_t& e2) const {return comparison_(e1, e2) < 0;}
          xtd::comparison<const type_t&> comparison_;
        };
        
        struct __enumerator__ : public ienumerator<type_t> {
        public:
          explicit __enumerator__(const list& items, xtd::size version) : items_(items), version_(version) {}
          
          const type_t& current() const 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.");
            if (index_ < items_.count()) return items_[index_];
            return default_value_;
          }
          
          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;
          }
          
        protected:
          const list& items_;
          xtd::size index_ = list::npos;
          xtd::size version_ = 0;
          type_t default_value_;
        };
        
      public:
        
        using value_type = typename ilist<type_t>::value_type;
        using base_type = typename __xtd_raw_array_data__<value_type>::base_type;
        using const_base_type = const base_type;
        using size_type = xtd::size;
        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) {add_range(collection);}
        list(const list& list) {*data_ = *list.data_;}
        list(list&& list) {
          data_ = std::move(list.data_);
          list.data_ = new_ptr<list_data>();
        }

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

        
        
        size_type capacity() const noexcept {return data_->items.capacity();}
        void capacity(size_type value) {
          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);
        }
        
        size_type count() const noexcept override {return data_->items.size();}
        
        pointer data() noexcept {return reinterpret_cast<pointer>(data_->items.data());}
        const_pointer data() const noexcept {return reinterpret_cast<const_pointer>(data_->items.data());}
        
        const auto& items() const noexcept {return data_->items;}
        auto& items() noexcept {return data_->items;}
        
        
        void add(const type_t& item) override {data_->items.push_back(item);}
        void add(type_t&& item) {data_->items.push_back(std::move(item));}
        
        void add_range(const xtd::collections::generic::ienumerable<type_t>& enumerable) {insert_range(count(), enumerable);}
        
        void add_range(std::initializer_list<type_t> il) {insert_range(count(), il);}
        
        template<class enumerable_t>
        void add_range(const enumerable_t& enumerable) {insert_range(count(), enumerable);}
        
        read_only_collection as_read_only() const noexcept {return read_only_collection {self_};}
        
        xtd::size binary_search(const type_t& item) const noexcept {return binary_search(0, count(), item, xtd::collections::generic::comparer<type_t>::default_comparer);}
        xtd::size binary_search(const type_t& item, const xtd::collections::generic::icomparer<type_t>& comparer) const noexcept {return binary_search(0, count(), item, comparer);}
        xtd::size binary_search(xtd::size index, xtd::size count, const type_t& item, const xtd::collections::generic::icomparer<type_t>& comparer) const {
          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, __comparer__{comparer});
          
          if (position != data_->items.end() && !comparer.compare(item, *position))
            return std::distance(data_->items.begin(), position);
          return ~std::distance(data_->items.begin(), position);
        }
        
        void clear() override {data_->items.clear();}
        
        bool contains(const type_t& value) const noexcept override {
          return index_of(value) != npos;
        }
        
        template<class output_t, class converter_t>
        list<output_t> convert_all(converter_t converter) const {
          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;
        }
        
        void copy_to(xtd::array<type_t>& array) const {copy_to(0, array, 0, count());}
        void copy_to(xtd::array<type_t>& array, size_type array_index) const override {copy_to(0, array, array_index, count());}
        void copy_to(size_type index, xtd::array<type_t>& array, size_type array_index, size_type count) const {
          if (index + count > self_.count() || array_index + count > array.size()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::argument_out_of_range);
          auto i = size_type {0}, c = size_type {0};
          for (const type_t& item : self_) {
            if (i >= index + count) return;
            if (i >= index) {
              array[array_index + c] = item;
              c += 1;
            }
            i += 1;
          }
        }
        
        xtd::size ensure_capacity(xtd::size capacity) {
          data_->items.reserve(capacity);
          return self_.capacity();
        }
        
        bool equals(const object& obj) const noexcept override {return is<list<value_type>>(obj) && equals(static_cast<const list<value_type>& > (obj));}
        bool equals(const list& obj) const noexcept 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<class predicate_t>
        bool exists(predicate_t match) const {
          return find_index(match) != npos;
        }
        
        template<class predicate_t>
        optional<type_t> find(predicate_t match) const {
          auto index = find_index(match);
          if (index == npos) return nullopt;
          return self_[index];
        }
        
        template<class predicate_t>
        list find_all(predicate_t match) const {
          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<class predicate_t>
        xtd::size find_index(predicate_t match) const {return find_index(0, count(), match);}
        template<class predicate_t>
        xtd::size find_index(xtd::size start_index, predicate_t match) const {return find_index(start_index, count() - start_index, match);}
        template<class predicate_t>
        xtd::size find_index(xtd::size start_index, xtd::size count, predicate_t match) const {
          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<class predicate_t>
        optional<type_t> find_last(predicate_t match) const {
          auto index = find_last_index(match);
          if (index == npos) return nullopt;
          return self_[index];
        }
        
        template<class predicate_t>
        xtd::size find_last_index(predicate_t match) const {return find_last_index(count() - 1, count(), match);}
        template<class predicate_t>
        xtd::size find_last_index(xtd::size start_index, predicate_t match) const {return find_last_index(start_index, start_index + 1, match);}
        template<class predicate_t>
        xtd::size find_last_index(xtd::size start_index, xtd::size count, predicate_t match) const {
          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<class action_t>
        void for_each(action_t action) {
          auto apply_action = xtd::action<const type_t&> {action};
          for (const auto& item : self_)
            apply_action(item);
        }
        
        enumerator<value_type> get_enumerator() const noexcept override {
          return {new_ptr<__enumerator__>(self_, data_->items.version())};
        }
        
        list get_range(size_type index, size_type count) {
          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};
        }
        
        size_type index_of(const type_t& value) const noexcept override {
          if (count() == 0)  return npos;
          return index_of(value, 0, count());
        }

        size_type index_of(const type_t& value, size_type index) const {return index_of(value, index, count() - index);}
        size_type index_of(const type_t& value, size_type index, size_type count) const {
          return find_index(index, count, delegate_(auto n) {return helpers::equator<type_t> {}(n, value);});
        }
        
        void insert(size_type index, const type_t& value) override {
          if (index > count()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::argument_out_of_range);
          data_->items.insert(data_->items.begin() + index, value);
        }
        void insert(size_type index, type_t&& value) {
          if (index > count()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::argument_out_of_range);
          data_->items.insert(data_->items.begin() + index, std::move(value));
        }
        
        void insert_range(size_type index, const xtd::collections::generic::ienumerable<type_t>& enumerable) {
          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());
        }
        void insert_range(size_type index, const std::initializer_list<type_t>& items) {
          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<class collection_t>
        void insert_range(size_type index, const collection_t& items) {
          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());
        }
        
        size_type last_index_of(const type_t& value) const noexcept {
          if (count() == 0) return npos;
          return last_index_of(value, count() - 1, count());
        }
        size_type last_index_of(const type_t& value, size_type index) const {
          return last_index_of(value, index, index + 1);
        }

        size_type last_index_of(const type_t& value, size_type index, size_type count) const {
          return find_last_index(index, count, delegate_(auto n) {return helpers::equator<type_t> {}(n, value);});
        }
        
        bool remove(const type_t& item) noexcept override {
          auto index = index_of(item);
          if (index == npos) return false;
          remove_at(index);
          return true;
        }
        
        template<class predicate_t>
        xtd::size remove_all(predicate_t match) {
          auto predicate = xtd::predicate<const type_t&> {match};
          auto count = xtd::size {0};
          auto iterator = data_->items.begin();
          while (iterator != data_->items.end())
            if (!predicate(*iterator)) iterator++;
            else {
              iterator = data_->items.erase(iterator);
              ++count;
            }
          return count;
        }
        
        void remove_at(size_type index) override {
          if (index >= count()) xtd::helpers::throw_helper::throws(xtd::helpers::exception_case::argument_out_of_range);
          data_->items.erase(data_->items.begin() + index);
        }
        
        void remove_range(size_type index, size_type count) {
          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 void resize(size_type count)  {resize(count, value_type {});}
        virtual void resize(size_type count, const value_type& value) {
          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);
        }
        
        void reverse() {reverse(0, count());}
        void reverse(size_type index, size_type count) {
          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);
        }
        
        list<type_t> slice(size_type start, size_type length) const {
          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};
        }
        
        list<type_t>& sort() {return sort(xtd::collections::generic::comparer<type_t>::default_comparer);}
        
        list<type_t>& sort(xtd::comparison<const type_t&> comparison) {
          data_->items.increment_version();
          std::sort(data_->items.begin(), data_->items.end(), __comparison_comparer__ {comparison});
          return self_;
        }
        
        list<type_t>& sort(const xtd::collections::generic::icomparer<type_t>& comparer) {
          return sort(0, count(), comparer);
        }
        
        list<type_t>& sort(xtd::size index, xtd::size count, const xtd::collections::generic::icomparer<type_t>& comparer) {
          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, __comparer__ {comparer});
          return self_;
        }
        
        xtd::array<value_type> to_array() const noexcept {return count() ? xtd::array<value_type>(data(), count()) : xtd::array<value_type> {};}
        
        string to_string() const noexcept override {return xtd::string::format("[{}]", xtd::string::join(", ", self_));}
        
        void trim_excess() {data_->items.shrink_to_fit();}
        
        template<class prediacate_t>
        bool true_for_all(prediacate_t match) const {
          auto predicate = xtd::predicate<const type_t&> {match};
          for (const auto& item : self_)
            if (!predicate(item)) return false;
          return true;
        }

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

        list& operator =(const std::initializer_list<type_t>& items) {
          data_->items = items;
          return self_;
        }
        
        const_reference operator [](size_type index) const 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];
        }

        reference operator [](size_type index) 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:
        bool is_fixed_size() const noexcept override {return false;}
        bool is_read_only() const noexcept override {return false;}
        bool is_synchronized() const noexcept override {return false;}
        const xtd::object& sync_root() const noexcept override {return data_->sync_root;}
        
        struct list_data {
          __xtd_raw_array_data__<value_type> items;
          xtd::object sync_root;
        };
        
        xtd::ptr<list_data> data_ = xtd::new_ptr<list_data>();
      };
      
      // C++17 deduction guides for xtd::collections::generic::list
      // {
      template<class type_t>
      list(std::initializer_list<type_t>) -> list<type_t, helpers::allocator<type_t >>;
      
      template<class type_t>
      list(const ienumerable<type_t>&) -> list<type_t, helpers::allocator<type_t >>;
      
      template<class type_t>
      list(const ilist<type_t>&) -> list<type_t, helpers::allocator<type_t >>;
      
      template<class type_t>
      list(const std::vector<type_t>&) -> list<type_t, helpers::allocator<type_t >>;
      
      template<class type_t, class allocator_t = helpers::allocator<type_t>>
      list(const list<type_t, allocator_t>&) -> list<type_t, allocator_t>;
      
      template<class type_t>
      list(std::vector<type_t>&&) -> list<type_t, helpers::allocator<type_t >>;
      
      template<class type_t, class allocator_t = helpers::allocator<type_t>>
      list(list<type_t, allocator_t>&&) -> list<type_t, allocator_t>;
      // }
    }
  }
}

namespace xtd::collections::generic::extensions {
  template <class enumerable_t, class source_t>
  inline xtd::collections::generic::list<source_t> enumerable<enumerable_t, source_t>::to_list() const noexcept {
    return xtd::linq::enumerable::to_list(base());
  }
}
 
namespace xtd::linq {
  template <class source_t>
  inline auto enumerable::to_list(const xtd::collections::generic::ienumerable<source_t>& source) noexcept {
    auto result = xtd::collections::generic::list<source_t> {};
    result = xtd::collections::generic::list<source_t> {source};
    return result;
  }
}