from io import BytesIO
import os
import zlib
import sys
import atexit
from datetime import datetime, timedelta
from collections import deque

DEBUG = True
PHASE_I_READ_ADDR_BATCH_SIZE = 16384 * 8
TYPICAL_ADDR_BYTE_SIZE = len(b'111111111111111111112xT3273') + len(b'\n')
DUST_THRESHOLD = 10_000
CHUNK_MAX_COMPRESSED_BYTE_SIZE = 5 * (1024 ** 2)  # 7.5 Mb
CHUNK_MAX_BUF_ADDR_SIZE = 150_000
CHUNK_REFORGING_ADDR_THRESHOLD = 50_000
CHUNK_REFORGING_SIZE_THRESHOLD = 128 * 1024  # 128k
# TODO: what happens if MIN_ADDR_LEN is set to zero?
MIN_ADDR_LEN = 14  # bc1pfeessrawgf
MAX_ADDR_LEN = 256

filename = os.path.expanduser(sys.argv[-1])
assert os.path.exists(filename)

f_r = open(filename, 'rb')
f_w = open(filename, 'r+b')

class ReadComplete(Exception): pass
addresses_read = 0
def make_rrw():
    r_idx = w_idx = 0
    buf = deque()
    decomp = zlib.decompressobj(0b10000 | zlib.MAX_WBITS)

    if DEBUG is True:
        last_buffer_size_report_at = datetime.fromtimestamp(0)

    uc_buf, newlines_count = BytesIO(), 0
    compressed_bytes_per_address = TYPICAL_ADDR_BYTE_SIZE // 2
    def read_addr_batch():
        if DEBUG is True:
            nonlocal last_buffer_size_report_at, newlines_count
            global addresses_read
        nonlocal uc_buf
        nonlocal r_idx
        nonlocal compressed_bytes_per_address
        count, c_bytes_read = 0, 0
        while count < PHASE_I_READ_ADDR_BATCH_SIZE:
            c_data = f_r.read(int(
                compressed_bytes_per_address * (PHASE_I_READ_ADDR_BATCH_SIZE - count) + 128 ))
            if len(c_data) == 0:
                if count == 0:
                    maybe_address = uc_buf.read().strip()
                    if len(maybe_address) >= MIN_ADDR_LEN:
                        buf.append(maybe_address)
                        return
                    raise ReadComplete()
                return
            c_bytes_read += len(c_data)
            r_idx += len(c_data)

            uc_buf.write(decomp.decompress(c_data))
            uc_buf.seek(0)
            del c_data

            tail = None
            for address in uc_buf:
                if address.endswith(b'\n') is False:
                    tail = address
                    break
                buf.append(address.strip())
                count += 1
                if DEBUG:
                    assert MIN_ADDR_LEN <= len(address) <= MAX_ADDR_LEN, (len(address), address[:25])
                    addresses_read += 1

            uc_buf = BytesIO()
            if tail is not None:
                uc_buf.write(tail)
        compressed_bytes_per_address = c_bytes_read / count

        if (datetime.now() - last_buffer_size_report_at) > timedelta(seconds=2):
            last_buffer_size_report_at = datetime.now()
            print(f">>> Address buffer size: {len(buf)}, w_idx = {w_idx}, r_idx = {r_idx} <<<")
            print(f">>> {w_idx / (1024 ** 3):.4f} Gb of compressed data read so far <<<\n")
            assert w_idx < r_idx

    if DEBUG is True:
        atexit.register(lambda: print(f"{addresses_read} addresses were read from {filename}"))
        atexit.register(lambda: print(f"{newlines_count} newline characters were present in {filename}"))

    def read_addr():
        if len(buf) == 0:
            read_addr_batch()
        result = buf.popleft()
        assert len(result) < 256
        return result

    def write(data):
        nonlocal w_idx
        while (w_idx + len(data)) >= r_idx:
            try:
                read_addr_batch()
            except ReadComplete:
                break

        data_len = len(data)
        while len(data) > 0:
            data = data[f_w.write(data):]  # TODO: make SURE that everything is actually written
        f_w.flush()
        w_idx += data_len
        return data_len

    return read_addr, buf.appendleft, write

read_addr, regurgitate_addr, write = make_rrw()

