implement quick find.

3 files changed, 84 insertions, 0 deletions

diff --git a/lib/quick_find.rb b/lib/quick_find.rb
new file mode 100644
index 0000000..419ed8b
--- /dev/null
+++ b/lib/quick_find.rb
@@ -0,0 +1,23 @@
+class QuickFind
+  def initialize(size)
+    @items = []
+    size.times.each do |n|
+      @items[n] = n
+    end
+  end
+
+  def connected?(x, y)
+    @items[x] == @items[y]
+  end
+
+  def union(x, y)
+    x_value = @items[x]
+    y_value = @items[y]
+
+    @items.size.times do |n|
+      if @items[n] == x_value
+        @items[n] = y_value
+      end
+    end
+  end
+end
diff --git a/spec/quick_find_spec.rb b/spec/quick_find_spec.rb
new file mode 100644
index 0000000..88929e3
--- /dev/null
+++ b/spec/quick_find_spec.rb
@@ -0,0 +1,60 @@
+require "spec_helper"
+
+describe QuickFind do
+  subject { QuickFind.new(10) }
+
+  it "is not connected by default" do
+    10.times do |n|
+      expect(subject.connected?(n, n+1)).to be_false
+    end
+  end
+
+  it "is connected" do
+    subject.union(0, 1)
+    expect(subject.connected?(0, 1)).to be_true
+  end
+
+  it "unions and connects properly" do
+    subject.union(4, 3)
+    expect(subject.connected?(4, 3)).to be_true
+    expect(subject.connected?(3, 4)).to be_true
+
+    subject.union(3, 8)
+    expect(subject.connected?(3, 8)).to be_true
+
+    subject.union(6, 5)
+    expect(subject.connected?(6, 5)).to be_true
+
+    subject.union(9, 4)
+    expect(subject.connected?(9, 4)).to be_true
+
+    subject.union(2, 1)
+    expect(subject.connected?(2, 1)).to be_true
+
+    subject.union(8, 9)
+    expect(subject.connected?(8, 9)).to be_true
+
+    expect(subject.connected?(5, 0)).to be_false
+    subject.union(5, 0)
+    expect(subject.connected?(5, 0)).to be_true
+    expect(subject.connected?(6, 0)).to be_true
+    expect(subject.connected?(5, 6)).to be_true
+
+    subject.union(7, 2)
+    subject.union(6, 1)
+
+    tuples = [
+      [0, 5],
+      [5, 6],
+      [6, 1],
+      [1, 2],
+      [2, 7],
+      [8, 3],
+      [3, 4],
+      [4, 9],
+    ]
+    tuples.each do |tuple|
+      expect(subject.connected?(tuple.first, tuple.last)).to be_true
+    end
+  end
+end
diff --git a/spec/spec_helper.rb b/spec/spec_helper.rb
index 6cfb317..7d79f94 100644
--- a/spec/spec_helper.rb
+++ b/spec/spec_helper.rb
@@ -1,5 +1,6 @@
 require 'benchmark'
 require_relative '../lib/in_order_traversal'
+require_relative '../lib/quick_find'
 
 require_relative '../lib/sorting/bubble_sort'
 require_relative '../lib/sorting/insertion_sort'