/
redgpu
/
ezEngine
Обзор
Документация
Войти
/
redgpu
/
ezEngine
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
dev
Code/Engine/Foundation/Containers/Implementation/Set_inl.h
778 строк
21 KB
Jan Krassnigg
Minor container improvements (#1195)
04 фев 2024, 17:07
Не верифицирован
04 фев 2024, 17:07
f6448df
Код
Авторство
О чём код?
#pragma once #include <Foundation/Math/Math.h> #define STACK_SIZE 64 // ***** Const Iterator ***** template <typename KeyType, typename Comparer> template <bool REVERSE> void ezSetBase<KeyType, Comparer>::IteratorBase<REVERSE>::Advance(ezInt32 dir0, ezInt32 dir1) { if (m_pElement == nullptr) { EZ_ASSERT_DEBUG(m_pElement != nullptr, "The Iterator is invalid (end)."); return; } // if this element has a right child, go there and then search for the left most child of that if (m_pElement->m_pLink[dir1] != m_pElement->m_pLink[dir1]->m_pLink[dir1]) { m_pElement = m_pElement->m_pLink[dir1]; while (m_pElement->m_pLink[dir0] != m_pElement->m_pLink[dir0]->m_pLink[dir0]) m_pElement = m_pElement->m_pLink[dir0]; return; } // if this element has a parent and this element is that parents left child, go directly to the parent if ((m_pElement->m_pParent != m_pElement->m_pParent->m_pParent) && (m_pElement->m_pParent->m_pLink[dir0] == m_pElement)) { m_pElement = m_pElement->m_pParent; return; } // if this element has a parent and this element is that parents right child, search for the next parent, whose left child this is if ((m_pElement->m_pParent != m_pElement->m_pParent->m_pParent) && (m_pElement->m_pParent->m_pLink[dir1] == m_pElement)) { while (m_pElement->m_pParent->m_pLink[dir1] == m_pElement) m_pElement = m_pElement->m_pParent; // if we are at the root node.. if ((m_pElement->m_pParent == nullptr) || (m_pElement->m_pParent == m_pElement->m_pParent->m_pParent)) { m_pElement = nullptr; return; } m_pElement = m_pElement->m_pParent; return; } m_pElement = nullptr; } template <typename KeyType, typename Comparer> template <bool REVERSE> void ezSetBase<KeyType, Comparer>::IteratorBase<REVERSE>::Next() { if constexpr (REVERSE) { Advance(1, 0); } else { Advance(0, 1); } } template <typename KeyType, typename Comparer> template <bool REVERSE> void ezSetBase<KeyType, Comparer>::IteratorBase<REVERSE>::Prev() { if constexpr (REVERSE) { Advance(0, 1); } else { Advance(1, 0); } } // ***** ezSetBase ***** template <typename KeyType, typename Comparer> void ezSetBase<KeyType, Comparer>::Constructor() { m_uiCount = 0; m_NilNode.m_uiLevel = 0; m_NilNode.m_pLink[0] = reinterpret_cast<Node*>(&m_NilNode); m_NilNode.m_pLink[1] = reinterpret_cast<Node*>(&m_NilNode); m_NilNode.m_pParent = reinterpret_cast<Node*>(&m_NilNode); m_pFreeElementStack = nullptr; m_pRoot = reinterpret_cast<Node*>(&m_NilNode); } template <typename KeyType, typename Comparer> ezSetBase<KeyType, Comparer>::ezSetBase(const Comparer& comparer, ezAllocator* pAllocator) : m_Elements(pAllocator) , m_Comparer(comparer) { Constructor(); } template <typename KeyType, typename Comparer> ezSetBase<KeyType, Comparer>::ezSetBase(const ezSetBase<KeyType, Comparer>& cc, ezAllocator* pAllocator) : m_Elements(pAllocator) { Constructor(); operator=(cc); } template <typename KeyType, typename Comparer> ezSetBase<KeyType, Comparer>::~ezSetBase() { Clear(); } template <typename KeyType, typename Comparer> void ezSetBase<KeyType, Comparer>::operator=(const ezSetBase<KeyType, Comparer>& rhs) { Clear(); for (Iterator it = rhs.GetIterator(); it.IsValid(); ++it) Insert(it.Key()); } template <typename KeyType, typename Comparer> void ezSetBase<KeyType, Comparer>::Clear() { for (Iterator it = GetIterator(); it.IsValid(); ++it) ezMemoryUtils::Destruct<Node>(it.m_pElement, 1); m_pFreeElementStack = nullptr; m_Elements.Clear(); m_uiCount = 0; m_NilNode.m_uiLevel = 0; m_NilNode.m_pLink[0] = reinterpret_cast<Node*>(&m_NilNode); m_NilNode.m_pLink[1] = reinterpret_cast<Node*>(&m_NilNode); m_NilNode.m_pParent = reinterpret_cast<Node*>(&m_NilNode); m_pRoot = reinterpret_cast<Node*>(&m_NilNode); } template <typename KeyType, typename Comparer> EZ_ALWAYS_INLINE bool ezSetBase<KeyType, Comparer>::IsEmpty() const { return (m_uiCount == 0); } template <typename KeyType, typename Comparer> EZ_ALWAYS_INLINE ezUInt32 ezSetBase<KeyType, Comparer>::GetCount() const { return m_uiCount; } template <typename KeyType, typename Comparer> EZ_ALWAYS_INLINE typename ezSetBase<KeyType, Comparer>::Iterator ezSetBase<KeyType, Comparer>::GetIterator() const { return Iterator(GetLeftMost()); } template <typename KeyType, typename Comparer> EZ_ALWAYS_INLINE typename ezSetBase<KeyType, Comparer>::ReverseIterator ezSetBase<KeyType, Comparer>::GetReverseIterator() const { return ReverseIterator(GetRightMost()); } template <typename KeyType, typename Comparer> typename ezSetBase<KeyType, Comparer>::Node* ezSetBase<KeyType, Comparer>::GetLeftMost() const { if (IsEmpty()) return nullptr; Node* pNode = m_pRoot; while (pNode->m_pLink[0] != &m_NilNode) pNode = pNode->m_pLink[0]; return pNode; } template <typename KeyType, typename Comparer> typename ezSetBase<KeyType, Comparer>::Node* ezSetBase<KeyType, Comparer>::GetRightMost() const { if (IsEmpty()) return nullptr; Node* pNode = m_pRoot; while (pNode->m_pLink[1] != &m_NilNode) pNode = pNode->m_pLink[1]; return pNode; } template <typename KeyType, typename Comparer> template <typename CompatibleKeyType> typename ezSetBase<KeyType, Comparer>::Node* ezSetBase<KeyType, Comparer>::Internal_Find(const CompatibleKeyType& key) const { Node* pNode = m_pRoot; while (pNode != &m_NilNode) // && (pNode->m_Key != key)) { const ezInt32 dir = (ezInt32)m_Comparer.Less(pNode->m_Key, key); const ezInt32 dir2 = (ezInt32)m_Comparer.Less(key, pNode->m_Key); if (dir == dir2) break; pNode = pNode->m_pLink[dir]; } if (pNode == &m_NilNode) return nullptr; return pNode; } template <typename KeyType, typename Comparer> template <typename CompatibleKeyType> EZ_ALWAYS_INLINE typename ezSetBase<KeyType, Comparer>::Iterator ezSetBase<KeyType, Comparer>::Find(const CompatibleKeyType& key) const { return Iterator(Internal_Find(key)); } template <typename KeyType, typename Comparer> template <typename CompatibleKeyType> EZ_ALWAYS_INLINE bool ezSetBase<KeyType, Comparer>::Contains(const CompatibleKeyType& key) const { return Internal_Find(key) != nullptr; } template <typename KeyType, typename Comparer> EZ_FORCE_INLINE bool ezSetBase<KeyType, Comparer>::ContainsSet(const ezSetBase<KeyType, Comparer>& operand) const { for (const KeyType& key : operand) { if (!Contains(key)) return false; } return true; } template <typename KeyType, typename Comparer> template <typename CompatibleKeyType> typename ezSetBase<KeyType, Comparer>::Node* ezSetBase<KeyType, Comparer>::Internal_LowerBound(const CompatibleKeyType& key) const { Node* pNode = m_pRoot; Node* pNodeSmaller = nullptr; while (pNode != &m_NilNode) { const ezInt32 dir = (ezInt32)m_Comparer.Less(pNode->m_Key, key); const ezInt32 dir2 = (ezInt32)m_Comparer.Less(key, pNode->m_Key); if (dir == dir2) return pNode; if (dir == 0) pNodeSmaller = pNode; pNode = pNode->m_pLink[dir]; } return pNodeSmaller; } template <typename KeyType, typename Comparer> template <typename CompatibleKeyType> EZ_ALWAYS_INLINE typename ezSetBase<KeyType, Comparer>::Iterator ezSetBase<KeyType, Comparer>::LowerBound(const CompatibleKeyType& key) const { return Iterator(Internal_LowerBound(key)); } template <typename KeyType, typename Comparer> template <typename CompatibleKeyType> typename ezSetBase<KeyType, Comparer>::Node* ezSetBase<KeyType, Comparer>::Internal_UpperBound(const CompatibleKeyType& key) const { Node* pNode = m_pRoot; Node* pNodeSmaller = nullptr; while (pNode != &m_NilNode) { const ezInt32 dir = (ezInt32)m_Comparer.Less(pNode->m_Key, key); const ezInt32 dir2 = (ezInt32)m_Comparer.Less(key, pNode->m_Key); if (dir == dir2) { Iterator it(pNode); ++it; return it.m_pElement; } if (dir == 0) pNodeSmaller = pNode; pNode = pNode->m_pLink[dir]; } return pNodeSmaller; } template <typename KeyType, typename Comparer> template <typename CompatibleKeyType> EZ_ALWAYS_INLINE typename ezSetBase<KeyType, Comparer>::Iterator ezSetBase<KeyType, Comparer>::UpperBound(const CompatibleKeyType& key) const { return Iterator(Internal_UpperBound(key)); } template <typename KeyType, typename Comparer> void ezSetBase<KeyType, Comparer>::Union(const ezSetBase<KeyType, Comparer>& operand) { for (const auto& key : operand) { Insert(key); } } template <typename KeyType, typename Comparer> void ezSetBase<KeyType, Comparer>::Difference(const ezSetBase<KeyType, Comparer>& operand) { for (const auto& key : operand) { Remove(key); } } template <typename KeyType, typename Comparer> void ezSetBase<KeyType, Comparer>::Intersection(const ezSetBase<KeyType, Comparer>& operand) { for (auto it = GetIterator(); it.IsValid();) { if (!operand.Contains(it.Key())) it = Remove(it); else ++it; } } template <typename KeyType, typename Comparer> template <typename CompatibleKeyType> typename ezSetBase<KeyType, Comparer>::Iterator ezSetBase<KeyType, Comparer>::Insert(CompatibleKeyType&& key) { Node* pInsertedNode = nullptr; m_pRoot = Insert(m_pRoot, std::forward<CompatibleKeyType>(key), pInsertedNode); m_pRoot->m_pParent = reinterpret_cast<Node*>(&m_NilNode); m_NilNode.m_pParent = reinterpret_cast<Node*>(&m_NilNode); return Iterator(pInsertedNode); } template <typename KeyType, typename Comparer> template <typename CompatibleKeyType> bool ezSetBase<KeyType, Comparer>::Remove(const CompatibleKeyType& key) { bool bRemoved = true; m_pRoot = Remove(m_pRoot, key, bRemoved); m_pRoot->m_pParent = reinterpret_cast<Node*>(&m_NilNode); m_NilNode.m_pParent = reinterpret_cast<Node*>(&m_NilNode); return bRemoved; } template <typename KeyType, typename Comparer> template <typename CompatibleKeyType> typename ezSetBase<KeyType, Comparer>::Node* ezSetBase<KeyType, Comparer>::AcquireNode(CompatibleKeyType&& key, ezUInt16 uiLevel, Node* pParent) { Node* pNode; if (m_pFreeElementStack == nullptr) { m_Elements.PushBack(); pNode = &m_Elements.PeekBack(); } else { pNode = m_pFreeElementStack; m_pFreeElementStack = m_pFreeElementStack->m_pParent; } ezMemoryUtils::Construct<SkipTrivialTypes, Node>(pNode, 1); pNode->m_pParent = pParent; pNode->m_Key = std::forward<CompatibleKeyType>(key); pNode->m_uiLevel = uiLevel; pNode->m_pLink[0] = reinterpret_cast<Node*>(&m_NilNode); pNode->m_pLink[1] = reinterpret_cast<Node*>(&m_NilNode); ++m_uiCount; return pNode; } template <typename KeyType, typename Comparer> void ezSetBase<KeyType, Comparer>::ReleaseNode(Node* pNode) { EZ_ASSERT_DEBUG(pNode != nullptr, "pNode is invalid."); ezMemoryUtils::Destruct<Node>(pNode, 1); // try to reduce the element array, if possible if (pNode == &m_Elements.PeekBack()) { m_Elements.PopBack(); } else if (pNode == &m_Elements.PeekFront()) { m_Elements.PopFront(); } else { pNode->m_pParent = m_pFreeElementStack; m_pFreeElementStack = pNode; } --m_uiCount; } template <typename KeyType, typename Comparer> typename ezSetBase<KeyType, Comparer>::Node* ezSetBase<KeyType, Comparer>::SkewNode(Node* root) { if ((root->m_pLink[0]->m_uiLevel == root->m_uiLevel) && (root->m_uiLevel != 0)) { Node* save = root->m_pLink[0]; root->m_pLink[0] = save->m_pLink[1]; root->m_pLink[0]->m_pParent = root; save->m_pLink[1] = root; save->m_pLink[1]->m_pParent = save; root = save; } return root; } template <typename KeyType, typename Comparer> typename ezSetBase<KeyType, Comparer>::Node* ezSetBase<KeyType, Comparer>::SplitNode(Node* root) { if ((root->m_pLink[1]->m_pLink[1]->m_uiLevel == root->m_uiLevel) && (root->m_uiLevel != 0)) { Node* save = root->m_pLink[1]; root->m_pLink[1] = save->m_pLink[0]; root->m_pLink[1]->m_pParent = root; save->m_pLink[0] = root; save->m_pLink[0]->m_pParent = save; root = save; ++root->m_uiLevel; } return root; } template <typename KeyType, typename Comparer> template <typename CompatibleKeyType> typename ezSetBase<KeyType, Comparer>::Node* ezSetBase<KeyType, Comparer>::Insert(Node* root, CompatibleKeyType&& key, Node*& pInsertedNode) { if (root == &m_NilNode) { pInsertedNode = AcquireNode(std::forward<CompatibleKeyType>(key), 1, reinterpret_cast<Node*>(&m_NilNode)); root = pInsertedNode; } else { Node* it = root; Node* up[STACK_SIZE]; ezInt32 top = 0; ezInt32 dir = 0; while (true) { EZ_ASSERT_DEBUG(top < STACK_SIZE, "ezSetBase's internal stack is not large enough to be able to sort {0} elements.", GetCount()); up[top++] = it; dir = m_Comparer.Less(it->m_Key, key) ? 1 : 0; // element is identical => do not insert if ((ezInt32)m_Comparer.Less(key, it->m_Key) == dir) { pInsertedNode = it; return root; } if (it->m_pLink[dir] == &m_NilNode) break; it = it->m_pLink[dir]; } pInsertedNode = AcquireNode(std::forward<CompatibleKeyType>(key), 1, it); it->m_pLink[dir] = pInsertedNode; while (--top >= 0) { if (top != 0) dir = up[top - 1]->m_pLink[1] == up[top]; up[top] = SkewNode(up[top]); up[top] = SplitNode(up[top]); if (top != 0) { up[top - 1]->m_pLink[dir] = up[top]; up[top - 1]->m_pLink[dir]->m_pParent = up[top - 1]; } else root = up[top]; } } return root; } template <typename KeyType, typename Comparer> template <typename CompatibleKeyType> typename ezSetBase<KeyType, Comparer>::Node* ezSetBase<KeyType, Comparer>::Remove(Node* root, const CompatibleKeyType& key, bool& bRemoved) { bRemoved = false; Node* ToErase = reinterpret_cast<Node*>(&m_NilNode); Node* ToOverride = reinterpret_cast<Node*>(&m_NilNode); if (root != &m_NilNode) { Node* it = root; Node* up[STACK_SIZE]; ezInt32 top = 0; ezInt32 dir = 0; while (true) { EZ_ASSERT_DEBUG(top >= 0 && top < STACK_SIZE, "Implementation error"); up[top++] = it; if (it == &m_NilNode) return root; ezInt32 newdir = (ezInt32)(m_Comparer.Less(it->m_Key, key)); if (newdir == (ezInt32)(m_Comparer.Less(key, it->m_Key))) break; dir = newdir; it = it->m_pLink[dir]; } ToOverride = it; if ((it->m_pLink[0] == &m_NilNode) || (it->m_pLink[1] == &m_NilNode)) { ezInt32 dir2 = it->m_pLink[0] == &m_NilNode; if (--top != 0) { EZ_ASSERT_DEBUG(top >= 1 && top < STACK_SIZE, "Implementation error"); up[top - 1]->m_pLink[dir] = it->m_pLink[dir2]; up[top - 1]->m_pLink[dir]->m_pParent = up[top - 1]; } else root = it->m_pLink[1]; } else { Node* heir = it->m_pLink[1]; Node* prev = it; while (heir->m_pLink[0] != &m_NilNode) { EZ_ASSERT_DEBUG(top >= 0 && top < STACK_SIZE, "Implementation error"); up[top++] = prev = heir; heir = heir->m_pLink[0]; } ToErase = heir; ToOverride = it; prev->m_pLink[prev == it] = heir->m_pLink[1]; prev->m_pLink[prev == it]->m_pParent = prev; } while (--top >= 0) { if (top != 0) { EZ_ASSERT_DEBUG(top >= 1 && top < STACK_SIZE, "Implementation error"); dir = up[top - 1]->m_pLink[1] == up[top]; } EZ_ASSERT_DEBUG(top >= 0 && top < STACK_SIZE, "Implementation error"); if ((up[top]->m_pLink[0]->m_uiLevel < up[top]->m_uiLevel - 1) || (up[top]->m_pLink[1]->m_uiLevel < up[top]->m_uiLevel - 1)) { if (up[top]->m_pLink[1]->m_uiLevel > --up[top]->m_uiLevel) up[top]->m_pLink[1]->m_uiLevel = up[top]->m_uiLevel; up[top] = SkewNode(up[top]); up[top]->m_pLink[1] = SkewNode(up[top]->m_pLink[1]); up[top]->m_pLink[1]->m_pParent = up[top]; up[top]->m_pLink[1]->m_pLink[1] = SkewNode(up[top]->m_pLink[1]->m_pLink[1]); up[top] = SplitNode(up[top]); up[top]->m_pLink[1] = SplitNode(up[top]->m_pLink[1]); up[top]->m_pLink[1]->m_pParent = up[top]; } if (top != 0) { EZ_ASSERT_DEBUG(top >= 1 && top < STACK_SIZE, "Implementation error"); up[top - 1]->m_pLink[dir] = up[top]; up[top - 1]->m_pLink[dir]->m_pParent = up[top - 1]; } else { EZ_ASSERT_DEBUG(top >= 0 && top < STACK_SIZE, "Implementation error"); root = up[top]; } } } root->m_pParent = reinterpret_cast<Node*>(&m_NilNode); // if necessary, swap nodes if (ToErase != &m_NilNode) { Node* parent = ToOverride->m_pParent; if (parent != &m_NilNode) { if (parent->m_pLink[0] == ToOverride) { parent->m_pLink[0] = ToErase; parent->m_pLink[0]->m_pParent = parent; } if (parent->m_pLink[1] == ToOverride) { parent->m_pLink[1] = ToErase; parent->m_pLink[1]->m_pParent = parent; } } else root = ToErase; ToErase->m_uiLevel = ToOverride->m_uiLevel; ToErase->m_pLink[0] = ToOverride->m_pLink[0]; ToErase->m_pLink[0]->m_pParent = ToErase; ToErase->m_pLink[1] = ToOverride->m_pLink[1]; ToErase->m_pLink[1]->m_pParent = ToErase; } // remove the erased node if (ToOverride != &m_NilNode) { bRemoved = true; ReleaseNode(ToOverride); } return root; } template <typename KeyType, typename Comparer> typename ezSetBase<KeyType, Comparer>::Iterator ezSetBase<KeyType, Comparer>::Remove(const Iterator& pos) { EZ_ASSERT_DEBUG(pos.m_pElement != nullptr, "The Iterator(pos) is invalid."); Iterator temp(pos); ++temp; Remove(pos.Key()); return temp; } template <typename KeyType, typename Comparer> bool ezSetBase<KeyType, Comparer>::operator==(const ezSetBase<KeyType, Comparer>& rhs) const { if (GetCount() != rhs.GetCount()) return false; auto itLhs = GetIterator(); auto itRhs = rhs.GetIterator(); while (itLhs.IsValid()) { if (!m_Comparer.Equal(itLhs.Key(), itRhs.Key())) return false; ++itLhs; ++itRhs; } return true; } #undef STACK_SIZE template <typename KeyType, typename Comparer, typename AllocatorWrapper> ezSet<KeyType, Comparer, AllocatorWrapper>::ezSet() : ezSetBase<KeyType, Comparer>(Comparer(), AllocatorWrapper::GetAllocator()) { } template <typename KeyType, typename Comparer, typename AllocatorWrapper> ezSet<KeyType, Comparer, AllocatorWrapper>::ezSet(ezAllocator* pAllocator) : ezSetBase<KeyType, Comparer>(Comparer(), pAllocator) { } template <typename KeyType, typename Comparer, typename AllocatorWrapper> ezSet<KeyType, Comparer, AllocatorWrapper>::ezSet(const Comparer& comparer, ezAllocator* pAllocator) : ezSetBase<KeyType, Comparer>(comparer, pAllocator) { } template <typename KeyType, typename Comparer, typename AllocatorWrapper> ezSet<KeyType, Comparer, AllocatorWrapper>::ezSet(const ezSet<KeyType, Comparer, AllocatorWrapper>& other) : ezSetBase<KeyType, Comparer>(other, AllocatorWrapper::GetAllocator()) { } template <typename KeyType, typename Comparer, typename AllocatorWrapper> ezSet<KeyType, Comparer, AllocatorWrapper>::ezSet(const ezSetBase<KeyType, Comparer>& other) : ezSetBase<KeyType, Comparer>(other, AllocatorWrapper::GetAllocator()) { } template <typename KeyType, typename Comparer, typename AllocatorWrapper> void ezSet<KeyType, Comparer, AllocatorWrapper>::operator=(const ezSet<KeyType, Comparer, AllocatorWrapper>& rhs) { ezSetBase<KeyType, Comparer>::operator=(rhs); } template <typename KeyType, typename Comparer, typename AllocatorWrapper> void ezSet<KeyType, Comparer, AllocatorWrapper>::operator=(const ezSetBase<KeyType, Comparer>& rhs) { ezSetBase<KeyType, Comparer>::operator=(rhs); } template <typename KeyType, typename Comparer> void ezSetBase<KeyType, Comparer>::Swap(ezSetBase<KeyType, Comparer>& other) { SwapNilNode(this->m_pRoot, &this->m_NilNode, &other.m_NilNode); SwapNilNode(other.m_pRoot, &other.m_NilNode, &this->m_NilNode); ezMath::Swap(this->m_pRoot, other.m_pRoot); ezMath::Swap(this->m_uiCount, other.m_uiCount); ezMath::Swap(this->m_pFreeElementStack, other.m_pFreeElementStack); ezMath::Swap(this->m_Comparer, other.m_Comparer); // after we swapped the root nodes, fix up their parent nodes this->m_pRoot->m_pParent = reinterpret_cast<Node*>(&this->m_NilNode); other.m_pRoot->m_pParent = reinterpret_cast<Node*>(&other.m_NilNode); // the set allocator is stored in this array m_Elements.Swap(other.m_Elements); } template <typename KeyType, typename Comparer> void ezSetBase<KeyType, Comparer>::SwapNilNode(Node*& pCurNode, NilNode* pOld, NilNode* pNew) { if (pCurNode == pOld) { pCurNode = reinterpret_cast<Node*>(pNew); return; } SwapNilNode(pCurNode->m_pLink[0], pOld, pNew); SwapNilNode(pCurNode->m_pLink[1], pOld, pNew); }