use std::{collections::HashSet, hash::Hash};

pub trait Node<Id> {
    fn id(&self) -> &Id;
    fn parent(&self) -> Option<Id>;
    fn parent_set(&mut self, id: Id);
    fn parent_set_none(&mut self);
    fn children(&self) -> Vec<Id>;
    fn children_ref_mut(&mut self) -> &mut Vec<Id>;
}

/// provides basic node-reflection abiliy; no check
pub trait FlowBase {
    type Id: Default + Clone + Hash + Eq;
    type Node: Default + Clone + Node<Self::Id>;
    /// ensures root and returns it
    fn orphan(&self) -> Vec<Self::Id>;
    fn contains_node(&self, obj: &Self::Id) -> bool {
        self.node(obj).is_some()
    }
    fn node(&self, obj: &Self::Id) -> Option<&Self::Node>;
    fn node_mut(&mut self, obj: &Self::Id) -> Option<&mut Self::Node>;
    fn parent(&self, obj: &Self::Id) -> Option<Self::Id> {
        self.node(obj).map_or(None, |node| node.parent())
    }
    fn children(&self, obj: &Self::Id) -> Vec<Self::Id> {
        self.node(obj).map_or(Vec::new(), |node| node.children())
    }

    /// returns parent's children
    fn friends(&self, obj: &Self::Id) -> Vec<Self::Id> {
        self.parent(obj)
            .map_or(Vec::new(), |obj| self.children(&obj))
    }

    /// returns nth position in friends; None if not found in either way
    fn nth_friend(&self, obj: &Self::Id) -> Option<usize> {
        self.friends(obj).into_iter().position(|id| &id == obj)
    }

    /// returns owned children
    fn children_owned(&self, obj: &Self::Id) -> Vec<Self::Id> {
        self.children(obj)
            .into_iter()
            .filter_map(|id| {
                if self.parent(&id) == Some(obj.clone()) {
                    Some(id)
                } else {
                    None
                }
            })
            .collect()
    }

    /// judge whether the obj is owned by the owner
    fn is_owned(&self, obj: &Self::Id, owner: &Self::Id) -> bool {
        self.parent(obj).map_or(false, |id| &id == owner)
            && self.children(owner).contains(obj)
    }

    /// judge whether the obj is *purely* linked from the owner
    fn is_linked(&self, obj: &Self::Id, owner: &Self::Id) -> bool {
        self.parent(obj).map_or(true, |id| &id != owner)
            && self.children(owner).contains(obj)
    }

    /// returns all the offspring of a node, not including itself
    fn node_offspring_set(&self, obj: &Self::Id) -> HashSet<Self::Id> {
        let mut visit_set = HashSet::new();
        let mut final_set = HashSet::new();
        visit_set.insert(obj.clone());
        while !visit_set.is_empty() {
            let mut wait_set = HashSet::new();
            for obj in visit_set.iter() {
                let children =
                    self.node(&obj).map(|x| x.children()).unwrap_or_default();
                wait_set.extend(children);
            }
            final_set.extend(wait_set.iter().cloned());
            visit_set.clear();
            visit_set.extend(wait_set);
        }
        final_set
    }

    /// returns all the nodes owned by a node, including itself
    fn node_ownership_set(&self, obj: &Self::Id) -> HashSet<Self::Id> {
        let mut visit_set = HashSet::new();
        let mut final_set = HashSet::new();
        if self.contains_node(obj) {
            visit_set.insert(obj.clone());
            final_set.insert(obj.clone());
        }
        while !visit_set.is_empty() {
            let mut wait_set = HashSet::new();
            for obj in visit_set.iter() {
                let children =
                    self.node(&obj).map(|x| x.children()).unwrap_or_default();
                let set: Vec<Self::Id> = children
                    .into_iter()
                    .filter_map(|id| {
                        self.node(&id)
                            .map(|node| {
                                if node.parent() == Some(obj.clone()) {
                                    Some(id)
                                } else {
                                    None
                                }
                            })
                            .flatten()
                    })
                    .collect();
                wait_set.extend(set);
            }
            final_set.extend(wait_set.iter().cloned());
            visit_set.clear();
            visit_set.extend(wait_set);
        }
        final_set
    }
}

