[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

vigra/union_find.hxx
00001 /************************************************************************/
00002 /*                                                                      */
00003 /*               Copyright 2008-2009 by Ullrich Koethe                  */
00004 /*                                                                      */
00005 /*    This file is part of the VIGRA computer vision library.           */
00006 /*    The VIGRA Website is                                              */
00007 /*        http://hci.iwr.uni-heidelberg.de/vigra/                       */
00008 /*    Please direct questions, bug reports, and contributions to        */
00009 /*        ullrich.koethe@iwr.uni-heidelberg.de    or                    */
00010 /*        vigra@informatik.uni-hamburg.de                               */
00011 /*                                                                      */
00012 /*    Permission is hereby granted, free of charge, to any person       */
00013 /*    obtaining a copy of this software and associated documentation    */
00014 /*    files (the "Software"), to deal in the Software without           */
00015 /*    restriction, including without limitation the rights to use,      */
00016 /*    copy, modify, merge, publish, distribute, sublicense, and/or      */
00017 /*    sell copies of the Software, and to permit persons to whom the    */
00018 /*    Software is furnished to do so, subject to the following          */
00019 /*    conditions:                                                       */
00020 /*                                                                      */
00021 /*    The above copyright notice and this permission notice shall be    */
00022 /*    included in all copies or substantial portions of the             */
00023 /*    Software.                                                         */
00024 /*                                                                      */
00025 /*    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND    */
00026 /*    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES   */
00027 /*    OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND          */
00028 /*    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT       */
00029 /*    HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,      */
00030 /*    WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING      */
00031 /*    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR     */
00032 /*    OTHER DEALINGS IN THE SOFTWARE.                                   */
00033 /*                                                                      */
00034 /************************************************************************/
00035 
00036 
00037 #ifndef VIGRA_UNION_FIND_HXX
00038 #define VIGRA_UNION_FIND_HXX
00039 
00040 #include "config.hxx"
00041 #include "error.hxx"
00042 #include "array_vector.hxx"
00043 
00044 namespace vigra {
00045 
00046 namespace detail {
00047 
00048 template <class T>
00049 class UnionFindArray
00050 {
00051     typedef typename ArrayVector<T>::difference_type IndexType;
00052     mutable ArrayVector<T> labels_;
00053     
00054   public:
00055     UnionFindArray(T next_free_label = 1)
00056     {
00057         for(T k=0; k <= next_free_label; ++k)
00058             labels_.push_back(k);
00059     }
00060     
00061     T nextFreeLabel() const
00062     {
00063         return labels_.back();
00064     }
00065     
00066     T find(T label) const
00067     {
00068         T root = label;
00069         while(root != labels_[(IndexType)root])
00070             root = labels_[(IndexType)root];
00071         // path compression
00072         while(label != root)
00073         {
00074             T next = labels_[(IndexType)label];
00075             labels_[(IndexType)label] = root;
00076             label = next;
00077         }
00078         return root;
00079     } 
00080     
00081     T makeUnion(T l1, T l2)
00082     {
00083         l1 = find(l1);
00084         l2 = find(l2);
00085         if(l1 <= l2)
00086         {
00087             labels_[(IndexType)l2] = l1;
00088             return l1;
00089         }
00090         else
00091         {
00092             labels_[(IndexType)l1] = l2;
00093             return l2;
00094         }
00095     }
00096     
00097     T finalizeLabel(T label)
00098     {
00099         if(label == (T)labels_.size()-1)
00100         {
00101             // indeed a new region
00102             vigra_invariant(label < NumericTraits<T>::max(),
00103                     "connected components: Need more labels than can be represented in the destination type.");
00104             // create new back entry
00105             labels_.push_back((T)labels_.size());
00106         }
00107         else
00108         {
00109             // no new label => reset the back entry of the label array
00110             labels_.back() = (T)labels_.size()-1;
00111         }
00112         return label;
00113     }
00114     
00115     T makeNewLabel() 
00116     {
00117         T label = labels_.back();
00118         vigra_invariant(label < NumericTraits<T>::max(),
00119           "connected components: Need more labels than can be represented in the destination type.");
00120         labels_.push_back((T)labels_.size());
00121         return label;
00122     }
00123     
00124     unsigned int makeContiguous()
00125     {
00126         // compress trees
00127         unsigned int count = 0; 
00128         for(IndexType i=0; i<(IndexType)(labels_.size()-1); ++i)
00129         {
00130             if(labels_[i] == i)
00131             {
00132                     labels_[i] = (T)count++;
00133             }
00134             else
00135             {
00136                     labels_[i] = labels_[(IndexType)labels_[i]]; 
00137             }
00138         }
00139         return count-1;   
00140     }
00141     
00142     T operator[](T label) const
00143     {
00144         return labels_[(IndexType)label];
00145     }
00146 };
00147 
00148 } // namespace detail
00149 
00150 } // namespace vigra
00151 
00152 #endif // VIGRA_UNION_FIND_HXX

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de)
Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany

html generated using doxygen and Python
vigra 1.7.0 (Thu Aug 25 2011)