use std::collections::{HashMap, HashSet};
use std::fmt;

use crate::error::Error;

/// A single token in a parsed wildcard pattern.
#[derive(Debug, Clone, PartialEq, Eq)]
enum PatternToken {
    /// Matches a literal topic segment exactly.
    Literal(String),
    /// `*` — matches exactly one segment.
    Single,
    /// `>` — matches one or more trailing segments (must be last token).
    MultiTrail,
}

/// Compiled wildcard pattern for fast matching against concrete topic names.
///
/// Topic names are dot-delimited. Two wildcard tokens are supported:
/// - `*` matches exactly one segment between dots
/// - `>` matches one or more trailing segments (must be the last token)
///
/// A `TopicPattern` with no wildcard tokens is an exact-match pattern
/// and uses a fast string-equality check in `matches()`.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct TopicPattern {
    tokens: Vec<PatternToken>,
    is_wildcard: bool,
    /// The original pattern string, preserved for display/logging.
    raw: String,
}

impl TopicPattern {
    /// Parse a subscription topic string into a compiled pattern.
    ///
    /// Returns `Error::InvalidTopic` for invalid syntax:
    /// - Empty string
    /// - Empty segments between dots (`orders..foo`)
    /// - `>` not in the last position (`orders.>.foo`)
    /// - Segment longer than 255 bytes
    /// - Total pattern longer than 255 bytes
    pub fn parse(topic: &str) -> Result<Self, Error> {
        if topic.is_empty() {
            return Err(Error::InvalidTopic("pattern cannot be empty".into()));
        }
        if topic.len() > 255 {
            return Err(Error::InvalidTopic("pattern exceeds 255 byte limit".into()));
        }

        let segments: Vec<&str> = topic.split('.').collect();
        let mut tokens = Vec::with_capacity(segments.len());
        let mut is_wildcard = false;

        for (i, seg) in segments.iter().enumerate() {
            if seg.is_empty() {
                return Err(Error::InvalidTopic(
                    "empty segment (double dot) in pattern".into(),
                ));
            }
            match *seg {
                ">" => {
                    if i != segments.len() - 1 {
                        return Err(Error::InvalidTopic(
                            "'>' must be the last token in a pattern".into(),
                        ));
                    }
                    tokens.push(PatternToken::MultiTrail);
                    is_wildcard = true;
                }
                "*" => {
                    tokens.push(PatternToken::Single);
                    is_wildcard = true;
                }
                literal => {
                    tokens.push(PatternToken::Literal(literal.to_owned()));
                }
            }
        }

        Ok(Self {
            tokens,
            is_wildcard,
            raw: topic.to_owned(),
        })
    }

    /// Returns `true` if this pattern contains any wildcard tokens (`*` or `>`).
    pub fn is_wildcard(&self) -> bool {
        self.is_wildcard
    }

    /// Returns the original pattern string.
    pub fn raw(&self) -> &str {
        &self.raw
    }

    /// Test whether a concrete topic name matches this pattern.
    ///
    /// For non-wildcard patterns, this is a simple string equality check.
    /// For wildcard patterns, segments are matched token-by-token.
    pub fn matches(&self, topic: &str) -> bool {
        // Fast path: exact match patterns use string comparison.
        if !self.is_wildcard {
            return self.raw == topic;
        }

        let segments: Vec<&str> = topic.split('.').collect();
        self.match_segments(&segments, 0, 0)
    }

    fn match_segments(&self, segments: &[&str], pat_idx: usize, seg_idx: usize) -> bool {
        // If we've consumed all pattern tokens, we must have consumed all segments.
        if pat_idx >= self.tokens.len() {
            return seg_idx >= segments.len();
        }

        match &self.tokens[pat_idx] {
            PatternToken::MultiTrail => {
                // `>` matches one or more trailing segments.
                seg_idx < segments.len()
            }
            PatternToken::Single => {
                // `*` matches exactly one segment.
                if seg_idx >= segments.len() {
                    return false;
                }
                self.match_segments(segments, pat_idx + 1, seg_idx + 1)
            }
            PatternToken::Literal(lit) => {
                if seg_idx >= segments.len() {
                    return false;
                }
                if segments[seg_idx] != lit.as_str() {
                    return false;
                }
                self.match_segments(segments, pat_idx + 1, seg_idx + 1)
            }
        }
    }
}

impl std::fmt::Display for TopicPattern {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.raw)
    }
}

