use crate::line::{Line, parse_line};
use crate::options::{SortableDirective, TimelessPosition};
use regex::Regex;
use std::collections::BTreeMap;
use std::sync::LazyLock;

#[derive(Debug, Clone)]
struct Entry {
    lines: Vec<String>,
    date: Option<String>,
    time: Option<String>,
}

static TIME_HM_RE: LazyLock<Regex> = LazyLock::new(|| Regex::new(r"^(\d{1,2}):(\d{2})$").unwrap());

static TIME_HMS_RE: LazyLock<Regex> =
    LazyLock::new(|| Regex::new(r"^(\d{1,2}):(\d{2}):(\d{2})$").unwrap());

static ISO_DATETIME_RE: LazyLock<Regex> =
    LazyLock::new(|| Regex::new(r"^\d{4}-\d{2}-\d{2}[T ](\d{1,2}):(\d{2})(?::(\d{2}))?").unwrap());

static UNIX_TS_RE: LazyLock<Regex> = LazyLock::new(|| Regex::new(r"^(\d{10,16})$").unwrap());

pub fn parse_time(value: &str) -> Option<String> {
    let value = value.trim().trim_matches('"');
    if let Some(caps) = TIME_HMS_RE.captures(value) {
        return Some(format!(
            "{:02}:{}:{}",
            caps[1].parse::<u32>().ok()?,
            &caps[2],
            &caps[3]
        ));
    }
    if let Some(caps) = TIME_HM_RE.captures(value) {
        return Some(format!(
            "{:02}:{}:00",
            caps[1].parse::<u32>().ok()?,
            &caps[2]
        ));
    }
    if let Some(caps) = ISO_DATETIME_RE.captures(value) {
        let h: u32 = caps[1].parse().ok()?;
        let m = &caps[2];
        let s = caps.get(3).map_or("00", |c| c.as_str());
        return Some(format!("{h:02}:{m}:{s}"));
    }
    if let Some(caps) = UNIX_TS_RE.captures(value) {
        let digits: u64 = caps[1].parse().ok()?;
        // Check micros before millis
        let secs = if digits >= 1_000_000_000_000_000 {
            digits / 1_000_000
        } else if digits >= 1_000_000_000_000 {
            digits / 1_000
        } else {
            digits
        };
        let time_of_day = secs % 86400;
        let h = time_of_day / 3600;
        let m = (time_of_day % 3600) / 60;
        let s = time_of_day % 60;
        return Some(format!("{h:02}:{m:02}:{s:02}"));
    }
    None
}

fn is_continuation(line: &Line) -> bool {
    match line {
        Line::Posting { .. } | Line::MetaItem { .. } => true,
        Line::Comment { indent, .. } => !indent.is_empty(),
        _ => false,
    }
}

fn extract_date(line: &Line, exclude: &[SortableDirective]) -> Option<String> {
    match line {
        Line::TransactionHeader { date, .. }
            if !exclude.contains(&SortableDirective::Transaction) =>
        {
            Some(date.to_string())
        }
        Line::Balance { date, .. } if !exclude.contains(&SortableDirective::Balance) => {
            Some(date.to_string())
        }
        Line::Open { date, .. } if !exclude.contains(&SortableDirective::Open) => {
            Some(date.to_string())
        }
        Line::Close { date, .. } if !exclude.contains(&SortableDirective::Close) => {
            Some(date.to_string())
        }
        Line::Price { date, .. } if !exclude.contains(&SortableDirective::Price) => {
            Some(date.to_string())
        }
        Line::DateDirective { date, keyword, .. } => {
            let directive = match *keyword {
                "pad" => SortableDirective::Pad,
                "note" => SortableDirective::Note,
                "document" => SortableDirective::Document,
                "event" => SortableDirective::Event,
                "custom" => SortableDirective::Custom,
                "query" => SortableDirective::Query,
                "commodity" => SortableDirective::Commodity,
                _ => return None,
            };
            if !exclude.contains(&directive) {
                Some(date.to_string())
            } else {
                None
            }
        }
        _ => None,
    }
}

