From d9c2af035ac2edb68bc8b6a1f94b7c772c3509c8 Mon Sep 17 00:00:00 2001
From: Keuin <keuinx@gmail.com>
Date: Sun, 2 Aug 2020 18:31:50 +0800
Subject: Refactor & object tree impl. stage 1

---
 src/main/java/com/keuin/kbackupfabric/Random.java | 97 +++++++++++++++++++++++
 1 file changed, 97 insertions(+)
 create mode 100644 src/main/java/com/keuin/kbackupfabric/Random.java

(limited to 'src/main/java/com/keuin/kbackupfabric/Random.java')

diff --git a/src/main/java/com/keuin/kbackupfabric/Random.java b/src/main/java/com/keuin/kbackupfabric/Random.java
new file mode 100644
index 0000000..e87e4c1
--- /dev/null
+++ b/src/main/java/com/keuin/kbackupfabric/Random.java
@@ -0,0 +1,97 @@
+package com.keuin.kbackupfabric;
+
+import java.util.ArrayList;
+import java.util.LinkedList;
+import java.util.List;
+
+public class Random {
+    public int random(int A, int B) {
+        return (int) (A + (B - A + 1) * Math.random());
+    }
+
+    public double[] randomArray(int MaxN, int lowA, int highA) {
+        double[] array = new double[random(1,MaxN)];
+        for (int i = 0; i < array.length; i++) {
+            array[i] = lowA + (highA - lowA) * Math.random();
+        }
+        return array;
+    }
+
+    public double[] generate(int MaxN, int lowA, int highA) {
+        double[] testData = randomArray(MaxN,lowA,highA);
+        double x = testData[random(0,testData.length-1)];
+    }
+
+    public int R(double[] a, double x) {
+        List<Integer> list = new LinkedList<>();
+        int k;
+        for (int i = 0; i < a.length; i++) {
+            if(Math.abs(a[i] - x) < 1e-6)
+                list.add(i);
+        }
+        assert !list.isEmpty();
+        k = list.get(list.size() / 2);
+        return k;
+    }
+
+
+    public boolean domR(double[] a, double x) {
+        for (double v : a) {
+            if(Math.abs(v - x) < 1e-6)
+                return true;
+        }
+        return false;
+    }
+
+    public boolean oracle(double[] a, double x, int k) {
+        if(!(Math.abs(a[k] - x) < 1e-6))
+            return false;
+        int c1=0,c2=0;
+        for (int i = 0; i < k; i++) {
+            if(Math.abs(a[i] - x) < 1e-6)
+                ++c1;
+        }
+        for (int i = k; i < a.length; i++) {
+            if(Math.abs(a[i] - x) < 1e-6)
+                ++c2;
+        }
+        return c1 - c2 >= -1 && c1 - c2 <= 1;
+    }
+
+    public boolean driver() {
+        int MaxN = 80, lowA = 20, highA = 50;
+        double[] a = randomArray(MaxN,lowA,highA);
+        double x = a[random(0,a.length-1)];
+        return oracle(a,x,search(a,x));
+    }
+
+
+    public int search(double[] a, double x) {
+        int counter = 0;
+        for (double i : a) {
+            if(Math.abs(i - x) < 1e-6)
+                ++counter;
+        }
+        counter /= 2;
+        for (int i = 0; i < a.length; i++) {
+            if(Math.abs(a[i] - x) < 1e-6) {
+                --counter;
+                if(counter == 0)
+                    return i;
+            }
+        }
+        return -1;
+    }
+
+    public static void Main() {
+        int pass = 0, fail = 0;
+        for (int i = 0; i < 10000; i++) {
+            if(driver())
+                pass++;
+            else
+                fail++;
+        }
+        System.out.println(String.format("pass: %d, fail: %d.",pass,fail));
+    }
+
+}
-- 
cgit v1.2.3