chunks = []
offset, read_complete = 0, False
total_mbytes_written, start_at = 0, datetime.now()
while read_complete is False:
    compressor = zlib.compressobj(wbits=0b10000 | 9, strategy=zlib.Z_FILTERED)
    buf, dusty = [], False
    while len(buf) < DUST_THRESHOLD and dusty is False:
        try:
            addr = read_addr()
        except ReadComplete:
            read_complete = True
            break

        if len(buf) > 0:
            dusty = (buf[-1] <= addr) is False
        buf.append(addr)  # TODO: do not add an address if it is the same as the previous one

    if dusty is True:  # TODO: do not create a chunk if no addresses were found
        seq_len = 0
        while seq_len < DUST_THRESHOLD and len(buf) < CHUNK_MAX_BUF_ADDR_SIZE:
            try:
                buf.append(read_addr())
            except ReadComplete:
                read_complete, seq_len = True, 0
                break

            seq_len += 1
            if (buf[-2] <= buf[-1]) is False:
                seq_len = 0

        for i in range(1, seq_len + 1):
            regurgitate_addr(buf[-i])

        if seq_len > 0:
            buf = sorted(set(buf[:-seq_len]))
        else:
            buf = sorted(set(buf))

        bytes_written = write(compressor.compress(b'\n'.join(buf)))
        bytes_written += write(compressor.compress(b'\n'))
        bytes_written += write(compressor.flush())
        addresses_written = len(buf)
        first_address = None
        if addresses_written > 0:
            first_address = buf[0]
    else:
        bytes_written, addresses_written, first_address, prev_addr = 0, 0, buf[0], None
        while bytes_written < CHUNK_MAX_COMPRESSED_BYTE_SIZE:
            try:
                addr = read_addr()
                if prev_addr is not None and prev_addr == addr:
                    continue
                prev_addr = addr
            except ReadComplete:
                read_complete = True
                break

            if len(buf) > 0 and (buf[-1] <= addr) is False:
                regurgitate_addr(addr)
                break

            buf.append(addr)
            if len(buf) >= CHUNK_MAX_BUF_ADDR_SIZE // 2:
                bytes_written += write(compressor.compress(b'\n'.join(buf)))
                bytes_written += write(compressor.compress(b'\n'))
                addresses_written += len(buf)
                buf = []

        if len(buf) > 0:
            bytes_written += write(compressor.compress(b'\n'.join(buf)))
            bytes_written += write(compressor.compress(b'\n'))
            addresses_written += len(buf)
        bytes_written += write(compressor.flush())

    if addresses_written > 0:
        chunks.append((addresses_written, offset, bytes_written, first_address))
    elif DEBUG is True:
        print("addresses_written = 0!")
    offset += bytes_written
    mbytes_written = bytes_written / (1024 ** 2)
    print(f"New {mbytes_written:.2f} Mb long chunk containing {addresses_written} addresses is written, dusty = {dusty}")
    total_mbytes_written += mbytes_written
    mbytes_per_second = total_mbytes_written / (datetime.now() - start_at).total_seconds()
    compressed_bytes_per_address = bytes_written / addresses_written
    print(f"{mbytes_written:.2f} MB is written, {mbytes_per_second:.2f} MB/s (total), {compressed_bytes_per_address:.2f} bytes/address")
    print(f"Chunks created so far: {len(chunks)}\n")
print("First pass complete")
total_amt_of_addresses = sum([c[0] for c in chunks])
total_size_in_bytes = sum([c[2] for c in chunks])
print(f"{total_amt_of_addresses} addresses saved, filesize = {total_size_in_bytes / 1024 ** 2:.2f} Mb")
f_r.close()
f_w.close()

# PASS II

import os
import gc
import zlib
from io import SEEK_END
from time import time