/// A segment is either a barrier, a blank line, or a sortable group of entries.
#[derive(Debug)]
enum Segment {
    Barrier(Vec<String>),
    Blank,
    Entries(Vec<Entry>),
}

/// Parse input into entries, grouping them into segments.
fn parse_segments(input: &str, exclude: &[SortableDirective]) -> Vec<Segment> {
    let raw_lines: Vec<&str> = input.lines().collect();
    let mut segments: Vec<Segment> = Vec::new();
    let mut current_entries: Vec<Entry> = Vec::new();
    let mut current_entry: Option<Entry> = None;

    let flush_entry = |current_entry: &mut Option<Entry>, current_entries: &mut Vec<Entry>| {
        if let Some(entry) = current_entry.take() {
            current_entries.push(entry);
        }
    };

    let flush_entries = |current_entries: &mut Vec<Entry>, segments: &mut Vec<Segment>| {
        if !current_entries.is_empty() {
            segments.push(Segment::Entries(std::mem::take(current_entries)));
        }
    };

    for raw in &raw_lines {
        let parsed = parse_line(raw);

        if matches!(parsed, Line::BlankLine) {
            flush_entry(&mut current_entry, &mut current_entries);
            flush_entries(&mut current_entries, &mut segments);
            segments.push(Segment::Blank);
            continue;
        }

        if matches!(parsed, Line::BlockDirective { .. }) {
            flush_entry(&mut current_entry, &mut current_entries);
            flush_entries(&mut current_entries, &mut segments);
            segments.push(Segment::Barrier(vec![raw.to_string()]));
            continue;
        }

        if is_continuation(&parsed) {
            if let Some(ref mut entry) = current_entry {
                if let Line::MetaItem { key, value, .. } = &parsed
                    && *key == "time"
                {
                    entry.time = parse_time(value);
                }
                entry.lines.push(raw.to_string());
            } else if let Some(Segment::Barrier(lines)) = segments.last_mut() {
                // Continuation line after a barrier — attach to the barrier
                lines.push(raw.to_string());
            } else {
                current_entry = Some(Entry {
                    lines: vec![raw.to_string()],
                    date: None,
                    time: None,
                });
            }
        } else {
            let date = extract_date(&parsed, exclude);
            if date.is_some() {
                // Dated directive — starts a new sortable entry
                flush_entry(&mut current_entry, &mut current_entries);
                current_entry = Some(Entry {
                    lines: vec![raw.to_string()],
                    date,
                    time: None,
                });
            } else {
                // Undated top-level line (comment, include, option, etc.) — treat as barrier
                flush_entry(&mut current_entry, &mut current_entries);
                flush_entries(&mut current_entries, &mut segments);
                segments.push(Segment::Barrier(vec![raw.to_string()]));
            }
        }
    }

    flush_entry(&mut current_entry, &mut current_entries);
    flush_entries(&mut current_entries, &mut segments);

    segments
}

fn sort_key(entry: &Entry, timeless: TimelessPosition) -> (&str, &str) {
    let time = match &entry.time {
        Some(t) => t.as_str(),
        None => match timeless {
            TimelessPosition::Begin => "",
            TimelessPosition::End => "\x7f",
            TimelessPosition::Keep => unreachable!("Keep uses sort_entries_keep, not the LIS path"),
        },
    };
    (entry.date.as_deref().unwrap_or(""), time)
}

fn can_go_before(a: &Entry, b: &Entry, timeless: TimelessPosition) -> bool {
    debug_assert!(
        timeless != TimelessPosition::Keep,
        "Keep uses sort_entries_keep"
    );
    match (&a.date, &b.date) {
        (Some(da), Some(db)) => {
            if da < db {
                return true;
            }
            if da > db {
                return false;
            }
            // Same date
            match (&a.time, &b.time) {
                (Some(ta), Some(tb)) => ta <= tb,
                (None, Some(_)) => timeless == TimelessPosition::Begin,
                (Some(_), None) => timeless == TimelessPosition::End,
                (None, None) => true,
            }
        }
        _ => true,
    }
}

