text: /*=========================================================================
   *
   *  Copyright Insight Software Consortium
   *
   *  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 itkWatershedSegmentTree_h
  #define itkWatershedSegmentTree_h
  
  #include "itkProcessObject.h"
  #include <deque>
  #include <functional>
  
  namespace itk
  {
  namespace watershed
  {
  /** \class SegmentTree
   * A data structure for storing segment merge information used in filters of
   * the watershed segmentation algorithm.  See itk::WatershedImageFilter for an
   * overview.
   *
   * \par
   * This class is the implementation of the "merge tree" referred to in the
   * documentation for itk::WatershedImageFilter and other watershed segmentation
   * component classes.  It holds a list of merges among image segments at
   * various saliency levels. The list is actually a representation of a binary
   * tree, whose nodes are segments and edges are saliencies.
   *
   * \ingroup WatershedSegmentation
   * \sa itk::WatershedImageFilter
   *
   * \ingroup ITKWatersheds
   */
  template< typename TScalar >
  class ITK_TEMPLATE_EXPORT SegmentTree:public DataObject
  {
  public:
    /** Define itk Smart Pointers for this object */
    using Self = SegmentTree;
    using Superclass = DataObject;
    using Pointer = SmartPointer< Self >;
    using ConstPointer = SmartPointer< const Self >;
    itkNewMacro(Self);
    itkTypeMacro(WatershedSegmentTree, DataObject);
    using ScalarType = TScalar;
  
    /** Elements of the list (nodes of the tree).  A record of a merge
     * between two segments (IdentifierType labels) at a particular
     * saliency.   */
    struct merge_t {
      IdentifierType from;
      IdentifierType to;
      ScalarType saliency;
    };
  
    /** Define the container type used in this list data structure */
    using DequeType = std::deque< merge_t >;
    using Iterator = typename DequeType::iterator;
    using ConstIterator = typename DequeType::const_iterator;
    using ValueType = typename DequeType::value_type;
  
    /** Boolean comparison functor for use in sorting functions.  */
    struct merge_comp:public std:: binary_function< bool, const merge_t &,
                                                    const merge_t & > {
      merge_comp() = default;
      bool operator()(const merge_t & a, const merge_t & b)
      {
        return b.saliency < a.saliency;
      }
    };
  
    /** Boolean comparison functor for use in sorting functions.   */
    struct sort_comp:public std:: binary_function< bool, const merge_t &,
                                                   const merge_t & > {
      bool operator()(const merge_t & a, const merge_t & b)
      {
        return a.saliency < b.Saliency;
      }
    };
  
    /** Returns the size of the list.   */
    typename DequeType::size_type Size() const
    { return m_Deque.size(); }
  
    /** Returns TRUE if the SegmentTree is empty, FALSE if the SegmentTree is not
     * empty.    */
    bool Empty() const
    { return m_Deque.empty();    }
  
    /** Returns a const reference to the front of the list (node with the least
     * saliency value).    */
    const merge_t & Front() const
    { return m_Deque.front(); }
  
    /** Returns a const reference to the back of the list (node with the greatest
     * saliency value).   */
    const merge_t & Back() const
    { return m_Deque.back(); }
  
    /** Returns a reference to the front of the list   */
    merge_t & Front()
    { return m_Deque.front(); }
  
    /** Returns a reference to the back of the list   */
    merge_t & Back()
    { return m_Deque.back(); }
  
    /** Inserts a node at the front of the list.   */
    void PushFront(const ValueType & t)
    { m_Deque.push_front(t); }
  
    /** Inserts a node at the back of the list   */
    void PushBack(const ValueType & t)
    { m_Deque.push_back(t); }
  
    /** Erases the node at the front of the list.   */
    void PopFront()
    { m_Deque.pop_front(); }
  
    /** Erases the node at the back of the list.   */
    void PopBack()
    { m_Deque.pop_back(); }
  
    /** Returns an iterator pointing to the first element in the list.   */
    Iterator Begin()
    { return m_Deque.begin(); }
  
    /** Returns a const iterator pointing to the first element in the list. */
    ConstIterator Begin() const
    { return m_Deque.begin(); }
  
    /** Returns an iterator pointing one element past the last element in the
     * list.    */
    Iterator End()
    { return m_Deque.end(); }
  
    /** Returns a const iterator pointing one element past the last element in the
     * list.    */
    ConstIterator End() const
    { return m_Deque.end(); }
  
    /** Clears the Deque completely */
    void Clear()
    { m_Deque.clear(); }
  
    /** Standard DataObject routine to initialize.  Returns the segment
     * tree to a default state, deallocating memory. */
    void Initialize() override;
  
  protected:
    SegmentTree() = default;
    ~SegmentTree() override = default;
    SegmentTree(const Self &) {}
    void operator=(const Self &) {}
    void PrintSelf(std::ostream & os, Indent indent) const override;
  
    DequeType m_Deque;
  };
  } // end namespace watershed
  } // end namespace itk
  
  #ifndef ITK_MANUAL_INSTANTIATION
  #include "itkWatershedSegmentTree.hxx"
  #endif
  
  #endif
  