Checking in blob routines.
Change-Id: I364331d6f9239763ccac492460ed752a0b16871f
diff --git a/aos/vision/blob/disjoint_set.h b/aos/vision/blob/disjoint_set.h
new file mode 100644
index 0000000..ed15caf
--- /dev/null
+++ b/aos/vision/blob/disjoint_set.h
@@ -0,0 +1,46 @@
+#ifndef _AOS_VISION_BLOB_DISJOINT_SET_H_
+#define _AOS_VISION_BLOB_DISJOINT_SET_H_
+
+#include <vector>
+
+namespace aos {
+namespace vision {
+
+// Disjoint set algorithm:
+// https://en.wikipedia.org/wiki/Disjoint-set_data_structure
+class DisjointSet {
+ public:
+ DisjointSet() {}
+ DisjointSet(int node_count) : nodes_(node_count, -1) {}
+ // Adds another node. Not connected to anything.
+ // Returns id of the additional node for tracking purposes.
+ int Add() {
+ nodes_.push_back(-1);
+ return nodes_.size() - 1;
+ }
+ int &operator[](int id) { return nodes_[id]; }
+ // Find returns the canonical id of the set containing id.
+ // This id is an arbitrary artifact of the merge process.
+ int Find(int id) {
+ int chained_id = nodes_[id];
+ if (chained_id <= -1) {
+ return id;
+ }
+ return nodes_[id] = Find(chained_id);
+ }
+ // The blob mergeing needs to explicitly override the default union behavior.
+ void ExplicitUnion(int parent_id, int child_id) {
+ nodes_[parent_id] = child_id;
+ }
+ // Check to see if this node is the canonical id.
+ bool IsRoot(int id) { return nodes_[id] < 0; }
+
+ private:
+ // Implemented over a vector.
+ std::vector<int> nodes_;
+};
+
+} // namespace vision
+} // namespace aos
+
+#endif // _AOS_VISION_BLOB_DISJOINT_SET_H_