Add CLOS to union-findHEADmaster

5 files changed, 113 insertions, 91 deletions

diff --git a/union-find/quick-find.lisp b/union-find/quick-find.lisp
index 936c647..dd2c54b 100644
--- a/union-find/quick-find.lisp
+++ b/union-find/quick-find.lisp
@@ -5,34 +5,35 @@
 
 (in-package :com.lisp-algo.union-find)
 
-;;; Base functions
-
-(defun qf-create-network (n)
-  "Build a quick-find network using a dynamic vector"
-  (let ((nodes (make-array n :fill-pointer 0)))
-    (dotimes (id n)
+(defclass quick-find ()
+  ((nw-size
+    :initarg :network-size
+    :initform 10
+    :accessor network-size)
+   (nw
+    :initform nil
+    :accessor network)))
+
+(defmethod initialize-instance :after ((algo quick-find) &key)
+  ;; Initialize network using dynamic vector
+  (let* ((nw-size (slot-value algo 'nw-size))
+        (nodes (make-array nw-size :fill-pointer 0)))
+    (dotimes (id nw-size)
       (vector-push id nodes))
-    nodes))
+    (setf (slot-value algo 'nw) nodes)))
 
-;; Link two nodes in the network
-(defun qf-union (network n1 n2)
-  "Link two nodes in the quick-find network. union_ represent the union operation of the Quick Find Algorithm"
-  (let ((v-n1 (elt network n1))
-        (v-n2 (elt network n2))
-        (new-network (copy-seq network)))
+(defmethod union ((algo-instance quick-find) n1 n2)
+  (with-slots ((nw nw)) algo-instance
+  (let ((v-n1 (elt nw n1))
+        (v-n2 (elt nw n2))
+        (new-network (copy-seq nw)))
     (dotimes (n (length new-network))
       (if (= (elt new-network n) v-n2) (setf (elt new-network n) v-n1)))
-    new-network))
-
-;;; Macro definitions
+    (setf nw new-network))))
 
-(defmacro qf-connected (network n1 n2)
+(defmethod connected ((algo-instance quick-find) n1 n2)
   " Return t if there is a path between n1 and n2, nil otherwise. connected represent the find operation of the Quick Find Algorithm"
-    `(= (elt ,network ,n1) (elt ,network ,n2)))
-
-(defmacro qf-nunion (network n1 n2)
-  "A destructive version of union_"
-  `(setq ,network (union ,network ,n1 ,n2)))
-
+  (with-slots ((nw nw)) algo-instance
+    (= (elt nw n1) (elt nw n2))))
 
 
diff --git a/union-find/quick-union.lisp b/union-find/quick-union.lisp
index 0db2846..648aba4 100644
--- a/union-find/quick-union.lisp
+++ b/union-find/quick-union.lisp
@@ -7,37 +7,40 @@
 
 (in-package :com.lisp-algo.union-find)
 
-;;; Base functions
-
-(defun qu-create-network (n)
+(defclass quick-union ()
+  ((nw-size
+    :initarg :network-size
+    :initform 10
+    :accessor network-size)
+   (nw
+    :initarg nil
+    :accessor network)))
+
+(defmethod initialize-instance :after ((algo quick-union) &key)
   "Build a quick-find network using a dynamic vector"
+  (with-slots ((n nw-size) (nw nw)) algo
   (let ((nodes (make-array n :fill-pointer 0)))
     (dotimes (id n)
       (vector-push id nodes))
-    nodes))
+    (setf nw nodes))))
 
-(defun qu-find-root (network node)
+(defun quick-union-find-root (network node)
   "Find the root of a sub-tree in the network."
   (do ((id node value)
        (value (elt network node) (elt network value)))
       ((= id value) id)))
 
-(defun qu-union (network n1 n2)
+(defmethod union ((algo quick-union) n1 n2)
   "Connect to sub-tree together. union represent the union operation on the Quick Union algorithm"
+  (with-slots ((network nw)) algo
   (let ((new-network (copy-seq network)))
-    (setf (elt new-network (qu-find-root new-network n1))
-          (qu-find-root new-network n2))
-    new-network))
-
+    (setf (elt new-network (quick-union-find-root new-network n1))
+          (quick-union-find-root new-network n2))
+    (setf network new-network))))
 
-;;; Macro definitions
-
-(defmacro qu-connected (network n1 n2)
+(defmethod connected ((algo quick-union) n1 n2)
   "Return true if n1 and n2 are connected and nil otherwise. connection represent
 the find operation on the Quick Union algorithm"
-  `(= (qu-find-root ,network ,n1) (qu-find-root ,network ,n2)))
-
-(defmacro qu-nunion (network n1 n2)
-  "A destructive version of union_"
-  `(setf ,network (qu-union ,network ,n1 ,n2)))
+  (with-slots ((network nw)) algo
+  (= (quick-union-find-root network n1) (quick-union-find-root network n2))))
 
diff --git a/union-find/union-find.lisp b/union-find/union-find.lisp
new file mode 100644
index 0000000..73f347f
--- /dev/null
+++ b/union-find/union-find.lisp
@@ -0,0 +1,10 @@
+(in-package :com.lisp-algo.union-find)
+
+(defgeneric create-network (algo-instance n)
+  (:documentation "Create a network for the algo-instance"))
+
+(defgeneric union (algo-instance n1 n2)
+  (:documentation "Link two nodes in the quick-find network. union_ represent the union operation of the Quick Find Algorithm"))
+
+(defgeneric connected (algo-instance n1 n2)
+  (:documentation "Check is there is a path between n1 and n2"))
diff --git a/union-find/weighted-quick-union-path-compression.lisp b/union-find/weighted-quick-union-path-compression.lisp
index ee1fc31..7235cf2 100644
--- a/union-find/weighted-quick-union-path-compression.lisp
+++ b/union-find/weighted-quick-union-path-compression.lisp
@@ -11,15 +11,28 @@
 
 (in-package :com.lisp-algo.union-find)
 
+
+(defclass weighted-quick-union-path-compression ()
+  ((nw-size
+    :initarg :network-size
+    :initform 10
+    :accessor network-size)
+   (nw
+    :initform nil
+    :accessor network)))
+
+
 ;;; Base functions
 
-(defun wqupc-create-network (n)
+(defmethod initialize-instance :after ((algo weighted-quick-union-path-compression) &key)
   "Build a quick-find network using a multi-dimensional dynamic vector:\n
 1st dimension = the network\n 2nd dimension = each subtree node quantities"
+  (with-slots ((n nw-size) (nw nw)) algo
   (let ((network (make-array `(2 ,n) :initial-element 1)))
     (dotimes (id n)
       (setf (aref network 0 id) id))
-    network))
+    (setf nw network))))
+
 
 (defun wqupc-find-root (network node)
   "Find the root of a sub-tree in the network. This is a destructive version of find-root that
@@ -29,33 +42,26 @@ include path compression"
       ((= id value) (progn (setf (aref network 0 node) id) ; Path compression
                            id))))
 
-(defun wqupc-union (network n1 n2)
+(defmethod union ((algo weighted-quick-union-path-compression) n1 n2)
   "Connect to sub-tree together. union represent the union operation on the Quick Union algorithm"
-  (let ((new-network (copy-tree network))) ; Duplicate network
-    (let* ((n1-root (wqupc-find-root new-network n1))
-          (n2-root (wqupc-find-root new-network n2))
-           (n1-size (aref new-network 1 n1-root))
-           (n2-size (aref new-network 1 n2-root)))
-      (if (>= n1-size n2-size) ; Check which subtree is LARGER (not deeper)
-          (progn (setf (aref new-network 0 n2-root) (aref new-network 0 n1-root)) ; Modify the second node
-                 (setf (aref new-network 1 n1-root) ; Update tree larger
-                       (+ (aref new-network 1 n1-root) (aref new-network 1 n2-root))))
+  (with-slots ((network nw)) algo
+    (let ((new-network (copy-tree network))) ; Duplicate network
+      (let* ((n1-root (wqupc-find-root new-network n1))
+             (n2-root (wqupc-find-root new-network n2))
+             (n1-size (aref new-network 1 n1-root))
+             (n2-size (aref new-network 1 n2-root)))
+        (if (>= n1-size n2-size) ; Check which subtree is LARGER (not deeper)
+            (progn (setf (aref new-network 0 n2-root) (aref new-network 0 n1-root)) ; Modify the second node
+                   (setf (aref new-network 1 n1-root) ; Update tree larger
+                         (+ (aref new-network 1 n1-root) (aref new-network 1 n2-root))))
           (progn (setf (aref new-network 0 n1-root) (aref new-network 0 n2-root)) ; Otherwise modify the first node
                  (setf (aref new-network 1 n2-root) ; Update tree larger
                        (+ (aref new-network 1 n2-root) (aref new-network 1 n1-root)))))
-      new-network)))
-
+        new-network))))
 
-;;; Macro definitions
-
-
-(defmacro wqupc-connected (network n1 n2)
+(defmethod connected ((algo weighted-quick-union-path-compression) n1 n2)
   "Return true if n1 and n2 are connected and nil otherwise. connection represent
 the find operation on the Quick Union algorithm"
-  `(= (wqupc-find-root ,network ,n1) (wqupc-find-root ,network ,n2)))
-
-(defmacro wqupc-nunion (network n1 n2)
-  "A destructive version of the union function."
-  `(setf ,network (wqupc-union ,network ,n1 ,n2)))
-
+  (with-slots ((network nw)) algo
+    (= (wqupc-find-root network n1) (wqupc-find-root network n2))))
 
diff --git a/union-find/weighted-quick-union.lisp b/union-find/weighted-quick-union.lisp
index dc54a2d..3564288 100644
--- a/union-find/weighted-quick-union.lisp
+++ b/union-find/weighted-quick-union.lisp
@@ -9,15 +9,24 @@
 
 (in-package :com.lisp-algo.union-find)
 
-;;; Base functions
 
-(defun wqu-create-network (n)
-  "Build a quick-find network using a multi-dimensional dynamic vector:\n
+(defclass weighted-quick-union ()
+  ((nw-size
+    :initarg :network-size
+    :initform 10
+    :accessor network-size)
+   (nw
+    :initform nil
+    :accessor network)))
+
+(defmethod initialize-instance :after ((algo weighted-quick-union) &key)
+    "Build a quick-find network using a multi-dimensional dynamic vector:\n
 1st dimension = the network\n 2nd dimension = each subtree node quantities"
+    (with-slots ((n nw-size) (nw nw)) algo
   (let ((network (make-array `(2 ,n) :initial-element 1)))
     (dotimes (id n)
       (setf (aref network 0 id) id))
-    network))
+    (setf nw network))))
 
 (defun wqu-find-root (network node)
   "Find the root of a sub-tree in the network."
@@ -25,33 +34,26 @@
        (value (aref network 0 node) (aref network 0 value)))
       ((= id value) id)))
 
-(defun wqu-union-union (network n1 n2)
+(defmethod union ((algo weighted-quick-union) n1 n2)
   "Connect to sub-tree together. union represent the union operation on the Quick Union algorithm"
-  (let ((new-network (copy-tree network))) ; Duplicate network
-    (let* ((n1-root (wqu-find-root new-network n1))
-          (n2-root (wqu-find-root new-network n2))
-           (n1-size (aref new-network 1 n1-root))
-           (n2-size (aref new-network 1 n2-root)))
-      (if (>= n1-size n2-size) ; Check which subtree is LARGER (not deeper)
-          (progn (setf (aref new-network 0 n2-root) (aref new-network 0 n1-root)) ; Modify the second node
-                 (setf (aref new-network 1 n1-root) ; Update tree larger
-                       (+ (aref new-network 1 n1-root) (aref new-network 1 n2-root))))
+  (with-slots ((network nw)) algo
+    (let ((new-network (copy-tree network))) ; Duplicate network
+      (let* ((n1-root (wqu-find-root new-network n1))
+             (n2-root (wqu-find-root new-network n2))
+             (n1-size (aref new-network 1 n1-root))
+             (n2-size (aref new-network 1 n2-root)))
+        (if (>= n1-size n2-size) ; Check which subtree is LARGER (not deeper)
+            (progn (setf (aref new-network 0 n2-root) (aref new-network 0 n1-root)) ; Modify the second node
+                   (setf (aref new-network 1 n1-root) ; Update tree larger
+                         (+ (aref new-network 1 n1-root) (aref new-network 1 n2-root))))
           (progn (setf (aref new-network 0 n1-root) (aref new-network 0 n2-root)) ; Otherwise modify the first node
                  (setf (aref new-network 1 n2-root) ; Update tree larger
                        (+ (aref new-network 1 n2-root) (aref new-network 1 n1-root)))))
-      new-network)))
+        (setf network new-network)))))
 
-
-;;; Macro definitions
-
-
-(defmacro wqu-connected (network n1 n2)
+(defmethod connected ((algo weighted-quick-union) n1 n2)
   "Return true if n1 and n2 are connected and nil otherwise. connection represent
 the find operation on the Quick Union algorithm"
-  `(= (wqu-find-root ,network ,n1) (wqu-find-root ,network ,n2)))
-
-(defmacro wqu-nunion (network n1 n2)
-  "A destructive version of the union function."
-  `(setf ,network (wqu-union ,network ,n1 ,n2)))
-
+  (with-slots ((network nw)) algo
+    (= (wqu-find-root network n1) (wqu-find-root network n2))))