use std::collections::{HashSet, VecDeque};

type NodeIdx = usize;
type EdgeIdx = usize;

struct RelationGraph {
    nodes: Vec<Node>,
    edges: Vec<Edge>,
}

#[derive(Hash, PartialEq, Eq)]
struct Node {
    id: u64,
    is_namespace: bool,
    edge_list_head: Option<EdgeIdx>,
}

struct Edge {
    dst: NodeIdx,
    op: Option<Operator>,
    next_edge: Option<EdgeIdx>,
}

enum Operator {
    And,
    Or,
    Difference,
    Complement,
    AndAll,
    OrAll,
    DifferenceAll,
    ComplementAll,
}

impl RelationGraph {
    pub fn new() -> Self {
        // As I think about how to serialize this graph, when reading from the DB
        // I should chunk up the namespaces so that I can read-on-demand when I
        // encounter a namespace that has not yet been loaded, and in this way
        // I don't need to deal with the entire graph...
        //
        // but that's a totally unnecessary fun optimization.
        RelationGraph {
            nodes: vec![],
            edges: vec![],
        }
    }

    pub fn add_node(&mut self, id: u64, is_namespace: bool) -> NodeIdx {
        let idx = self.nodes.len();
        self.nodes.push(Node {
            id,
            is_namespace,
            edge_list_head: None,
        });
        idx
    }

    pub fn add_edge(
        &mut self,
        src: NodeIdx,
        dst: NodeIdx,
        op: Option<Operator>,
        follow: Option<NodeIdx>,
    ) {
        let edge_idx = self.edges.len();
        let node = &mut self.nodes[src];
        // TODO: dupe check
        self.edges.push(Edge {
            dst,
            op,
            next_edge: node.edge_list_head,
        });
        node.edge_list_head = Some(edge_idx);
    }

    // doc:2#viewer@user:1
    pub fn find_leaves(&self, src: NodeIdx, filterIdx: Option<NodeIdx>) -> Vec<NodeIdx> {
        let mut all_leaves = vec![];
        // let mut and_leaves = vec![];
        // let mut exc_leaves = vec![];

        // the output should basically be leaves to look up
        // for example
        // the leaves of doc might be (user), <(organization, admin)>, <(role, foo)>
        // and since (organization, admin) has leaves (user) as well
        // if the user is in that final set, then they are valid
        // and those leaves would be queried as relation tuples saved in the DB

        println!("HERE I AM");

        let start = self.nodes.get(src);
        let mut seen = HashSet::new();
        let mut q = VecDeque::new();

        seen.insert(start);
        q.push_back(start);

        // I need to build a chain of ops
        // [AND, OR, OR, AND, OR, ...]
        // at each stage, I need to apply the operator chain
        while let Some(&Some(node)) = q.iter().next() {
            if node.is_namespace {
                all_leaves.push(node);
            }

            // for edge in edge list

            println!("IN QUEUE\n");
            println!("node: {:?}\n", node.id);
            q.pop_front();
        }
        println!("DONE");

        // task...starting at doc_viewer, return all leaf nodes
        // to do this....
        // check all children
        // if child is OR
        //    if child is leaf, return child
        //    else return all of these children
        // if child is AND
        //    if child is leaf, return if also present in all other nodes
        //    else return all children which are also present in other nodes
        // if child is Difference
        //    if child is leaf, do not include and remove if it part of the user set
        //    else remove all of these children

        // TOTAL pool of leafs
        // Intersection leaves (i.e. ONLY leaves which MUST exist)
        // exclusion leaves (i.e. leaves which CANNOT exist)

        // bfs build query...
        // execute query

        // start at nodeIdx: doc_viewer
        // expand until I find all leaf nodes.
        // we are interested in leaf nodes with nodeIdx: user
        // return all leaf nodeIdx that match the filter. If no filter provided, return all leaf idx.

        // TODO: optionally build the expansion path by pushing every intermediate step as the bfs is walked.

        // with each step of the bfs, perform the operator.
        // e.g. if first step is doc_viewer -> user with operator OR then we have leaf user with operator chain [OR]
        // the next step might be doc_viewer -> doc_editor with step OR and doc_editor -> user with step OR, so we have leaf user with chain [OR, OR]
        // the next step might be doc_viewer -> doc_auditor with OR
        //   then doc_auditor -> doc_editor with OR
        //     then doc_editor -> doc_user with OR
        //     then doc_editor -> doc_owner
        //     then doc_auditor -> doc_owner with Difference
        //

        todo!()
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn build_graph_test() {
        let mut g = RelationGraph::new();
        let user = g.add_node(1, true);
        let role = g.add_node(2, true);
        let group = g.add_node(3, true);
        let doc = g.add_node(4, true);

        let role_member = g.add_node(5, false);

        let group_member = g.add_node(6, false);
        let group_admin = g.add_node(7, false);

        let doc_owner = g.add_node(8, false);
        let doc_editor = g.add_node(9, false);
        let doc_viewer = g.add_node(10, false);
        let doc_auditor = g.add_node(11, false);
        let doc_parent = g.add_node(12, false);

        g.add_edge(role, role_member, None, None);
        g.add_edge(role_member, user, Some(Operator::Or), None);
        g.add_edge(role_member, group_member, Some(Operator::Or), None);

        g.add_edge(group, group_member, None, None);
        g.add_edge(group, group_admin, None, None);

        g.add_edge(group_member, user, Some(Operator::Or), None);
        g.add_edge(group_member, group_admin, Some(Operator::Or), None);
        g.add_edge(group_admin, user, Some(Operator::Or), None);

        g.add_edge(doc, doc_owner, None, None);
        g.add_edge(doc, doc_editor, None, None);
        g.add_edge(doc, doc_viewer, None, None);
        g.add_edge(doc, doc_auditor, None, None);
        g.add_edge(doc, doc_parent, None, None);

        g.add_edge(doc_owner, user, Some(Operator::Or), None);
        g.add_edge(doc_editor, user, Some(Operator::Or), None);
        g.add_edge(doc_editor, doc_owner, Some(Operator::Or), None);
        g.add_edge(doc_viewer, user, Some(Operator::Or), None);
        g.add_edge(doc_viewer, doc_editor, Some(Operator::Or), None);
        g.add_edge(doc_viewer, doc_parent, Some(Operator::Or), Some(doc_viewer));
        g.add_edge(doc_viewer, user, Some(Operator::OrAll), None);
        g.add_edge(doc_viewer, doc_auditor, Some(Operator::Or), None);
        g.add_edge(doc_auditor, doc_editor, Some(Operator::Difference), None);

        g.find_leaves(doc_viewer, None);
        assert_eq!(1, 2);
    }
}