24 typedef Pool<SPListNode<T> > NodePool;
25 typedef typename NodePool::Key NodeKey;
28 SPListNode() : m_prev(
nullptr), m_next(
nullptr) {}
29 explicit SPListNode(
const T& data) : m_prev(
nullptr), m_next(
nullptr), m_data(data) {}
54 explicit SPL_Iterator(Node* listNode) : m_node(listNode) {}
59 KY_INLINE
bool operator==(
const SPL_Iterator& rhs)
const {
return m_node == rhs.m_node; }
60 KY_INLINE
bool operator!=(
const SPL_Iterator& rhs)
const {
return m_node != rhs.m_node; }
62 KY_INLINE
SPL_Iterator& operator++() { m_node = m_node->m_next;
return *
this; }
63 KY_INLINE
SPL_Iterator& operator--() { m_node = m_node->m_prev;
return *
this; }
68 KY_INLINE T& operator*()
const {
return m_node->m_data; }
69 KY_INLINE T* operator->()
const {
return &m_node->m_data; }
74 KY_INLINE
bool IsNull()
const {
return m_node ==
nullptr; }
75 KY_INLINE
bool IsNotNull()
const {
return m_node !=
nullptr; }
100 KY_INLINE
bool operator==(
const SPL_ConstIterator& rhs)
const {
return m_node == rhs.m_node; }
101 KY_INLINE
bool operator!=(
const SPL_ConstIterator& rhs)
const {
return m_node != rhs.m_node; }
103 KY_INLINE
SPL_ConstIterator& operator++() { m_node = m_node->m_next;
return *
this; }
104 KY_INLINE
SPL_ConstIterator& operator--() { m_node = m_node->m_prev;
return *
this; }
109 KY_INLINE
const T& operator*()
const {
return m_node->m_data; }
110 KY_INLINE
const T* operator->()
const {
return &m_node->m_data; }
115 KY_INLINE
bool IsNull()
const {
return m_node ==
nullptr; }
116 KY_INLINE
bool IsNotNull()
const {
return m_node !=
nullptr; }
146 template <
typename T>
158 typedef Pool<SPListNode<T> > NodePool;
159 typedef typename NodePool::Key NodeKey;
164 explicit SharedPoolList(NodePool* nodePool =
nullptr) : m_nodePool(nodePool), m_count(0)
165 { m_root.m_next = m_root.m_prev = RootAsNode(); }
167 void SetNodePool(NodePool* nodePool) { m_nodePool = nodePool; }
173 KyUInt32 GetCount()
const {
return m_count; }
178 ConstIterator GetFirst()
const {
return ConstIterator(m_root.m_next); }
179 ConstIterator GetLast()
const {
return ConstIterator(m_root.m_prev); }
180 Iterator GetFirst() {
return Iterator(m_root.m_next); }
181 Iterator GetLast () {
return Iterator(m_root.m_prev); }
183 ConstIterator Begin()
const {
return ConstIterator(m_root.m_next); }
184 ConstIterator End()
const {
return ConstIterator(RootAsNode()); }
185 Iterator Begin() {
return Iterator(m_root.m_next); }
186 Iterator End() {
return Iterator(RootAsNode()); }
195 bool IsEmpty()
const {
return m_root.m_next == RootAsNode(); }
197 bool IsFirst(ConstIterator it)
const {
return it.m_node == m_root.m_next; }
198 bool IsFirst(Iterator it)
const {
return it.m_node == m_root.m_next; }
200 bool IsLast (ConstIterator it)
const {
return it.m_node == m_root.m_prev; }
201 bool IsLast (Iterator it)
const {
return it.m_node == m_root.m_prev; }
203 bool IsNull (ConstIterator it)
const {
return it.m_node == RootAsNode(); }
204 bool IsNull (Iterator it)
const {
return it.m_node == RootAsNode(); }
206 bool IsValid(ConstIterator it)
const {
return it.m_node != RootAsNode(); }
207 bool IsValid(Iterator it)
const {
return it.m_node != RootAsNode(); }
209 ConstIterator Find(
const T& data)
const;
210 Iterator Find(
const T& data);
215 Iterator InsertBefore(
const T& data, Iterator nextNodeIt) { Node* newNode = NewNode(data); InsertNodeBefore(newNode, nextNodeIt.m_node);
return Iterator(newNode); }
216 Iterator InsertAfter(Iterator prevNodeIt,
const T& data) { Node* newNode = NewNode(data); InsertNodeAfter(prevNodeIt.m_node, newNode);
return Iterator(newNode); }
218 Iterator InsertBefore(Iterator nextNodeIt) { Node* newNode = NewNode(); InsertNodeBefore(newNode, nextNodeIt.m_node);
return Iterator(newNode); }
219 Iterator InsertAfter(Iterator prevNodeIt) { Node* newNode = NewNode(); InsertNodeAfter(prevNodeIt.m_node, newNode);
return Iterator(newNode); }
221 Iterator PushFront(
const T& data) { Node* newNode = NewNode(data); InsertNodeBefore(newNode, m_root.m_next);
return Iterator(newNode); }
222 Iterator PushBack(
const T& data) { Node* newNode = NewNode(data); InsertNodeAfter(m_root.m_prev, newNode);
return Iterator(newNode); }
224 Iterator PushFront() { Node* newNode = NewNode(); InsertNodeBefore(newNode, m_root.m_next);
return Iterator(newNode); }
225 Iterator PushBack() { Node* newNode = NewNode(); InsertNodeAfter(m_root.m_prev, newNode);
return Iterator(newNode); }
230 Iterator Erase(Iterator it);
232 Iterator RemoveFirstOccurrence(Iterator begin,
const T& data);
234 KyUInt32 RemoveAllOccurrences(
const T& data);
236 template<
class Predicate>
237 KyUInt32 Remove_If(Predicate predicate)
240 for (Iterator it = Begin(); it != End(); )
254 void InsertNodeBefore(Node* newNode, Node* nextNode) { InsertNodeBetween(nextNode->m_prev, newNode, nextNode); }
255 void InsertNodeAfter(Node* prevNode, Node* newNode) { InsertNodeBetween(prevNode, newNode, prevNode->m_next); }
256 void InsertNodeBetween(Node* prevNode, Node* newNode, Node* nextNode);
257 Node* NewNode(
const T& data);
259 void RemoveNode(Node* node) { node->m_prev->m_next = node->m_next; node->m_next->m_prev = node->m_prev; }
260 Node* RootAsNode() {
return &m_root; }
261 const Node* RootAsNode()
const {
return &m_root; }
264 NodePool* m_nodePool;
270 template <
typename T>
274 Node* node =
nullptr;
275 m_nodePool->New_CompactKeyAndPtr(key, node);
278 node->m_nodeKey = key;
285 template <
typename T>
286 typename SharedPoolList<T>::Node* SharedPoolList<T>::NewNode()
288 NodeKey nodeKey = m_nodePool->New_CompactKey();
289 Node* node = &m_nodePool->Get(nodeKey);
291 node->m_nodeKey = nodeKey;
296 template <
typename T>
297 void SharedPoolList<T>::InsertNodeBetween(Node* prevNode, Node* newNode, Node* nextNode)
299 prevNode->m_next = newNode;
300 newNode->m_prev = prevNode;
302 newNode->m_next = nextNode;
303 nextNode->m_prev = newNode;
307 template <
typename T>
308 typename SharedPoolList<T>::Iterator SharedPoolList<T>::Erase(Iterator it)
310 Node* node = it.m_node;
311 Node* nextNode = node->m_next;
313 m_nodePool->Delete(node->m_nodeKey);
315 return Iterator(nextNode);
319 template <
typename T>
320 void SharedPoolList<T>::Clear()
322 for (Iterator it = Begin(); it != End(); ++it)
323 m_nodePool->Delete(it.m_node->m_nodeKey);
326 m_root.m_next = m_root.m_prev = RootAsNode();
330 template <
typename T>
331 typename SharedPoolList<T>::ConstIterator SharedPoolList<T>::Find(
const T& data)
const
333 for (ConstIterator it = Begin(); it != End(); ++it)
341 template <
typename T>
342 typename SharedPoolList<T>::Iterator SharedPoolList<T>::Find(
const T& data)
344 for (Iterator it = Begin(); it != End(); ++it)
353 template <
typename T>
354 typename SharedPoolList<T>::Iterator SharedPoolList<T>::RemoveFirstOccurrence(Iterator begin,
const T& data)
357 for (; it != End(); ++it)
366 template <
typename T>
367 KyUInt32 SharedPoolList<T>::RemoveAllOccurrences(
const T& data)
370 for (Iterator it = Begin(); it != End(); )
std::uint32_t KyUInt32
uint32_t
Definition: types.h:29
Const iterator on SharedPoolList nodes (SPL stands for SharedPoolList).
Definition: sharedpoollist.h:83
SharedPoolList represents an ordered list of elements of a single type, drawn as needed from a pre-al...
Definition: sharedpoollist.h:147
#define KY_CLASS_WITHOUT_COPY(ClassName)
Define to forbid copy constructor and copy assignment.
Definition: types.h:196
#define KY_DEFINE_NEW_DELETE_OPERATORS(MemStat)
This macro defines new and delete operators.
Definition: memory.h:132
This is the list node used in SharedPoolList implementation (SP stands for SharedPool).
Definition: sharedpoollist.h:18
The Autodesk Navigation namespace.
Definition: gamekitcrowddispersion.cpp:17
Iterator on SharedPoolList nodes (SPL stands for SharedPoolList).
Definition: sharedpoollist.h:41