use std::fs::File;
use std::io::{self, BufRead};
use std::path::Path;
use std::time::Instant;
use mimalloc::MiMalloc;
use smallvec::SmallVec;

#[global_allocator]
static GLOBAL: MiMalloc = MiMalloc;

fn main() {
    // We iterate through all R(K4, J5, 18), add a vertex without any edges to each graph (simulating a degree-18 vertex in the dual), and vertex extend
    if let Ok(lines) = read_lines("./rk4j5_18.g6") {
        lines.flatten().for_each(|line| {
            let now = Instant::now();
            let graph= decode_g6(line);
            let n = graph.len();
            vertex_extend(vec![[0u32, (1 << n) - 1]], &max_subgraph(&graph, n), &graph, n);
            let elapsed = now.elapsed(); 
            println!("Elapsed: {:.3?}", elapsed);
        });
    }
    // The largest graph size generated was 24.
}
/////////////////////////////////////////
#[inline]
fn read_lines<P>(filename: P) -> io::Result<io::Lines<io::BufReader<File>>>
where P: AsRef<Path>, {
    let file = File::open(filename)?;
    Ok(io::BufReader::new(file).lines())
}
/////////////////////////////////////////
enum SubGraph {
    Triangle(u32),
    IndSet(u32),
    IndJ(u32),
}

#[inline(always)]
fn value(sub_graph: &SubGraph) -> u32 {
    match sub_graph {
        SubGraph::Triangle(val) => *val,
        SubGraph::IndSet(val) => *val,
        SubGraph::IndJ(val) => *val,
    }
}
/////////////////////////////////////////
#[inline(always)]
fn bit_to_vect_3(mut x: u32) -> SmallVec::<[u32; 3]> {
    let mut bit_vect = SmallVec::<[u32; 3]>::new();
    for _i in 0..x.count_ones() {
        let pw = 1 << x.ilog2();
        bit_vect.push(pw);
        x ^= pw;
    }
    bit_vect
}

#[inline(always)]
fn bit_to_vect_4(mut x: u32) -> SmallVec::<[u32; 4]> {
    let mut bit_vect = SmallVec::<[u32; 4]>::new();
    for _i in 0..x.count_ones() {
        let pw = 1 << x.ilog2();
        bit_vect.push(pw);
        x ^= pw;
    }
    bit_vect
}

#[inline(always)]
fn bit_to_vect_5(mut x: u32) -> SmallVec::<[u32; 5]> {
    let mut bit_vect = SmallVec::<[u32;5]>::new();
    for _i in 0..x.count_ones() {
        let pw = 1 << x.ilog2();
        bit_vect.push(pw);
        x ^= pw;
    }
    bit_vect
}

#[inline(always)]
fn bit_to_index(mut x: u32) -> Vec<usize> {
    let num_ones = x.count_ones() as usize;
    let mut index_vect = Vec::with_capacity(num_ones);
    for _i in 0..num_ones {
        let index = x.ilog2() as usize;
        index_vect.push(index + 1);
        x ^= 1 << index;
    }
    index_vect
}

fn expand_intervals(intervals: &mut [[u32; 2]], n: usize) -> Vec<u32>{
    let mut expanded = vec![];
    for interval in intervals.iter_mut() {
        let mut insert = bit_to_index((interval[0] | !interval[1]) & ((1 << n) - 1));
        insert.reverse();
        for mut i in 0..1<<(n - insert.len()) {
            for index in insert.iter(){
                i = (i >> (index - 1) << index) | (i & ((1 << (index - 1)) - 1));
            }
            expanded.push(i | interval[0]);
        }
        interval[0] <<= 1;
        interval[1] = (interval[1] << 1) + 1;
    }
    expanded
}
/////////////////////////////////////////
fn decode_g6(line: String) -> Vec<u32> {
    let line_vec = &line.into_bytes()[..];
    let num_vertices = line_vec[0] - 63;
    let size = u16::from(num_vertices) * (u16::from(num_vertices) - 1) / 2;
    let mut bit_vect: Vec<u8> = vec![0; (size + 6).into()];
    
    let mut i = 0;
    let mut fixed_letter;
    for letter in line_vec[1..].iter() {
        fixed_letter = letter - 63;
        for bit_place in (0..6).rev() {
            bit_vect[i] = (fixed_letter & (1 << bit_place)) >> bit_place;
            i += 1;
        }
    }

    let mut graph: Vec<u32> = vec![0; num_vertices.into()];
    i = 0;
    for column in 1..num_vertices {
        for row in 0..column {
            graph[usize::from(row)] |= u32::from(bit_vect[i]) << (num_vertices - column - 1);
            graph[usize::from(column)] |= u32::from(bit_vect[i]) << (num_vertices - row - 1);
            i += 1;
        }
    }
    graph.insert(0, 0); // Attach a vertex with degree 18 in the dual
    graph
}

