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
|