import random
import threading


FILE = '/tmp/foobarbaz.tmp'

LIST = []
LOCK = threading.Lock()
LINES_READ = 0
READER_FINISHED = False
FILTERED_UNTIL = 0
FILTER_FINISHED = False
SORTED_UNTIL = 1


def initialize_file(path):
    lines = 1_000_000
    values = lines / 100

    try:
        with open(path, 'xt', encoding='ascii') as file:
            lines = ('{:05X}\n'.format(random.randrange(0, values)) for _ in range(lines))
            file.write(''.join(lines))
        return True
    except FileExistsError:
        return False


def reader_main():
    global LINES_READ, READER_FINISHED
    initialize_file(FILE)

    with open(FILE, 'rt', encoding='ascii') as file:
        while True:
            line = file.readline()
            if not line:
                break
            LIST.append(line)
            LINES_READ += 1

    LOCK.acquire()
    READER_FINISHED = True
    LOCK.release()


def filter_main():
    global FILTERED_UNTIL, FILTER_FINISHED

    while True:
        try:
            LOCK.acquire()

            item = LIST[FILTERED_UNTIL]

            if item == '00000\n':
                LIST.pop(FILTERED_UNTIL)
            else:
                FILTERED_UNTIL += 1

        except IndexError:
            if READER_FINISHED:
                FILTER_FINISHED = True
                break
        finally:
            LOCK.release()


def sorter_main():
    global SORTED_UNTIL

    while True:
        if SORTED_UNTIL >= FILTERED_UNTIL and not FILTER_FINISHED:
            continue

        try:
            item = LIST[SORTED_UNTIL]
        except IndexError:
            break

        begin, end = 0, SORTED_UNTIL
        middle = (begin + end) // 2

        while True:
            item_in_middle = LIST[middle]
            insert_before = item < item_in_middle
            if begin == middle:
                break
            elif insert_before:
                end = middle
            else:
                begin = middle
            middle = (begin + end) // 2

        LOCK.acquire()
        LIST.pop(SORTED_UNTIL)
        LIST.insert(middle if insert_before else middle + 1, item)
        LOCK.release()

        SORTED_UNTIL += 1


def monitor_main():
    import time
    while True:
        print(LINES_READ, FILTERED_UNTIL, SORTED_UNTIL)
        time.sleep(5)


def main():
    reader = threading.Thread(target=reader_main)
    reader.start()

    filter_ = threading.Thread(target=filter_main)
    filter_.start()

    sorter = threading.Thread(target=sorter_main)
    sorter.start()

    monitor = threading.Thread(target=monitor_main, daemon=True)
    monitor.start()

    reader.join()
    filter_.join()
    sorter.join()

    print(''.join(LIST), end='')

    with open(FILE, 'rt', encoding='ascii') as file:
        lines = file.readlines()
    lines = list(sorted(l for l in lines if l != '00000\n'))

    print(LIST == lines)

    return LIST != lines


if __name__ == '__main__':
    exit(main())