/// checks the Flow's properties and see whether they hold
pub trait FlowCheck {
    fn check(&self) -> Result<(), (FlowError, String)>;
    /// panics if anything went wrong. Iff in debug state.
    fn check_assert(&self) {
        if cfg!(debug_assertions) {
            if let Err((err, current)) = self.check() {
                panic!("{:?}{}", err, current)
            }
        }
    }
}

/// provides hashmap functionality
pub trait FlowMap: FlowBase + FlowCheck {
    /// inserts a node; returns err if id exists.
    fn grow(&mut self, obj: Self::Node) -> Result<Self::Id, FlowError>;

    /// removes a node; returns err if id not found under root
    fn erase(&mut self, obj: &Self::Id) -> Result<Self::Node, FlowError>;
}

/// provides ability to link nodes; graph-ish
pub trait FlowLink: FlowBase + FlowCheck {
    /// randomly ensures the link of a node to another; won't change if aleady has the node as child
    fn link(
        &mut self,
        obj: &Self::Id,
        owner: &Self::Id,
        nth: usize,
    ) -> Result<(), FlowError> {
        if !self.contains_node(obj) {
            Err(FlowError::NotExistObj)?
        }
        let res = self
            .node_mut(owner)
            .map(|owner| {
                if owner.children().contains(obj) {
                    return Ok(());
                    // owner.children_ref_mut().retain(|id| id != obj)
                }
                if nth > owner.children().len() {
                    Err(FlowError::InvalidLen)?
                }
                owner.children_ref_mut().insert(nth, obj.clone());
                Ok(())
            })
            .unwrap_or(Err(FlowError::NotExistOwner));
        self.check_assert();
        res
    }

    fn link_push(
        &mut self,
        obj: &Self::Id,
        owner: &Self::Id,
    ) -> Result<(), FlowError> {
        let nth = self.node(owner).map_or(0, |node| node.children().len());
        let res = self.link(obj, owner, nth);
        self.check_assert();
        res
    }
    /// detaches a node from a non-owner link
    fn detach(
        &mut self,
        obj: &Self::Id,
        owner: &Self::Id,
    ) -> Result<(), FlowError> {
        if !self.contains_node(obj) {
            Err(FlowError::NotExistObj)?
        }
        let res = self
            .node_mut(owner)
            .map(|owner| {
                if !owner.children().contains(obj) {
                    Err(FlowError::AbandonedChild)?
                }
                owner.children_ref_mut().retain(|x| x != obj);
                Ok(())
            })
            .unwrap_or(Err(FlowError::NotExistOwner));
        self.check_assert();
        res
    }
}

/// provides ability to devote / own nodes; tree-ish
pub trait FlowDevote: FlowBase + FlowLink + FlowCheck {
    /// appoints and ensures an owner; also links to owner; won't do anything if aleady has the node as child
    fn devote(
        &mut self,
        obj: &Self::Id,
        owner: &Self::Id,
        nth: usize,
    ) -> Result<(), FlowError> {
        let res = self.link(obj, owner, nth).and_then(|_| {
            self.node_mut(obj)
                .map(|obj| {
                    obj.parent_set(owner.clone());
                    Ok(())
                })
                .unwrap_or(Err(FlowError::NotExistObj))
        });
        self.check_assert();
        res
    }

    fn devote_push(
        &mut self,
        obj: &Self::Id,
        owner: &Self::Id,
    ) -> Result<(), FlowError> {
        let res = self.link_push(obj, owner).and_then(|_| {
            self.node_mut(obj)
                .map_or(Err(FlowError::NotExistObj), |obj| {
                    obj.parent_set(owner.clone());
                    Ok(())
                })
        });
        self.check_assert();
        res
    }

