1 /** 2 * Copyright 2019 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 #ifndef MINDSPORE_CCSRC_MINDDATA_DATASET_UTIL_LIST_H_ 17 #define MINDSPORE_CCSRC_MINDDATA_DATASET_UTIL_LIST_H_ 18 19 #include <iostream> 20 #include <iterator> 21 22 #include "minddata/dataset/util/log_adapter.h" 23 24 namespace mindspore { 25 namespace dataset { 26 template <typename T> 27 struct Node { 28 using value_type = T; 29 using pointer = T *; 30 pointer prev; 31 pointer next; 32 NodeNode33 Node() { 34 prev = nullptr; 35 next = nullptr; 36 } 37 }; 38 39 template <typename T> 40 struct List { 41 using value_type = T; 42 using pointer = T *; 43 using const_pointer = const T *; 44 using reference = T &; 45 using const_reference = const T &; 46 int count; 47 pointer head; 48 pointer tail; 49 Node<T> T::*node; 50 51 // Constructor ListList52 explicit List(Node<T> T::*m) : count(0), head(nullptr), tail(nullptr), node(m) {} 53 54 // Destructor ~ListList55 virtual ~List() { 56 head = nullptr; 57 tail = nullptr; 58 } 59 60 // Prepend PrependList61 virtual void Prepend(pointer elem) { 62 Node<T> &elem_node = elem->*node; 63 elem_node.prev = nullptr; 64 elem_node.next = head; 65 if (head != nullptr) { 66 Node<T> &base_node = head->*node; 67 base_node.prev = elem; 68 } 69 head = elem; 70 if (tail == nullptr) { 71 tail = elem; 72 } 73 ++count; 74 } 75 76 // Append AppendList77 virtual void Append(pointer elem) { 78 Node<T> &elem_node = elem->*node; 79 elem_node.next = nullptr; 80 elem_node.prev = tail; 81 if (tail != nullptr) { 82 Node<T> &base_node = tail->*node; 83 base_node.next = elem; 84 } 85 tail = elem; 86 if (head == nullptr) { 87 head = elem; 88 } 89 ++count; 90 } 91 92 // Insert elem2 after elem1 in the list. InsertAfterList93 virtual void InsertAfter(pointer elem1, pointer elem2) { 94 MS_ASSERT(elem1 != elem2); 95 Node<T> &elem1_node = elem1->*node; 96 Node<T> &elem2_node = elem2->*node; 97 elem2_node.prev = elem1; 98 elem2_node.next = elem1_node.next; 99 if (elem1_node.next != nullptr) { 100 Node<T> &next_node = elem1_node.next->*node; 101 next_node.prev = elem2; 102 } 103 elem1_node.next = elem2; 104 if (tail == elem1) { 105 tail = elem2; 106 } 107 ++count; 108 } 109 110 // Insert elem2 before elem1 in the list. InsertBeforeList111 virtual void InsertBefore(pointer elem1, pointer elem2) { 112 MS_ASSERT(elem1 != elem2); 113 Node<T> &elem1_node = elem1->*node; 114 Node<T> &elem2_node = elem2->*node; 115 elem2_node.next = elem1; 116 elem2_node.prev = elem1_node.prev; 117 if (elem1_node.prev != nullptr) { 118 Node<T> &prev_node = elem1_node.prev->*node; 119 prev_node.next = elem2; 120 } 121 elem1_node.prev = elem2; 122 if (head == elem1) { 123 head = elem2; 124 } 125 ++count; 126 } 127 128 // Remove an element in the list RemoveList129 virtual void Remove(pointer elem) noexcept { 130 Node<T> &elem_node = elem->*node; 131 if (elem_node.next != nullptr) { 132 Node<T> &next_node = elem_node.next->*node; 133 next_node.prev = elem_node.prev; 134 } else { 135 tail = elem_node.prev; 136 } 137 if (elem_node.prev != nullptr) { 138 Node<T> &prev_node = elem_node.prev->*node; 139 prev_node.next = elem_node.next; 140 } else { 141 head = elem_node.next; 142 } 143 elem_node.prev = nullptr; 144 elem_node.next = nullptr; 145 --count; 146 } 147 148 // Iterator 149 class Iterator : public std::iterator<std::forward_iterator_tag, T> { 150 public: 151 pointer elem_; 152 elem_List153 explicit Iterator(const List<T> &v, pointer p = nullptr) : elem_(p), li_(v) {} 154 155 ~Iterator() = default; 156 157 reference operator*() { return *elem_; } 158 159 pointer operator->() { return elem_; } 160 161 const_reference operator*() const { return *elem_; } 162 163 const_pointer operator->() const { return elem_; } 164 165 bool operator==(const Iterator &rhs) const { return elem_ == rhs.elem_; } 166 167 bool operator!=(const Iterator &rhs) const { return elem_ != rhs.elem_; } 168 169 // Prefix increment 170 Iterator &operator++() { 171 Node<T> &elem_node = elem_->*(li_.node); 172 elem_ = elem_node.next; 173 return *this; 174 } 175 176 // Postfix increment 177 Iterator operator++(int junk) { 178 Iterator tmp(*this); 179 Node<T> &elem_node = elem_->*(li_.node); 180 elem_ = elem_node.next; 181 return tmp; 182 } 183 184 // Prefix decrement 185 Iterator &operator--() { 186 Node<T> &elem_node = elem_->*(li_.node); 187 elem_ = elem_node.prev; 188 return *this; 189 } 190 191 // Postfix decrement 192 Iterator operator--(int junk) { 193 Iterator tmp(*this); 194 Node<T> &elem_node = elem_->*(li_.node); 195 elem_ = elem_node.prev; 196 return tmp; 197 } 198 199 private: 200 const List<T> &li_; 201 }; 202 beginList203 Iterator begin() { 204 Iterator it(*this, head); 205 return it; 206 } 207 endList208 Iterator end() { 209 Iterator it(*this); 210 return it; 211 } 212 }; 213 } // namespace dataset 214 } // namespace mindspore 215 216 #endif // MINDSPORE_CCSRC_MINDDATA_DATASET_UTIL_LIST_H_ 217