37 #ifndef VIGRA_UNION_FIND_HXX
38 #define VIGRA_UNION_FIND_HXX
42 #include "array_vector.hxx"
51 typedef typename ArrayVector<T>::difference_type IndexType;
52 mutable ArrayVector<T> labels_;
55 UnionFindArray(T next_free_label = 1)
57 for(T k=0; k <= next_free_label; ++k)
61 T nextFreeLabel()
const
63 return labels_.back();
69 while(root != labels_[(IndexType)root])
70 root = labels_[(IndexType)root];
74 T next = labels_[(IndexType)label];
75 labels_[(IndexType)label] = root;
81 T makeUnion(T l1, T l2)
87 labels_[(IndexType)l2] = l1;
92 labels_[(IndexType)l1] = l2;
97 T finalizeLabel(T label)
99 if(label == (T)labels_.size()-1)
102 vigra_invariant(label < NumericTraits<T>::max(),
103 "connected components: Need more labels than can be represented in the destination type.");
105 labels_.push_back((T)labels_.size());
110 labels_.back() = (T)labels_.size()-1;
117 T label = labels_.back();
118 vigra_invariant(label < NumericTraits<T>::max(),
119 "connected components: Need more labels than can be represented in the destination type.");
120 labels_.push_back((T)labels_.size());
124 unsigned int makeContiguous()
127 unsigned int count = 0;
128 for(IndexType i=0; i<(IndexType)(labels_.size()-1); ++i)
132 labels_[i] = (T)count++;
136 labels_[i] = labels_[(IndexType)labels_[i]];
142 T operator[](T label)
const
144 return labels_[(IndexType)label];
152 #endif // VIGRA_UNION_FIND_HXX