    /// removes ownership; also detaches
    fn decay(&mut self, obj: &Self::Id) -> Result<(), FlowError> {
        let owner = self.node(obj).map(|x| x.parent());
        // Not owned by anyone
        if let Some(None) = owner {
            return Ok(());
        }
        let owner = owner.flatten();
        let res = self
            .node_mut(obj)
            .map_or(Err(FlowError::NotExistObj), |obj| {
                obj.parent_set_none();
                Ok(())
            })
            .and_then(|_| {
                owner.map_or(Err(FlowError::NotExistOwner), |owner| {
                    self.detach(obj, &owner)
                })
            });
        self.check_assert();
        res
    }

    /// decay before devote
    fn devote_loyal(
        &mut self,
        obj: &Self::Id,
        owner: &Self::Id,
        nth: usize,
    ) -> Result<(), FlowError> {
        self.decay(&obj)?;
        self.devote(&obj, &owner, nth)
    }

    /// decay before devote
    fn devote_loyal_push(
        &mut self,
        obj: &Self::Id,
        owner: &Self::Id,
    ) -> Result<(), FlowError> {
        self.decay(&obj)?;
        self.devote_push(&obj, &owner)
    }
}

/// provides ability to cut (undock) and copy (snap) a flow from a node and paste it to another node (dock)
pub trait FlowDock: FlowDevote + FlowCheck + Sized {
    /// adds all the nodes in another flow to self and mounts all orphan nodes to the designated node
    ///
    /// Err if:
    /// 1. Owner not found.
    /// 2. Node exists in current flow.
    fn dock_unordered(
        &mut self,
        owner: &Self::Id,
        flow: Self,
    ) -> Result<(), FlowError> {
        self.dock(owner, flow.orphan(), flow)
    }
    fn dock(
        &mut self,
        owner: &Self::Id,
        vec: Vec<Self::Id>,
        flow: Self,
    ) -> Result<(), FlowError>;
    /// moves all the nodes under the designated node out of the current flow and unmounts them
    ///
    /// Err if:
    /// 1. Obj not found.
    /// 2. Node linked by other nodes.
    fn undock_impl(
        &mut self,
        obj: &Self::Id,
        owned: bool,
    ) -> Result<(Self, Vec<Self::Id>), FlowError>;
    fn undock(
        &mut self,
        obj: &Self::Id,
    ) -> Result<(Self, Vec<Self::Id>), FlowError> {
        self.undock_impl(obj, false)
    }
    fn undock_owned(
        &mut self,
        obj: &Self::Id,
    ) -> Result<(Self, Vec<Self::Id>), FlowError> {
        self.undock_impl(obj, true)
    }
    /// clones all the nodes linked under the designated node and unmounts the clone
    ///
    /// Err if:
    /// 1. Obj not found.
    fn snap(&self, obj: &Self::Id) -> Result<(Self, Vec<Self::Id>), FlowError>;
    /// clones all the nodes owned under the designated node and unmounts the clone
    ///
    /// Err if:
    /// 1. Obj not found.
    fn snap_owned(
        &self,
        obj: &Self::Id,
    ) -> Result<(Self, Vec<Self::Id>), FlowError>;
}

/// Direction under FlowView:
///
/// - Forward - Down
/// - Backward - Up
/// - Ascend - Left
/// - Descend - Right
#[derive(Debug, Copy, Clone)]
pub enum Direction {
    Forward,
    Backward,
    Ascend,
    Descend,
}

impl Direction {
    /// shift isize according to dir
    fn shift(&self) -> isize {
        use Direction::*;
        match self {
            Forward => 1,
            Backward => -1,
            _ => 0,
        }
    }

    /// bounded in [0, len)
    fn walk(&self, nth: usize, len: usize) -> Result<usize, ()> {
        let pos = nth as isize + self.shift();
        if pos < 0 {
            Err(())
        } else if (pos as usize) < len {
            Ok(pos as usize)
        } else {
            Err(())
        }
    }
}