fn split_sorted_unsorted(
    entries: &[Entry],
    timeless: TimelessPosition,
) -> (Vec<usize>, Vec<usize>) {
    if entries.is_empty() {
        return (vec![], vec![]);
    }

    // Patience sort for longest non-decreasing subsequence
    let mut tails: Vec<usize> = Vec::new();
    let mut predecessors: Vec<Option<usize>> = vec![None; entries.len()];

    for i in 0..entries.len() {
        let pos = tails.partition_point(|&t| can_go_before(&entries[t], &entries[i], timeless));

        if pos == tails.len() {
            tails.push(i);
        } else {
            tails[pos] = i;
        }

        if pos > 0 {
            predecessors[i] = Some(tails[pos - 1]);
        }
    }

    // Backtrack to recover LIS
    let mut lis_indices: Vec<usize> = Vec::new();
    let mut idx = *tails.last().unwrap();
    lis_indices.push(idx);
    while let Some(prev) = predecessors[idx] {
        lis_indices.push(prev);
        idx = prev;
    }
    lis_indices.reverse();

    let lis_set: std::collections::HashSet<usize> = lis_indices.iter().copied().collect();
    let unsorted: Vec<usize> = (0..entries.len())
        .filter(|i| !lis_set.contains(i))
        .collect();

    (lis_indices, unsorted)
}

fn merge_entries(
    entries: &[Entry],
    sorted_idx: &[usize],
    unsorted_idx: &[usize],
    timeless: TimelessPosition,
) -> Vec<usize> {
    if unsorted_idx.is_empty() {
        return sorted_idx.to_vec();
    }

    let mut to_insert: Vec<usize> = unsorted_idx.to_vec();
    to_insert
        .sort_by(|&a, &b| sort_key(&entries[a], timeless).cmp(&sort_key(&entries[b], timeless)));

    let mut result = Vec::with_capacity(entries.len());
    let mut si = 0;
    let mut ui = 0;

    while si < sorted_idx.len() && ui < to_insert.len() {
        let s = sorted_idx[si];
        let u = to_insert[ui];
        if can_go_before(&entries[u], &entries[s], timeless) {
            result.push(u);
            ui += 1;
        } else {
            result.push(s);
            si += 1;
        }
    }
    while si < sorted_idx.len() {
        result.push(sorted_idx[si]);
        si += 1;
    }
    while ui < to_insert.len() {
        result.push(to_insert[ui]);
        ui += 1;
    }

    result
}

fn sort_entries_keep(entries: Vec<Entry>, descending: bool) -> Vec<Entry> {
    // Step 1: Group entries by date, preserving insertion order within each group.
    let mut date_groups: BTreeMap<String, Vec<Entry>> = BTreeMap::new();
    for entry in entries {
        let key = entry.date.clone().unwrap_or_default();
        date_groups.entry(key).or_default().push(entry);
    }

    // Step 2: Determine date iteration order.
    let date_keys: Vec<String> = if descending {
        date_groups.keys().rev().cloned().collect()
    } else {
        date_groups.keys().cloned().collect()
    };

    // Step 3: For each date group, sort only timed entries via slot replacement.
    let mut result: Vec<Entry> = Vec::new();
    for date_key in date_keys {
        let mut group = date_groups.remove(&date_key).unwrap();

        // Collect indices of timed entries, sort by time.
        let mut timed_indices: Vec<usize> = group
            .iter()
            .enumerate()
            .filter(|(_, e)| e.time.is_some())
            .map(|(i, _)| i)
            .collect();
        timed_indices.sort_by(|&a, &b| {
            let ord = group[a].time.cmp(&group[b].time);
            if descending { ord.reverse() } else { ord }
        });

        // Build sorted timed entries via Option::take to avoid clones.
        let mut slots: Vec<Option<Entry>> = group.drain(..).map(Some).collect();
        let sorted_timed: Vec<Entry> = timed_indices
            .iter()
            .map(|&i| slots[i].take().unwrap())
            .collect();

        // Slot replacement: timeless entries stay in place, timed slots filled from sorted queue.
        let mut timed_iter = sorted_timed.into_iter();
        for slot in &mut slots {
            if slot.is_some() {
                result.push(slot.take().unwrap());
            } else {
                result.push(timed_iter.next().unwrap());
            }
        }
    }

    result
}

