1 /*
2  * Copyright (c) 2020-2021 Huawei Device Co., Ltd.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  *     http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 /**
17  * @addtogroup UI_Utils
18  * @{
19  *
20  * @brief Defines basic UI utils.
21  *
22  * @since 1.0
23  * @version 1.0
24  */
25 
26 /**
27  * @file list.h
28  *
29  * @brief Defines a linked list template class, which implements the data structure of bidirectional linked list and
30  *        provides basic functions such as adding, deleting, inserting, clearing, popping up, and obtaining the size of
31  *        the linked list.
32  *
33  * @since 1.0
34  * @version 1.0
35  */
36 
37 #ifndef GRAPHIC_LITE_LIST_H
38 #define GRAPHIC_LITE_LIST_H
39 #include "gfx_utils/heap_base.h"
40 #include <cstdint>
41 
42 namespace OHOS {
43 /**
44  * @brief Stores linked list data and contains pointers to the previous node and the next node.
45  *
46  * @param T Indicates the type of the data stored in the linked list.
47  * @since 1.0
48  * @version 1.0
49  */
50 template<typename T>
51 class ListNode : public HeapBase {
52 public:
53     ListNode<T>* prev_;
54     ListNode<T>* next_;
55     T data_;
56 };
57 
58 /**
59  * @brief Defines a linked list template class, which implements the data structure of bidirectional linked list and
60  *        provides basic functions such as adding, deleting, inserting, clearing, popping up, and obtaining the size of
61  *        the linked list.
62  *
63  * @param T Indicates the type of the data stored in the linked list.
64  * @since 1.0
65  * @version 1.0
66  */
67 template<typename T>
68 class List : public HeapBase {
69 public:
70     /**
71      * @brief A default constructor used to create a <b>List</b> instance. The initial size is <b>0</b>.
72      *
73      * @since 1.0
74      * @version 1.0
75      */
List()76     List() : size_(0)
77     {
78         head_.next_ = &head_;
79         head_.prev_ = &head_;
80     }
81 
82     /**
83      * @brief A destructor used to delete the <b>List</b> instance.
84      *
85      * @since 1.0
86      * @version 1.0
87      */
~List()88     virtual ~List() {}
89 
90     /**
91      * @brief Obtains the head node data of a linked list.
92      *
93      * @return Returns the head node data.
94      * @since 1.0
95      * @version 1.0
96      */
Front()97     const T Front() const
98     {
99         return head_.next_->data_;
100     }
101 
102     /**
103      * @brief Obtains the tail node data of a linked list.
104      *
105      * @return Returns the tail node data.
106      * @since 1.0
107      * @version 1.0
108      */
Back()109     const T Back() const
110     {
111         return head_.prev_->data_;
112     }
113 
114     /**
115      * @brief Inserts data at the end of a linked list.
116      *
117      * @param data Indicates the data to insert.
118      * @since 1.0
119      * @version 1.0
120      */
PushBack(T data)121     void PushBack(T data)
122     {
123         ListNode<T>* listNode = new ListNode<T>();
124         if (listNode == nullptr) {
125             return;
126         }
127         listNode->data_ = data;
128 
129         listNode->prev_ = head_.prev_;
130         listNode->next_ = &head_;
131         head_.prev_->next_ = listNode;
132         head_.prev_ = listNode;
133 
134         size_++;
135     }
136 
137     /**
138      * @brief Inserts data at the start of a linked list.
139      *
140      * @param data Indicates the data to insert.
141      * @since 1.0
142      * @version 1.0
143      */
PushFront(T data)144     void PushFront(T data)
145     {
146         ListNode<T>* listNode = new ListNode<T>();
147         if (listNode == nullptr) {
148             return;
149         }
150         listNode->data_ = data;
151 
152         listNode->next_ = head_.next_;
153         listNode->prev_ = &head_;
154         head_.next_->prev_ = listNode;
155         head_.next_ = listNode;
156 
157         size_++;
158     }
159 
160     /**
161      * @brief Pops up a data record at the end of a linked list.
162      *
163      * @since 1.0
164      * @version 1.0
165      */
PopBack()166     void PopBack()
167     {
168         if (IsEmpty()) {
169             return;
170         }
171         ListNode<T>* tmpTail = head_.prev_;
172 
173         tmpTail->prev_->next_ = &head_;
174         head_.prev_ = tmpTail->prev_;
175 
176         delete tmpTail;
177 
178         if (size_ > 0) {
179             size_--;
180         }
181     }
182 
183     /**
184      * @brief Pops up a data record at the start of a linked list.
185      *
186      * @since 1.0
187      * @version 1.0
188      */
PopFront()189     void PopFront()
190     {
191         if (IsEmpty()) {
192             return;
193         }
194         ListNode<T>* tmpHead = head_.next_;
195 
196         head_.next_ = tmpHead->next_;
197         tmpHead->next_->prev_ = &head_;
198 
199         delete tmpHead;
200 
201         if (size_ > 0) {
202             size_--;
203         }
204     }
205 
206     /**
207      * @brief Inserts data before a specified node, which follows the inserted data node.
208      * @param node Indicates the pointer to the node holding the inserted data.
209      * @param data Indicates the data to insert.
210      * @since 1.0
211      * @version 1.0
212      */
Insert(ListNode<T> * node,T data)213     void Insert(ListNode<T>* node, T data)
214     {
215         if ((node == nullptr) || (node->prev_ == nullptr)) {
216             return;
217         }
218         ListNode<T>* listNode = new ListNode<T>();
219         if (listNode == nullptr) {
220             return;
221         }
222         listNode->data_ = data;
223 
224         listNode->next_ = node;
225         listNode->prev_ = node->prev_;
226         node->prev_->next_ = listNode;
227         node->prev_ = listNode;
228 
229         size_++;
230     }
231 
232     /**
233      * @brief Deletes a data node.
234      *
235      * @param node Indicates the pointer to the node to delete.
236      * @return 返回要删除节点的下一个节点.
237      * @since 1.0
238      * @version 1.0
239      */
Remove(ListNode<T> * node)240     ListNode<T>* Remove(ListNode<T>* node)
241     {
242         if (IsEmpty()) {
243             return &head_;
244         }
245         if ((node == nullptr) || (node->prev_ == nullptr) || (node->next_ == nullptr)) {
246             return &head_;
247         }
248         ListNode<T>* next = node->next_;
249         node->prev_->next_ = node->next_;
250         node->next_->prev_ = node->prev_;
251 
252         delete node;
253 
254         if (size_ > 0) {
255             size_--;
256         }
257         return next;
258     }
259 
260     /**
261      * @brief Deletes all nodes from a linked list.
262      *
263      * @since 1.0
264      * @version 1.0
265      */
Clear()266     void Clear()
267     {
268         if (IsEmpty()) {
269             return;
270         }
271 
272         ListNode<T>* node = head_.next_;
273         ListNode<T>* tmpNode = node->next_;
274         do {
275             delete node;
276             node = tmpNode;
277             tmpNode = tmpNode->next_;
278         } while (node != &head_);
279 
280         head_.next_ = &head_;
281         head_.prev_ = &head_;
282 
283         size_ = 0;
284     }
285 
286     /**
287      * @brief Obtains the head node address of a linked list.
288      *
289      * @return Returns the head node address.
290      * @since 1.0
291      * @version 1.0
292      */
Head()293     ListNode<T>* Head() const
294     {
295         return head_.next_;
296     }
297 
298     /**
299      * @brief Obtains the tail node address of a linked list.
300      *
301      * @return Returns the tail node address.
302      * @since 1.0
303      * @version 1.0
304      */
Tail()305     ListNode<T>* Tail() const
306     {
307         return head_.prev_;
308     }
309 
310     /**
311      * @brief Obtains the head node address of a linked list.
312      *
313      * @return Returns the head node address.
314      * @since 1.0
315      * @version 1.0
316      */
Begin()317     ListNode<T>* Begin() const
318     {
319         return head_.next_;
320     }
321 
322     /**
323      * @brief Obtains the end node address of a linked list.
324      *
325      * @return Returns the end node address.
326      * @since 1.0
327      * @version 1.0
328      */
End()329     const ListNode<T>* End() const
330     {
331         return &head_;
332     }
333 
334     /**
335      * @brief Obtains the address of the node following the specified <b>node</b>.
336      *
337      * @param node Indicates the pointer to the data node in the linked list.
338      * @return Returns the address of the node following <b>node</b>.
339      * @since 1.0
340      * @version 1.0
341      */
Next(const ListNode<T> * node)342     ListNode<T>* Next(const ListNode<T>* node) const
343     {
344         return node != nullptr ? node->next_ : nullptr;
345     }
346 
347     /**
348      * @brief Checks whether a linked list is empty.
349      *
350      * @return Returns <b>true</b> if the linked list is empty; returns <b>false</b> otherwise.
351      * @since 1.0
352      * @version 1.0
353      */
IsEmpty()354     bool IsEmpty() const
355     {
356         return (head_.next_ == &head_);
357     }
358 
359     /**
360      * @brief Obtains the size of a linked list.
361      *
362      * @return Returns the size of the linked list.
363      * @since 1.0
364      * @version 1.0
365      */
Size()366     uint16_t Size() const
367     {
368         return size_;
369     }
370 
371 protected:
372     ListNode<T> head_;
373     uint16_t size_;
374 };
375 } // namespace OHOS
376 #endif // GRAPHIC_LITE_LIST_H
377