/// provides ability to move around in flow
pub trait FlowShift: FlowBase + FlowDevote {
    /// returns the obj in the corresponding relative position
    fn shuttle(
        &self,
        obj: &Self::Id,
        dir: Direction,
    ) -> Result<Self::Id, FlowError> {
        use Direction::*;
        match dir {
            Forward | Backward => {
                let friends = self.friends(obj);
                let nth = if let Some(nth) =
                    friends.iter().position(|id| id == obj)
                {
                    nth
                } else {
                    Err(FlowError::AbandonedChild)?
                };
                let len = friends.len();
                let walk =
                    dir.walk(nth, len).map_err(|_| FlowError::InvalidLen)?;
                Ok(friends[walk].clone())
            }
            Ascend => {
                let candidate = self.parent(obj);
                let res = candidate.map_or(obj.clone(), |id| id);
                Ok(res)
            }
            Descend => {
                let candidate = self.children(obj).get(0).cloned();
                let res = candidate.map_or(obj.clone(), |id| id);
                Ok(res)
            }
        }
    }

    /// iteratively shuttles within the flow
    fn shuttle_iter(
        &self,
        obj: &Self::Id,
        dir: Direction,
    ) -> Result<Self::Id, FlowError> {
        use Direction::*;
        match dir {
            Forward | Backward => self.shuttle(obj, dir).map_or_else(
                |_| Ok(self.parent(obj).unwrap_or(obj.clone())),
                |id| Ok(id),
            ),
            Ascend | Descend => self.shuttle(obj, dir),
        }
    }

    /// alters the node position by the corresponding relative position, within a single node
    fn migrate(
        &mut self,
        obj: &Self::Id,
        dir: Direction,
    ) -> Result<(), FlowError> {
        use Direction::*;
        if !self.contains_node(obj) {
            Err(FlowError::NotExistObj)?
        }
        match dir {
            Forward | Backward => {
                let owner = self.parent(obj).ok_or(FlowError::NotExistObj)?;
                let nth =
                    self.nth_friend(obj).ok_or(FlowError::AbandonedChild)?;
                let len = self.friends(&owner).len();
                let walk =
                    dir.walk(nth, len).map_err(|_| FlowError::InvalidLen)?;
                self.decay(obj)?;
                self.devote(obj, &owner, walk)?
            }
            Ascend => {
                let parent = self.parent(obj).ok_or(FlowError::NotExistObj)?;
                let owner =
                    self.parent(&parent).ok_or(FlowError::IsOrphaned)?;
                let nth = self
                    .nth_friend(&parent)
                    .ok_or(FlowError::AbandonedChild)?
                    + 1;
                self.decay(obj)?;
                self.devote(obj, &owner, nth)?
            }
            Descend => Err(FlowError::InvalidDir)?,
        }
        self.check_assert();
        Ok(())
    }

    /// alters the node position by the corresponding relative position, iteratively within the flow
    fn migrate_iter(
        &mut self,
        obj: &Self::Id,
        dir: Direction,
    ) -> Result<(), FlowError> {
        use Direction::*;
        match dir {
            Forward | Backward => self.migrate(obj, dir).map_or_else(
                |e| {
                    if let FlowError::InvalidLen = e {
                        self.migrate(obj, Ascend)
                    } else {
                        Err(e)
                    }
                },
                |v| Ok(v),
            ),
            Ascend | Descend => self.migrate(obj, dir),
        }
    }
}

/// Represents all possible Errors in Flow Operations
#[derive(Debug)]
pub enum FlowError {
    NotExistObj,
    NotExistOwner,
    InvalidLen,
    ExistGrow,
    ExistDock,
    OwnerDetach,
    LinkedUndock,
    InvalidDir,
    /// certain operations requires node to be orphaned
    NotOrphaned,
    /// certain operations requires node to be unorphaned
    IsOrphaned,

    NodeIdNotMatch,
    NotExistParent,
    NotExistChild,
    /// potential parent doesn't have the child
    AbandonedChild,
}

/// The overall `Flow` trait, checking whether anything is missing.
pub trait Flow:
    FlowBase + FlowCheck + FlowMap + FlowLink + FlowDevote + FlowDock + FlowShift
{
}