//! Reachability store for efficient ancestor/descendant queries.
//!
//! Uses interval-based reachability trees to provide O(1) reachability queries
//! after O(n) preprocessing. Based on the algorithm described in the GHOSTDAG paper.
//!
//! The key insight is assigning each block an interval [start, end] such that
//! block A is an ancestor of block B iff A.interval contains B.interval.

use crate::BlockId;
use hashbrown::HashMap;
use parking_lot::RwLock;
use serde::{Deserialize, Serialize};
use thiserror::Error;

/// An interval assigned to a block for reachability queries.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct ReachabilityInterval {
    /// Start of the interval (inclusive).
    pub start: u64,
    /// End of the interval (inclusive).
    pub end: u64,
}

impl ReachabilityInterval {
    /// Creates a new interval.
    pub fn new(start: u64, end: u64) -> Self {
        debug_assert!(start <= end);
        ReachabilityInterval { start, end }
    }

    /// Creates an empty/invalid interval.
    pub fn empty() -> Self {
        ReachabilityInterval { start: 0, end: 0 }
    }

    /// Returns true if this interval contains another interval.
    pub fn contains(&self, other: &ReachabilityInterval) -> bool {
        self.start <= other.start && other.end <= self.end
    }

    /// Returns true if this interval overlaps with another.
    pub fn overlaps(&self, other: &ReachabilityInterval) -> bool {
        self.start <= other.end && other.start <= self.end
    }

    /// Returns the size of the interval.
    pub fn size(&self) -> u64 {
        self.end - self.start + 1
    }

    /// Returns true if the interval is valid.
    pub fn is_valid(&self) -> bool {
        self.start <= self.end
    }
}

impl Default for ReachabilityInterval {
    fn default() -> Self {
        Self::empty()
    }
}

/// Data stored for each block in the reachability store.
#[derive(Clone, Debug, Serialize, Deserialize)]
pub struct ReachabilityData {
    /// The interval assigned to this block.
    pub interval: ReachabilityInterval,
    /// Parent in the spanning tree (for interval allocation).
    pub tree_parent: Option<BlockId>,
    /// Children in the spanning tree.
    pub tree_children: Vec<BlockId>,
    /// Height in the spanning tree.
    pub height: u64,
}

impl ReachabilityData {
    /// Creates new reachability data.
    pub fn new(interval: ReachabilityInterval, tree_parent: Option<BlockId>, height: u64) -> Self {
        ReachabilityData {
            interval,
            tree_parent,
            tree_children: Vec::new(),
            height,
        }
    }
}

/// Store for reachability data with O(1) query performance.
pub struct ReachabilityStore {
    /// Reachability data for each block.
    data: RwLock<HashMap<BlockId, ReachabilityData>>,
    /// Current allocation counter for intervals.
    counter: RwLock<u64>,
}

impl ReachabilityStore {
    /// Creates a new reachability store with the genesis block.
    pub fn new(genesis_id: BlockId) -> Self {
        let mut data = HashMap::new();

        // Genesis gets the entire interval space
        let genesis_data = ReachabilityData::new(
            ReachabilityInterval::new(1, u64::MAX / 2), // Leave room for growth
            None,
            0,
        );
        data.insert(genesis_id, genesis_data);

        ReachabilityStore {
            data: RwLock::new(data),
            counter: RwLock::new(2), // Start after genesis
        }
    }

    /// Checks if block `ancestor` is in the past of block `descendant`.
    /// Returns true if ancestor is an ancestor of descendant.
    pub fn is_ancestor(
        &self,
        ancestor: &BlockId,
        descendant: &BlockId,
    ) -> Result<bool, ReachabilityError> {
        if ancestor == descendant {
            return Ok(true); // A block is its own ancestor
        }

        let data = self.data.read();

        let ancestor_data = data
            .get(ancestor)
            .ok_or(ReachabilityError::BlockNotFound(*ancestor))?;
        let descendant_data = data
            .get(descendant)
            .ok_or(ReachabilityError::BlockNotFound(*descendant))?;

        Ok(ancestor_data.interval.contains(&descendant_data.interval))
    }

    /// Checks if two blocks are in each other's anticone (neither is ancestor of other).
    pub fn is_anticone(
        &self,
        block_a: &BlockId,
        block_b: &BlockId,
    ) -> Result<bool, ReachabilityError> {
        if block_a == block_b {
            return Ok(false);
        }

        let a_ancestor_of_b = self.is_ancestor(block_a, block_b)?;
        let b_ancestor_of_a = self.is_ancestor(block_b, block_a)?;

        Ok(!a_ancestor_of_b && !b_ancestor_of_a)
    }

