std::map<uint64_t, std::string> buffer_ {};
uint64_t index_ { 0 };
uint64_t eof_ = { static_cast<uint64_t>( -1 ) };

/*
* Insert a new substring to be reassembled into a ByteStream.
*   `first_index`: the index of the first byte of the substring
*   `data`: the substring itself
*   `is_last_substring`: this substring represents the end of the stream
*   `output`: a mutable reference to the Writer
*
* The Reassembler's job is to reassemble the indexed substrings (possibly out-of-order
* and possibly overlapping) back into the original ByteStream. As soon as the Reassembler
* learns the next byte in the stream, it should write it to the output.
*
* If the Reassembler learns about bytes that fit within the stream's available capacity
* but can't yet be written (because earlier bytes remain unknown), it should store them
* internally until the gaps are filled in.
*
* The Reassembler should discard any bytes that lie beyond the stream's available capacity
* (i.e., bytes that couldn't be written even if earlier gaps get filled in).
*
* The Reassembler should close the stream after writing the last byte.
*/
void insert( uint64_t first_index, std::string data, bool is_last_substring );

void Reassembler::insert( uint64_t first_index, string data, bool is_last_substring )
{
  auto& writer_inst = output_.writer();

  if ( is_last_substring ) {
    eof_ = first_index + data.size();
    if ( eof_ == index_ ) {
      writer_inst.close();
    }
  }

  if ( data.empty() ) {
    return;
  }

  // ----- Check for out-of-bounds data -----
  if ( first_index + data.size() <= index_ ) { // ...(...)..[...]...
    return;
  }
  if ( first_index < index_ ) { // ...(..[.)..]...
    uint64_t overlap = index_ - first_index;
    data = data.substr( overlap );
    first_index = index_;
  }
  if ( first_index >= index_ + writer_inst.available_capacity() ) { // ...[...]..(...)...
    return;
  }
  if ( first_index + data.size() > index_ + writer_inst.available_capacity() ) { // ...[..(.]..)...
    uint64_t left = index_ + writer_inst.available_capacity() - first_index;
    data = data.substr( 0, left );
  }

  // ----- Check for internal overlaps -----
  auto it = buffer_.lower_bound( first_index );
  if ( it == buffer_.end() || it->first > first_index ) {
    it = buffer_.insert( { first_index, std::move( data ) } ).first;
    if ( it != buffer_.begin() ) {
      it--; // now `it` is the previous one
    }
  } else {
    if ( data.size() > it->second.size() ) {
      // it->second = std::move( data );
      it->second += data.substr( it->second.size() );
    } else {
      // it->second = std::move( data ) + it->second.substr( data.size() );
    }
  }
  auto nxt = std::next( it );
  while ( nxt != buffer_.end() ) {
    if ( it->first + it->second.size() >= nxt->first ) {
      if ( it->first + it->second.size() < nxt->first + nxt->second.size() ) {
        // overlapping but not fully included, merge them
        it->second += nxt->second.substr( it->first + it->second.size() - nxt->first );
      }
      nxt = buffer_.erase( nxt );
    } else {
      break;
    }
  }

  // ----- Now we can write out -----
  while ( !buffer_.empty() && buffer_.begin()->first == index_ ) {
    it = buffer_.begin();
    uint64_t len = it->second.size();
    writer_inst.push( std::move( it->second ) );
    index_ += len;
    buffer_.erase( buffer_.begin() );
  }

  if ( eof_ == index_ ) {
    writer_inst.close();
  }
}

// How many bytes are stored in the Reassembler itself?
// This function is for testing only; don't add extra state to support it.
uint64_t Reassembler::count_bytes_pending() const
{
  uint64_t count = 0;
  for ( const auto& [index, str] : buffer_ ) {
    count += str.size();
  }
  return count;
}