/////////////////////////////////////////
fn max_clique(r: &mut u32, p: &mut u32, x: &mut u32, max_subgraphs: &mut Vec<SubGraph>, graph: &Vec<u32>, n: usize) {
    if *p == 0 && *x == 0 {
        if r.count_ones() == 3 {
            max_subgraphs.push(SubGraph::Triangle(*r));
        }
        return;
    }
    for index in bit_to_index(*p & !graph[n - ((*p | *x).ilog2() as usize)  - 1]) {
        let neighbors = graph[n - index];
        let pointer = 1 << (index - 1);
        max_clique(&mut (*r | pointer), &mut (*p & neighbors), &mut (*x & neighbors), max_subgraphs, graph, n);
        *p &= !pointer;
        *x |= pointer;
    }
}

fn max_set(r: &mut u32, p: &mut u32, x: &mut u32, max_subgraphs: &mut Vec<SubGraph>, max_sets_4: &mut Vec<u32>, graph: &Vec<u32>, n: usize) {
    if *p == 0 && *x == 0 {
        let num_vertices = r.count_ones();
        if num_vertices == 5 {
            max_subgraphs.push(SubGraph::IndSet(*r));
        } else if num_vertices == 4 {
            for max_set_4 in max_sets_4.iter() {
                if (*r & max_set_4).count_ones() == 3 {
                    max_subgraphs.push(SubGraph::IndJ(*r | max_set_4));
                }
            }
            max_sets_4.push(*r);
        }
        return;
    }
    let pivot = (*p | *x).ilog2() as usize;
    for index in bit_to_index(*p & (graph[n - pivot - 1] | (1 << pivot))) {
        let pointer = 1 << (index - 1);
        let neighbors = !graph[n - index] ^ pointer;
        max_set(&mut (*r | pointer), &mut (*p & neighbors), &mut (*x & neighbors), max_subgraphs, max_sets_4, graph, n);
        *p &= !pointer;
        *x |= pointer;
    }
}

fn max_subgraph(graph: &Vec<u32>, n: usize) -> Vec<SubGraph>{
    let mut max_subgraphs = vec![];
    max_clique(&mut 0, &mut ((1 << n) - 1), &mut 0, &mut max_subgraphs, graph, n);
    max_set(&mut 0, &mut ((1 << n) - 1), &mut 0, &mut max_subgraphs, &mut vec![], graph, n);
    max_subgraphs.sort_by_key(value);
    max_subgraphs

}