    /// Adds a new block to the reachability store.
    ///
    /// The block must have at least one parent already in the store.
    /// We choose one parent as the "selected parent" for the spanning tree.
    pub fn add_block(
        &self,
        block_id: BlockId,
        selected_parent: BlockId,
        _all_parents: &[BlockId], // Used for validation
    ) -> Result<(), ReachabilityError> {
        let mut data = self.data.write();
        let mut counter = self.counter.write();

        if data.contains_key(&block_id) {
            return Err(ReachabilityError::BlockExists(block_id));
        }

        // Get parent data
        let parent_data = data
            .get(&selected_parent)
            .ok_or(ReachabilityError::ParentNotFound(selected_parent))?
            .clone();

        // Allocate interval within parent's interval
        // We need to split the parent's remaining space
        let (new_interval, parent_needs_realloc) = self.allocate_interval(&parent_data, &data)?;

        // Create new block's data
        let new_data =
            ReachabilityData::new(new_interval, Some(selected_parent), parent_data.height + 1);

        // Update parent's tree children
        if let Some(parent) = data.get_mut(&selected_parent) {
            parent.tree_children.push(block_id);
        }

        data.insert(block_id, new_data);
        *counter += 1;

        // If parent needs reallocation, trigger a reindex
        // (In production, this would be handled more efficiently)
        if parent_needs_realloc {
            tracing::debug!("Reallocation needed for block {:?}", selected_parent);
            // For now, we'll just log - full reindex is expensive
        }

        Ok(())
    }

    /// Allocates an interval for a new child block.
    fn allocate_interval(
        &self,
        parent_data: &ReachabilityData,
        all_data: &HashMap<BlockId, ReachabilityData>,
    ) -> Result<(ReachabilityInterval, bool), ReachabilityError> {
        let parent_interval = &parent_data.interval;

        // Find the rightmost interval used by existing children
        let mut max_used = parent_interval.start;
        for child_id in &parent_data.tree_children {
            if let Some(child_data) = all_data.get(child_id) {
                max_used = max_used.max(child_data.interval.end);
            }
        }

        // New interval starts after all existing children
        let new_start = max_used + 1;

        // Check if we have space
        if new_start > parent_interval.end {
            // No space left, need reallocation
            return Ok((
                ReachabilityInterval::new(new_start, new_start),
                true, // Needs reallocation
            ));
        }

        // Allocate a reasonable chunk of the remaining space
        let remaining = parent_interval.end - new_start;
        let allocation_size = remaining / 4; // Leave room for more children
        let allocation_size = allocation_size.max(1); // At least 1

        let new_interval = ReachabilityInterval::new(new_start, new_start + allocation_size);

        Ok((new_interval, false))
    }

    /// Gets the interval for a block.
    pub fn get_interval(&self, block_id: &BlockId) -> Option<ReachabilityInterval> {
        self.data.read().get(block_id).map(|d| d.interval)
    }

    /// Gets the tree parent of a block.
    pub fn get_tree_parent(&self, block_id: &BlockId) -> Option<BlockId> {
        self.data.read().get(block_id).and_then(|d| d.tree_parent)
    }

    /// Gets the height of a block in the spanning tree.
    pub fn get_height(&self, block_id: &BlockId) -> Option<u64> {
        self.data.read().get(block_id).map(|d| d.height)
    }

    /// Finds the lowest common ancestor of two blocks.
    pub fn lowest_common_ancestor(
        &self,
        block_a: &BlockId,
        block_b: &BlockId,
    ) -> Result<BlockId, ReachabilityError> {
        if block_a == block_b {
            return Ok(*block_a);
        }

        let data = self.data.read();

        // Get chains to root
        let chain_a = self.get_chain_to_root(block_a, &data)?;
        let chain_b = self.get_chain_to_root(block_b, &data)?;

        // Find first common block
        for a in &chain_a {
            for b in &chain_b {
                if a == b {
                    return Ok(*a);
                }
            }
        }

        Err(ReachabilityError::NoCommonAncestor(*block_a, *block_b))
    }

    /// Gets the chain of tree parents from a block to the root.
    fn get_chain_to_root(
        &self,
        block_id: &BlockId,
        data: &HashMap<BlockId, ReachabilityData>,
    ) -> Result<Vec<BlockId>, ReachabilityError> {
        let mut chain = vec![*block_id];
        let mut current = *block_id;

        while let Some(block_data) = data.get(&current) {
            if let Some(parent) = block_data.tree_parent {
                chain.push(parent);
                current = parent;
            } else {
                break; // Reached root
            }
        }

        Ok(chain)
    }

    /// Returns the number of blocks in the store.
    pub fn len(&self) -> usize {
        self.data.read().len()
    }

    /// Returns true if the store is empty.
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Checks if a block exists in the store.
    pub fn contains(&self, block_id: &BlockId) -> bool {
        self.data.read().contains_key(block_id)
    }
}

impl std::fmt::Debug for ReachabilityStore {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("ReachabilityStore")
            .field("block_count", &self.len())
            .finish()
    }
}

/// Errors that can occur with reachability queries.
#[derive(Debug, Error)]
pub enum ReachabilityError {
    #[error("Block not found: {0}")]
    BlockNotFound(BlockId),

    #[error("Block already exists: {0}")]
    BlockExists(BlockId),

