/*========================================================================= * * Copyright NumFOCUS * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * https://www.apache.org/licenses/LICENSE-2.0.txt * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. * *=========================================================================*/ #ifndef itkPriorityQueueContainer_hxx #define itkPriorityQueueContainer_hxx #include #include "itkNumericTraits.h" namespace itk { // ----------------------------------------------------------------------------- template const typename ElementWrapperInterface::ElementIdentifierType ElementWrapperInterface::m_ElementNotFound = NumericTraits::max(); // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template auto ElementWrapperPointerInterface::GetLocation( const ElementWrapperPointerType & element) const -> ElementIdentifierType { return (element->GetLocation(*element)); } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template void ElementWrapperPointerInterface::SetLocation( ElementWrapperPointerType & element, const ElementIdentifierType & identifier) { element->SetLocation(*element, identifier); } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template bool ElementWrapperPointerInterface::is_less( const ElementWrapperPointerType & element1, const ElementWrapperPointerType & element2) const { return (element1->is_less((*element1), (*element2))); } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template bool ElementWrapperPointerInterface::is_greater( const ElementWrapperPointerType & element1, const ElementWrapperPointerType & element2) const { return (element1->is_greater((*element1), (*element2))); } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template const TElementIdentifier ElementWrapperPointerInterface::m_ElementNotFound = NumericTraits::max(); // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template MinPriorityQueueElementWrapper::MinPriorityQueueElementWrapper( ElementType element, ElementPriorityType priority) : m_Element(element) , m_Priority(std::move(priority)) , m_Location(Superclass::m_ElementNotFound) {} // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template bool MinPriorityQueueElementWrapper::operator>( const MinPriorityQueueElementWrapper & other) const { return this->m_Priority > other.m_Priority; } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template bool MinPriorityQueueElementWrapper::operator<( const MinPriorityQueueElementWrapper & other) const { return this->m_Priority < other.m_Priority; } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template bool MinPriorityQueueElementWrapper::operator==( const MinPriorityQueueElementWrapper & other) const { return this->m_Priority == other.m_Priority; } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template auto MinPriorityQueueElementWrapper::GetLocation( const MinPriorityQueueElementWrapper & element) const -> ElementIdentifierType { return element.m_Location; } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template void MinPriorityQueueElementWrapper::SetLocation( MinPriorityQueueElementWrapper & element, const ElementIdentifierType & identifier) { element.m_Location = identifier; } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template bool MinPriorityQueueElementWrapper::is_less( const MinPriorityQueueElementWrapper & element1, const MinPriorityQueueElementWrapper & element2) const { return (element1 < element2); } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template bool MinPriorityQueueElementWrapper::is_greater( const MinPriorityQueueElementWrapper & element1, const MinPriorityQueueElementWrapper & element2) const { return (element1 > element2); } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- // MaxPriorityQueueElementWrapper // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template MaxPriorityQueueElementWrapper::MaxPriorityQueueElementWrapper( ElementType element, ElementPriorityType priority) : Superclass(element, priority) {} // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template bool MaxPriorityQueueElementWrapper::is_less( const MaxPriorityQueueElementWrapper & element1, const MaxPriorityQueueElementWrapper & element2) const { return (element1 > element2); } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template bool MaxPriorityQueueElementWrapper::is_less( const Superclass & element1, const Superclass & element2) const { return Superclass::is_less(element1, element2); } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template bool MaxPriorityQueueElementWrapper::is_greater( const MaxPriorityQueueElementWrapper & element1, const MaxPriorityQueueElementWrapper & element2) const { return (element1 < element2); } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template bool MaxPriorityQueueElementWrapper::is_greater( const Superclass & element1, const Superclass & element2) const { return Superclass::is_greater(element1, element2); } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- // PriorityQueueContainer // ----------------------------------------------------------------------------- template const TElementIdentifier PriorityQueueContainer:: m_ElementNotFound = NumericTraits::max(); // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template void PriorityQueueContainer::Clear() { this->Initialize(); } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template bool PriorityQueueContainer::Empty() const { return (this->empty()); } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template void PriorityQueueContainer::Push( ElementWrapperType element) { this->push_back(element); this->UpdateUpTree(this->Size() - 1); } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template const typename PriorityQueueContainer:: ElementWrapperType & PriorityQueueContainer::Peek() const { if (Empty()) { itkGenericExceptionMacro("Empty PriorityQueueContainer"); } return (GetElementAtLocation(0)); } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template void PriorityQueueContainer::Pop() { m_Interface.SetLocation(this->front(), // GetElementAtLocation(0), m_ElementNotFound); if (this->Size() > 1) { SetElementAtLocation(0, this->back()); // GetElementAtLocation( this->Size() - 1 ) ); this->pop_back(); UpdateDownTree(0); } else { if (this->Size() == 1) { this->pop_back(); } } } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template bool PriorityQueueContainer::Update( const ElementWrapperType & element) { ElementIdentifierType location = m_Interface.GetLocation(element); if (location != m_ElementNotFound) { if (location >= this->Size()) { itkGenericExceptionMacro(" ElementWrapperType location is out of range"); } UpdateDownTree(location); UpdateUpTree(location); return true; } return false; } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template bool PriorityQueueContainer::DeleteElement( const ElementWrapperType & element) { ElementIdentifierType location = m_Interface.GetLocation(element); if (location != m_ElementNotFound) { // m_Interface.SetLocation(element, m_ElementNotFound); ElementIdentifierType tsize = this->Size(); if (location >= tsize) { itkGenericExceptionMacro(" ElementWrapperType location is out of range"); } else { if (location == tsize - 1) { this->pop_back(); } else { SetElementAtLocation(location, GetElementAtLocation(tsize - 1)); this->pop_back(); UpdateDownTree(location); UpdateUpTree(location); } } return true; } return false; } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template void PriorityQueueContainer::UpdateUpTree( const ElementIdentifierType & identifier) { if (HasParent(identifier)) { ElementIdentifierType id(identifier); ElementWrapperType element = GetElementAtLocation(id); ElementIdentifierType parentIdentifier = GetParent(id); ElementWrapperType parent_element = GetElementAtLocation(parentIdentifier); while (HasParent(id) && m_Interface.is_less(element, parent_element)) { SetElementAtLocation(id, parent_element); id = parentIdentifier; if (HasParent(id)) { parentIdentifier = GetParent(id); parent_element = GetElementAtLocation(parentIdentifier); } } SetElementAtLocation(id, element); } } // ----------------------------------------------------------------------------- // ----------------------------------------------------------------------------- template void PriorityQueueContainer::UpdateDownTree( const ElementIdentifierType & identifier) { ElementIdentifierType id(identifier); ElementWrapperType element = GetElementAtLocation(id); ElementIdentifierType queueSize = this->Size(); while (id < queueSize) { ElementIdentifierType childIdentifier = GetLeft(id); if (childIdentifier >= queueSize) { break; } if ((childIdentifier + 1 < queueSize) && (m_Interface.is_less(GetElementAtLocation(childIdentifier + 1), GetElementAtLocation(childIdentifier)))) { ++childIdentifier; } ElementWrapperType temp = GetElementAtLocation(childIdentifier); if (m_Interface.is_less(element, temp)) { break; } SetElementAtLocation(id, temp); id = childIdentifier; } SetElementAtLocation(id, element); } // ----------------------------------------------------------------------------- } // namespace itk #endif // itkPriorityQueueContainer_hxx