use std::marker::PhantomData;
use std::ops::Deref;

// A reference-counted pointer.
pub unsafe trait RcPtr {
    fn new<T>(t: T) -> Self;
    unsafe fn clone<T>(&self) -> Self;
    unsafe fn deref<T>(&self) -> &T;
}

// Construct a type which wraps a reference-counted pointer (Rc or Arc), and
// implements RcPtr.
macro_rules! impl_rc_ptr {
    ($name:ident, $type_param:ident, $typ:ty, $new:path) => {
        struct $name {
            inner: *mut (),
        }

        impl $name {
            unsafe fn inner<$type_param>(&self) -> &$typ {
                &*(self.inner as *const $typ)
            }
        }

        unsafe impl RcPtr for $name {
            fn new<$type_param>(t: $type_param) -> Self {
                let inner = Box::new($new(t));
                // let inner = Box::new($typ::new(t));
                $name {
                    inner: Box::into_raw(inner) as *mut (),
                }
            }

            unsafe fn clone<$type_param>(&self) -> Self {
                let inner: &$typ = self.inner();
                let new_inner: $typ = inner.clone();
                let new_inner = Box::new(new_inner);
                $name {
                    inner: Box::into_raw(new_inner) as *mut (),
                }
            }

            unsafe fn deref<$type_param>(&self) -> &$type_param {
                let inner: &$typ = self.inner();
                inner.deref()
            }
        }
    };
}

impl_rc_ptr!(SingleThreadedRc, T, std::rc::Rc<T>, std::rc::Rc::<T>::new);
impl_rc_ptr!(
    MultiThreadedRc,
    T,
    std::sync::Arc<T>,
    std::sync::Arc::<T>::new
);

// Instead of writing the native-HKT R<T>, write RcWrapper<R, T>.
struct RcWrapper<R: RcPtr, T> {
    rc: R,
    _marker: PhantomData<T>,
}

impl<R: RcPtr, T> RcWrapper<R, T> {
    fn new(t: T) -> Self {
        RcWrapper {
            rc: R::new::<T>(t),
            _marker: PhantomData,
        }
    }
}

impl<R: RcPtr, T> Clone for RcWrapper<R, T> {
    fn clone(&self) -> Self {
        RcWrapper {
            rc: unsafe { self.rc.clone::<T>() },
            _marker: PhantomData,
        }
    }
}

impl<R: RcPtr, T> Deref for RcWrapper<R, T> {
    type Target = T;
    fn deref(&self) -> &T {
        unsafe { self.rc.deref() }
    }
}

mod tree {
    use super::*;

    use std::fmt::{self, Debug, Formatter};

    // A tree data structure with user-specified thread-safety.
    pub struct Tree<R: RcPtr, T> {
        root: Option<RcWrapper<R, TreeNode<R, T>>>,
        _marker: PhantomData<T>,
    }

    struct TreeNode<R: RcPtr, T> {
        val: T,
        left: Option<RcWrapper<R, TreeNode<R, T>>>,
        right: Option<RcWrapper<R, TreeNode<R, T>>>,
    }

    impl<R: RcPtr, T: Debug> Debug for Tree<R, T> {
        fn fmt(&self, f: &mut Formatter) -> Result<(), fmt::Error> {
            if let Some(root) = self.root.as_ref() {
                write!(f, "{:?}", root.deref())
            } else {
                write!(f, "{{}}")
            }
        }
    }

    impl<R: RcPtr, T: Debug> Debug for TreeNode<R, T> {
        fn fmt(&self, f: &mut Formatter) -> Result<(), fmt::Error> {
            write!(f, "{{ val: {:?}", self.val)?;
            if let Some(left) = self.left.as_ref() {
                write!(f, ", left: {:?}", left.deref())?;
            }
            if let Some(right) = self.right.as_ref() {
                write!(f, ", right: {:?}", right.deref())?;
            }
            write!(f, " }}")
        }
    }

    pub fn test_tree<R: RcPtr, T: Debug, F: FnMut() -> T>(mut new_t: F) {
        let left = TreeNode::<R, _> {
            val: new_t(),
            left: None,
            right: None,
        };
        let right = TreeNode::<R, _> {
            val: new_t(),
            left: None,
            right: None,
        };
        let tree = Tree {
            root: Some(RcWrapper::new(TreeNode {
                val: new_t(),
                left: Some(RcWrapper::new(left)),
                right: Some(RcWrapper::new(right)),
            })),
            _marker: PhantomData,
        };
        println!("{:?}", tree);
    }
}

fn main() {
    use tree::test_tree;

    let mut ctr = 0;
    test_tree::<SingleThreadedRc, usize, _>(|| {
        ctr += 1;
        ctr
    });
    test_tree::<SingleThreadedRc, String, _>(|| {
        ctr += 1;
        format!("{}", ctr)
    });
    test_tree::<MultiThreadedRc, usize, _>(|| {
        ctr += 1;
        ctr
    });
    test_tree::<MultiThreadedRc, String, _>(|| {
        ctr += 1;
        format!("{}", ctr)
    });
}