[Olena-patches] last-svn-commit-883-gb303289 Add union find class. Increase the quality of the letter detection.

--- scribo/sandbox/raphael/code/my/debug/pict.hh | 15 ++ scribo/sandbox/raphael/code/my/document/clean.hh | 35 +++- .../sandbox/raphael/code/my/document/document.hh | 188 ++++++++++---------- .../raphael/code/my/document/filter/filter.hh | 182 +++++++++++++++++++ .../sandbox/raphael/code/my/document/separator.hh | 79 +++++++-- scribo/sandbox/raphael/code/my/util/union.hh | 86 +++++++++ 6 files changed, 474 insertions(+), 111 deletions(-) create mode 100644 scribo/sandbox/raphael/code/my/document/filter/filter.hh create mode 100644 scribo/sandbox/raphael/code/my/util/union.hh diff --git a/scribo/sandbox/raphael/code/my/debug/pict.hh b/scribo/sandbox/raphael/code/my/debug/pict.hh index 1597d53..56fdca3 100644 --- a/scribo/sandbox/raphael/code/my/debug/pict.hh +++ b/scribo/sandbox/raphael/code/my/debug/pict.hh @@ -3,6 +3,7 @@ #include <mln/util/graph.hh> #include <mln/debug/superpose.hh> +#include <my/util/union.hh> using namespace mln; using namespace std; namespace mymln @@ -26,6 +27,20 @@ namespace mymln image2d<value::rgb8> ima_color = labeling::colorize(value::rgb8(), ima); io::ppm::save(ima_color, file); } + + template<typename I1, typename I2> inline void save_label_image(image2d<I1> ima, mymln::util::union_find<I2> trans, std::string file) + { + mln_piter(image2d<I1>) p(ima.domain()); + p.start(); + while(p.is_valid()) + { + ima(p) = trans[ima(p)]; + p.next(); + } + image2d<value::rgb8> ima_color = labeling::colorize(value::rgb8(), ima); + io::ppm::save(ima_color, file); + } + template<typename p_v> inline void save_graph_image(p_v& pv, unsigned int SizeX, unsigned int SizeY, std::string file) { image2d<value::rgb8> ima_graph(SizeY, SizeX); diff --git a/scribo/sandbox/raphael/code/my/document/clean.hh b/scribo/sandbox/raphael/code/my/document/clean.hh index 9028e63..2ce8614 100644 --- a/scribo/sandbox/raphael/code/my/document/clean.hh +++ b/scribo/sandbox/raphael/code/my/document/clean.hh @@ -12,31 +12,52 @@ namespace mymln template<typename L, typename F, typename D> void clean_containers_items(mymln::document::document<L,F,D>& doc) { + typedef vertex_image<point2d,bool> v_ima_g; typedef p_vertices<mln::util::graph, fun::i2v::array<mln::point2d> > g_vertices_p; - v_ima_g mask = doc.fun_mask_containers(); + v_ima_g mask = doc.fun_mask_letters(); mln_piter_(v_ima_g) v(mask.domain()); typedef graph_elt_neighborhood_if<mln::util::graph, g_vertices_p, v_ima_g> nbh_t; nbh_t nbh(mask); mln_niter_(nbh_t) q(nbh, v); + mln::util::array<unsigned> count = mln::util::array<unsigned>(doc.size()); + mln::util::array<bool> inside = mln::util::array<bool>(doc.size()); + count.fill(0); + inside.fill(false); for_all(v) { + unsigned link = 0; for_all(q) - { - if(!doc.contain_container(v) && doc.get_bbox(q).has(v)) + { + if(doc.contain_container(v) && doc.get_bbox(v).has(q)) + { + + inside[doc[q]] = true; + link++; + } + else if(doc.contain_letter(v)) { - doc.add_noise(v); + count[doc[q]]++; } + - } + } + } + for(unsigned int N = 0; N < doc.size();N++) + { + if(inside[N]) + if(count[N] < 3) + doc.add_noise(N); } + } template<typename L, typename F, typename D> void clean_letters_items(mymln::document::document<L,F,D>& doc) { + typedef vertex_image<point2d,bool> v_ima_g; typedef p_vertices<mln::util::graph, fun::i2v::array<mln::point2d> > g_vertices_p; v_ima_g mask = doc.fun_mask_letters(); @@ -63,7 +84,7 @@ namespace mymln template<typename L, typename F, typename D> void clean_get_lines(mymln::document::document<L,F,D>& doc, std::string dgb_out,image2d<bool> s) - { + { image2d<value::rgb8> out; mln::initialize(out, s); typedef vertex_image<point2d,bool> v_ima_g; @@ -212,7 +233,7 @@ namespace mymln draw::line(out, q,v, mln::literal::magenta); } } - else if (doc.allign_H_Large(q, v) && doc.allign_up_line(v, q)) + else if (doc.allign_H_Large(q, v) && doc.allign_top(v, q)) { doc.add_to_line_link(v, q); draw::line(out, q,v, mln::literal::blue); diff --git a/scribo/sandbox/raphael/code/my/document/document.hh b/scribo/sandbox/raphael/code/my/document/document.hh index 4e13103..67bda18 100644 --- a/scribo/sandbox/raphael/code/my/document/document.hh +++ b/scribo/sandbox/raphael/code/my/document/document.hh @@ -1,7 +1,10 @@ #ifndef INC_DOCUMENT_DOC #define INC_DOCUMENT_DOC #include<my/util/vector_bbox_group.hh> +#include<my/util/union.hh> #include <mln/util/graph.hh> + + using namespace mln; namespace mymln { @@ -48,11 +51,10 @@ namespace mymln Vseparator_mask = fun::i2v::array<bool>(Areas + 1); noise_mask = fun::i2v::array<bool>(Areas + 1); alone_letters_mask = fun::i2v::array<bool>(Areas + 1); - - lines_mark = mln::util::array<unsigned int>(Areas + 1); - lines_mark_link = mln::util::array<unsigned int>(Areas + 1); - lines_mark.fill(0); - lines_mark_link.fill(0); + CImpSep = 1; + NImpSep = 2; + lines_union = mymln::util::union_find<Label>(Areas + 1); + implicit_separators_union = mymln::util::union_find<Label>(Areas + 1); img_influ = ima_influ; CSep = 0; CSepH = 0; @@ -65,9 +67,7 @@ namespace mymln } /* OPERATION ON LINES */ inline void add_to_line_self_link(const point2d& point) - { - add_to_line_self_link(img_influ(point)); - } + { add_to_line_self_link(img_influ(point));} inline void add_to_line(const point2d& point) { add_to_line(img_influ(point)); } @@ -77,7 +77,7 @@ namespace mymln inline bool same_line(const point2d& A, const point2d& B) { return same_line(img_influ(A), img_influ(B)); } inline bool same_line(const Label A, const Label B) - { return lines_mark[A] == lines_mark[B]; } + { return lines_union[A] == lines_union[B]; } inline void add_new_line(const point2d& point) { add_new_line(img_influ(point)); } @@ -88,74 +88,33 @@ namespace mymln { return contain_line(img_influ(point)); } inline void add_to_line(const Label lbl) - { lines_mark[lbl] = CLine; } + { lines_union[lbl] = CLine; } inline void add_new_line(const Label lbl) { CLine = NLine; NLine++; } + inline void add_to_line_self_link(const Label A) - { - lines_mark_link[A] = A; - } + {lines_union.add_self_link(A);} + inline void add_to_line_link(const Label A, const Label B) - { - - unsigned int Pos = find_line_parent(A); - if(lines_mark_link[B] == 0) - { - if(Pos != B) - { - if(Pos != 0) - { - lines_mark_link[B] = Pos; - lines_mark_link[A] = Pos; - } - else - { - lines_mark_link[A] = B; - } - } - } - else - { - unsigned int PosB = find_line_parent(B); - if(PosB == Pos) - { - lines_mark_link[B] = Pos; - lines_mark_link[A] = Pos; - } - else - { - lines_mark_link[B] = Pos; - lines_mark_link[PosB] = Pos; - } - } - - - - } - inline unsigned int find_line_parent(const Label A) - { - unsigned int Pos = A; - while(Pos != lines_mark_link[Pos] && Pos != 0){Pos = lines_mark_link[Pos];} - return Pos; - } + {lines_union.add_link(A, B);} inline void jump_to_line(const Label lbl) { - if(lines_mark[lbl] != 0) - CLine = lines_mark[lbl]; + if(lines_union[lbl] != 0) + CLine = lines_union[lbl]; else add_new_line(lbl); } inline bool contain_line(const Label lbl) - { return lines_mark[lbl] != 0;} + { return lines_union[lbl] != 0;} - /* LABELS MUST ALLWAYS BE SORTED */ inline void add_noise(const point2d& point) {add_noise(img_influ(point));} + inline unsigned int size(){return Areas_Number_;} void add_noise(Label lbl) @@ -463,7 +422,9 @@ namespace mymln } void debug_save_lines(std::string file) - { mymln::debug::save_label_image(img, lines_mark , file);} + { mymln::debug::save_label_image(img, lines_union , file);} + void debug_save_separators(std::string file) + { mymln::debug::save_label_image(img, implicit_separators_union , file);} vertex_image<point2d,bool> fun_mask_separators() { return fun_mask_(separators_mask); } vertex_image<point2d,bool> fun_mask_containers() @@ -525,27 +486,27 @@ namespace mymln { return get_line_length(img_influ(point)); } unsigned int get_line_length(Label L) - { return lines_len[lines_mark[L]]; } + { return lines_len[lines_union[L]]; } unsigned int get_beginning_of_line(point2d point) { return get_beginning_of_line(img_influ(point)); } unsigned int get_beginning_of_line(Label L) - { return lines_first_label[lines_mark[L]]; } + { return lines_first_label[lines_union[L]]; } unsigned int get_end_of_line(point2d point) { return get_end_of_line(img_influ(point)); } unsigned int get_end_of_line(Label L) - { return lines_last_label[lines_mark[L]]; } + { return lines_last_label[lines_union[L]]; } unsigned int get_parent_line(point2d point) - { return lines_mark[img_influ(point)]; } + { return lines_union[img_influ(point)]; } unsigned int get_parent_line(Label L) - { return lines_mark[L]; } + { return lines_union[L]; } inline void recook_lines() @@ -569,20 +530,68 @@ namespace mymln cook_lines_(); } inline void propage_line_link() - { - for(unsigned int N = 1; N < lines_mark_link.size(); N++) - { - unsigned int Pos = N; - while(Pos != lines_mark_link[Pos] && Pos != 0){Pos = lines_mark_link[Pos]; } - lines_mark[N] = lines_mark[Pos]; - } - } + { lines_union.propage_links(); } /*image_if<image2d<Label> masked_image_letters() {return masked_image_(letters_mask); } image_if<image2d<Label> masked_image_separator() - {return masked_image_(letters_mask); }*/ + {return masked_image_(letters_mask); }*/ + + /* IMPLICIT SEPARATORS */ + inline void add_new_separator(const point2d& point) + { add_new_separator(img_influ(point));} + inline void add_new_separator(const Label lbl) + { CImpSep = NImpSep; NImpSep++; } + + inline void add_to_separator_self_link(const point2d& point) + { add_to_separator_self_link(img_influ(point));} + inline void add_to_separator_self_link(const Label A) + {implicit_separators_union.add_self_link(A);} + + inline void add_to_separator_link(const point2d& A, const point2d& B) + { add_to_separator_link(img_influ(A), img_influ(B));} + inline void add_to_separator_link(const Label A, const Label B) + {implicit_separators_union.add_link(A, B);} + + inline bool same_implicit_separator(const point2d& A, const point2d& B) + {return same_implicit_separator(img_influ(A), img_influ(B));} + inline bool same_implicit_separator(const Label A, const Label B) + {return implicit_separators_union[A] == implicit_separators_union[B];} + + inline void propage_separator_link() + { implicit_separators_union.propage_links(); } + + inline void jump_to_separator(const point2d& point) + { jump_to_separator(img_influ(point)); } + inline void jump_to_separator(const Label lbl) + { + if(implicit_separators_union[lbl] != 0) + CImpSep = implicit_separators_union[lbl]; + else + add_new_separator(lbl); + } + inline bool contain_implicit_separator(const point2d& point) + { return contain_implicit_separator(img_influ(point)); } + inline bool contain_implicit_separator(const Label lbl) + {return implicit_separators_union[lbl] != 0; } + + inline void add_to_separator(const point2d& point) + { add_to_separator(img_influ(point)); } + inline void add_to_separator(const Label lbl) + { implicit_separators_union[lbl] = CImpSep; } + + inline void invalidate_implicit_separator(const point2d& point) + { invalidate_implicit_separator(img_influ(point)); } + inline void invalidate_implicit_separator(Label lbl) + { implicit_separators_union[lbl] = 0; } + + inline Label& operator[](point2d i) + { return img_influ(i); } + + inline point2d& operator[](Label i) + { return _bboxgp[i].pcenter(); } private: + // PRIVATE DATA ON LINES mln::util::array<unsigned int> lines_len; mln::util::array<unsigned int> lines_first_label; @@ -595,22 +604,22 @@ namespace mymln inline void cook_lines_() { - for(unsigned int N = 1; N < lines_mark.size(); N++) + for(unsigned int N = 1; N < lines_union.size(); N++) { - if(lines_mark[N] != 0) + if(lines_union[N] != 0) { /* APPROXIMATE THE NUMBER OF CHAR IN THE LINE */ - lines_len[lines_mark[N]]++; + lines_len[lines_union[N]]++; /* COOK THE FIRST AND THE LAST LABEL OF THE LINE */ - if(lines_first_label[lines_mark[N]] == 0) - lines_first_label[lines_mark[N]] = N; - else if(_bboxgp[N].pcenter()[1] < _bboxgp[lines_first_label[lines_mark[N]]].pcenter()[1]) - lines_first_label[lines_mark[N]] = N; + if(lines_first_label[lines_union[N]] == 0) + lines_first_label[lines_union[N]] = N; + else if(_bboxgp[N].pcenter()[1] < _bboxgp[lines_first_label[lines_union[N]]].pcenter()[1]) + lines_first_label[lines_union[N]] = N; - if(lines_last_label[lines_mark[N]] == 0) - lines_last_label[lines_mark[N]] = N; - else if(_bboxgp[N].pcenter()[1] > _bboxgp[lines_last_label[lines_mark[N]]].pcenter()[1]) - lines_last_label[lines_mark[N]] = N; + if(lines_last_label[lines_union[N]] == 0) + lines_last_label[lines_union[N]] = N; + else if(_bboxgp[N].pcenter()[1] > _bboxgp[lines_last_label[lines_union[N]]].pcenter()[1]) + lines_last_label[lines_union[N]] = N; /* FILL THE MASK WITH FALSE:MAYBE USELESS IF THE MASK IS INITIALIZED */ start_lines_mask(N) = false; @@ -738,10 +747,10 @@ namespace mymln unsigned int CLine; unsigned int NLine; + unsigned int CImpSep; + unsigned int NImpSep; - - mln::util::array<unsigned int> lines_mark; - mln::util::array<unsigned int> lines_mark_link; + mymln::util::union_find<Label> lines_union; unsigned int CLet ; unsigned int CSep ; unsigned int CSepH ; @@ -770,8 +779,7 @@ namespace mymln Label Areas_Number_; /* IMPLICIT SEPARATOR DETECTION */ - mln::util::array<unsigned int> implicit_separator_mark; - mln::util::array<unsigned int> implicit_separator_mark_link; + mymln::util::union_find<Label> implicit_separators_union; }; } } diff --git a/scribo/sandbox/raphael/code/my/document/filter/filter.hh b/scribo/sandbox/raphael/code/my/document/filter/filter.hh new file mode 100644 index 0000000..c3a294c --- /dev/null +++ b/scribo/sandbox/raphael/code/my/document/filter/filter.hh @@ -0,0 +1,182 @@ +#ifndef INC_DOCUMENT_FILTER_GENERIC +#define INC_DOCUMENT_FILTER_GENERIC +namespace mymln +{ + namespace document + { + namespace filter + { + template<typename L, typename F, typename D, typename Left, typename Right> + class filter + { + public: + filter(){} + filter(document<L,F,D>& doc){ doc_ = doc; } + filter(document<L,F,D>& doc, vertex_image<point2d,bool> mask){ doc_ = doc; mask_ = mask; } + inline bool link_test(point2d& A, point2d& B){ return true; } + inline bool vertex_test(point2d& A){ return true; } + inline bool gen_link_test(point2d& A, point2d& B) + { + return link_test(A, B); + } + inline bool gen_vertex_test(point2d& A) + { + return vertex_test(A); + } + inline void iter_dgb(std::string dgb_out, image2d<bool> s) + { + image2d<value::rgb8> out; + mln::initialize(out, s); + typedef vertex_image<point2d,bool> v_ima_g; + typedef p_vertices<mln::util::graph, fun::i2v::array<mln::point2d> > g_vertices_p; + mln_piter_(v_ima_g) v(mask_.domain()); + typedef graph_elt_neighborhood_if<mln::util::graph, g_vertices_p, v_ima_g> nbh_t; + nbh_t nbh(mask_); + mln_niter_(nbh_t) q(nbh, v); + for_all(v) + { + if(gen_vertex_test(v)) + { + for_all(q) + { + if(gen_link_test(v, q)) + { + draw::line(out, q,v, mln::literal::green); + } + else + { + draw::line(out, q,v, mln::literal::magenta); + } + } + } + else + { + draw::line(out, q,v, mln::literal::magenta); + } + } + } + inline void iter() + { + typedef vertex_image<point2d,bool> v_ima_g; + typedef p_vertices<mln::util::graph, fun::i2v::array<mln::point2d> > g_vertices_p; + mln_piter_(v_ima_g) v(mask_.domain()); + typedef graph_elt_neighborhood_if<mln::util::graph, g_vertices_p, v_ima_g> nbh_t; + nbh_t nbh(mask_); + mln_niter_(nbh_t) q(nbh, v); + for_all(v) + { + if(gen_vertex_test(v)) + { + for_all(q) + { + if(gen_link_test(v, q)) + { + + } + } + } + } + } + + inline filter& operator|(filter& B) + { + filter<L,F,D> PFilter = filter_or(doc_, mask_); + PFilter.sub_filter_A_ = this; + PFilter.sub_filter_B_ = B; + B.doc_ = doc_; + B.mask_ = mask_; + return PFilter; + } + + inline filter& operator&(filter& B) + { + filter<L,F,D> PFilter = filter_and(doc_, mask_); + PFilter.sub_filter_A_ = this; + PFilter.sub_filter_B_ = B; + B.doc_ = doc_; + B.mask_ = mask_; + return PFilter; + } + + protected: + Left sub_filter_A_; + Right sub_filter_B_; + + document<L,F,D> doc_; + vertex_image<point2d,bool> mask_; + + + + }; + + + + + + + + + + + template<typename L, typename F, typename D> + class filter_or : filter<L,F,D> + { + public: + inline bool gen_link_test(point2d& A, point2d& B) + { + return sub_filter_A_.gen_link_test(A, B) || sub_filter_B_.gen_link_test(A, B); + } + inline bool gen_vertex_test(point2d& A) + { + return sub_filter_A_.gen_vertex_test(A) || sub_filter_B_.gen_vertex_test(A); + } + + protected: + filter<L,F,D> sub_filter_A_; + filter<L,F,D> sub_filter_B_; + + document<L,F,D> doc_; + vertex_image<point2d,bool> mask_; + }; + + template<typename L, typename F, typename D> + class filter_and : filter<L,F,D> + { + public: + inline bool gen_link_test(point2d& A, point2d& B) + { + return sub_filter_A_.gen_link_test(A, B) || sub_filter_B_.gen_link_test(A, B); + } + inline bool gen_vertex_test(point2d& A) + { + return sub_filter_A_.gen_vertex_test(A) || sub_filter_B_.gen_vertex_test(A); + } + + protected: + filter<L,F,D> sub_filter_A_; + filter<L,F,D> sub_filter_B_; + + document<L,F,D> doc_; + vertex_image<point2d,bool> mask_; + }; + + template<typename L, typename F, typename D> + class filter_letter : filter<L,F,D> + { + public: + inline bool vertex_test(point2d& A){ return doc_.contain_letter(A); } + + protected: + filter<L,F,D> sub_filter_A_; + filter<L,F,D> sub_filter_B_; + + document<L,F,D> doc_; + vertex_image<point2d,bool> mask_; + }; + + + + } + } +} +#endif \ No newline at end of file diff --git a/scribo/sandbox/raphael/code/my/document/separator.hh b/scribo/sandbox/raphael/code/my/document/separator.hh index 756f04b..f5a32db 100644 --- a/scribo/sandbox/raphael/code/my/document/separator.hh +++ b/scribo/sandbox/raphael/code/my/document/separator.hh @@ -2,7 +2,7 @@ #define INC_DOCUMENT_SEPARATOR #include <my/util/vector_bbox_group.hh> #include <mln/util/graph.hh> -#include <mln/document/document.hh> +#include <my/document/document.hh> using namespace mln; namespace mymln { @@ -11,7 +11,7 @@ namespace mymln namespace separators { template<typename L, typename F, typename D> - void clean_containers_items(mymln::document::document<L,F,D>& doc, std::string dgb_out, image2d<bool> s) + void separators_find_allign(mymln::document::document<L,F,D>& doc, std::string dgb_out, image2d<bool> s) { image2d<value::rgb8> out; mln::initialize(out, s); @@ -27,42 +27,93 @@ namespace mymln if(doc.contain_letter(v)) { + doc.jump_to_separator(v); if((!doc.contain_implicit_separator(v))) { - doc.add_to_implicit_separator(v); - doc.add_to_implicit_separator_self_link(v); + doc.add_to_separator(v); + doc.add_to_separator_self_link(v); } - + bool All_Alone = true; for_all(q) { - if((!doc.contain_line(q))) + if((!doc.contain_implicit_separator(q))) { // draw::line(out, q,v, mln::literal::blue); - if(doc.allign_H(q,v) && doc.allign_size(q, v)) + if(doc.allign_H_Large(q,v) && doc.allign_size(q, v)) { - doc.add_to_implicit_separator_link(v, q); + doc.add_to_separator_link(v, q); draw::line(out, q,v, mln::literal::magenta); - All_Alone = false; + All_Alone = false; } } else { - if(doc.allign_V(q,v) && doc.allign_size(q, v)) + if(doc.allign_H_Large(q,v) && doc.allign_size(q, v)) { - doc.add_to_implicit_separator_link(q, v); + doc.add_to_separator_link(q, v); draw::line(out, q,v, mln::literal::green); - All_Alone = false; + All_Alone = false; } } } + if(All_Alone){doc.invalidate_implicit_separator(v);} } } - doc.propage_implicit_separator_link(); + doc.propage_separator_link(); io::ppm::save(mln::debug::superpose(out, s, literal::white),dgb_out); } + + template<typename L, typename F, typename D> + void separators_make_clean(mymln::document::document<L,F,D>& doc) + { + + typedef vertex_image<point2d,bool> v_ima_g; + typedef p_vertices<mln::util::graph, fun::i2v::array<mln::point2d> > g_vertices_p; + v_ima_g mask = doc.fun_mask_letters(); + mln_piter_(v_ima_g) v(mask.domain()); + typedef graph_elt_neighborhood_if<mln::util::graph, g_vertices_p, v_ima_g> nbh_t; + nbh_t nbh(mask); + mln_niter_(nbh_t) q(nbh, v); + mln::util::array<unsigned> count = mln::util::array<unsigned>(doc.size()); + count.fill(0); + for_all(v) + { + + if(doc.contain_implicit_separator(v)) + { + bool All_Alone = true; + doc.jump_to_line(v); + if((!doc.contain_line(v))) + { + doc.add_to_line(v); + doc.add_to_line_self_link(v); + } + + for_all(q) + { + + if(doc.contain_implicit_separator(q) && doc.same_implicit_separator(q,v)) + { + // draw::line(out, q,v, mln::literal::blue); + if(doc.allign_V(q,v) && doc.allign_size(q, v)) + { + count[doc[q]]++; + } + } + + } + } + } + for(unsigned int N = 0; N < doc.size();N++) + { + if(count[N] > 1) + doc.invalidate_implicit_separator(N); + } + } } } -} \ No newline at end of file +} +#endif \ No newline at end of file diff --git a/scribo/sandbox/raphael/code/my/util/union.hh b/scribo/sandbox/raphael/code/my/util/union.hh new file mode 100644 index 0000000..7f21e87 --- /dev/null +++ b/scribo/sandbox/raphael/code/my/util/union.hh @@ -0,0 +1,86 @@ +#ifndef INC_DOCUMENT_UNION +#define INC_DOCUMENT_UNION +namespace mymln +{ + namespace util + { + template<typename Label> + class union_find + { + public : + union_find() + {size_ = 0;} + union_find(const unsigned int max_size) + { + mark = mln::util::array<unsigned int>(max_size); + mark_link = mln::util::array<unsigned int>(max_size); + mark.fill(0); + mark_link.fill(0); + size_ = max_size; + } + + inline void add_self_link(const Label A) + { mark_link[A] = A; } + inline void add_link(const Label A, const Label B) + { + + unsigned int Pos = find_parent_(A); + if(mark_link[B] == 0) + { + if(Pos != B) + { + if(Pos != 0) + { + mark_link[B] = Pos; + mark_link[A] = Pos; + } + else + { + mark_link[A] = B; + } + } + } + else + { + unsigned int PosB = find_parent_(B); + if(PosB == Pos) + { + mark_link[B] = Pos; + mark_link[A] = Pos; + } + else + { + mark_link[B] = Pos; + mark_link[PosB] = Pos; + } + } + } + inline void propage_links() + { + for(unsigned int N = 1; N < size_; N++) + { + unsigned int Pos = N; + while(Pos != mark_link[Pos] && Pos != 0){Pos = mark_link[Pos]; } + mark[N] = mark[Pos]; + } + } + inline unsigned int size() + {return size_; } + inline unsigned int& operator[](unsigned int i) + { + return mark[i]; + } + private : + inline unsigned int find_parent_(const Label A) + { + unsigned int Pos = A; + while(Pos != mark_link[Pos] && Pos != 0){Pos = mark_link[Pos];} + return Pos; + } + mln::util::array<unsigned int> mark; + mln::util::array<unsigned int> mark_link; + unsigned int size_; + }; + } +} +#endif \ No newline at end of file -- 1.7.2.5