/// Returns `true` if any dot-delimited segment is exactly `*` or `>`.
///
/// This is a segment-aware check: `my*data` returns `false` (not a wildcard
/// segment), while `orders.*` returns `true`.
pub fn contains_wildcard(topic: &str) -> bool {
    topic.split('.').any(|seg| seg == "*" || seg == ">")
}

/// Opaque identifier for a subscription in the trie.
///
/// This is a lightweight handle used by the trie to track which subscriptions
/// match a given topic. Phase 20.3 will map these to actual subscription state
/// in the namespace manager.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct SubscriptionId(pub u64);

impl fmt::Display for SubscriptionId {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.0)
    }
}

/// A node in the subscription trie.
///
/// Each node represents a position in the dot-delimited topic hierarchy.
/// Subscriptions are registered at terminal nodes matching their pattern.
///
/// Subscriber lists use `HashSet` to prevent duplicate registrations and
/// provide O(1) removal.
#[derive(Debug, Default)]
struct TrieNode {
    /// Literal children: segment string → child node.
    children: HashMap<String, TrieNode>,
    /// Single-wildcard (`*`) child — matches any one segment.
    star_child: Option<Box<TrieNode>>,
    /// Multi-wildcard (`>`) terminal subscribers — matches one or more trailing segments.
    gt_subscribers: HashSet<SubscriptionId>,
    /// Exact-match terminal subscribers at this node.
    exact_subscribers: HashSet<SubscriptionId>,
}

impl TrieNode {
    /// Returns true if this node has no children and no subscribers.
    fn is_empty(&self) -> bool {
        self.children.is_empty()
            && self.star_child.is_none()
            && self.gt_subscribers.is_empty()
            && self.exact_subscribers.is_empty()
    }
}

/// Trie for efficient wildcard subscription matching.
///
/// Given a concrete topic name, returns all subscription IDs whose patterns
/// match that topic. Supports NATS-style wildcards:
/// - `*` matches exactly one segment
/// - `>` matches one or more trailing segments
///
/// # Performance
///
/// `matching()` walks the trie once per topic segment, branching at `*` nodes.
/// For N registered patterns and a topic with K segments, worst case is O(K)
/// per pattern that shares a prefix — but in practice the trie prunes most
/// branches early, yielding sub-microsecond lookups even with thousands of
/// patterns.
#[derive(Debug, Default)]
pub struct SubscriptionTrie {
    root: TrieNode,
    /// Total number of (pattern, sub_id) registrations in the trie.
    count: usize,
}

impl SubscriptionTrie {
    /// Create an empty trie.
    pub fn new() -> Self {
        Self::default()
    }

    /// Register a subscription pattern in the trie.
    ///
    /// The same `sub_id` can be inserted with different patterns.
    /// Inserting the same `(pattern, sub_id)` pair twice is a no-op
    /// (subscriber sets are deduplicated).
    pub fn insert(&mut self, pattern: &TopicPattern, sub_id: SubscriptionId) {
        let mut node = &mut self.root;

        for token in &pattern.tokens {
            match token {
                PatternToken::Literal(s) => {
                    node = node.children.entry(s.clone()).or_default();
                }
                PatternToken::Single => {
                    node = node
                        .star_child
                        .get_or_insert_with(|| Box::new(TrieNode::default()));
                }
                PatternToken::MultiTrail => {
                    // `>` is always the last token — register here and return.
                    if node.gt_subscribers.insert(sub_id) {
                        self.count += 1;
                    }
                    return;
                }
            }
        }

        // Reached the end of the pattern without a `>` — this is an exact terminal.
        if node.exact_subscribers.insert(sub_id) {
            self.count += 1;
        }
    }

    /// Remove a subscription from the trie.
    ///
    /// Walks the pattern path and removes `sub_id` from the terminal node.
    /// Prunes empty branches on the way back up.
    ///
    /// Returns `true` if the subscription was found and removed.
    pub fn remove(&mut self, pattern: &TopicPattern, sub_id: SubscriptionId) -> bool {
        let removed = Self::remove_recursive(&mut self.root, &pattern.tokens, 0, sub_id);
        if removed {
            self.count -= 1;
        }
        removed
    }