fn sort_entries(mut entries: Vec<Entry>, timeless: TimelessPosition) -> Vec<Entry> {
    if entries.len() <= 1 {
        return entries;
    }

    let (sorted_idx, unsorted_idx) = split_sorted_unsorted(&entries, timeless);
    if unsorted_idx.is_empty() {
        return entries;
    }

    let order = merge_entries(&entries, &sorted_idx, &unsorted_idx, timeless);

    // Reorder in-place using the index mapping
    let mut result = Vec::with_capacity(entries.len());
    // We need to move out of entries by index; use Option wrapper
    let mut slots: Vec<Option<Entry>> = entries.drain(..).map(Some).collect();
    for i in order {
        result.push(slots[i].take().unwrap());
    }
    result
}

pub fn sort_input(
    input: &str,
    descending: bool,
    timeless: TimelessPosition,
    exclude: &[SortableDirective],
) -> String {
    let segments = parse_segments(input, exclude);

    let mut output = String::new();

    #[derive(Debug)]
    enum CompartmentItem {
        Entries(Vec<Entry>),
        Blank,
    }

    let mut compartment_items: Vec<CompartmentItem> = Vec::new();

    let flush_compartment = |items: &mut Vec<CompartmentItem>,
                             output: &mut String,
                             descending: bool,
                             timeless: TimelessPosition| {
        // Collect all entries from the compartment
        let mut all_entries: Vec<Entry> = Vec::new();
        let mut separator_positions: Vec<usize> = Vec::new(); // after which entry index to insert blank

        for item in items.drain(..) {
            match item {
                CompartmentItem::Entries(entries) => {
                    all_entries.extend(entries);
                }
                CompartmentItem::Blank => {
                    if !all_entries.is_empty() {
                        separator_positions.push(all_entries.len());
                    } else {
                        // Leading blank
                        output.push('\n');
                    }
                }
            }
        }

        if all_entries.is_empty() {
            return;
        }

        let sorted = if timeless == TimelessPosition::Keep {
            sort_entries_keep(all_entries, descending)
        } else {
            // When descending, reverse() flips within-day order too,
            // so flip the timeless position to compensate.
            let effective_timeless = if descending {
                match timeless {
                    TimelessPosition::Begin => TimelessPosition::End,
                    TimelessPosition::End => TimelessPosition::Begin,
                    TimelessPosition::Keep => unreachable!(),
                }
            } else {
                timeless
            };
            let mut s = sort_entries(all_entries, effective_timeless);
            if descending {
                s.reverse();
            }
            s
        };

        // Build a set of entry indices (1-based) after which a blank line should appear,
        // preserving the original blank-line pattern from the input.
        let blank_after: std::collections::HashSet<usize> =
            separator_positions.iter().copied().collect();

        for (i, entry) in sorted.iter().enumerate() {
            for line in &entry.lines {
                output.push_str(line);
                output.push('\n');
            }
            if blank_after.contains(&(i + 1)) {
                output.push('\n');
            }
        }
    };

    for segment in segments {
        match segment {
            Segment::Barrier(lines) => {
                flush_compartment(&mut compartment_items, &mut output, descending, timeless);
                for line in &lines {
                    output.push_str(line);
                    output.push('\n');
                }
            }
            Segment::Blank => {
                compartment_items.push(CompartmentItem::Blank);
            }
            Segment::Entries(entries) => {
                compartment_items.push(CompartmentItem::Entries(entries));
            }
        }
    }
    flush_compartment(&mut compartment_items, &mut output, descending, timeless);

    // Preserve trailing newline behavior
    if !input.ends_with('\n') && output.ends_with('\n') {
        output.pop();
    }

    output
}
