OpenShot Library | OpenShotAudio 0.2.2
juce_LinkedListPointer.h
1
2/** @weakgroup juce_core-containers
3 * @{
4 */
5/*
6 ==============================================================================
7
8 This file is part of the JUCE library.
9 Copyright (c) 2017 - ROLI Ltd.
10
11 JUCE is an open source library subject to commercial or open-source
12 licensing.
13
14 The code included in this file is provided under the terms of the ISC license
15 http://www.isc.org/downloads/software-support-policy/isc-license. Permission
16 To use, copy, modify, and/or distribute this software for any purpose with or
17 without fee is hereby granted provided that the above copyright notice and
18 this permission notice appear in all copies.
19
20 JUCE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY, AND ALL WARRANTIES, WHETHER
21 EXPRESSED OR IMPLIED, INCLUDING MERCHANTABILITY AND FITNESS FOR PURPOSE, ARE
22 DISCLAIMED.
23
24 ==============================================================================
25*/
26
27namespace juce
28{
29
30//==============================================================================
31/**
32 Helps to manipulate singly-linked lists of objects.
33
34 For objects that are designed to contain a pointer to the subsequent item in the
35 list, this class contains methods to deal with the list. To use it, the ObjectType
36 class that it points to must contain a LinkedListPointer called nextListItem, e.g.
37
38 @code
39 struct MyObject
40 {
41 int x, y, z;
42
43 // A linkable object must contain a member with this name and type, which must be
44 // accessible by the LinkedListPointer class. (This doesn't mean it has to be public -
45 // you could make your class a friend of a LinkedListPointer<MyObject> instead).
46 LinkedListPointer<MyObject> nextListItem;
47 };
48
49 LinkedListPointer<MyObject> myList;
50 myList.append (new MyObject());
51 myList.append (new MyObject());
52
53 int numItems = myList.size(); // returns 2
54 MyObject* lastInList = myList.getLast();
55 @endcode
56
57 @tags{Core}
58*/
59template <class ObjectType>
61{
62public:
63 //==============================================================================
64 /** Creates a null pointer to an empty list. */
66 : item (nullptr)
67 {
68 }
69
70 /** Creates a pointer to a list whose head is the item provided. */
71 explicit LinkedListPointer (ObjectType* const headItem) noexcept
72 : item (headItem)
73 {
74 }
75
76 /** Sets this pointer to point to a new list. */
77 LinkedListPointer& operator= (ObjectType* const newItem) noexcept
78 {
79 item = newItem;
80 return *this;
81 }
82
83 LinkedListPointer (LinkedListPointer&& other) noexcept
84 : item (other.item)
85 {
86 other.item = nullptr;
87 }
88
90 {
91 jassert (this != &other); // hopefully the compiler should make this situation impossible!
92
93 item = other.item;
94 other.item = nullptr;
95 return *this;
96 }
97
98 //==============================================================================
99 /** Returns the item which this pointer points to. */
100 inline operator ObjectType*() const noexcept
101 {
102 return item;
103 }
104
105 /** Returns the item which this pointer points to. */
106 inline ObjectType* get() const noexcept
107 {
108 return item;
109 }
110
111 /** Returns the last item in the list which this pointer points to.
112 This will iterate the list and return the last item found. Obviously the speed
113 of this operation will be proportional to the size of the list. If the list is
114 empty the return value will be this object.
115 If you're planning on appending a number of items to your list, it's much more
116 efficient to use the Appender class than to repeatedly call getLast() to find the end.
117 */
119 {
120 auto* l = this;
121
122 while (l->item != nullptr)
123 l = &(l->item->nextListItem);
124
125 return *l;
126 }
127
128 /** Returns the number of items in the list.
129 Obviously with a simple linked list, getting the size involves iterating the list, so
130 this can be a lengthy operation - be careful when using this method in your code.
131 */
132 int size() const noexcept
133 {
134 int total = 0;
135
136 for (auto* i = item; i != nullptr; i = i->nextListItem)
137 ++total;
138
139 return total;
140 }
141
142 /** Returns the item at a given index in the list.
143 Since the only way to find an item is to iterate the list, this operation can obviously
144 be slow, depending on its size, so you should be careful when using this in algorithms.
145 */
146 LinkedListPointer& operator[] (int index) noexcept
147 {
148 auto* l = this;
149
150 while (--index >= 0 && l->item != nullptr)
151 l = &(l->item->nextListItem);
152
153 return *l;
154 }
155
156 /** Returns the item at a given index in the list.
157 Since the only way to find an item is to iterate the list, this operation can obviously
158 be slow, depending on its size, so you should be careful when using this in algorithms.
159 */
160 const LinkedListPointer& operator[] (int index) const noexcept
161 {
162 auto* l = this;
163
164 while (--index >= 0 && l->item != nullptr)
165 l = &(l->item->nextListItem);
166
167 return *l;
168 }
169
170 /** Returns true if the list contains the given item. */
171 bool contains (const ObjectType* const itemToLookFor) const noexcept
172 {
173 for (auto* i = item; i != nullptr; i = i->nextListItem)
174 if (itemToLookFor == i)
175 return true;
176
177 return false;
178 }
179
180 //==============================================================================
181 /** Inserts an item into the list, placing it before the item that this pointer
182 currently points to.
183 */
184 void insertNext (ObjectType* const newItem)
185 {
186 jassert (newItem != nullptr);
187 jassert (newItem->nextListItem == nullptr);
188 newItem->nextListItem = item;
189 item = newItem;
190 }
191
192 /** Inserts an item at a numeric index in the list.
193 Obviously this will involve iterating the list to find the item at the given index,
194 so be careful about the impact this may have on execution time.
195 */
196 void insertAtIndex (int index, ObjectType* newItem)
197 {
198 jassert (newItem != nullptr);
199 auto* l = this;
200
201 while (index != 0 && l->item != nullptr)
202 {
203 l = &(l->item->nextListItem);
204 --index;
205 }
206
207 l->insertNext (newItem);
208 }
209
210 /** Replaces the object that this pointer points to, appending the rest of the list to
211 the new object, and returning the old one.
212 */
213 ObjectType* replaceNext (ObjectType* const newItem) noexcept
214 {
215 jassert (newItem != nullptr);
216 jassert (newItem->nextListItem == nullptr);
217
218 auto oldItem = item;
219 item = newItem;
220 item->nextListItem = oldItem->nextListItem.item;
221 oldItem->nextListItem.item = nullptr;
222 return oldItem;
223 }
224
225 /** Adds an item to the end of the list.
226
227 This operation involves iterating the whole list, so can be slow - if you need to
228 append a number of items to your list, it's much more efficient to use the Appender
229 class than to repeatedly call append().
230 */
231 void append (ObjectType* const newItem)
232 {
233 getLast().item = newItem;
234 }
235
236 /** Creates copies of all the items in another list and adds them to this one.
237 This will use the ObjectType's copy constructor to try to create copies of each
238 item in the other list, and appends them to this list.
239 */
241 {
242 auto* insertPoint = this;
243
244 for (auto* i = other.item; i != nullptr; i = i->nextListItem)
245 {
246 insertPoint->insertNext (new ObjectType (*i));
247 insertPoint = &(insertPoint->item->nextListItem);
248 }
249 }
250
251 /** Removes the head item from the list.
252 This won't delete the object that is removed, but returns it, so the caller can
253 delete it if necessary.
254 */
255 ObjectType* removeNext() noexcept
256 {
257 auto oldItem = item;
258
259 if (oldItem != nullptr)
260 {
261 item = oldItem->nextListItem;
262 oldItem->nextListItem.item = nullptr;
263 }
264
265 return oldItem;
266 }
267
268 /** Removes a specific item from the list.
269 Note that this will not delete the item, it simply unlinks it from the list.
270 */
271 void remove (ObjectType* const itemToRemove)
272 {
273 if (auto* l = findPointerTo (itemToRemove))
274 l->removeNext();
275 }
276
277 /** Iterates the list, calling the delete operator on all of its elements and
278 leaving this pointer empty.
279 */
281 {
282 while (item != nullptr)
283 {
284 auto oldItem = item;
285 item = oldItem->nextListItem;
286 delete oldItem;
287 }
288 }
289
290 /** Finds a pointer to a given item.
291 If the item is found in the list, this returns the pointer that points to it. If
292 the item isn't found, this returns null.
293 */
294 LinkedListPointer* findPointerTo (ObjectType* const itemToLookFor) noexcept
295 {
296 auto* l = this;
297
298 while (l->item != nullptr)
299 {
300 if (l->item == itemToLookFor)
301 return l;
302
303 l = &(l->item->nextListItem);
304 }
305
306 return nullptr;
307 }
308
309 /** Copies the items in the list to an array.
310 The destArray must contain enough elements to hold the entire list - no checks are
311 made for this!
312 */
313 void copyToArray (ObjectType** destArray) const noexcept
314 {
315 jassert (destArray != nullptr);
316
317 for (auto* i = item; i != nullptr; i = i->nextListItem)
318 *destArray++ = i;
319 }
320
321 /** Swaps this pointer with another one */
322 void swapWith (LinkedListPointer& other) noexcept
323 {
324 std::swap (item, other.item);
325 }
326
327 //==============================================================================
328 /**
329 Allows efficient repeated insertions into a list.
330
331 You can create an Appender object which points to the last element in your
332 list, and then repeatedly call Appender::append() to add items to the end
333 of the list in O(1) time.
334 */
336 {
337 public:
338 /** Creates an appender which will add items to the given list.
339 */
340 Appender (LinkedListPointer& endOfListPointer) noexcept
341 : endOfList (&endOfListPointer)
342 {
343 // This can only be used to add to the end of a list.
344 jassert (endOfListPointer.item == nullptr);
345 }
346
347 /** Appends an item to the list. */
348 void append (ObjectType* const newItem) noexcept
349 {
350 *endOfList = newItem;
351 endOfList = &(newItem->nextListItem);
352 }
353
354 private:
355 LinkedListPointer* endOfList;
356
357 JUCE_DECLARE_NON_COPYABLE (Appender)
358 };
359
360private:
361 //==============================================================================
362 ObjectType* item;
363
364 JUCE_DECLARE_NON_COPYABLE (LinkedListPointer)
365};
366
367} // namespace juce
368
369/** @}*/
Allows efficient repeated insertions into a list.
Appender(LinkedListPointer &endOfListPointer) noexcept
Creates an appender which will add items to the given list.
void append(ObjectType *const newItem) noexcept
Appends an item to the list.
Helps to manipulate singly-linked lists of objects.
LinkedListPointer & getLast() noexcept
Returns the last item in the list which this pointer points to.
LinkedListPointer * findPointerTo(ObjectType *const itemToLookFor) noexcept
Finds a pointer to a given item.
LinkedListPointer & operator[](int index) noexcept
Returns the item at a given index in the list.
ObjectType * replaceNext(ObjectType *const newItem) noexcept
Replaces the object that this pointer points to, appending the rest of the list to the new object,...
void append(ObjectType *const newItem)
Adds an item to the end of the list.
void deleteAll()
Iterates the list, calling the delete operator on all of its elements and leaving this pointer empty.
LinkedListPointer & operator=(ObjectType *const newItem) noexcept
Sets this pointer to point to a new list.
bool contains(const ObjectType *const itemToLookFor) const noexcept
Returns true if the list contains the given item.
ObjectType * removeNext() noexcept
Removes the head item from the list.
LinkedListPointer(ObjectType *const headItem) noexcept
Creates a pointer to a list whose head is the item provided.
void insertNext(ObjectType *const newItem)
Inserts an item into the list, placing it before the item that this pointer currently points to.
ObjectType * get() const noexcept
Returns the item which this pointer points to.
void addCopyOfList(const LinkedListPointer &other)
Creates copies of all the items in another list and adds them to this one.
int size() const noexcept
Returns the number of items in the list.
void insertAtIndex(int index, ObjectType *newItem)
Inserts an item at a numeric index in the list.
void copyToArray(ObjectType **destArray) const noexcept
Copies the items in the list to an array.
LinkedListPointer() noexcept
Creates a null pointer to an empty list.
void swapWith(LinkedListPointer &other) noexcept
Swaps this pointer with another one.
void remove(ObjectType *const itemToRemove)
Removes a specific item from the list.