    fn remove_recursive(
        node: &mut TrieNode,
        tokens: &[PatternToken],
        depth: usize,
        sub_id: SubscriptionId,
    ) -> bool {
        if depth >= tokens.len() {
            return node.exact_subscribers.remove(&sub_id);
        }

        match &tokens[depth] {
            PatternToken::Literal(s) => {
                let Some(child) = node.children.get_mut(s.as_str()) else {
                    return false;
                };
                let removed = Self::remove_recursive(child, tokens, depth + 1, sub_id);
                // Prune empty branch (re-lookup is needed since we borrowed mutably above).
                if removed && node.children.get(s.as_str()).is_some_and(|c| c.is_empty()) {
                    node.children.remove(s.as_str());
                }
                removed
            }
            PatternToken::Single => {
                let Some(child) = node.star_child.as_mut() else {
                    return false;
                };
                let removed = Self::remove_recursive(child, tokens, depth + 1, sub_id);
                if removed && node.star_child.as_ref().is_some_and(|c| c.is_empty()) {
                    node.star_child = None;
                }
                removed
            }
            PatternToken::MultiTrail => node.gt_subscribers.remove(&sub_id),
        }
    }

    /// Find all subscriptions matching a concrete topic name.
    ///
    /// The topic must be a concrete name (no wildcards). Returns all
    /// subscription IDs whose patterns match.
    pub fn matching(&self, topic: &str) -> Vec<SubscriptionId> {
        let segments: Vec<&str> = topic.split('.').collect();
        let mut results = Vec::new();
        Self::collect_matches(&self.root, &segments, 0, &mut results);
        results
    }

    fn collect_matches(
        node: &TrieNode,
        segments: &[&str],
        depth: usize,
        results: &mut Vec<SubscriptionId>,
    ) {
        // `>` at this node matches one or more remaining segments.
        if depth < segments.len() {
            results.extend(&node.gt_subscribers);
        }

        if depth >= segments.len() {
            // No more segments — collect exact matches at this node.
            results.extend(&node.exact_subscribers);
            return;
        }

        let seg = segments[depth];

        // Follow literal child.
        if let Some(child) = node.children.get(seg) {
            Self::collect_matches(child, segments, depth + 1, results);
        }

        // Follow `*` child (matches this one segment).
        if let Some(child) = &node.star_child {
            Self::collect_matches(child, segments, depth + 1, results);
        }
    }

    /// Returns `true` if the trie has no registered subscriptions.
    pub fn is_empty(&self) -> bool {
        self.count == 0
    }

