[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]
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) |
html generated using doxygen and Python
|