    #[error("Parent not found: {0}")]
    ParentNotFound(BlockId),

    #[error("No common ancestor between {0} and {1}")]
    NoCommonAncestor(BlockId, BlockId),

    #[error("Interval allocation failed")]
    AllocationFailed,

    #[error("Reindex required")]
    ReindexRequired,
}

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

    fn make_block_id(n: u8) -> BlockId {
        let mut bytes = [0u8; 32];
        bytes[0] = n;
        Hash256::from_bytes(bytes)
    }

    #[test]
    fn test_interval_contains() {
        let outer = ReachabilityInterval::new(10, 100);
        let inner = ReachabilityInterval::new(20, 80);
        let outside = ReachabilityInterval::new(101, 150);

        assert!(outer.contains(&inner));
        assert!(!inner.contains(&outer));
        assert!(!outer.contains(&outside));
    }

    #[test]
    fn test_genesis_creation() {
        let genesis = make_block_id(0);
        let store = ReachabilityStore::new(genesis);

        assert!(store.contains(&genesis));
        assert_eq!(store.len(), 1);

        let interval = store.get_interval(&genesis).unwrap();
        assert!(interval.is_valid());
        assert!(interval.size() > 0);
    }

    #[test]
    fn test_add_block() {
        let genesis = make_block_id(0);
        let store = ReachabilityStore::new(genesis);

        let block1 = make_block_id(1);
        store.add_block(block1, genesis, &[genesis]).unwrap();

        assert!(store.contains(&block1));
        assert_eq!(store.len(), 2);

        // Block1's interval should be contained in genesis's interval
        let genesis_interval = store.get_interval(&genesis).unwrap();
        let block1_interval = store.get_interval(&block1).unwrap();
        assert!(genesis_interval.contains(&block1_interval));
    }

    #[test]
    fn test_is_ancestor() {
        let genesis = make_block_id(0);
        let store = ReachabilityStore::new(genesis);

        let block1 = make_block_id(1);
        let block2 = make_block_id(2);

        store.add_block(block1, genesis, &[genesis]).unwrap();
        store.add_block(block2, block1, &[block1]).unwrap();

        // Genesis is ancestor of all
        assert!(store.is_ancestor(&genesis, &block1).unwrap());
        assert!(store.is_ancestor(&genesis, &block2).unwrap());

        // Block1 is ancestor of block2
        assert!(store.is_ancestor(&block1, &block2).unwrap());

        // Block2 is not ancestor of genesis
        assert!(!store.is_ancestor(&block2, &genesis).unwrap());
        assert!(!store.is_ancestor(&block2, &block1).unwrap());

        // Self-ancestry
        assert!(store.is_ancestor(&genesis, &genesis).unwrap());
    }

    #[test]
    fn test_is_anticone() {
        let genesis = make_block_id(0);
        let store = ReachabilityStore::new(genesis);

        let block1 = make_block_id(1);
        let block2 = make_block_id(2);

        // Two blocks with same parent (parallel)
        store.add_block(block1, genesis, &[genesis]).unwrap();
        store.add_block(block2, genesis, &[genesis]).unwrap();

        // They should be in each other's anticone
        assert!(store.is_anticone(&block1, &block2).unwrap());
        assert!(store.is_anticone(&block2, &block1).unwrap());

        // Genesis is not in anticone with either
        assert!(!store.is_anticone(&genesis, &block1).unwrap());
        assert!(!store.is_anticone(&genesis, &block2).unwrap());
    }

    #[test]
    fn test_lowest_common_ancestor() {
        let genesis = make_block_id(0);
        let store = ReachabilityStore::new(genesis);

        let block1 = make_block_id(1);
        let block2 = make_block_id(2);
        let block3 = make_block_id(3);

        store.add_block(block1, genesis, &[genesis]).unwrap();
        store.add_block(block2, genesis, &[genesis]).unwrap();
        store.add_block(block3, block1, &[block1]).unwrap();

        // LCA of block1 and block2 is genesis
        let lca = store.lowest_common_ancestor(&block1, &block2).unwrap();
        assert_eq!(lca, genesis);

        // LCA of block3 and block1 is block1
        let lca = store.lowest_common_ancestor(&block3, &block1).unwrap();
        assert_eq!(lca, block1);

        // LCA of same block is itself
        let lca = store.lowest_common_ancestor(&block1, &block1).unwrap();
        assert_eq!(lca, block1);
    }

    #[test]
    fn test_height() {
        let genesis = make_block_id(0);
        let store = ReachabilityStore::new(genesis);

        let block1 = make_block_id(1);
        let block2 = make_block_id(2);

        store.add_block(block1, genesis, &[genesis]).unwrap();
        store.add_block(block2, block1, &[block1]).unwrap();

        assert_eq!(store.get_height(&genesis), Some(0));
        assert_eq!(store.get_height(&block1), Some(1));
        assert_eq!(store.get_height(&block2), Some(2));
    }
}
