/*=========================================================================
 *
 *  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
 *
 *         http://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 <utility>

#include "itkNumericTraits.h"
#include "itkPriorityQueueContainer.h"

namespace itk
{

// -----------------------------------------------------------------------------
template <typename TElement, typename TElementIdentifier>
const typename ElementWrapperInterface<TElement, TElementIdentifier>::ElementIdentifierType
  ElementWrapperInterface<TElement, TElementIdentifier>::m_ElementNotFound = NumericTraits<TElementIdentifier>::max();
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
template <typename TElementWrapperPointer, typename TElementIdentifier>
typename ElementWrapperPointerInterface<TElementWrapperPointer, TElementIdentifier>::ElementIdentifierType
ElementWrapperPointerInterface<TElementWrapperPointer, TElementIdentifier>::GetLocation(
  const ElementWrapperPointerType & element) const
{
  return ((*element).GetLocation(*element));
}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElementWrapperPointer, typename TElementIdentifier>
void
ElementWrapperPointerInterface<TElementWrapperPointer, TElementIdentifier>::SetLocation(
  ElementWrapperPointerType &   element,
  const ElementIdentifierType & identifier)
{
  (*element).SetLocation(*element, identifier);
}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElementWrapperPointer, typename TElementIdentifier>
bool
ElementWrapperPointerInterface<TElementWrapperPointer, TElementIdentifier>::is_less(
  const ElementWrapperPointerType & element1,
  const ElementWrapperPointerType & element2) const
{
  return ((*element1).is_less((*element1), (*element2)));
}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElementWrapperPointer, typename TElementIdentifier>
bool
ElementWrapperPointerInterface<TElementWrapperPointer, TElementIdentifier>::is_greater(
  const ElementWrapperPointerType & element1,
  const ElementWrapperPointerType & element2) const
{
  return ((*element1).is_greater((*element1), (*element2)));
}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElement, typename TElementIdentifier>
const TElementIdentifier ElementWrapperPointerInterface<TElement, TElementIdentifier>::m_ElementNotFound =
  NumericTraits<TElementIdentifier>::max();
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------


// -----------------------------------------------------------------------------
// MinPriorityQueueElementWrapper
// -----------------------------------------------------------------------------
template <typename TElement, typename TElementPriority, typename TElementIdentifier>
MinPriorityQueueElementWrapper<TElement, TElementPriority, TElementIdentifier>::MinPriorityQueueElementWrapper()
  : m_Element(0)
  , m_Priority(0)
  , m_Location(Superclass::m_ElementNotFound)
{}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElement, typename TElementPriority, typename TElementIdentifier>
MinPriorityQueueElementWrapper<TElement, TElementPriority, TElementIdentifier>::MinPriorityQueueElementWrapper(
  ElementType         element,
  ElementPriorityType priority)
  : m_Element(element)
  , m_Priority(std::move(priority))
  , m_Location(Superclass::m_ElementNotFound)
{}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElement, typename TElementPriority, typename TElementIdentifier>
bool
MinPriorityQueueElementWrapper<TElement, TElementPriority, TElementIdentifier>::operator>(
  const MinPriorityQueueElementWrapper & other) const
{
  return this->m_Priority > other.m_Priority;
}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElement, typename TElementPriority, typename TElementIdentifier>
bool
MinPriorityQueueElementWrapper<TElement, TElementPriority, TElementIdentifier>::operator<(
  const MinPriorityQueueElementWrapper & other) const
{
  return this->m_Priority < other.m_Priority;
}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElement, typename TElementPriority, typename TElementIdentifier>
bool
MinPriorityQueueElementWrapper<TElement, TElementPriority, TElementIdentifier>::operator==(
  const MinPriorityQueueElementWrapper & other) const
{
  return this->m_Priority == other.m_Priority;
}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElement, typename TElementPriority, typename TElementIdentifier>
typename MinPriorityQueueElementWrapper<TElement, TElementPriority, TElementIdentifier>::ElementIdentifierType
MinPriorityQueueElementWrapper<TElement, TElementPriority, TElementIdentifier>::GetLocation(
  const MinPriorityQueueElementWrapper & element) const
{
  return element.m_Location;
}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElement, typename TElementPriority, typename TElementIdentifier>
void
MinPriorityQueueElementWrapper<TElement, TElementPriority, TElementIdentifier>::SetLocation(
  MinPriorityQueueElementWrapper & element,
  const ElementIdentifierType &    identifier)
{
  element.m_Location = identifier;
}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElement, typename TElementPriority, typename TElementIdentifier>
bool
MinPriorityQueueElementWrapper<TElement, TElementPriority, TElementIdentifier>::is_less(
  const MinPriorityQueueElementWrapper & element1,
  const MinPriorityQueueElementWrapper & element2) const
{
  return (element1 < element2);
}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElement, typename TElementPriority, typename TElementIdentifier>
bool
MinPriorityQueueElementWrapper<TElement, TElementPriority, TElementIdentifier>::is_greater(
  const MinPriorityQueueElementWrapper & element1,
  const MinPriorityQueueElementWrapper & element2) const
{
  return (element1 > element2);
}
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------


// -----------------------------------------------------------------------------
// MaxPriorityQueueElementWrapper
// -----------------------------------------------------------------------------
template <typename TElement, typename TElementPriority, typename TElementIdentifier>
MaxPriorityQueueElementWrapper<TElement, TElementPriority, TElementIdentifier>::MaxPriorityQueueElementWrapper()
  : Superclass()
{}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElement, typename TElementPriority, typename TElementIdentifier>
MaxPriorityQueueElementWrapper<TElement, TElementPriority, TElementIdentifier>::MaxPriorityQueueElementWrapper(
  ElementType         element,
  ElementPriorityType priority)
  : Superclass(element, priority)
{}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElement, typename TElementPriority, typename TElementIdentifier>
bool
MaxPriorityQueueElementWrapper<TElement, TElementPriority, TElementIdentifier>::is_less(
  const MaxPriorityQueueElementWrapper & element1,
  const MaxPriorityQueueElementWrapper & element2) const
{
  return (element1 > element2);
}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElement, typename TElementPriority, typename TElementIdentifier>
bool
MaxPriorityQueueElementWrapper<TElement, TElementPriority, TElementIdentifier>::is_less(
  const Superclass & element1,
  const Superclass & element2) const
{
  return Superclass::is_less(element1, element2);
}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElement, typename TElementPriority, typename TElementIdentifier>
bool
MaxPriorityQueueElementWrapper<TElement, TElementPriority, TElementIdentifier>::is_greater(
  const MaxPriorityQueueElementWrapper & element1,
  const MaxPriorityQueueElementWrapper & element2) const
{
  return (element1 < element2);
}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElement, typename TElementPriority, typename TElementIdentifier>
bool
MaxPriorityQueueElementWrapper<TElement, TElementPriority, TElementIdentifier>::is_greater(
  const Superclass & element1,
  const Superclass & element2) const
{
  return Superclass::is_greater(element1, element2);
}
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------


// -----------------------------------------------------------------------------
// PriorityQueueContainer
// -----------------------------------------------------------------------------
template <typename TElementWrapper,
          typename TElementWrapperInterface,
          typename TElementPriority,
          typename TElementIdentifier>
const TElementIdentifier
  PriorityQueueContainer<TElementWrapper, TElementWrapperInterface, TElementPriority, TElementIdentifier>::
    m_ElementNotFound = NumericTraits<TElementIdentifier>::max();
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElementWrapper,
          typename TElementWrapperInterface,
          typename TElementPriority,
          typename TElementIdentifier>
PriorityQueueContainer<TElementWrapper, TElementWrapperInterface, TElementPriority, TElementIdentifier>::
  PriorityQueueContainer()
  : Superclass()
{}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElementWrapper,
          typename TElementWrapperInterface,
          typename TElementPriority,
          typename TElementIdentifier>
void
PriorityQueueContainer<TElementWrapper, TElementWrapperInterface, TElementPriority, TElementIdentifier>::Clear()
{
  this->Initialize();
}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElementWrapper,
          typename TElementWrapperInterface,
          typename TElementPriority,
          typename TElementIdentifier>
bool
PriorityQueueContainer<TElementWrapper, TElementWrapperInterface, TElementPriority, TElementIdentifier>::Empty() const
{
  return (this->empty());
}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElementWrapper,
          typename TElementWrapperInterface,
          typename TElementPriority,
          typename TElementIdentifier>
void
PriorityQueueContainer<TElementWrapper, TElementWrapperInterface, TElementPriority, TElementIdentifier>::Push(
  ElementWrapperType element)
{
  this->push_back(element);
  this->UpdateUpTree(this->Size() - 1);
}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElementWrapper,
          typename TElementWrapperInterface,
          typename TElementPriority,
          typename TElementIdentifier>
const typename PriorityQueueContainer<TElementWrapper, TElementWrapperInterface, TElementPriority, TElementIdentifier>::
  ElementWrapperType &
  PriorityQueueContainer<TElementWrapper, TElementWrapperInterface, TElementPriority, TElementIdentifier>::Peek() const
{
  if (Empty())
  {
    itkGenericExceptionMacro(<< "Empty PriorityQueueContainer");
  }
  return (GetElementAtLocation(0));
}
// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
template <typename TElementWrapper,
          typename TElementWrapperInterface,
          typename TElementPriority,
          typename TElementIdentifier>
void
PriorityQueueContainer<TElementWrapper, TElementWrapperInterface, TElementPriority, TElementIdentifier>::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 <typename TElementWrapper,
          typename TElementWrapperInterface,
          typename TElementPriority,
          typename TElementIdentifier>
bool
PriorityQueueContainer<TElementWrapper, TElementWrapperInterface, TElementPriority, TElementIdentifier>::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 <typename TElementWrapper,
          typename TElementWrapperInterface,
          typename TElementPriority,
          typename TElementIdentifier>
bool
PriorityQueueContainer<TElementWrapper, TElementWrapperInterface, TElementPriority, TElementIdentifier>::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 <typename TElementWrapper,
          typename TElementWrapperInterface,
          typename TElementPriority,
          typename TElementIdentifier>
void
PriorityQueueContainer<TElementWrapper, TElementWrapperInterface, TElementPriority, TElementIdentifier>::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 <typename TElementWrapper,
          typename TElementWrapperInterface,
          typename TElementPriority,
          typename TElementIdentifier>
void
PriorityQueueContainer<TElementWrapper, TElementWrapperInterface, TElementPriority, TElementIdentifier>::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
