File: juce_LinkedListPointer.h

package info (click to toggle)
juce 6.1.3~ds0-1~exp1
  • links: PTS, VCS
  • area: main
  • in suites: experimental
  • size: 61,612 kB
  • sloc: cpp: 431,694; java: 2,592; ansic: 797; xml: 259; sh: 164; python: 126; makefile: 64
file content (370 lines) | stat: -rw-r--r-- 11,919 bytes parent folder | download | duplicates (3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
/*
  ==============================================================================

   This file is part of the JUCE library.
   Copyright (c) 2020 - Raw Material Software Limited

   JUCE is an open source library subject to commercial or open-source
   licensing.

   The code included in this file is provided under the terms of the ISC license
   http://www.isc.org/downloads/software-support-policy/isc-license. Permission
   To use, copy, modify, and/or distribute this software for any purpose with or
   without fee is hereby granted provided that the above copyright notice and
   this permission notice appear in all copies.

   JUCE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY, AND ALL WARRANTIES, WHETHER
   EXPRESSED OR IMPLIED, INCLUDING MERCHANTABILITY AND FITNESS FOR PURPOSE, ARE
   DISCLAIMED.

  ==============================================================================
*/

namespace juce
{

//==============================================================================
/**
    Helps to manipulate singly-linked lists of objects.

    For objects that are designed to contain a pointer to the subsequent item in the
    list, this class contains methods to deal with the list. To use it, the ObjectType
    class that it points to must contain a LinkedListPointer called nextListItem, e.g.

    @code
    struct MyObject
    {
        int x, y, z;

        // A linkable object must contain a member with this name and type, which must be
        // accessible by the LinkedListPointer class. (This doesn't mean it has to be public -
        // you could make your class a friend of a LinkedListPointer<MyObject> instead).
        LinkedListPointer<MyObject> nextListItem;
    };

    LinkedListPointer<MyObject> myList;
    myList.append (new MyObject());
    myList.append (new MyObject());

    int numItems = myList.size(); // returns 2
    MyObject* lastInList = myList.getLast();
    @endcode

    @tags{Core}
*/
template <class ObjectType>
class LinkedListPointer
{
public:
    //==============================================================================
    /** Creates a null pointer to an empty list. */
    LinkedListPointer() noexcept
        : item (nullptr)
    {
    }

    /** Creates a pointer to a list whose head is the item provided. */
    explicit LinkedListPointer (ObjectType* const headItem) noexcept
        : item (headItem)
    {
    }

    /** Sets this pointer to point to a new list. */
    LinkedListPointer& operator= (ObjectType* const newItem) noexcept
    {
        item = newItem;
        return *this;
    }

    LinkedListPointer (LinkedListPointer&& other) noexcept
        : item (other.item)
    {
        other.item = nullptr;
    }

    LinkedListPointer& operator= (LinkedListPointer&& other) noexcept
    {
        jassert (this != &other); // hopefully the compiler should make this situation impossible!

        item = other.item;
        other.item = nullptr;
        return *this;
    }

    //==============================================================================
    /** Returns the item which this pointer points to. */
    inline operator ObjectType*() const noexcept
    {
        return item;
    }

    /** Returns the item which this pointer points to. */
    inline ObjectType* get() const noexcept
    {
        return item;
    }

    /** Returns the last item in the list which this pointer points to.
        This will iterate the list and return the last item found. Obviously the speed
        of this operation will be proportional to the size of the list. If the list is
        empty the return value will be this object.
        If you're planning on appending a number of items to your list, it's much more
        efficient to use the Appender class than to repeatedly call getLast() to find the end.
    */
    LinkedListPointer& getLast() noexcept
    {
        auto* l = this;

        while (l->item != nullptr)
            l = &(l->item->nextListItem);

        return *l;
    }

    /** Returns the number of items in the list.
        Obviously with a simple linked list, getting the size involves iterating the list, so
        this can be a lengthy operation - be careful when using this method in your code.
    */
    int size() const noexcept
    {
        int total = 0;

        for (auto* i = item; i != nullptr; i = i->nextListItem)
            ++total;

        return total;
    }

    /** Returns the item at a given index in the list.
        Since the only way to find an item is to iterate the list, this operation can obviously
        be slow, depending on its size, so you should be careful when using this in algorithms.
    */
    LinkedListPointer& operator[] (int index) noexcept
    {
        auto* l = this;

        while (--index >= 0 && l->item != nullptr)
            l = &(l->item->nextListItem);

        return *l;
    }

    /** Returns the item at a given index in the list.
        Since the only way to find an item is to iterate the list, this operation can obviously
        be slow, depending on its size, so you should be careful when using this in algorithms.
    */
    const LinkedListPointer& operator[] (int index) const noexcept
    {
        auto* l = this;

        while (--index >= 0 && l->item != nullptr)
            l = &(l->item->nextListItem);

        return *l;
    }

    /** Returns true if the list contains the given item. */
    bool contains (const ObjectType* const itemToLookFor) const noexcept
    {
        for (auto* i = item; i != nullptr; i = i->nextListItem)
            if (itemToLookFor == i)
                return true;

        return false;
    }

    //==============================================================================
    /** Inserts an item into the list, placing it before the item that this pointer
        currently points to.
    */
    void insertNext (ObjectType* const newItem)
    {
        JUCE_BEGIN_IGNORE_WARNINGS_MSVC (6011)
        jassert (newItem != nullptr);
        jassert (newItem->nextListItem == nullptr);
        newItem->nextListItem = item;
        item = newItem;
        JUCE_END_IGNORE_WARNINGS_MSVC
    }

    /** Inserts an item at a numeric index in the list.
        Obviously this will involve iterating the list to find the item at the given index,
        so be careful about the impact this may have on execution time.
    */
    void insertAtIndex (int index, ObjectType* newItem)
    {
        jassert (newItem != nullptr);
        auto* l = this;

        while (index != 0 && l->item != nullptr)
        {
            l = &(l->item->nextListItem);
            --index;
        }

        l->insertNext (newItem);
    }

    /** Replaces the object that this pointer points to, appending the rest of the list to
        the new object, and returning the old one.
    */
    ObjectType* replaceNext (ObjectType* const newItem) noexcept
    {
        JUCE_BEGIN_IGNORE_WARNINGS_MSVC (6011 28182)
        jassert (newItem != nullptr);
        jassert (newItem->nextListItem == nullptr);

        auto oldItem = item;
        item = newItem;
        item->nextListItem = oldItem->nextListItem.item;
        oldItem->nextListItem.item = nullptr;
        return oldItem;
        JUCE_END_IGNORE_WARNINGS_MSVC
    }

    /** Adds an item to the end of the list.

        This operation involves iterating the whole list, so can be slow - if you need to
        append a number of items to your list, it's much more efficient to use the Appender
        class than to repeatedly call append().
    */
    void append (ObjectType* const newItem)
    {
        getLast().item = newItem;
    }

    /** Creates copies of all the items in another list and adds them to this one.
        This will use the ObjectType's copy constructor to try to create copies of each
        item in the other list, and appends them to this list.
    */
    void addCopyOfList (const LinkedListPointer& other)
    {
        auto* insertPoint = this;

        for (auto* i = other.item; i != nullptr; i = i->nextListItem)
        {
            insertPoint->insertNext (new ObjectType (*i));
            insertPoint = &(insertPoint->item->nextListItem);
        }
    }

    /** Removes the head item from the list.
        This won't delete the object that is removed, but returns it, so the caller can
        delete it if necessary.
    */
    ObjectType* removeNext() noexcept
    {
        auto oldItem = item;

        if (oldItem != nullptr)
        {
            item = oldItem->nextListItem;
            oldItem->nextListItem.item = nullptr;
        }

        return oldItem;
    }

    /** Removes a specific item from the list.
        Note that this will not delete the item, it simply unlinks it from the list.
    */
    void remove (ObjectType* const itemToRemove)
    {
        if (auto* l = findPointerTo (itemToRemove))
            l->removeNext();
    }

    /** Iterates the list, calling the delete operator on all of its elements and
        leaving this pointer empty.
    */
    void deleteAll()
    {
        while (item != nullptr)
        {
            auto oldItem = item;
            item = oldItem->nextListItem;
            delete oldItem;
        }
    }

    /** Finds a pointer to a given item.
        If the item is found in the list, this returns the pointer that points to it. If
        the item isn't found, this returns null.
    */
    LinkedListPointer* findPointerTo (ObjectType* const itemToLookFor) noexcept
    {
        auto* l = this;

        while (l->item != nullptr)
        {
            if (l->item == itemToLookFor)
                return l;

            l = &(l->item->nextListItem);
        }

        return nullptr;
    }

    /** Copies the items in the list to an array.
        The destArray must contain enough elements to hold the entire list - no checks are
        made for this!
    */
    void copyToArray (ObjectType** destArray) const noexcept
    {
        JUCE_BEGIN_IGNORE_WARNINGS_MSVC (6011)
        jassert (destArray != nullptr);

        for (auto* i = item; i != nullptr; i = i->nextListItem)
            *destArray++ = i;

        JUCE_END_IGNORE_WARNINGS_MSVC
    }

    /** Swaps this pointer with another one */
    void swapWith (LinkedListPointer& other) noexcept
    {
        std::swap (item, other.item);
    }

    //==============================================================================
    /**
        Allows efficient repeated insertions into a list.

        You can create an Appender object which points to the last element in your
        list, and then repeatedly call Appender::append() to add items to the end
        of the list in O(1) time.
    */
    class Appender
    {
    public:
        /** Creates an appender which will add items to the given list.
        */
        Appender (LinkedListPointer& endOfListPointer) noexcept
            : endOfList (&endOfListPointer)
        {
            // This can only be used to add to the end of a list.
            jassert (endOfListPointer.item == nullptr);
        }

        /** Appends an item to the list. */
        void append (ObjectType* const newItem) noexcept
        {
            *endOfList = newItem;
            endOfList = &(newItem->nextListItem);
        }

    private:
        LinkedListPointer* endOfList;

        JUCE_DECLARE_NON_COPYABLE (Appender)
    };

private:
    //==============================================================================
    ObjectType* item;

    JUCE_DECLARE_NON_COPYABLE (LinkedListPointer)
};

} // namespace juce