class Chunk:
    ADDR_COUNTER = 0
    class ChunkExhausted(Exception): pass

    def __init__(self, ovwrt_shielded_fileobj, addresses_count, offset, compressed_bytes_count, first_address):
        self.f = ovwrt_shielded_fileobj
        self.addresses_count = addresses_count
        self.offset = offset
        self.compressed_ptr = 0
        self.prev_compressed_ptr = None
        self.compressed_bytes_count = compressed_bytes_count
        self.first_address = first_address
        self.last_abs_addr_given = None

    def __lt__(self, other):
        return self.first_address < other.first_address

    enabled = property(lambda self: hasattr(self, 'decompressor'))
    def enable(self):
        assert self.enabled is False

        self.addr_q = deque()
        self.decompressed_tail = b''
        self.last_abs_addr_given = None

        self.decompressor = zlib.decompressobj(0b10000 | zlib.MAX_WBITS)
        if self.compressed_ptr > 0:
            self.f.seek(self.offset)
            _compressed_ptr = 0
            while _compressed_ptr < self.compressed_ptr:
                compressed_data = self.f.read(min(65536, self.compressed_ptr - _compressed_ptr))
                _compressed_ptr += len(compressed_data)
                self.decompressor.decompress(compressed_data)
            self.decompressed_tail = None
            self.reenabled = True

        assert self.enabled is True

    def disable(self):
        assert self.enabled is True

        if self.prev_compressed_ptr is not None:
            assert self.prev_compressed_ptr < self.compressed_ptr
            self.compressed_ptr, self.prev_compressed_ptr = self.prev_compressed_ptr, None

        del self.decompressor
        del self.addr_q
        del self.decompressed_tail
        if hasattr(self, 'reenabled'):
            del self.reenabled
        gc.collect()

        assert self.enabled is False

    def _load_addrs(self):
        assert self.compressed_ptr <= self.compressed_bytes_count
        if self.compressed_ptr == self.compressed_bytes_count:
            raise Chunk.ChunkExhausted(self.addresses_count)

        self.f.seek(self.offset + self.compressed_ptr)
        compressed_data = self.f.read(min(16384, self.compressed_bytes_count - self.compressed_ptr))
        self.prev_compressed_ptr = max(self.compressed_ptr - 512, 0)
        self.compressed_ptr += len(compressed_data)

        buf = BytesIO()
        if self.decompressed_tail:
            buf.write(self.decompressed_tail)
            self.decompressed_tail = None
        buf.write(self.decompressor.decompress(compressed_data))
        buf.seek(0)

        for i, addr in enumerate(buf):
            if i == 0 and hasattr(self, 'reenabled'):
                del self.reenabled
                continue
            if addr.endswith(b'\n') is False:
                self.decompressed_tail = addr
                break
            addr = addr.strip()
            if addr >= self.first_address:
                self.addr_q.append(addr)
            if DEBUG:
                assert MIN_ADDR_LEN <= len(addr) <= MAX_ADDR_LEN, (
                    len(addr), addr[:32],
                    None if len(self.addr_q) <= 1 else self.addr_q[-2], i )

        if DEBUG:
            pos = buf.tell()
            buf.seek(0, SEEK_END)
            assert pos == buf.tell()

        if self.compressed_ptr >= self.compressed_bytes_count and self.decompressed_tail is not None:
            addr = self.decompressed_tail.strip()
            if len(addr) > 0:
                if addr >= self.first_address:
                    self.addr_q.append(addr)
                if DEBUG:
                    assert MIN_ADDR_LEN <= len(addr) <= MAX_ADDR_LEN, (
                        len(addr), addr[:32],
                        None if len(self.addr_q) <= 1 else self.addr_q[-2], self.compressed_ptr, self.compressed_bytes_count )

    def get_addr(self):
        try:
            if len(self.addr_q) == 0:
                self._load_addrs()
                if len(self.addr_q) == 0:
                    self._load_addrs()
        except AttributeError:
            if self.enabled is True:
                raise
            self.enable()
            return self.get_addr()

        try:
            result = self.addr_q.popleft()
        except:
            chunk_idx = chunk_offset2idx[self.offset]
            import code
            code.interact(local={**globals(), **locals()})
            raise Exception(f"Failed to get an address from chunk #{chunk_idx}, first_address = {self.first_address}")
        self.addresses_count -= 1
        if self.addresses_count > 0:
            if len(self.addr_q) == 0:
                self._load_addrs()
            self.first_address = self.addr_q[0]
        else:
            self.first_address = None
        type(self).ADDR_COUNTER += 1
        self.last_abs_addr_given = type(self).ADDR_COUNTER
        return result

