From 98cfcd753eefac002ca6e6d9d3d5bb09e4bf2b9f Mon Sep 17 00:00:00 2001
From: fred <fred>
Date: Mon, 30 Sep 1996 07:48:31 +0000
Subject: [PATCH] Import of flower-1.0.0

---
 flower/compare.hh   | 24 ++++++++++++++++++++++++
 flower/unionfind.cc | 35 +++++++++++++++++++++++++++++++++++
 flower/unionfind.hh | 25 +++++++++++++++++++++++++
 3 files changed, 84 insertions(+)
 create mode 100644 flower/compare.hh
 create mode 100644 flower/unionfind.cc
 create mode 100644 flower/unionfind.hh

diff --git a/flower/compare.hh b/flower/compare.hh
new file mode 100644
index 0000000000..05b6e89e41
--- /dev/null
+++ b/flower/compare.hh
@@ -0,0 +1,24 @@
+#ifndef COMPARE_HH
+#define COMPARE_HH
+
+/// handy notations for a signed comparison
+#define instantiate_compare(type, function)				\
+inline bool operator>(type t1, type t2) { return function(t1, t2) > 0; }	\
+ inline bool operator>=(type t1, type t2) { return function(t1, t2) >= 0; }	\
+ inline bool operator==(type t1, type t2) { return function(t1, t2) == 0; }	\
+ inline bool operator<=(type t1, type t2) { return function(t1, t2) <= 0; }	\
+ inline bool operator<(type t1, type t2) { return function(t1, t2) < 0; } \
+ inline type MAX(type t1, type t2) {  return (t1 > t2 )? t1 : t2; }\
+ inline type MIN(type t1, type t2) {  return (t1 < t2 )? t1 : t2; }\
+  \
+  bool operator<(type t1, type t2) /* stupid fix to allow ; */
+     /**
+    make the operators{<,<=,==,>=,>} and the MAX and MIN of two.
+    Please fill a & in the type argument if necessary.    
+    */
+
+     
+
+     
+#endif
+     
diff --git a/flower/unionfind.cc b/flower/unionfind.cc
new file mode 100644
index 0000000000..e7b0831dd1
--- /dev/null
+++ b/flower/unionfind.cc
@@ -0,0 +1,35 @@
+#include "unionfind.hh"
+/*
+    see a book on data structures
+    */
+
+Union_find::Union_find(int n)
+{
+    classes.set_size(n);
+
+    for (int i=0; i < n; i++) {
+	classes[i] = i;
+    }
+}
+
+int
+Union_find::find(int i)
+{
+    int rep = i;
+    while (classes[rep] != rep)
+	rep = classes[rep];
+    while (classes[i] != rep) {
+	int next =classes[i];
+	classes[i] = rep;
+	i = next;
+    }
+    return rep;
+}
+
+void
+Union_find::connect(int i, int j)
+{
+    i = find(i);
+    j = find(j);
+    classes[i] = j;    
+}
diff --git a/flower/unionfind.hh b/flower/unionfind.hh
new file mode 100644
index 0000000000..8fcc6b438e
--- /dev/null
+++ b/flower/unionfind.hh
@@ -0,0 +1,25 @@
+#ifndef UNIONFIND_HH
+#define UNIONFIND_HH
+#include "vray.hh"
+
+/// which points of a graph are connected?
+struct Union_find {    
+    void connect(int i, int j);
+    int find(int i);
+    bool equiv(int i, int j) { return find(i) == find(j); }
+    Union_find(int sz);
+
+private:
+    svec<int> classes;
+
+};
+/*
+    Union find, a standard algorithm:
+
+    Union_find represents an undirected graph of N points. You can
+    connect two points using #connect()#. #find(i)# finds a uniquely
+    determined representant of the equivalence class of points
+    connected to #i#.
+    
+    */
+#endif
-- 
2.39.5