    /// Returns the total number of (pattern, subscription) registrations.
    pub fn len(&self) -> usize {
        self.count
    }
}

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

    // ── Parse valid patterns ──────────────────────────────────────────

    #[test]
    fn parse_exact() {
        let p = TopicPattern::parse("orders.us").unwrap();
        assert!(!p.is_wildcard());
        assert_eq!(p.raw(), "orders.us");
    }

    #[test]
    fn parse_single_wildcard() {
        let p = TopicPattern::parse("orders.*").unwrap();
        assert!(p.is_wildcard());
    }

    #[test]
    fn parse_multi_trail() {
        let p = TopicPattern::parse("orders.>").unwrap();
        assert!(p.is_wildcard());
    }

    #[test]
    fn parse_combined() {
        let p = TopicPattern::parse("events.*.created").unwrap();
        assert!(p.is_wildcard());
    }

    #[test]
    fn parse_bare_star() {
        let p = TopicPattern::parse("*").unwrap();
        assert!(p.is_wildcard());
    }

    #[test]
    fn parse_bare_gt() {
        let p = TopicPattern::parse(">").unwrap();
        assert!(p.is_wildcard());
    }

    #[test]
    fn parse_single_segment_literal() {
        let p = TopicPattern::parse("orders").unwrap();
        assert!(!p.is_wildcard());
    }

    #[test]
    fn parse_no_dots() {
        let p = TopicPattern::parse("my-topic-name").unwrap();
        assert!(!p.is_wildcard());
    }

    #[test]
    fn parse_deep_pattern() {
        let p = TopicPattern::parse("a.b.c.d.e.*.f").unwrap();
        assert!(p.is_wildcard());
    }

    #[test]
    fn parse_multiple_stars() {
        let p = TopicPattern::parse("*.*.created").unwrap();
        assert!(p.is_wildcard());
    }

    // ── Parse invalid patterns ────────────────────────────────────────

    #[test]
    fn parse_empty_rejected() {
        assert!(TopicPattern::parse("").is_err());
    }

    #[test]
    fn parse_double_dot_rejected() {
        assert!(TopicPattern::parse("orders..foo").is_err());
    }

    #[test]
    fn parse_leading_dot_rejected() {
        assert!(TopicPattern::parse(".orders").is_err());
    }

    #[test]
    fn parse_trailing_dot_rejected() {
        assert!(TopicPattern::parse("orders.").is_err());
    }

    #[test]
    fn parse_just_dots_rejected() {
        assert!(TopicPattern::parse("..").is_err());
    }

    #[test]
    fn parse_gt_not_last_rejected() {
        assert!(TopicPattern::parse("orders.>.foo").is_err());
    }

    #[test]
    fn parse_gt_in_middle_rejected() {
        assert!(TopicPattern::parse("a.>.b.c").is_err());
    }

    #[test]
    fn parse_too_long_rejected() {
        let long = "a".repeat(256);
        assert!(TopicPattern::parse(&long).is_err());
    }

    // ── Matching: single wildcard (*) ──────────────────────────────────

    #[test]
    fn star_matches_one_segment() {
        let p = TopicPattern::parse("orders.*").unwrap();
        assert!(p.matches("orders.us"));
        assert!(p.matches("orders.eu"));
    }

    #[test]
    fn star_does_not_match_zero_segments() {
        let p = TopicPattern::parse("orders.*").unwrap();
        assert!(!p.matches("orders"));
    }

    #[test]
    fn star_does_not_match_two_segments() {
        let p = TopicPattern::parse("orders.*").unwrap();
        assert!(!p.matches("orders.us.east"));
    }

    #[test]
    fn star_does_not_match_different_prefix() {
        let p = TopicPattern::parse("orders.*").unwrap();
        assert!(!p.matches("events.us"));
    }

    #[test]
    fn bare_star_matches_any_single_token() {
        let p = TopicPattern::parse("*").unwrap();
        assert!(p.matches("orders"));
        assert!(p.matches("events"));
        assert!(!p.matches("orders.us"));
    }

    // ── Matching: multi-trail wildcard (>) ─────────────────────────────

    #[test]
    fn gt_matches_one_trailing_segment() {
        let p = TopicPattern::parse("orders.>").unwrap();
        assert!(p.matches("orders.us"));
    }

    #[test]
    fn gt_matches_multiple_trailing_segments() {
        let p = TopicPattern::parse("orders.>").unwrap();
        assert!(p.matches("orders.us.east"));
        assert!(p.matches("orders.eu.west.1"));
    }

    #[test]
    fn gt_does_not_match_prefix_only() {
        let p = TopicPattern::parse("orders.>").unwrap();
        assert!(!p.matches("orders"));
    }

    #[test]
    fn gt_does_not_match_different_prefix() {
        let p = TopicPattern::parse("orders.>").unwrap();
        assert!(!p.matches("events.us"));
    }

    #[test]
    fn bare_gt_matches_any_topic() {
        let p = TopicPattern::parse(">").unwrap();
        assert!(p.matches("orders"));
        assert!(p.matches("orders.us"));
        assert!(p.matches("a.b.c.d.e"));
    }

    // ── Matching: combined patterns ────────────────────────────────────

    #[test]
    fn combined_star_literal() {
        let p = TopicPattern::parse("events.*.created").unwrap();
        assert!(p.matches("events.user.created"));
        assert!(p.matches("events.order.created"));
        assert!(!p.matches("events.created"));
        assert!(!p.matches("events.user.updated"));
        assert!(!p.matches("events.user.order.created"));
    }

    #[test]
    fn multiple_stars() {
        let p = TopicPattern::parse("*.*.created").unwrap();
        assert!(p.matches("events.user.created"));
        assert!(p.matches("logs.app.created"));
        assert!(!p.matches("events.created"));
        assert!(!p.matches("a.b.c.created"));
    }

    #[test]
    fn deep_star() {
        let p = TopicPattern::parse("a.b.c.d.e.*.f").unwrap();
        assert!(p.matches("a.b.c.d.e.x.f"));
        assert!(!p.matches("a.b.c.d.e.f"));
        assert!(!p.matches("a.b.c.d.e.x.y.f"));
    }

    // ── Matching: exact patterns ───────────────────────────────────────

    #[test]
    fn exact_pattern_matches_same_string() {
        let p = TopicPattern::parse("orders.us").unwrap();
        assert!(p.matches("orders.us"));
    }

    #[test]
    fn exact_pattern_does_not_match_different() {
        let p = TopicPattern::parse("orders.us").unwrap();
        assert!(!p.matches("orders.eu"));
        assert!(!p.matches("orders"));
        assert!(!p.matches("orders.us.east"));
    }

    #[test]
    fn exact_single_segment() {
        let p = TopicPattern::parse("orders").unwrap();
        assert!(p.matches("orders"));
        assert!(!p.matches("events"));
        assert!(!p.matches("orders.us"));
    }

    // ── contains_wildcard helper ───────────────────────────────────────

    #[test]
    fn contains_wildcard_star() {
        assert!(contains_wildcard("orders.*"));
        assert!(contains_wildcard("*"));
    }

    #[test]
    fn contains_wildcard_gt() {
        assert!(contains_wildcard("orders.>"));
        assert!(contains_wildcard(">"));
    }

    #[test]
    fn contains_wildcard_none() {
        assert!(!contains_wildcard("orders.us"));
        assert!(!contains_wildcard("my-topic"));
    }

    #[test]
    fn contains_wildcard_embedded_chars_not_segments() {
        // `*` and `>` embedded within a segment are NOT wildcard segments.
        assert!(!contains_wildcard("my*data"));
        assert!(!contains_wildcard("value>10"));
        assert!(!contains_wildcard("a.b*c.d"));
    }

    // ── Display ────────────────────────────────────────────────────────

    #[test]
    fn display_shows_raw() {
        let p = TopicPattern::parse("orders.*").unwrap();
        assert_eq!(format!("{p}"), "orders.*");
    }

    // ══════════════════════════════════════════════════════════════════
    // SubscriptionTrie tests
    // ══════════════════════════════════════════════════════════════════

    fn sid(n: u64) -> SubscriptionId {
        SubscriptionId(n)
    }

    fn sorted(mut v: Vec<SubscriptionId>) -> Vec<SubscriptionId> {
        v.sort_by_key(|s| s.0);
        v
    }

    // ── Empty trie ───────────────────────────────────────────────────

    #[test]
    fn trie_empty_returns_no_matches() {
        let trie = SubscriptionTrie::new();
        assert!(trie.matching("orders.us").is_empty());
        assert!(trie.matching("anything").is_empty());
        assert!(trie.is_empty());
    }

    // ── Single pattern insert + match ────────────────────────────────

    #[test]
    fn trie_exact_match() {
        let mut trie = SubscriptionTrie::new();
        let p = TopicPattern::parse("orders.us").unwrap();
        trie.insert(&p, sid(1));

        assert_eq!(trie.matching("orders.us"), vec![sid(1)]);
        assert!(trie.matching("orders.eu").is_empty());
        assert!(trie.matching("orders").is_empty());
        assert!(trie.matching("orders.us.east").is_empty());
    }

    #[test]
    fn trie_star_match() {
        let mut trie = SubscriptionTrie::new();
        let p = TopicPattern::parse("orders.*").unwrap();
        trie.insert(&p, sid(1));

        assert_eq!(trie.matching("orders.us"), vec![sid(1)]);
        assert_eq!(trie.matching("orders.eu"), vec![sid(1)]);
        assert!(trie.matching("orders").is_empty());
        assert!(trie.matching("orders.us.east").is_empty());
        assert!(trie.matching("events.us").is_empty());
    }

    #[test]
    fn trie_gt_match() {
        let mut trie = SubscriptionTrie::new();
        let p = TopicPattern::parse("orders.>").unwrap();
        trie.insert(&p, sid(1));

        assert_eq!(trie.matching("orders.us"), vec![sid(1)]);
        assert_eq!(trie.matching("orders.us.east"), vec![sid(1)]);
        assert_eq!(trie.matching("orders.eu.west.1"), vec![sid(1)]);
        assert!(trie.matching("orders").is_empty());
        assert!(trie.matching("events.us").is_empty());
    }

    #[test]
    fn trie_bare_star() {
        let mut trie = SubscriptionTrie::new();
        let p = TopicPattern::parse("*").unwrap();
        trie.insert(&p, sid(1));

        assert_eq!(trie.matching("orders"), vec![sid(1)]);
        assert_eq!(trie.matching("events"), vec![sid(1)]);
        assert!(trie.matching("orders.us").is_empty());
    }

    #[test]
    fn trie_bare_gt() {
        let mut trie = SubscriptionTrie::new();
        let p = TopicPattern::parse(">").unwrap();
        trie.insert(&p, sid(1));

        assert_eq!(trie.matching("orders"), vec![sid(1)]);
        assert_eq!(trie.matching("orders.us"), vec![sid(1)]);
        assert_eq!(trie.matching("a.b.c.d.e"), vec![sid(1)]);
    }

    #[test]
    fn trie_combined_star_literal() {
        let mut trie = SubscriptionTrie::new();
        let p = TopicPattern::parse("events.*.created").unwrap();
        trie.insert(&p, sid(1));

        assert_eq!(trie.matching("events.user.created"), vec![sid(1)]);
        assert_eq!(trie.matching("events.order.created"), vec![sid(1)]);
        assert!(trie.matching("events.created").is_empty());
        assert!(trie.matching("events.user.updated").is_empty());
        assert!(trie.matching("events.user.order.created").is_empty());
    }

    #[test]
    fn trie_deep_pattern() {
        let mut trie = SubscriptionTrie::new();
        let p = TopicPattern::parse("a.b.c.d.e.*.f").unwrap();
        trie.insert(&p, sid(1));

        assert_eq!(trie.matching("a.b.c.d.e.x.f"), vec![sid(1)]);
        assert!(trie.matching("a.b.c.d.e.f").is_empty());
        assert!(trie.matching("a.b.c.d.e.x.y.f").is_empty());
    }

    // ── Multiple patterns ────────────────────────────────────────────

    #[test]
    fn trie_multiple_different_patterns() {
        let mut trie = SubscriptionTrie::new();
        trie.insert(&TopicPattern::parse("orders.*").unwrap(), sid(1));
        trie.insert(&TopicPattern::parse("events.*").unwrap(), sid(2));

        assert_eq!(trie.matching("orders.us"), vec![sid(1)]);
        assert_eq!(trie.matching("events.click"), vec![sid(2)]);
        assert!(trie.matching("logs.info").is_empty());
    }

    #[test]
    fn trie_multiple_subs_same_pattern() {
        let mut trie = SubscriptionTrie::new();
        let p = TopicPattern::parse("orders.*").unwrap();
        trie.insert(&p, sid(1));
        trie.insert(&p, sid(2));

        let results = sorted(trie.matching("orders.us"));
        assert_eq!(results, vec![sid(1), sid(2)]);
    }

    // ── Overlapping patterns ─────────────────────────────────────────

    #[test]
    fn trie_star_and_gt_overlap() {
        let mut trie = SubscriptionTrie::new();
        trie.insert(&TopicPattern::parse("orders.*").unwrap(), sid(1));
        trie.insert(&TopicPattern::parse("orders.>").unwrap(), sid(2));

        // Both match orders.us
        let results = sorted(trie.matching("orders.us"));
        assert_eq!(results, vec![sid(1), sid(2)]);

        // Only > matches orders.us.east
        assert_eq!(trie.matching("orders.us.east"), vec![sid(2)]);

        // Neither matches orders
        assert!(trie.matching("orders").is_empty());
    }

    #[test]
    fn trie_exact_and_star_overlap() {
        let mut trie = SubscriptionTrie::new();
        trie.insert(&TopicPattern::parse("orders.us").unwrap(), sid(1));
        trie.insert(&TopicPattern::parse("orders.*").unwrap(), sid(2));

        // Both match orders.us
        let results = sorted(trie.matching("orders.us"));
        assert_eq!(results, vec![sid(1), sid(2)]);

        // Only * matches orders.eu
        assert_eq!(trie.matching("orders.eu"), vec![sid(2)]);
    }

    #[test]
    fn trie_exact_star_and_gt_all_overlap() {
        let mut trie = SubscriptionTrie::new();
        trie.insert(&TopicPattern::parse("orders.us").unwrap(), sid(1));
        trie.insert(&TopicPattern::parse("orders.*").unwrap(), sid(2));
        trie.insert(&TopicPattern::parse("orders.>").unwrap(), sid(3));

        // All three match orders.us
        let results = sorted(trie.matching("orders.us"));
        assert_eq!(results, vec![sid(1), sid(2), sid(3)]);

        // * and > match orders.eu
        let results = sorted(trie.matching("orders.eu"));
        assert_eq!(results, vec![sid(2), sid(3)]);

        // Only > matches orders.us.east
        assert_eq!(trie.matching("orders.us.east"), vec![sid(3)]);
    }

    #[test]
    fn trie_gt_at_different_depths() {
        let mut trie = SubscriptionTrie::new();
        trie.insert(&TopicPattern::parse(">").unwrap(), sid(1));
        trie.insert(&TopicPattern::parse("a.>").unwrap(), sid(2));
        trie.insert(&TopicPattern::parse("a.b.>").unwrap(), sid(3));

        // "a.b.c" matches all three
        let results = sorted(trie.matching("a.b.c"));
        assert_eq!(results, vec![sid(1), sid(2), sid(3)]);

        // "a.b" matches > and a.>
        let results = sorted(trie.matching("a.b"));
        assert_eq!(results, vec![sid(1), sid(2)]);

        // "a" matches only >
        assert_eq!(trie.matching("a"), vec![sid(1)]);

        // "x.y" matches only >
        assert_eq!(trie.matching("x.y"), vec![sid(1)]);
    }

    // ── Remove ───────────────────────────────────────────────────────

    #[test]
    fn trie_remove_exact() {
        let mut trie = SubscriptionTrie::new();
        let p = TopicPattern::parse("orders.us").unwrap();
        trie.insert(&p, sid(1));
        assert_eq!(trie.matching("orders.us"), vec![sid(1)]);

        assert!(trie.remove(&p, sid(1)));
        assert!(trie.matching("orders.us").is_empty());
        assert!(trie.is_empty());
    }

    #[test]
    fn trie_remove_star() {
        let mut trie = SubscriptionTrie::new();
        let p = TopicPattern::parse("orders.*").unwrap();
        trie.insert(&p, sid(1));

        assert!(trie.remove(&p, sid(1)));
        assert!(trie.matching("orders.us").is_empty());
        assert!(trie.is_empty());
    }

    #[test]
    fn trie_remove_gt() {
        let mut trie = SubscriptionTrie::new();
        let p = TopicPattern::parse("orders.>").unwrap();
        trie.insert(&p, sid(1));

        assert!(trie.remove(&p, sid(1)));
        assert!(trie.matching("orders.us").is_empty());
        assert!(trie.is_empty());
    }

    #[test]
    fn trie_remove_nonexistent_returns_false() {
        let mut trie = SubscriptionTrie::new();
        let p = TopicPattern::parse("orders.*").unwrap();
        trie.insert(&p, sid(1));

        // Wrong sub_id
        assert!(!trie.remove(&p, sid(99)));
        // Pattern still works
        assert_eq!(trie.matching("orders.us"), vec![sid(1)]);
    }

    #[test]
    fn trie_remove_from_empty_returns_false() {
        let mut trie = SubscriptionTrie::new();
        let p = TopicPattern::parse("orders.*").unwrap();
        assert!(!trie.remove(&p, sid(1)));
    }

    #[test]
    fn trie_remove_one_of_multiple_subs() {
        let mut trie = SubscriptionTrie::new();
        let p = TopicPattern::parse("orders.*").unwrap();
        trie.insert(&p, sid(1));
        trie.insert(&p, sid(2));
        trie.insert(&p, sid(3));

        assert!(trie.remove(&p, sid(2)));
        let results = sorted(trie.matching("orders.us"));
        assert_eq!(results, vec![sid(1), sid(3)]);
    }

    #[test]
    fn trie_remove_preserves_other_patterns() {
        let mut trie = SubscriptionTrie::new();
        trie.insert(&TopicPattern::parse("orders.*").unwrap(), sid(1));
        trie.insert(&TopicPattern::parse("events.*").unwrap(), sid(2));

        assert!(trie.remove(&TopicPattern::parse("orders.*").unwrap(), sid(1)));
        assert!(trie.matching("orders.us").is_empty());
        assert_eq!(trie.matching("events.click"), vec![sid(2)]);
    }

    #[test]
    fn trie_remove_preserves_sibling_at_same_depth() {
        let mut trie = SubscriptionTrie::new();
        // Two patterns sharing a prefix but diverging
        trie.insert(&TopicPattern::parse("a.b.c").unwrap(), sid(1));
        trie.insert(&TopicPattern::parse("a.b.d").unwrap(), sid(2));

        assert!(trie.remove(&TopicPattern::parse("a.b.c").unwrap(), sid(1)));
        assert!(trie.matching("a.b.c").is_empty());
        assert_eq!(trie.matching("a.b.d"), vec![sid(2)]);
    }

    // ── Branch pruning ───────────────────────────────────────────────

    #[test]
    fn trie_prune_cleans_empty_branches() {
        let mut trie = SubscriptionTrie::new();
        let p = TopicPattern::parse("a.b.c.d.e").unwrap();
        trie.insert(&p, sid(1));
        assert!(!trie.is_empty());

        assert!(trie.remove(&p, sid(1)));
        // After removing the only subscription, trie should be fully pruned.
        assert!(trie.is_empty());
    }

    #[test]
    fn trie_prune_does_not_remove_shared_branches() {
        let mut trie = SubscriptionTrie::new();
        trie.insert(&TopicPattern::parse("a.b.c").unwrap(), sid(1));
        trie.insert(&TopicPattern::parse("a.b.d").unwrap(), sid(2));

        // Remove one — "a.b" branch should remain for the other.
        assert!(trie.remove(&TopicPattern::parse("a.b.c").unwrap(), sid(1)));
        assert!(!trie.is_empty());
        assert_eq!(trie.matching("a.b.d"), vec![sid(2)]);
    }

    #[test]
    fn trie_prune_star_child() {
        let mut trie = SubscriptionTrie::new();
        let p = TopicPattern::parse("a.*.c").unwrap();
        trie.insert(&p, sid(1));

        assert!(trie.remove(&p, sid(1)));
        assert!(trie.is_empty());
    }

    // ── Edge cases ───────────────────────────────────────────────────

    #[test]
    fn trie_single_segment_topics() {
        let mut trie = SubscriptionTrie::new();
        trie.insert(&TopicPattern::parse("orders").unwrap(), sid(1));
        trie.insert(&TopicPattern::parse("*").unwrap(), sid(2));
        trie.insert(&TopicPattern::parse(">").unwrap(), sid(3));

        let results = sorted(trie.matching("orders"));
        assert_eq!(results, vec![sid(1), sid(2), sid(3)]);

        let results = sorted(trie.matching("events"));
        assert_eq!(results, vec![sid(2), sid(3)]);
    }

    #[test]
    fn trie_gt_requires_at_least_one_segment() {
        let mut trie = SubscriptionTrie::new();
        // "a.>" requires at least "a.X" — "a" alone should not match.
        trie.insert(&TopicPattern::parse("a.>").unwrap(), sid(1));

        assert!(trie.matching("a").is_empty());
        assert_eq!(trie.matching("a.b"), vec![sid(1)]);
    }

    #[test]
    fn trie_multiple_stars() {
        let mut trie = SubscriptionTrie::new();
        trie.insert(&TopicPattern::parse("*.*.created").unwrap(), sid(1));

        assert_eq!(trie.matching("events.user.created"), vec![sid(1)]);
        assert_eq!(trie.matching("logs.app.created"), vec![sid(1)]);
        assert!(trie.matching("events.created").is_empty());
        assert!(trie.matching("a.b.c.created").is_empty());
    }

    #[test]
    fn trie_subscription_id_display() {
        assert_eq!(format!("{}", sid(42)), "42");
    }

    // ── Duplicate insert idempotency ─────────────────────────────────

    #[test]
    fn trie_duplicate_insert_is_idempotent() {
        let mut trie = SubscriptionTrie::new();
        let p = TopicPattern::parse("orders.*").unwrap();
        trie.insert(&p, sid(1));
        trie.insert(&p, sid(1)); // duplicate

        assert_eq!(trie.len(), 1);
        assert_eq!(trie.matching("orders.us"), vec![sid(1)]);

        // Single remove clears it completely.
        assert!(trie.remove(&p, sid(1)));
        assert!(trie.is_empty());
        assert_eq!(trie.len(), 0);
    }

    #[test]
    fn trie_duplicate_insert_gt_is_idempotent() {
        let mut trie = SubscriptionTrie::new();
        let p = TopicPattern::parse("orders.>").unwrap();
        trie.insert(&p, sid(1));
        trie.insert(&p, sid(1));

        assert_eq!(trie.len(), 1);
        assert_eq!(trie.matching("orders.us"), vec![sid(1)]);
    }

    // ── len() ────────────────────────────────────────────────────────

    #[test]
    fn trie_len_tracks_insertions_and_removals() {
        let mut trie = SubscriptionTrie::new();
        assert_eq!(trie.len(), 0);

        trie.insert(&TopicPattern::parse("orders.*").unwrap(), sid(1));
        assert_eq!(trie.len(), 1);

        trie.insert(&TopicPattern::parse("events.*").unwrap(), sid(2));
        assert_eq!(trie.len(), 2);

        // Same sub_id, different pattern — counts as separate registration.
        trie.insert(&TopicPattern::parse("logs.>").unwrap(), sid(1));
        assert_eq!(trie.len(), 3);

        trie.remove(&TopicPattern::parse("orders.*").unwrap(), sid(1));
        assert_eq!(trie.len(), 2);

        trie.remove(&TopicPattern::parse("events.*").unwrap(), sid(2));
        assert_eq!(trie.len(), 1);

        trie.remove(&TopicPattern::parse("logs.>").unwrap(), sid(1));
        assert_eq!(trie.len(), 0);
        assert!(trie.is_empty());
    }

    #[test]
    fn trie_len_not_decremented_on_failed_remove() {
        let mut trie = SubscriptionTrie::new();
        trie.insert(&TopicPattern::parse("orders.*").unwrap(), sid(1));
        assert_eq!(trie.len(), 1);

        // Remove nonexistent — len unchanged.
        assert!(!trie.remove(&TopicPattern::parse("orders.*").unwrap(), sid(99)));
        assert_eq!(trie.len(), 1);

        // Remove wrong pattern — len unchanged.
        assert!(!trie.remove(&TopicPattern::parse("events.*").unwrap(), sid(1)));
        assert_eq!(trie.len(), 1);
    }
}