CHUNK_MAX_COMPRESSED_BYTE_SIZE = 7.5 * (1024 ** 2)  # 7.5 Mb
class OverwriteShield():
    def __init__(self, f, retention_offset=0):
        assert f.tell() == 0
        self.f = f
        self._write_pos = 0
        self.read_pos = 0
        self._retention_offset = retention_offset
        self.retention_data = bytearray(int(CHUNK_MAX_COMPRESSED_BYTE_SIZE * 2))
        self.retention_data_len = 0

    def seek(self, pos):
        assert pos >= self.retention_offset
        self.read_pos = pos

    def read(self, length):
        result = []
        if self.read_pos < self.write_pos:
            assert self.read_pos >= self.retention_offset
            result.append(self.retention_data[
                self.read_pos - self.retention_offset:
                min( self.write_pos,
                     self.read_pos + length ) - self.retention_offset
            ])
            if (self.read_pos + length) >= self.write_pos:
                assert (self.read_pos + len(result[0])) == self.write_pos, (
                    self.read_pos, self.write_pos, self.retention_data_len, length)
            self.read_pos += len(result[0])
            length -= len(result[0])

        while length > 0:
            self.f.seek(self.read_pos)
            result.append(self.f.read(length))
            self.read_pos += len(result[-1])
            length -= len(result[-1])

        return b''.join(result)

    def write(self, data):
        if (self.write_pos + len(data)) >= self.retention_offset:
            file_idx = self.retention_offset + self.retention_data_len
            self.f.seek(file_idx)
            # Am i sure about that?
            bytes_to_read = self.write_pos + len(data) - file_idx
            while bytes_to_read > 0:
                try:
                    new_data = self.f.read(bytes_to_read)
                except KeyboardInterrupt:
                    print(f"KeyboardInterrupt while trying to read {bytes_to_read} bytes from the position {file_idx}")
                    raise
                self.retention_data[
                    self.retention_data_len:
                    self.retention_data_len + len(new_data)] = new_data
                self.retention_data_len += len(new_data)
                bytes_to_read -= len(new_data)

        if self.f.tell() != self.write_pos:
            self.f.seek(self.write_pos)
        data_written = 0
        while data_written < len(data):
            data_written += self.f.write(data[data_written:])
        assert data_written == len(data)
        self.write_pos += data_written

    def set_retention_offset(self, val):
        assert val >= self._retention_offset
        if val == self._retention_offset:
            return
        d_offset = val - self._retention_offset
        self.retention_data_len -= d_offset
        if self.retention_data_len < 0:
            self.retention_data_len = 0
        self.retention_data = self.retention_data[d_offset:]
        # ???
        extend_by = int(CHUNK_MAX_COMPRESSED_BYTE_SIZE * 2) - len(self.retention_data)
        if extend_by > 0:
            self.retention_data += bytearray(extend_by)
        self._retention_offset = val
        gc.collect()
    retention_offset = property(lambda self: self._retention_offset, set_retention_offset)

    def set_write_pos(self, val):
        assert val >= self._write_pos, "Writes should be done sequentially, remember?"
        self._write_pos = val
    write_pos = property(lambda self: self._write_pos, set_write_pos)

    def close(self):
        self.f.close()

chunks, _chunks = [], chunks
for addresses_written, offset, bytes_written, first_address in _chunks:
    chunks.append(Chunk(None, addresses_written, offset, bytes_written, first_address))
del _chunks
chunk_offset2idx = {ch.offset: i for i, ch in enumerate(chunks, 1)}
chunks.sort()
print(f"{len(chunks)} chunks loaded and sorted (kind of)")

f_hdlr = open(filename, 'r+b')
f = OverwriteShield(f_hdlr)
for chunk in chunks:
    chunk.f = f

relocation_areas = []

def find_longest_relocation_area():
    if len(relocation_areas) == 0:
        return None
    return sorted(relocation_areas, key=lambda area: area[-1])[-1]