fn max_subgraph_last(graph: &Vec<u32>, n: usize) -> Vec<SubGraph>{
    let mut max_subgraphs = vec![];
    max_clique(&mut 1, &mut (graph[n - 1].clone()), &mut 0, &mut max_subgraphs, graph, n);
    max_set(&mut 0, &mut ((1 << n) - 1), &mut 0, &mut max_subgraphs, &mut vec![], graph, n);
    max_subgraphs.retain(|subgraph| value(subgraph) & 1 == 1);
    max_subgraphs.sort_by_key(value); //special
    max_subgraphs
}
/////////////////////////////////////////
fn vertex_extend(mut intervals: Vec<[u32; 2]>, max_subgraphs: &[SubGraph], graph: &[u32], n: usize) {
    for subgraph in max_subgraphs.iter() {
        match subgraph {
            SubGraph::Triangle(val) => {
                let mut new_intervals: Vec<[u32; 2]> = Vec::with_capacity(intervals.len() * 2);
                for [bottom, top] in intervals.into_iter() {
                    if val & top == *val {
                        let diff = bit_to_vect_3(val & !bottom);
                        let diff_len = diff.len();
                        if diff_len >= 1 {
                            new_intervals.push([bottom, top & !diff[0]]);
                        } 
                        if diff_len >= 2 {
                            new_intervals.push([bottom | diff[0], top & !diff[1]]);
                        } 
                        if diff_len == 3 {
                            new_intervals.push([bottom | diff[0] | diff[1], top & !diff[2]]);
                        }
                    } else {
                        new_intervals.push([bottom, top]);
                    }
                }
                intervals = new_intervals;
            },
            SubGraph::IndSet(val) => {
                let mut new_intervals: Vec<[u32; 2]> = Vec::with_capacity(intervals.len() * 3);
                for [bottom, top] in intervals.into_iter() {
                    let count = (val & bottom).count_ones();
                    if count == 0 {
                        let inter = bit_to_vect_5(val & top);
                        let inter_len = inter.len();
                        if inter_len >= 2 {
                            new_intervals.push([bottom | inter[0] | inter[1], top]);
                        } 
                        if inter_len >= 3 {
                            new_intervals.push([bottom | inter[0] | inter[2], top & !inter[1]]);
                            new_intervals.push([bottom | inter[1] | inter[2], top & !inter[0]]);
                        }
                        if inter_len >= 4 {
                            new_intervals.push([bottom | inter[0] | inter[3], top & !(inter[1] | inter[2])]);
                            new_intervals.push([bottom | inter[1] | inter[3], top & !(inter[0] | inter[2])]);
                            new_intervals.push([bottom | inter[2] | inter[3], top & !(inter[0] | inter[1])]);
                        }
                        if inter_len == 5 {
                            new_intervals.push([bottom | inter[0] | inter[4], top & !(inter[1] | inter[2] | inter[3])]);
                            new_intervals.push([bottom | inter[1] | inter[4], top & !(inter[0] | inter[2] | inter[3])]);
                            new_intervals.push([bottom | inter[2] | inter[4], top & !(inter[0] | inter[1] | inter[3])]);
                            new_intervals.push([bottom | inter[3] | inter[4], top & !(inter[0] | inter[1] | inter[2])]);
                        }
                    } else if count == 1 {
                        let inter = bit_to_vect_4(val & top & !bottom);
                        let inter_len = inter.len();
                        if inter_len >= 1 {
                            new_intervals.push([bottom | inter[0], top]);
                        } 
                        if inter_len >= 2 {
                            new_intervals.push([bottom | inter[1], top & !inter[0]]);
                        } 
                        if inter_len >= 3 {
                            new_intervals.push([bottom | inter[2], top & !(inter[0] | inter[1])]);
                        }
                        if inter_len == 4 {
                            new_intervals.push([bottom | inter[3], top & !(inter[0] | inter[1] | inter[2])]);
                        }
                    } else {
                        new_intervals.push([bottom, top]);
                    }
                }
                intervals = new_intervals;
            },
            SubGraph::IndJ(val) => {
                let mut new_intervals: Vec<[u32; 2]> = Vec::with_capacity(intervals.len() * 2);
                for [bottom, top] in intervals.into_iter() {
                    if val & bottom == 0 {
                        let inter = bit_to_vect_5(val & top);
                        let inter_len = inter.len();
                        if inter_len >= 1 {
                            new_intervals.push([bottom | inter[0], top]);
                        } 
                        if inter_len >= 2 {
                            new_intervals.push([bottom | inter[1], top & !inter[0]]);
                        } 
                        if inter_len >= 3 {
                            new_intervals.push([bottom | inter[2], top & !(inter[0] | inter[1])]);
                        }
                        if inter_len >= 4 {
                            new_intervals.push([bottom | inter[3], top & !(inter[0] | inter[1] | inter[2])]);
                        }
                        if inter_len == 5 {
                            new_intervals.push([bottom | inter[4], top & !(inter[0] | inter[1] | inter[2] | inter[3])]);
                        }
                    } else {
                        new_intervals.push([bottom, top]);
                    }
                }
                intervals = new_intervals;
            },
        }
    }
    
    if !intervals.is_empty() {
        let expanded = expand_intervals(&mut intervals, n);
        for gluing in expanded {
            let mut new_graph = Vec::with_capacity(n + 1);
            for (i, row) in graph.iter().enumerate().take(n) {
                new_graph.push((row << 1) | ((gluing & (1 << (n - i - 1))) >> (n - i - 1)));
            }
            new_graph.push(gluing << 1);
            if n >= 24 {
                println!("{}, {:?},", new_graph.len(), new_graph); // Print graphs with size greater than 24
            }
            vertex_extend(intervals.clone(), &max_subgraph_last(&new_graph, n + 1), &new_graph, n + 1);
        }
    }
} 
/////////////////////////////////////////