1 /** 2 * Copyright 2020 Huawei Technologies Co., Ltd 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef MINDSPORE_CCSRC_MINDDATA_DATASET_CYCLIC_ARRAY_H 18 #define MINDSPORE_CCSRC_MINDDATA_DATASET_CYCLIC_ARRAY_H 19 20 #include <memory> 21 #include <algorithm> 22 #include <cstring> 23 #include <type_traits> 24 #include "minddata/dataset/include/dataset/constants.h" 25 26 namespace mindspore { 27 namespace dataset { 28 29 /// \class CyclicArray "include/cyclic_array.h 30 /// \brief This is a container with a contiguous memory layout that pnly keeps N last entries, 31 /// when the number of entries exceeds the capacity 32 /// Must be preallocated 33 template <typename T> 34 class CyclicArray { 35 public: 36 using value_type = T; 37 class Iterator { 38 // Add operator[] and make fully compliant with random access iterator 39 // and add a const iterator 40 // add resize(), empty() 41 public: 42 using iterator_category = std::random_access_iterator_tag; 43 using value_type = CyclicArray::value_type; 44 using difference_type = std::ptrdiff_t; 45 using pointer = CyclicArray::value_type *; 46 using reference = CyclicArray::value_type &; 47 48 Iterator() = default; 49 Iterator(dsize_t idx,pointer ptr,dsize_t capacity,dsize_t head)50 Iterator(dsize_t idx, pointer ptr, dsize_t capacity, dsize_t head) 51 : cur_idx_(idx), ptr_(ptr), capacity_(capacity), head_(head) {} 52 53 Iterator(const Iterator &rhs) = default; 54 55 ~Iterator() = default; 56 57 Iterator &operator++() { 58 cur_idx_ = (cur_idx_ + 1) % (capacity_ + 1); 59 return *this; 60 } 61 62 Iterator operator++(int) { 63 Iterator tmp(*this); 64 cur_idx_ = (cur_idx_ + 1) % (capacity_ + 1); 65 return tmp; 66 } 67 68 Iterator &operator--() { 69 cur_idx_ = (cur_idx_ + capacity_) % (capacity_ + 1); 70 return *this; 71 } 72 73 Iterator operator--(int) { 74 Iterator tmp(*this); 75 cur_idx_ = (cur_idx_ + capacity_) % (capacity_ + 1); 76 return tmp; 77 } 78 79 Iterator operator+(dsize_t x) { return Iterator((cur_idx_ + x) % (capacity_ + 1), ptr_, capacity_, head_); } 80 81 Iterator operator-(dsize_t x) { 82 return Iterator((cur_idx_ + (capacity_ + 1 - x)) % (capacity_ + 1), ptr_, capacity_, head_); 83 } 84 85 bool operator<(const Iterator &rhs) { 86 return (head_ + cur_idx_) % (capacity_ + 1) < (rhs.head_ + rhs.cur_idx_) % (capacity_ + 1); 87 } 88 89 bool operator>(const Iterator &rhs) { 90 return (head_ + cur_idx_) % (capacity_ + 1) > (rhs.head_ + rhs.cur_idx_) % (capacity_ + 1); 91 } 92 93 bool operator>=(const Iterator &rhs) { 94 return (head_ + cur_idx_) % (capacity_ + 1) >= (rhs.head_ + rhs.cur_idx_) % (capacity_ + 1); 95 } 96 97 bool operator<=(const Iterator &rhs) { 98 return (head_ + cur_idx_) % (capacity_ + 1) <= (rhs.head_ + rhs.cur_idx_) % (capacity_ + 1); 99 } 100 101 difference_type operator-(const Iterator &rhs) { 102 return (cur_idx_ - rhs.cur_idx_ + capacity_ + 1) % (capacity_ + 1); 103 } 104 105 reference operator*() { return ptr_[cur_idx_]; } 106 107 pointer operator->() { return &(ptr_[cur_idx_]); } 108 109 bool operator==(const Iterator &rhs) { return cur_idx_ == rhs.cur_idx_; } 110 111 bool operator!=(const Iterator &rhs) { return cur_idx_ != rhs.cur_idx_; } 112 113 private: 114 dsize_t cur_idx_; 115 pointer ptr_; 116 dsize_t capacity_; 117 dsize_t head_; 118 }; 119 120 /// \brief Default constructor CyclicArray()121 CyclicArray() : buf_(nullptr), head_(0), tail_(0), size_(0), capacity_(0) {} 122 123 /// \brief Constructor 124 /// \param[in] capacity CyclicArray(dsize_t capacity)125 explicit CyclicArray(dsize_t capacity) 126 : buf_(std::make_unique<T[]>(capacity + 1)), head_(0), tail_(0), size_(0), capacity_(capacity) {} 127 CyclicArray(const CyclicArray<T> & rhs)128 CyclicArray(const CyclicArray<T> &rhs) 129 : buf_(std::make_unique<T[]>(rhs.capacity_ + 1)), 130 head_(rhs.head_), 131 tail_(rhs.tail_), 132 size_(rhs.size_), 133 capacity_(rhs.capacity_) { 134 std::copy(rhs.begin(), rhs.end(), begin()); 135 } 136 137 CyclicArray(CyclicArray &&rhs) = default; 138 139 ~CyclicArray() = default; 140 141 /// \brief Iterator begin() begin()142 Iterator begin() { return Iterator(head_, buf_.get(), capacity_, head_); } 143 144 /// \brief Iterator end() end()145 Iterator end() { return Iterator(tail_, buf_.get(), capacity_, head_); } 146 147 // not really const. begin()148 Iterator begin() const { return Iterator(head_, buf_.get(), capacity_, head_); } 149 end()150 Iterator end() const { return Iterator(tail_, buf_.get(), capacity_, head_); } 151 152 /// \brief clear the array. Does not deallocate memory, capacity remains the same clear()153 void clear() { 154 head_ = 0; 155 tail_ = 0; 156 size_ = 0; 157 } 158 159 /// \brief returns current size size()160 dsize_t size() { return size_; } 161 162 /// \brief returns capacity capacity()163 dsize_t capacity() { return capacity_; } 164 165 /// \brief pushes a value 166 /// \param[in] val value push_back(T val)167 void push_back(T val) { 168 buf_[tail_] = val; 169 if (size_ >= capacity_) { 170 (tail_ != capacity_) ? tail_++ : tail_ = 0; 171 (head_ != capacity_) ? head_++ : head_ = 0; 172 } else { 173 tail_++; 174 size_++; 175 } 176 } 177 178 /// \brief returns const reference to an element of the array 179 /// \param[in] idx index of the element 180 /// \param[out] const T& reference to an element of the array 181 const T &operator[](dsize_t idx) const { return buf_[(head_ + idx) % (capacity_ + 1)]; } 182 183 /// \brief returns non-const reference to an element of the array 184 /// \param[in] idx index of the element 185 /// \param[out] T& reference to an element of the array 186 T &operator[](dsize_t idx) { return buf_[(head_ + idx) % (capacity_ + 1)]; } 187 188 private: 189 std::unique_ptr<T[]> buf_; 190 dsize_t head_; 191 dsize_t tail_; 192 dsize_t size_; 193 dsize_t capacity_; 194 }; 195 } // namespace dataset 196 } // namespace mindspore 197 #endif // MINDSPORE_CCSRC_MINDDATA_DATASET_CYCLIC_ARRAY_H 198