# TODO: make sure that HUGE amount of data does not get moved around TOO often
last_major_relocation_at = datetime.fromtimestamp(0)
def relocate_chunks():
    global f_hdlr, relocation_areas

    def actualize_relocation_areas():
        global relocation_areas

        relocation_areas = [
            (offset, size) for offset, size in relocation_areas
            if (offset + size) > f.write_pos
        ]
        if len(relocation_areas) == 0:
            return False

        _relocation_areas, relocation_areas = relocation_areas, []
        for offset, size in _relocation_areas:
            if offset < f.write_pos:
                offset_shift = f.write_pos - offset + 1024 ** 2
                offset += offset_shift
                size -= offset_shift
                if size <= 0:
                    continue
            relocation_areas.append((offset, size))

        return len(relocation_areas) > 0
    if actualize_relocation_areas() is False:
        return

    def merge_relocation_areas():
        global relocation_areas
        relocation_areas.sort(key=lambda area: area[0])  # Sort by offset
        while True:
            _relocation_areas, relocation_areas = relocation_areas, []
            merge_count = 0
            while len(_relocation_areas) > 0:
                if len(_relocation_areas) == 1:
                    relocation_areas.append(_relocation_areas.pop())
                    break
                [[a_offset, a_size], [b_offset, b_size]] = _relocation_areas[:2]
                if (a_offset + a_size) < b_offset:
                    relocation_areas.append((a_offset, a_size))
                    _relocation_areas = _relocation_areas[1:]
                    continue

                merge_count += 1
                assert (b_offset - a_offset) == a_size
                relocation_areas.append((a_offset, a_size + b_size))
                _relocation_areas = _relocation_areas[2:]

            if merge_count == 0:
                break
    merge_relocation_areas()

    relocation_occured = False

    # Assumes that chunks are being moved from left to right, perhaps with an overlap
    def relocate_chunk(chunk, a_offset, a_size):
        global relocation_areas
        nonlocal relocation_occured

        chunk_idx = chunk_offset2idx[chunk.offset]
        chunk_offset, chunk_size = chunk.offset, chunk.compressed_bytes_count
        assert chunk_offset < a_offset
        assert a_size >= chunk_size or a_offset == (chunk_offset + chunk_size)

        # s == src, d == dst
        s1, s2 = chunk_offset, chunk_offset + chunk_size
        d1 = a_offset + a_size - chunk_size
        d2 = d1 + chunk_size
        backup = (s1, s2), (d1, d2)
        assert (s2 - s1) == (d2 - d1) and s1 < d1 and s2 < d2 and s1 < s2 and d1 < d2, backup

        print(f"Relocating chunk #{chunk_idx} ({chunk_size / 1024 ** 2:.2f} MB) from {s1}:{s2} to {d1}:{d2}")

        bytes_relocated = 0
        while bytes_relocated < chunk_size:
            space_available = d2 - max(d1, s2)
            assert space_available <= (chunk_size - bytes_relocated)
            bytes_to_transfer = min( space_available, 5 * 1024 ** 2, s2 - s1 )
            assert s1 <= (s2 - bytes_to_transfer)
            f.seek( s2 - bytes_to_transfer )
            # OverwriteShield.read() method should guarantee that we read everything in one go
            data = f.read(bytes_to_transfer)
            data_len = len(data)
            assert data_len == bytes_to_transfer
            f_hdlr.seek(d2 - data_len)
            while len(data) > 0:
                data = data[f_hdlr.write(data):]

            d2 -= data_len
            s2 -= data_len
            bytes_relocated += data_len
        assert s1 == s2 and d1 == d2, ((s1, s2), (d1, d2))

        del chunk_offset2idx[ chunk.offset ]
        chunk.offset = d1
        chunk_offset2idx[ chunk.offset ] = chunk_idx

        [s1, s2], [d1, d2] = backup
        new_relocation_areas = []
        if s2 < d1:  # Relocation area and chunk did not intersect
            new_relocation_areas.append( (s1, s2 - s1) )  # Space that used to be occupied by the chunk
            space_left = a_size - bytes_relocated
            if space_left > 0:
                new_relocation_areas.append( (a_offset, space_left) )
        else:  # Relocation area and chunk DID intersect
            new_relocation_areas.append( (s1, d1 - s1) )  # Whatever is left of the place chunk used to occupy
        relocation_areas = [(offset, size) for offset, size in relocation_areas if (offset, size) != (a_offset, a_size)]
        relocation_areas.extend(new_relocation_areas)
        actualize_relocation_areas()
        merge_relocation_areas()

        f_hdlr.flush()
        relocation_occured = True

        print(f"Chunk #{chunk_idx} successfully relocated")

    def find_area_suitable_for_a_chunk(chunk, smallest=False, rightmost=False, overlap_ok=False):
        assert smallest is not rightmost and isinstance(smallest, bool) and isinstance(rightmost, bool)
        suitable_areas = [(offset, size) for offset, size in relocation_areas
                          if ((size >= chunk.compressed_bytes_count) or
                              (overlap_ok is True and
                               (chunk.offset + chunk.compressed_bytes_count) == offset and
                               ((offset + size) - chunk.compressed_bytes_count) > f.write_pos))
                          # Moving chunk closer to the left is counter-productive
                          and offset > chunk.offset]
        if len(suitable_areas) == 0:
            return None, None
        if smallest is True:
            # We want the smallest area chunk will fit into
            suitable_areas.sort(key=lambda area: area[-1])
            if overlap_ok is True:
                # Trying to avoid areas that are smaller than the chunk
                suitable_areas.sort(key=lambda area: int(area[-1] < chunk.compressed_bytes_count))
        elif rightmost is True:
            suitable_areas.sort(key=lambda area: -area[0])
        return suitable_areas[0]

    def create_10mb_relocation_area_if_not_exists():
        longest_relocation_area = find_longest_relocation_area()
        if longest_relocation_area is None or longest_relocation_area[-1] >= 10 * 1024 ** 2:
            return
        print(f"Longest continuous relocation area is {longest_relocation_area[-1] / 1024 ** 2:.2f} MB long, " +
              "trying to find shortest chain of relocation areas that in sum will produce coveted 10MB")

        chains = []
        _relocation_areas = sorted(relocation_areas, key=lambda area: area[0])  # Sorting by offset
        while len(_relocation_areas) >= 2:
            chain, chain_size = [], 0
            for area in _relocation_areas:
                chain.append(area)
                chain_size += area[-1]
                if chain_size >= 10 * 1024 ** 2:
                    break
            chains.append((chain, chain_size))
            _relocation_areas = _relocation_areas[1:]

        chains = [(chain, chain_size) for chain, chain_size in chains if chain_size > longest_relocation_area[-1]]
        if len(chains) == 0:
            print("No suitable or semi-suitable chains of relocation areas found. SAD!")
            return

        # TODO: do not move things around if the amount of data that has to be moved
        # is more than 10 times larger than the amount of continious free space we are getting

        chains.sort(key=lambda chain__chain_size: chain__chain_size[-1])
        if chains[-1][-1] >= 10 * 1024 ** 2:
            chains = [(chain, chain_size) for chain, chain_size in chains if chain_size >= 10 * 1024 ** 2]
            target = 10 * 1024 ** 2
        else:
            print("No chains that can produce coveted 10 MB found, but there are ones that can give us more that we currently have")
            target = None

        print(f"{len(chain)} chains found, picking the shortest one")
        chains.sort(key=lambda chain: chain[0][-1][0] - chain[0][0][0])
        chain = chains[0]; del chains
        if target is None:
            target = chain[-1]
            print(f"Expected area length: {target / 1024 ** 2:.2f} MB")
        chain = chain[0]

        print(f"Trying to find chunks that lie between these {len(chain)} relocation areas")
        first_area_offset, last_area_offset = chain[0][0], chain[-1][0]
        chunks_to_be_shifted = [chunk for chunk in chunks if
                                first_area_offset < chunk.offset < last_area_offset]

        print(f"{len(chunks_to_be_shifted)} chunks lie between the relocation areas we wish to merge.")
        print(f"Total length of these chunks is {sum([ch.compressed_bytes_count for ch in chunks_to_be_shifted]) / 1024 ** 2:.2f} MB. Relocating them.")
        for i, chunk in enumerate(sorted(chunks_to_be_shifted, key=lambda chunk: -chunk.offset), 1):
            a_offset, a_size = find_area_suitable_for_a_chunk(chunk, rightmost=True, overlap_ok=True)
            relocate_chunk(chunk, a_offset, a_size)
            longest_area_length = find_longest_relocation_area()[-1]
            if longest_area_length >= target:
                print(f"{target / 1024 ** 2:.2f} MB goal was achived after relocating {i} chunks, longest relocation area: {longest_area_length / 1024 ** 2:.2f} MB")
                return

        if DEBUG is True:
            raise Exception("At this point we were supposed to have {target / 1024 ** 2:.2f} MB relocation area, yet we do not have it.")
        print(f"Something went wrong while moving chunks around: we were not able to create continious {target / 1024 ** 2:.2f} MB relocation area, even though calculations showed that we should've been able to")
    create_10mb_relocation_area_if_not_exists()

    chunks_were_moved = True
    while chunks_were_moved and (min([chunk.offset for chunk in chunks]) - f.write_pos) < 50 * 1024 ** 2:
        chunks_were_moved = False
        for chunk in sorted(chunks, key=lambda chunk: chunk.offset):
            # No need to shuffle around these chunks, this area almost certainly wont
            # be overwritten
            # ...or maybe it is a good idea after all, now that the chunks can be reforged
            # if chunk.offset > (last_chunk_offset + last_chunk_size):
            #     break

            a_offset, a_size = find_area_suitable_for_a_chunk(chunk, rightmost=True, overlap_ok=True)
            if a_offset is None:
                break
            relocate_chunk(chunk, a_offset, a_size)

            chunks_were_moved = True

    if relocation_occured is True:
        f.f.flush()
        f.retention_offset = min([chunk.offset for chunk in chunks])

