// Copyright (c) 2010 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "pdf/chunk_stream.h"

#include <stddef.h>
#include <string.h>

#include <algorithm>
#include <limits>

namespace chrome_pdf {

ChunkStream::ChunkStream() : stream_size_(0) {}

ChunkStream::~ChunkStream() {}

void ChunkStream::Clear() {
  chunks_.clear();
  data_.clear();
  stream_size_ = 0;
}

void ChunkStream::Preallocate(size_t stream_size) {
  data_.reserve(stream_size);
  stream_size_ = stream_size;
}

size_t ChunkStream::GetSize() const {
  return data_.size();
}

bool ChunkStream::WriteData(size_t offset, void* buffer, size_t size) {
  if (std::numeric_limits<size_t>::max() - size < offset)
    return false;

  if (data_.size() < offset + size)
    data_.resize(offset + size);

  memcpy(&data_[offset], buffer, size);

  if (chunks_.empty()) {
    chunks_[offset] = size;
    return true;
  }

  auto start = GetStartChunk(offset);
  auto end = chunks_.upper_bound(offset + size);
  if (start == end) {  // No chunks to merge.
    chunks_[offset] = size;
    return true;
  }

  auto prev = end;
  --prev;
  size_t prev_size = prev->first + prev->second;

  size_t new_offset = std::min<size_t>(start->first, offset);
  size_t new_size = std::max<size_t>(prev_size, offset + size) - new_offset;

  chunks_.erase(start, end);
  chunks_[new_offset] = new_size;
  return true;
}

bool ChunkStream::ReadData(size_t offset, size_t size, void* buffer) const {
  if (!IsRangeAvailable(offset, size))
    return false;

  memcpy(buffer, &data_[offset], size);
  return true;
}

bool ChunkStream::GetMissedRanges(
    size_t offset,
    size_t size,
    std::vector<std::pair<size_t, size_t>>* ranges) const {
  if (IsRangeAvailable(offset, size))
    return false;

  ranges->clear();
  if (chunks_.empty()) {
    ranges->push_back(std::pair<size_t, size_t>(offset, size));
    return true;
  }

  auto start = GetStartChunk(offset);
  auto end = chunks_.upper_bound(offset + size);
  if (start == end) {  // No data in the current range available.
    ranges->push_back(std::pair<size_t, size_t>(offset, size));
    return true;
  }

  size_t cur_offset = offset;
  for (auto it = start; it != end; ++it) {
    if (cur_offset < it->first) {
      size_t new_size = it->first - cur_offset;
      ranges->push_back(std::pair<size_t, size_t>(cur_offset, new_size));
      cur_offset = it->first + it->second;
    } else if (cur_offset < it->first + it->second) {
      cur_offset = it->first + it->second;
    }
  }

  // Add last chunk.
  if (cur_offset < offset + size) {
    ranges->push_back(
        std::pair<size_t, size_t>(cur_offset, offset + size - cur_offset));
  }

  return true;
}

bool ChunkStream::IsRangeAvailable(size_t offset, size_t size) const {
  if (chunks_.empty())
    return false;

  if (std::numeric_limits<size_t>::max() - size < offset)
    return false;

  auto it = chunks_.upper_bound(offset);
  if (it == chunks_.begin())
    return false;  // No chunks includes offset byte.

  --it;  // Now it starts equal or before offset.
  return it->first + it->second >= offset + size;
}

size_t ChunkStream::GetFirstMissingByte() const {
  if (chunks_.empty())
    return 0;
  auto begin = chunks_.begin();
  return begin->first > 0 ? 0 : begin->second;
}

size_t ChunkStream::GetFirstMissingByteInInterval(size_t offset) const {
  if (chunks_.empty())
    return 0;
  auto it = chunks_.upper_bound(offset);
  if (it == chunks_.begin())
    return 0;
  --it;
  return it->first + it->second;
}

size_t ChunkStream::GetLastMissingByteInInterval(size_t offset) const {
  if (chunks_.empty())
    return stream_size_ - 1;
  auto it = chunks_.upper_bound(offset);
  if (it == chunks_.end())
    return stream_size_ - 1;
  return it->first - 1;
}

std::map<size_t, size_t>::const_iterator ChunkStream::GetStartChunk(
    size_t offset) const {
  auto start = chunks_.upper_bound(offset);
  if (start != chunks_.begin())
    --start;  // start now points to the key equal or lower than offset.
  if (start->first + start->second < offset)
    ++start;  // start element is entirely before current chunk, skip it.
  return start;
}

}  // namespace chrome_pdf