OpenShot Library | libopenshot-audio  0.1.9
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 
27 namespace 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 */
59 template <class ObjectType>
61 {
62 public:
63  //==============================================================================
64  /** Creates a null pointer to an empty list. */
65  LinkedListPointer() noexcept
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  */
240  void addCopyOfList (const LinkedListPointer& other)
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  */
280  void deleteAll()
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  */
335  class Appender
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 
360 private:
361  //==============================================================================
362  ObjectType* item;
363 
364  JUCE_DECLARE_NON_COPYABLE (LinkedListPointer)
365 };
366 
367 } // namespace juce
368 
369 /** @}*/
void insertNext(ObjectType *const newItem)
Inserts an item into the list, placing it before the item that this pointer currently points to...
LinkedListPointer & operator[](int index) noexcept
Returns the item at a given index in the list.
void deleteAll()
Iterates the list, calling the delete operator on all of its elements and leaving this pointer empty...
void copyToArray(ObjectType **destArray) const noexcept
Copies the items in the list to an array.
LinkedListPointer & operator=(ObjectType *const newItem) noexcept
Sets this pointer to point to a new list.
void append(ObjectType *const newItem) noexcept
Appends an item to the list.
LinkedListPointer() noexcept
Creates a null pointer to an empty list.
ObjectType * removeNext() noexcept
Removes the head item from the list.
Appender(LinkedListPointer &endOfListPointer) noexcept
Creates an appender which will add items to the given list.
int size() const noexcept
Returns the number of items in the list.
void swapWith(LinkedListPointer &other) noexcept
Swaps this pointer with another one.
void addCopyOfList(const LinkedListPointer &other)
Creates copies of all the items in another list and adds them to this one.
void append(ObjectType *const newItem)
Adds an item to the end of the list.
LinkedListPointer & getLast() noexcept
Returns the last item in the list which this pointer points to.
ObjectType * replaceNext(ObjectType *const newItem) noexcept
Replaces the object that this pointer points to, appending the rest of the list to the new object...
Allows efficient repeated insertions into a list.
void insertAtIndex(int index, ObjectType *newItem)
Inserts an item at a numeric index in the list.
LinkedListPointer * findPointerTo(ObjectType *const itemToLookFor) noexcept
Finds a pointer to a given item.
bool contains(const ObjectType *const itemToLookFor) const noexcept
Returns true if the list contains the given item.
LinkedListPointer(ObjectType *const headItem) noexcept
Creates a pointer to a list whose head is the item provided.
Helps to manipulate singly-linked lists of objects.