last_chunk_offset = sorted(chunks, key=lambda chunk: chunk.offset)[-1]
last_chunk_offset, last_chunk_size = last_chunk_offset.offset, last_chunk_offset.compressed_bytes_count
file_size = os.path.getsize(filename)
if file_size > (last_chunk_offset + last_chunk_size):
    relocation_areas.append((
        last_chunk_offset + last_chunk_size,
        file_size - (last_chunk_offset + last_chunk_size)
    ))
    relocate_chunks()

buf, total_addr_count, dump_addr_count, compressor = BytesIO(), 0, 0, zlib.compressobj(wbits=0b10000 | 9, strategy=zlib.Z_FILTERED)

def dump():
    global buf, chunks, relocation_areas
    buf.seek(0)
    compressed, buf = compressor.compress(buf.read()), BytesIO()
    c_len = len(compressed)
    f.write(compressed)
    del compressed
    print(f"Dumped {c_len / (1024 ** 2):.2f} MB and {dump_addr_count} addresses, {c_len / dump_addr_count:.2f} bytes/address")
    print(f"Total amount of dumped addresses: {total_addr_count}")

    stuck_chunks = [(i, chunk) for i, chunk in enumerate(chunks) if
                    chunk.offset > f.write_pos and  # TODO: try moving these as well, maybe?
                    chunk.last_abs_addr_given is not None and
                    chunk.compressed_bytes_count >= CHUNK_REFORGING_SIZE_THRESHOLD and 
                    (Chunk.ADDR_COUNTER - chunk.last_abs_addr_given) >= CHUNK_REFORGING_ADDR_THRESHOLD]
    if len(stuck_chunks) > 0:
        print(f">>>>>>> {len(stuck_chunks)} chunks are STUCK! They are (or at one time were) active, yet the last time they")
        print(f">>>>>>> had given out any address was more than {CHUNK_REFORGING_ADDR_THRESHOLD} addresses ago")
        print(f">>>>>>> These chunks will be recompressed and rewritten to disk")
        for chunk_list_idx, chunk in stuck_chunks:
            was_disabled = not chunk.enabled
            if was_disabled is True:
                chunk.enable()

            original_compressed_size = chunk.compressed_bytes_count
            addresses_count = chunk.addresses_count
            first_address = chunk.first_address
            _compressor = zlib.compressobj(wbits=0b10000 | 9, strategy=zlib.Z_FILTERED)
            w_pos = chunk.offset

            bytes_written, addresses, addresses_extracted = 0, [], 0
            oyvey_buf = None
            while chunk.addresses_count > 0:
                address = chunk.get_addr()
                if bytes_written == 0 and len(addresses) == 0:
                    assert address == first_address
                addresses.append(address)
                addresses_extracted += 1
                if len(addresses) % 10_000 == 0 and len(addresses) > 0:
                    addresses = _compressor.compress(
                        b'\n'.join(addresses) +
                        (b'' if chunk.addresses_count == 0 else b'\n'))

                    if (len(addresses) + w_pos) > (chunk.offset + chunk.compressed_ptr):
                        print("Rewriting chunk directly to the file will overwrite addresses that had not been read yet.")
                        print("Dumping chunk data into the emergency in-memory buffer")
                        oyvey_buf = BytesIO()

                    bytes_written += len(addresses)

                    if oyvey_buf is None:
                        f.f.seek(w_pos)
                        w_pos += len(addresses)
                        while len(addresses) > 0:
                            addresses = addresses[f.f.write(addresses):]
                    else:
                        oyvey_buf.write(addresses)
                    addresses = []
            assert addresses_count == addresses_extracted

            if oyvey_buf is not None:
                print("Emergency buffer is not empty, dumping it's contents on disk")
                oyvey_buf.seek(0)
                oyvey_buf = oyvey_buf.read()
                oyvey_buf_size = len(oyvey_buf)
                f.f.seek(w_pos)
                while len(oyvey_buf) > 0:
                    oyvey_buf = oyvey_buf[f.f.write(oyvey_buf):]
                w_pos += oyvey_buf_size

            addresses = _compressor.compress(b'\n'.join(addresses))
            addresses += _compressor.flush()
            bytes_written += len(addresses)
            f.f.seek(w_pos)
            while len(addresses) > 0:
                addresses = addresses[f.f.write(addresses):]

            chunks[ chunk_list_idx ] = Chunk(
                f, addresses_count, chunk.offset, bytes_written, first_address )
            if was_disabled is False:
                chunks[ chunk_list_idx ].enable()
            assert original_compressed_size > bytes_written
            relocation_areas.append((chunk.offset + bytes_written, original_compressed_size - bytes_written))

            chunk_idx = chunk_offset2idx[chunk.offset]
            bytes_released = original_compressed_size - bytes_written
            print(f"Chunk #{chunk_idx} was reforged, {bytes_released / 1024 ** 2:.2f} MB should become available for relocation because of that. {bytes_written / 1024 ** 2:.2f} MB is left.")
            print(f"This chunk has {addresses_count} addresses left in it.")
        f.f.flush()

    if (min([chunk.offset for chunk in chunks]) - f.write_pos) < 100 * 1024 ** 2:
        relocate_chunks()

