#!/usr/bin/env python3
"""
binary_search.py - find a trading date in a large sorted CSV by binary search
on byte positions (O(log n), constant memory).

Part of the Kibot data tooling: https://www.kibot.com/file-format/binary-search-algorithm.html

Expected input: no header row, first field is the date as MM/DD/YYYY, lines
sorted by date ascending, terminated by "\\n" or "\\r\\n".

Requires Python 3.6+, standard library only.
"""

import os
from datetime import date, datetime
from enum import Enum


class PositionFileType(Enum):
    DAILY = 1
    INTRADAY = 2
    TICK = 3


DATE_FORMAT = "%m/%d/%Y"
DATE_LENGTH = 10
MAX_LINE_LENGTH = 1000


def find_position_in_file_binary(
    file_name,
    date_to_find,
    file_type=PositionFileType.TICK,
    find_next_match=False,
    debug_callback=None,
    error_callback=None,
):
    """
    Find the byte offset of the first line whose date matches `date_to_find`.

    Args:
        file_name: Path to the CSV file.
        date_to_find: A datetime.date (or datetime.datetime) to look for.
        file_type: PositionFileType; sets the read buffer (500 bytes for DAILY,
            2000 for INTRADAY and TICK).
        find_next_match:
            False - exact match: return the first line of that date, or
                    (-1, None, file_size) if the date is not in the file.
            True  - lower bound: return the first line whose date is >=
                    date_to_find (lands on the next trading day when the
                    target is a weekend or holiday).
        debug_callback: Optional callback(message) for trace messages.
        error_callback: Optional callback(message, exception) for non-fatal errors.

    Returns:
        (position, found_date, file_size), where position is the byte offset of
        the start of the line and found_date is a datetime.date. On a miss:
        (-1, None, file_size). On an unreadable file or invalid argument:
        (-1, None, 0).
    """

    def debug(message):
        if debug_callback:
            debug_callback(message)

    def error(message, exception=None):
        if error_callback:
            error_callback(message, exception)

    if date_to_find is None:
        error("Date to find is None")
        return -1, None, 0
    if isinstance(date_to_find, datetime):
        date_to_find = date_to_find.date()
    elif not isinstance(date_to_find, date):
        error("date_to_find must be a datetime.date or datetime.datetime")
        return -1, None, 0

    buffer_size = 500 if file_type == PositionFileType.DAILY else 2000
    debug(f"Searching {os.path.basename(file_name)} for {date_to_find}, buffer {buffer_size}")

    try:
        with open(file_name, "rb") as stream:
            file_size = os.path.getsize(file_name)
            low, high = 0, file_size
            found_position = -1
            found_date = None

            while low <= high:
                mid = low + ((high - low) // 2)
                base = 0 if mid == 0 else mid - 1
                stream.seek(base)
                data = stream.read(buffer_size)
                if not data:
                    high = mid - 1
                    continue
                at_eof = base + len(data) >= file_size

                # latin-1 maps one byte to one character, so text offsets are byte offsets
                text = data.decode("latin-1")

                line_start = 0
                if mid > 0:
                    newline_pos = text.find("\n")
                    if newline_pos == -1:
                        if at_eof:
                            high = mid - 1
                            continue
                        if buffer_size < MAX_LINE_LENGTH:
                            buffer_size *= 2
                            continue
                        high = mid - 1
                        continue
                    line_start = newline_pos + 1

                line_end = text.find("\n", line_start)
                if line_end == -1:
                    if not at_eof:
                        # the line is cut off by the end of the buffer: read more, do not guess
                        if buffer_size < MAX_LINE_LENGTH * 2:
                            buffer_size *= 2
                            continue
                        high = mid - 1
                        continue
                    line_end = len(text)

                date_str = text[line_start : line_start + DATE_LENGTH]
                try:
                    line_date = datetime.strptime(date_str, DATE_FORMAT).date()
                except ValueError as e:
                    error(f"Failed to parse date '{date_str}' at position {mid}", e)
                    high = mid - 1
                    continue

                if line_date >= date_to_find:
                    # candidate; keep looking left for an earlier line of the same date
                    found_position = base + line_start
                    found_date = line_date
                    high = mid - 1
                else:
                    low = mid + 1

            if found_position < 0:
                debug("No position found")
                return -1, None, file_size
            if not find_next_match and found_date != date_to_find:
                debug(f"Exact date not present; next date is {found_date}")
                return -1, None, file_size

            debug(f"Found {found_date} at byte {found_position}")
            return found_position, found_date, file_size

    except Exception as e:
        error("Error in find_position_in_file_binary", e)
        return -1, None, 0
