From 8e901fd37cbcde83dae306c49c22ce6404ff95d6 2017-09-05 09:23:29 From: Alexandre Leroux Date: 2017-09-05 09:23:29 Subject: [PATCH] Makes random access iterators Updates current iterators to be random access compatible. This allows to improve perfs on lower_bound/upper_bound algorithms --- diff --git a/core/include/Data/ArrayData.h b/core/include/Data/ArrayData.h index 5125f6b..e14f532 100644 --- a/core/include/Data/ArrayData.h +++ b/core/include/Data/ArrayData.h @@ -93,6 +93,15 @@ public: return std::make_unique >(*this); } + int distance(const ArrayDataIteratorValue::Impl &other) const override try { + /// @todo ALX : validate + const auto &otherImpl = dynamic_cast(other); + return std::distance(otherImpl.m_It, m_It) / m_NbComponents; + } + catch (const std::bad_cast &) { + return 0; + } + bool equals(const ArrayDataIteratorValue::Impl &other) const override try { const auto &otherImpl = dynamic_cast(other); return std::tie(m_It, m_NbComponents) == std::tie(otherImpl.m_It, otherImpl.m_NbComponents); @@ -101,6 +110,23 @@ public: return false; } + bool lowerThan(const ArrayDataIteratorValue::Impl &other) const override try { + const auto &otherImpl = dynamic_cast(other); + return m_It < otherImpl.m_It; + } + catch (const std::bad_cast &) { + return false; + } + + std::unique_ptr advance(int offset) const override + { + auto result = clone(); + while (offset--) { + result->next(); + } + return result; + } + void next() override { std::advance(m_It, m_NbComponents); } void prev() override { std::advance(m_It, -m_NbComponents); } diff --git a/core/include/Data/ArrayDataIterator.h b/core/include/Data/ArrayDataIterator.h index 791b473..040f5f1 100644 --- a/core/include/Data/ArrayDataIterator.h +++ b/core/include/Data/ArrayDataIterator.h @@ -19,7 +19,10 @@ public: struct Impl { virtual ~Impl() noexcept = default; virtual std::unique_ptr clone() const = 0; + virtual int distance(const Impl &other) const = 0; virtual bool equals(const Impl &other) const = 0; + virtual bool lowerThan(const Impl &other) const = 0; + virtual std::unique_ptr advance(int offset) const = 0; virtual void next() = 0; virtual void prev() = 0; virtual double at(int componentIndex) const = 0; @@ -35,8 +38,11 @@ public: ArrayDataIteratorValue(const ArrayDataIteratorValue &other); ArrayDataIteratorValue &operator=(ArrayDataIteratorValue other); + int distance(const ArrayDataIteratorValue &other) const; bool equals(const ArrayDataIteratorValue &other) const; + bool lowerThan(const ArrayDataIteratorValue &other) const; + ArrayDataIteratorValue advance(int offset) const; /// Advances to the next value void next(); /// Moves back to the previous value diff --git a/core/include/Data/DataSeries.h b/core/include/Data/DataSeries.h index ea2d962..e2bea9a 100644 --- a/core/include/Data/DataSeries.h +++ b/core/include/Data/DataSeries.h @@ -54,6 +54,14 @@ public: return std::make_unique >(*this); } + int distance(const DataSeriesIteratorValue::Impl &other) const override try { + const auto &otherImpl = dynamic_cast(other); + return m_XIt->distance(*otherImpl.m_XIt); + } + catch (const std::bad_cast &) { + return 0; + } + bool equals(const DataSeriesIteratorValue::Impl &other) const override try { const auto &otherImpl = dynamic_cast(other); return std::tie(m_XIt, m_ValuesIt) == std::tie(otherImpl.m_XIt, otherImpl.m_ValuesIt); @@ -62,6 +70,23 @@ public: return false; } + bool lowerThan(const DataSeriesIteratorValue::Impl &other) const override try { + const auto &otherImpl = dynamic_cast(other); + return m_XIt->lowerThan(*otherImpl.m_XIt); + } + catch (const std::bad_cast &) { + return false; + } + + std::unique_ptr advance(int offset) const override + { + auto result = clone(); + while (offset--) { + result->next(); + } + return result; + } + void next() override { ++m_XIt; diff --git a/core/include/Data/DataSeriesIterator.h b/core/include/Data/DataSeriesIterator.h index be513b0..ae0f7fa 100644 --- a/core/include/Data/DataSeriesIterator.h +++ b/core/include/Data/DataSeriesIterator.h @@ -20,7 +20,10 @@ public: struct Impl { virtual ~Impl() noexcept = default; virtual std::unique_ptr clone() const = 0; + virtual int distance(const Impl &other) const = 0; virtual bool equals(const Impl &other) const = 0; + virtual bool lowerThan(const Impl &other) const = 0; + virtual std::unique_ptr advance(int offset) const = 0; virtual void next() = 0; virtual void prev() = 0; virtual double x() const = 0; @@ -37,8 +40,11 @@ public: DataSeriesIteratorValue(const DataSeriesIteratorValue &other); DataSeriesIteratorValue &operator=(DataSeriesIteratorValue other); + int distance(const DataSeriesIteratorValue &other) const; bool equals(const DataSeriesIteratorValue &other) const; + bool lowerThan(const DataSeriesIteratorValue &other) const; + DataSeriesIteratorValue advance(int offset) const; /// Advances to the next value void next(); /// Moves back to the previous value diff --git a/core/include/Data/SqpIterator.h b/core/include/Data/SqpIterator.h index be7e79f..dcb0203 100644 --- a/core/include/Data/SqpIterator.h +++ b/core/include/Data/SqpIterator.h @@ -12,7 +12,7 @@ template class SCIQLOP_CORE_EXPORT SqpIterator { public: - using iterator_category = std::forward_iterator_tag; + using iterator_category = std::random_access_iterator_tag; using value_type = const T; using difference_type = std::ptrdiff_t; using pointer = value_type *; @@ -36,16 +36,72 @@ public: return *this; } + SqpIterator operator++(int)const + { + auto result = *this; + this->operator++(); + return result; + } + SqpIterator operator--(int)const + { + auto result = *this; + this->operator--(); + return result; + } + + SqpIterator &operator+=(int offset) + { + if (offset >= 0) { + while (offset--) { + m_CurrentValue.next(); + } + } + else { + while (offset++) { + m_CurrentValue.prev(); + } + } + + return *this; + } + SqpIterator &operator-=(int offset) { return *this += -offset; } + + SqpIterator operator+(int offset) const + { + auto result = *this; + result += offset; + return result; + } + SqpIterator operator-(int offset) const + { + auto result = *this; + result -= offset; + return result; + } + + int operator-(const SqpIterator &other) const + { + return m_CurrentValue.distance(other.m_CurrentValue); + } + const T *operator->() const { return &m_CurrentValue; } const T &operator*() const { return m_CurrentValue; } T *operator->() { return &m_CurrentValue; } T &operator*() { return m_CurrentValue; } + T &operator[](int offset) const { return m_CurrentValue.advance(offset); } bool operator==(const SqpIterator &other) const { return m_CurrentValue.equals(other.m_CurrentValue); } bool operator!=(const SqpIterator &other) const { return !(*this == other); } + bool operator>(const SqpIterator &other) const { return other.m_CurrentValue.lowerThan(*this); } + bool operator<(const SqpIterator &other) const + { + return m_CurrentValue.lowerThan(other.m_CurrentValue); + } + bool operator>=(const SqpIterator &other) const { return !(*this < other); } + bool operator<=(const SqpIterator &other) const { return !(*this > other); } private: T m_CurrentValue; diff --git a/core/src/Data/ArrayDataIterator.cpp b/core/src/Data/ArrayDataIterator.cpp index c7e7a9b..77734f2 100644 --- a/core/src/Data/ArrayDataIterator.cpp +++ b/core/src/Data/ArrayDataIterator.cpp @@ -16,11 +16,26 @@ ArrayDataIteratorValue &ArrayDataIteratorValue::operator=(ArrayDataIteratorValue return *this; } +int ArrayDataIteratorValue::distance(const ArrayDataIteratorValue &other) const +{ + return m_Impl->distance(*other.m_Impl); +} + bool ArrayDataIteratorValue::equals(const ArrayDataIteratorValue &other) const { return m_Impl->equals(*other.m_Impl); } +bool ArrayDataIteratorValue::lowerThan(const ArrayDataIteratorValue &other) const +{ + return m_Impl->lowerThan(*other.m_Impl); +} + +ArrayDataIteratorValue ArrayDataIteratorValue::advance(int offset) const +{ + return ArrayDataIteratorValue{m_Impl->advance(offset)}; +} + void ArrayDataIteratorValue::next() { m_Impl->next(); diff --git a/core/src/Data/DataSeriesIterator.cpp b/core/src/Data/DataSeriesIterator.cpp index 62e33b9..06a300b 100644 --- a/core/src/Data/DataSeriesIterator.cpp +++ b/core/src/Data/DataSeriesIterator.cpp @@ -17,11 +17,27 @@ DataSeriesIteratorValue &DataSeriesIteratorValue::operator=(DataSeriesIteratorVa return *this; } +int DataSeriesIteratorValue::distance(const DataSeriesIteratorValue &other) const +{ + auto dist = m_Impl->distance(*other.m_Impl); + return m_Impl->distance(*other.m_Impl); +} + bool DataSeriesIteratorValue::equals(const DataSeriesIteratorValue &other) const { return m_Impl->equals(*other.m_Impl); } +bool DataSeriesIteratorValue::lowerThan(const DataSeriesIteratorValue &other) const +{ + return m_Impl->lowerThan(*other.m_Impl); +} + +DataSeriesIteratorValue DataSeriesIteratorValue::advance(int offset) const +{ + return DataSeriesIteratorValue{m_Impl->advance(offset)}; +} + void DataSeriesIteratorValue::next() { m_Impl->next();