From 2c3ec9a3e8a33e49cdcb8c17037e8ccc66aca989 Mon Sep 17 00:00:00 2001
From: JSDurand <mmemmew@gmail.com>
Date: Thu, 9 Mar 2023 13:07:04 +0800
Subject: complete algorithm implementation

The sorting function is complete, and accepts any type that has a
partial order.
---
 src/main.rs | 173 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 173 insertions(+)
 create mode 100644 src/main.rs

(limited to 'src')

diff --git a/src/main.rs b/src/main.rs
new file mode 100644
index 0000000..301ca32
--- /dev/null
+++ b/src/main.rs
@@ -0,0 +1,173 @@
+use std::{
+    cmp::{Ordering, PartialOrd},
+    collections::HashSet,
+};
+
+type Graph = Vec<Vec<usize>>;
+
+fn add_edge(graph: &mut Graph, source: usize, target: usize) {
+    let len = graph.len();
+
+    if source >= len {
+        panic!("source = {source} >= len = {len}");
+    }
+
+    if target >= len {
+        panic!("target = {target} >= len = {len}");
+    }
+
+    if !graph.get(source).unwrap().contains(&target) {
+        graph.get_mut(source).unwrap().push(target);
+    }
+
+    if !graph.get(target).unwrap().contains(&source) {
+        graph.get_mut(target).unwrap().push(source);
+    }
+}
+
+fn sm1<T: PartialOrd>(a: Vec<T>, count: &mut usize) -> (usize, Graph) {
+    let n = a.len();
+
+    if n == 0 {
+        panic!("invalid empty input");
+    }
+
+    let mut result: Graph = std::iter::repeat_with(Default::default).take(n).collect();
+
+    let mut indices: Vec<usize> = (0..n).collect();
+
+    let mut upper_bound = n;
+
+    while upper_bound > 1 {
+        for i in 0..(upper_bound.div_euclid(2)) {
+            *count += 1;
+
+            let x = *indices.get(2 * i).unwrap();
+            let y = *indices.get(2 * i + 1).unwrap();
+
+            add_edge(&mut result, x, y);
+
+            match a.get(x).unwrap().partial_cmp(a.get(y).unwrap()) {
+                Some(Ordering::Less) | Some(Ordering::Equal) => {
+                    *indices.get_mut(i).unwrap() = x;
+                }
+                Some(_) => {
+                    *indices.get_mut(i).unwrap() = y;
+                }
+                None => {
+                    if a.get(x).unwrap().partial_cmp(a.get(x).unwrap()).is_some() {
+                        *indices.get_mut(i).unwrap() = x;
+                    } else {
+                        *indices.get_mut(i).unwrap() = y;
+                    }
+                }
+            }
+        }
+
+        let offset = upper_bound.rem_euclid(2);
+
+        if offset == 1 {
+            *indices.get_mut(upper_bound.div_euclid(2)).unwrap() =
+                *indices.get(upper_bound - 1).unwrap();
+        }
+
+        upper_bound = upper_bound.div_euclid(2) + offset;
+    }
+
+    (*indices.first().unwrap(), result)
+}
+
+fn sm<T: PartialOrd>(a: Vec<T>, count: &mut usize) -> Vec<usize> {
+    let n = a.len();
+
+    let mut result: Vec<usize> = Vec::with_capacity(n);
+
+    let mut added: Vec<bool> = std::iter::repeat(false).take(n).collect();
+
+    let mut g_to_a_s: Vec<Vec<usize>> = Vec::with_capacity(n);
+
+    g_to_a_s.push((0..n).collect());
+
+    let mut lis: Vec<Graph> = vec![];
+
+    for i in 0..n {
+        let g: Vec<&T> = g_to_a_s
+            .last()
+            .unwrap()
+            .iter()
+            .copied()
+            .map(|x| a.get(x).unwrap())
+            .collect();
+
+        let g_len = g.len();
+
+        assert_eq!(Some(g_len), g_to_a_s.last().map(|v| v.len()));
+
+        let (hi, li) = sm1(g, count);
+        assert!(hi < g_len);
+
+        let hi = *g_to_a_s.last().unwrap().get(hi).unwrap();
+
+        result.push(hi);
+        *added.get_mut(hi).unwrap() = true;
+
+        lis.push(li);
+
+        assert_eq!(lis.len(), i + 1);
+        assert_eq!(g_to_a_s.len(), i + 1);
+
+        let mut new_g_to_a: Vec<usize> = Vec::new();
+        let mut new_g_to_a_set: HashSet<usize> = Default::default();
+
+        for j in 0..=i {
+            let mut ell_j: Vec<usize> = Vec::new();
+
+            let i_j = g_to_a_s.get(j).unwrap();
+
+            let index = i_j.iter().position(|x| *x == hi);
+
+            if let Some(x_j) = index {
+                for y in lis.get(j).unwrap().get(x_j).unwrap().iter().copied() {
+                    ell_j.push(*i_j.get(y).unwrap());
+                }
+            }
+
+            for x in ell_j {
+                if !new_g_to_a_set.contains(&x) && !added.get(x).unwrap() {
+                    new_g_to_a.push(x);
+                    new_g_to_a_set.insert(x);
+                }
+            }
+        }
+
+        g_to_a_s.push(new_g_to_a);
+    }
+
+    result
+}
+
+fn main() {
+    // sample: 1 3 4 0 2 3 5 1
+    let inputs: Vec<f32> = std::env::args()
+        .skip(1)
+        .map(|arg| arg.parse().unwrap())
+        .collect();
+
+    // let enumeration: Vec<f32> = (0..inputs.len()).map(|n| n as f32).collect();
+
+    // println!("        {enumeration:?}");
+
+    println!("inputs: {inputs:?}");
+
+    let mut count = 0;
+
+    let sort = sm(inputs.clone(), &mut count);
+
+    let sort_result: Vec<f32> = sort
+        .iter()
+        .copied()
+        .map(|n| *inputs.get(n).unwrap())
+        .collect();
+
+    println!("sort indices = {sort:?}\nsort result: {sort_result:?}\ncount = {count}");
+}
-- 
cgit v1.2.3-18-g5258