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 itkWatershedSegmentTable_h
  #define itkWatershedSegmentTable_h
  
  
  #include "itkDataObject.h"
  #include <list>
  #include "itkOneWayEquivalencyTable.h"
  
  namespace itk
  {
  namespace watershed
  {
  /** \class SegmentTable
   * A table for storing segmentation information in various component filters of
   * the watershed segmentation algorithm.  See itk::WatershedImageFilter for an
   * overview.
   *
   * \par
   * This is a hash table that holds information about labeled segments in an
   * image.  Keys in the table are label values (IdentifierType). Each entry in
   * the table records the minimum value in the segment region and a list of all the
   * adjacent segments in the image.  The adjacency (edge) list also holds a
   * saliency value (likelihood of merge) for each adjacency.
   *
   * \ingroup WatershedSegmentation
   * \sa itk::WatershedImageFilter
   * \ingroup ITKWatersheds
   */
  template< typename TScalar >
  class SegmentTable:public DataObject
  {
  public:
    /** Define smart pointers for this object */
    typedef SegmentTable               Self;
    typedef DataObject                 Superclass;
    typedef SmartPointer< Self >       Pointer;
    typedef SmartPointer< const Self > ConstPointer;
    typedef TScalar                    ScalarType;
  
    itkNewMacro(Self);
    itkTypeMacro(WatershedSegmentTable, DataObject);
  
    /** The value type for lists of adjacencies contained in each table
        entry */
    struct edge_pair_t {
      edge_pair_t() {}
      edge_pair_t(IdentifierType l, ScalarType s):label(l), height(s) {}
      IdentifierType label;
      ScalarType height;
  
      /** Necessary operator for sorting the adjacency lists */
      bool operator<(const edge_pair_t & o) const
      {
        if ( this->height < o.height )
          {
          return true;
          }
        else
          {
          return false;
          }
      }
    };
  
    /** Structure for storing lists of adjacencies (edges) and their
        saliencies. */
    typedef std::list< edge_pair_t > edge_list_t;
  
    /** Structure holding information about each segment in an image. */
    struct segment_t {
      ScalarType min;
      edge_list_t edge_list;
    };
  
    /** Define the container type for the table */
    typedef itksys::hash_map< IdentifierType, segment_t,
      itksys::hash< IdentifierType > >           HashMapType;
    typedef typename HashMapType::iterator       Iterator;
    typedef typename HashMapType::const_iterator ConstIterator;
    typedef typename HashMapType::value_type     ValueType;
    typedef typename HashMapType::data_type      DataType;
  
    /** Inserts a segment into the table  */
    bool Add(IdentifierType a, const segment_t & t);
  
    /** Iterates through the table and removes edges
     * in every edge list whose saliencies are above the
     * specified maximum.  Requires that the edge lists
     * have been sorted prior to calling this method.   */
    void PruneEdgeLists(ScalarType maximum_saliency);
  
    /** Lookup a segment in the table.  Returns a pointer to the
     * entry.  On failure, returns a null pointer.   */
    segment_t * Lookup(const IdentifierType a)
    {
      Iterator result = m_HashMap.find(a);
  
      if ( result == m_HashMap.end() ) { return ITK_NULLPTR; }
      else { return &( ( *result ).second ); }
    }
  
    /** Lookup a segment in the table.  Returns a const pointer
     * to the entry.  On failure, returns a null pointer.   */
    const segment_t * Lookup(const IdentifierType a) const
    {
      ConstIterator result = m_HashMap.find(a);
  
      if ( result == m_HashMap.end() ) { return 0; }
      else { return &( ( *result ).second ); }
    }
  
    /** Returns TRUE if the entry key is found in the table.  FALSE if the key is
     * not found in the table.   */
    bool IsEntry(const IdentifierType a) const
    {
      if ( m_HashMap.find(a) == m_HashMap.end() ) { return false; }
      else { return true; }
    }
  
    /** Deletes an entry from the table.   */
    void Erase(const IdentifierType a)
    {  m_HashMap.erase(a); }
  
    /** Removes all the entries in the table.   */
    void Clear()
    {      m_HashMap.clear();    }
  
    /** Returns true if the table is empty and false if the table is not empty.
     */
    bool Empty() const
    {      return m_HashMap.empty();    }
  
    /** Sorts all the entries in the edge lists from least to greatest saliency.
     */
    void SortEdgeLists();
  
    /** Returns the number of entries in the table.   */
    typename HashMapType::size_type  Size() const
    {      return m_HashMap.size();     }
  
    /** Merges two entries of the table.  from->to  */
    //  void Merge(const IdentifierType from, const IdentifierType to);
  
    /** Returns an iterator pointing to the first element in the (unordered)
        table. */
    Iterator Begin() { return m_HashMap.begin(); }
  
    /** Returns an iterator pointing to one element past the last element in the
     * (unordered table).   */
    Iterator End()   { return m_HashMap.end();   }
  
    /** Returns a const iterator pointing to the first element in the (unordered)
     * table.  */
    ConstIterator Begin() const { return m_HashMap.begin(); }
  
    /** Returns a const iterator pointing to one element past the last element in
     * the  (unordered table).   */
    ConstIterator End()   const { return m_HashMap.end();   }
  
    /** Convenience methods for debugging   */
    unsigned int GetSegmentMemorySize() const
    {
      return sizeof( segment_t );
    }
  
    //  void PrintHashTable() const;
  
    /** Set/Get the maximum depth of image on which this segment table is based.
     * (Should set really be calling modified? jc 11/16/01) */
    void SetMaximumDepth(ScalarType s)
    {
      m_MaximumDepth = s;
      this->Modified();
    }
  
    ScalarType GetMaximumDepth() const
    { return m_MaximumDepth; }
  
    /** Copies the contents of another segment table into this segment table.
        This is really operator= in disguise, although superclass information is
        not copied. */
    void Copy(const Self & o)
    {
      m_HashMap = o.m_HashMap;
      m_MaximumDepth = o.m_MaximumDepth;
    }
  
  protected:
    SegmentTable() :
      m_MaximumDepth(0)
    {}
    virtual ~SegmentTable() {}
  
    HashMapType m_HashMap;
  
    ScalarType m_MaximumDepth;
  
  private:
    void operator=(const Self &) {}
  };
  } // end namespace watershed
  } // end namespace itk
  
  #ifndef ITK_MANUAL_INSTANTIATION
  #include "itkWatershedSegmentTable.hxx"
  #endif
  
  #endif
  