def write_addr(addr):
    global buf, total_addr_count, dump_addr_count
    buf.write(addr.strip() + b'\n')
    total_addr_count += 1
    dump_addr_count += 1
    if dump_addr_count >= 50_000:
        dump()
        dump_addr_count = 0

chunks[0].enable()
t = time()
while True:
    if chunks[0].first_address is None:
        if len(chunks) == 1:
            # Should not be happening, BTW
            break
        processed_chunk, chunks = chunks[0], chunks[1:]
        processed_chunk_idx = chunk_offset2idx[processed_chunk.offset]
        del chunk_offset2idx[processed_chunk.offset]
        print(f"!!! Chunk #{processed_chunk_idx} is exhausted")
        processed_chunk.disable()
        if f.retention_offset == processed_chunk.offset:
            f.retention_offset = f.retention_offset + processed_chunk.compressed_bytes_count
        else:
            relocation_areas.append( (processed_chunk.offset, processed_chunk.compressed_bytes_count) )
        gc.collect()
        print(f"!!! Processing of a chunk {processed_chunk_idx} is complete, {len(chunks)} chunks left, len(retention_data) = {len(f.retention_data)}")
        continue

    if len(chunks) == 1 or chunks[0].first_address < chunks[1].first_address:
        if len(chunks) > 1:
            try:
                while chunks[0].first_address < chunks[1].first_address:
                    write_addr(chunks[0].get_addr())
            except TypeError:
                assert chunks[0].first_address is None
            continue
        else:
            try:
                while True:
                    write_addr(chunks[0].get_addr())
            except Chunk.ChunkExhausted:
                assert chunks[0].first_address is None
                break
            raise Exception("That is not supposed to be happening")

    if chunks[0].first_address == chunks[1].first_address:
        chunks[0].get_addr()
        if chunks[0].first_address is None:
            continue

    if DEBUG:
        assert chunks[0].first_address > chunks[1].first_address

    i, j = None, None
    for i in range(1, len(chunks)):
        if chunks[i].first_address >= chunks[0].first_address:
            for j in range(i + 1, len(chunks)):
                if chunks[j].first_address > chunks[i].first_address:
                    break
            break
    assert i is not None
    i = i if j is None else j - 1
    chunks[:i + 1] = sorted(chunks[:i + 1])
    if chunks[0].enabled is False:
        chunks[0].enable()
        chunks_enabled = len([ch for ch in chunks if ch.enabled is True])
        print(">>> Enabling new chunk, %d chunks out of %s are currently enabled" %
              (chunks_enabled, len(chunks)))
        if chunks_enabled > 10:
            print("Way too many chunks are enabled, trying to find any that can be temporarily turned off")
            for chunk in chunks[1:]:
                if chunk.last_abs_addr_given is None or chunk.enabled is False:
                    continue
                if (Chunk.ADDR_COUNTER - chunk.last_abs_addr_given) > 5000:
                    chunk.disable()
                    print(f"Chunk #{chunk_offset2idx[chunk.offset]} is deactivated")
            chunks_enabled = len([ch for ch in chunks if ch.enabled is True])
            print(f"{chunks_enabled} chunks are active now")

dump()
f.write(compressor.flush())
f.f.flush()
f.f.truncate()
f.f.close()

print("Pass II complete")
print("Everything should be sorted and deduplicated now")

new_file_size = os.path.getsize(filename)
economy = file_size - new_file_size
if economy < 0:
    print("New file is bigger than the old one for some weird reason...")
else:
    print(f"New file is {economy / 1024 ** 2:.2f} MB shorter than the original [{file_size} => {new_file_size}]")