PARP Research Group

Universidad de Murcia

---

src/qvmath/qvdisjointset.h Go to the documentation of this file. /* * Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012. PARP Research Group. * <http://perception.inf.um.es> * University of Murcia, Spain. * * This file is part of the QVision library. * * QVision is free software: you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as * published by the Free Software Foundation, version 3 of the License. * * QVision is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with QVision. If not, see <http://www.gnu.org/licenses/>. */ #ifndef QVDISJOINTSET_H #define QVDISJOINTSET_H #include <QVImage> #define INDEX(Col, Row) (Row*cols + Col) class QVDisjointSet { public: QVDisjointSet(uInt numElements); QVDisjointSet(uInt cols, uInt rows); QVDisjointSet(const QVGenericImage &image); QVDisjointSet(const QVDisjointSet &other); //~QVDisjointSet(); inline uInt find(QPoint p) { Q_ASSERT_X(cols > 0, "QVDisjointSet::find", "Number of columns equals 0"); Q_ASSERT_X(rows > 0, "QVDisjointSet::find", "Number of rows equals 0"); Q_ASSERT_X(QRect(0,0,cols, rows).contains(p), "QVDisjointSet::find", "QPoint out of image bounds"); return find(INDEX(p.x(), p.y())); } inline uInt find(uInt col, uInt row) { Q_ASSERT_X(cols > 0, "QVDisjointSet::find", "Number of columns equals 0"); Q_ASSERT_X(rows > 0, "QVDisjointSet::find", "Number of rows equals 0"); Q_ASSERT_X(QRect(0,0,cols, rows).contains(QPoint(col, row)), "QVDisjointSet::find", "QPoint out of image bounds"); return find(INDEX(col, row)); } inline uInt find(uInt index) { Q_ASSERT_X(index < elements, "QVDisjointSet::find", "Index exceeds number of elements"); if (parent[index] == index) return index; if (parent[parent[index]] != parent[index]) parent[index] = find(parent[index]); return parent[index]; } inline uInt unify(QPoint p1, QPoint p2) { Q_ASSERT_X(cols > 0, "QVDisjointSet::unify", "Number of columns equals 0"); Q_ASSERT_X(rows > 0, "QVDisjointSet::unify", "Number of rows equals 0"); Q_ASSERT_X(QRect(0,0,cols, rows).contains(p1), "QVDisjointSet::unify", "First QPoint out of image bounds"); Q_ASSERT_X(QRect(0,0,cols, rows).contains(p2), "QVDisjointSet::unify", "Second QPoint out of image bounds"); return unify(INDEX(p1.x(),p1.y()),INDEX(p2.x(),p2.y())); } inline uInt unify(uInt c1, uInt r1, uInt c2, uInt r2) { Q_ASSERT_X(cols > 0, "QVDisjointSet::unify", "Number of columns equals 0"); Q_ASSERT_X(rows > 0, "QVDisjointSet::unify", "Number of rows equals 0"); Q_ASSERT_X(QRect(0,0,cols, rows).contains(QPoint(c1, r1)), "QVDisjointSet::unify", "First QPoint out of image bounds"); Q_ASSERT_X(QRect(0,0,cols, rows).contains(QPoint(c2, r2)), "QVDisjointSet::unify", "Second QPoint out of image bounds"); return unify(INDEX(c1,r1),INDEX(c2,r2)); } uInt unify(uInt index1, uInt index2); inline uInt getSetCardinality(const QPoint &p1) { return getSetCardinality(INDEX(p1.x(), p1.y())); } inline uInt getSetCardinality(uInt col, uInt row) { return getSetCardinality(INDEX(col, row)); } inline uInt getSetCardinality(uInt index) { Q_ASSERT(count[find(index)] > 0); return count[find(index)]; } inline uInt numberOfSets() const { return sets; } inline uInt index(QPoint p) const { return INDEX(p.x(), p.y()); } inline uInt index(uInt col, uInt row) const { return INDEX(col, row); } inline bool isRootElement(uInt col, uInt row) const { return isRootElement(INDEX(col, row)); } inline bool isRootElement(uInt index) const { return parent[index] == index; } private: uInt cols, rows, elements, sets; QVector<uInt> parent, rank, count; //uInt *parent, *rank, *count; void makeSet(); //void allocData(); //void freeData(); }; #endif

---

QVision framework. PARP research group. Copyright © 2007, 2008, 2009, 2010, 2011.