void read_tile_samples(KVS &store, int uid, std::string full_channel_name, TileIndex requested_index, TileIndex client_tile_index, std::vector<DataSample<T> > &samples, bool &binned)
{
  Channel ch(store, uid, full_channel_name);
  Tile tile;
  TileIndex actual_index;
  bool success = ch.read_tile_or_closest_ancestor(requested_index, actual_index, tile);

  if (!success) {
    log_f("gettile: no tile found for %s", requested_index.to_string().c_str());
  } else {
    log_f("gettile: requested %s: found %s", requested_index.to_string().c_str(), actual_index.to_string().c_str());
    for (unsigned i = 0; i < tile.get_samples<T>().size(); i++) {
      DataSample<T> &sample=tile.get_samples<T>()[i];
      if (client_tile_index.contains_time(sample.time)) samples.push_back(sample);
    }
  }

  if (samples.size() <= 512) {
    binned = false;
  } else {
    // Bin
    binned = true;
    std::vector<DataAccumulator<T> > bins(512);
    for (unsigned i = 0; i < samples.size(); i++) {
      DataSample<T> &sample=samples[i];
      bins[(int)floor(client_tile_index.position(sample.time)*512)] += sample;
    }
    samples.clear();
    for (unsigned i = 0; i < bins.size(); i++) {
      if (bins[i].weight > 0) samples.push_back(bins[i].get_sample());
    }
  }
}

void TestItemMarkerTiler::testIndices()
{
    const int maxLevel = TileIndex::MaxLevel;

    for (int l = 0; l<=maxLevel; ++l)
    {
        const TileIndex tileIndex = TileIndex::fromCoordinates(coord_1_2, l);
        QVERIFY(tileIndex.level() == l);
    }
}

void Channel::move_root_upwards(TileIndex new_root_index, TileIndex old_root_index) {
  Tile old_root_tile;
  Tile empty_tile;
  assert(read_tile(old_root_index, old_root_tile));
  TileIndex ti = old_root_index;
  while (ti != new_root_index) {
    write_tile(ti.sibling(), empty_tile);
    write_tile(ti.parent(), old_root_tile);
    ti = ti.parent();
  }
}

TileIndex TileIndex::fromIntList(const QIntList& intList)
{
    TileIndex result;

    for (int i = 0; i < intList.count(); ++i)
    {
        result.appendLinearIndex(intList.at(i));
    }

    return result;
}

IntRect TileGrid::rectForTileIndex(const TileIndex& tileIndex) const
{
    // FIXME: calculating the scaled size here should match with the rest of calculated sizes where we use the combination of
    // enclosingIntRect, expandedIntSize (floor vs ceil).
    // However enclosing this size could reveal gap on root layer's background. see RenderView::backgroundRect()
    IntSize tileSize = m_controller.tileSize();
    IntRect rect(tileIndex.x() * tileSize.width(), tileIndex.y() * tileSize.height(), tileSize.width(), tileSize.height());
    IntRect scaledBounds(m_controller.bounds());
    scaledBounds.scale(m_scale);
    rect.intersect(scaledBounds);
    return rect;
}

TileIndex TileIndex::mid(const int first, const int len) const
{
    GEOIFACE_ASSERT(first+(len-1) <= m_indicesCount);
    TileIndex result;

    for (int i = first; i < first+len; ++i)
    {
        result.appendLinearIndex(m_indices[i]);
    }

    return result;
}

bool TileIndex::indicesEqual(const TileIndex& a, const TileIndex& b, const int upToLevel)
{
    GEOIFACE_ASSERT(a.level() >= upToLevel);
    GEOIFACE_ASSERT(b.level() >= upToLevel);

    for (int i = 0; i <= upToLevel; ++i)
    {
        if (a.linearIndex(i)!=b.linearIndex(i))
        {
            return false;
        }
    }

    return true;
}

bool Channel::read_tile(TileIndex ti, Tile &tile) const {
  std::string binary;
  if (!m_kvs.get(tile_key(ti), binary)) return false;
  total_tiles_read++;
  tile.from_binary(binary);
  if (verbosity) log_f("Channel: read_tile %s %s: %s", 
                       descriptor().c_str(), ti.to_string().c_str(), tile.summary().c_str());
  return true;
}

void Channel::write_tile(TileIndex ti, const Tile &tile) {
  std::string binary;
  tile.to_binary(binary);
  //assert(binary.size() <= m_max_tile_size);
  m_kvs.set(tile_key(ti), binary);
  total_tiles_written++;
  if (verbosity) log_f("Channel: write_tile %s %s: %s", 
                       descriptor().c_str(), ti.to_string().c_str(), tile.summary().c_str());
}

void Channel::create_parent_tile_from_children(TileIndex parent_index, Tile &parent, Tile children[]) {
  // Subsample the children to create the parent
  // when do we want to show original values?
  // when do we want to do a real low-pass filter?
  // do we need to filter more than just the child tiles? e.g. gaussian beyond the tile border
  if (verbosity) log_f("Channel: creating parent %s from children %s, %s",
                       parent_index.to_string().c_str(),
                       parent_index.left_child().to_string().c_str(),
                       parent_index.right_child().to_string().c_str());

  combine_samples(BT_CHANNEL_DOUBLE_SAMPLES, parent_index, parent.double_samples, children[0].double_samples, children[1].double_samples);
  if (children[0].double_samples.size() + children[1].double_samples.size()) assert(parent.double_samples.size());

  combine_samples(BT_CHANNEL_STRING_SAMPLES, parent_index, parent.string_samples, children[0].string_samples, children[1].string_samples);
  if (children[0].string_samples.size() + children[1].string_samples.size()) assert(parent.string_samples.size());

  parent.ranges = children[0].ranges;
  parent.ranges.add(children[1].ranges);
}

void combine_samples(unsigned int n_samples,
                     TileIndex parent_index,
                     std::vector<DataSample<T> > &parent,
                     const std::vector<DataSample<T> > &left_child,
                     const std::vector<DataSample<T> > &right_child)
{
  std::vector<DataAccumulator<T> > bins(n_samples);

  const std::vector<DataSample<T> > *children[2];
  children[0]=&left_child; children[1]=&right_child;

  int n=0;
  for (unsigned j = 0; j < 2; j++) {
    const std::vector<DataSample<T> > &child = *children[j];
    for (unsigned i = 0; i < child.size(); i++) {
      // Version 1: bin samples into correct bin
      // Version 2: try gaussian or lanczos(1) or 1/4 3/4 3/4 1/4
      
      const DataSample<T> &sample = child[i];
      assert(parent_index.contains_time(sample.time));
      unsigned bin = (unsigned) floor(parent_index.position(sample.time) * n_samples);
      assert(bin < n_samples);
      n++;
      bins[bin] += sample;
      assert(bins[bin].weight>0);
    }
  }

  n = 0;
  int m=0;
  parent.clear();
  for (unsigned i = 0; i < bins.size(); i++) {
    if (bins[i].weight > 0) {
      parent.push_back(bins[i].get_sample());
      assert(parent.size());
      n++;
    } else {
      m++;
    }
  }
  if (left_child.size() || right_child.size()) assert(parent.size());
}

IntRect TileGrid::extent() const
{
    TileIndex topLeft;
    TileIndex bottomRight;
    getTileIndexRangeForRect(m_primaryTileCoverageRect, topLeft, bottomRight);

    // Return index of top, left tile and the number of tiles across and down.
    return IntRect(topLeft.x(), topLeft.y(), bottomRight.x() - topLeft.x() + 1, bottomRight.y() - topLeft.y() + 1);
}

TileIndex Channel::split_tile_if_needed(TileIndex ti, Tile &tile) {
  TileIndex new_root_index = TileIndex::null();
  if (tile.binary_length() <= m_max_tile_size) return new_root_index;
  Tile children[2];
  TileIndex child_indexes[2];
  if (verbosity) log_f("split_tile_if_needed: splitting tile %s", ti.to_string().c_str());

  // If we're splitting an "all" tile, it means that until now the channel has only had one tile's worth of
  // data, and that a proper root tile location couldn't be selected.  Select a new root tile now.
  if (ti.is_nonnegative_all()) {
    // TODO: this breaks if all samples are at one time
    ti = new_root_index = TileIndex::index_containing(Range(tile.first_sample_time(), tile.last_sample_time()));
    if (verbosity) log_f("split_tile_if_needed: Moving root tile to %s", ti.to_string().c_str());
  }
  
  child_indexes[0]= ti.left_child();
  child_indexes[1]= ti.right_child();

  double split_time = ti.right_child().start_time();
  split_samples(tile.double_samples, split_time, children[0], children[1]);
  split_samples(tile.string_samples, split_time, children[0], children[1]);

  for (int i = 0; i < 2; i++) {
    assert(!has_tile(child_indexes[i]));
    assert(split_tile_if_needed(child_indexes[i], children[i]) == TileIndex::null());
    write_tile(child_indexes[i], children[i]);
  }
  create_parent_tile_from_children(ti, tile, children);
  return new_root_index;
}

bool Channel::read_tile_or_closest_ancestor(TileIndex ti, TileIndex &ret_index, Tile &ret) const {
  Locker lock(*this);  // Lock self and hold lock until exiting this method
  ChannelInfo info;
  bool success = read_info(info);
  if (!success) {
    if (verbosity) log_f("read_tile_or_closest_ancestor: can't read info");
    return false;
  }
  TileIndex root = info.nonnegative_root_tile_index;

  if (ti.is_ancestor_of(root)) {
    ret_index = root;
  } else {
    if (ti != root && !root.is_ancestor_of(ti)) {
      // Tile isn't under root
      return false;
    }
    
    assert(tile_exists(root));
    ret_index = root;
    while (ret_index != ti) {
      TileIndex child = ti.start_time() < ret_index.left_child().end_time() ? ret_index.left_child() : ret_index.right_child();
      if (!tile_exists(child)) break;
      ret_index = child;
    }
  }
  // ret_index now holds closest ancestor to ti (or ti itself if it exists)  
    
  assert(read_tile(ret_index, ret));
  return true;
}

void TileGrid::setNeedsDisplayInRect(const IntRect& rect)
{
    if (m_tiles.isEmpty())
        return;

    FloatRect scaledRect(rect);
    scaledRect.scale(m_scale);
    IntRect repaintRectInTileCoords(enclosingIntRect(scaledRect));

    IntSize tileSize = m_controller.tileSize();

    // For small invalidations, lookup the covered tiles.
    if (repaintRectInTileCoords.height() < 2 * tileSize.height() && repaintRectInTileCoords.width() < 2 * tileSize.width()) {
        TileIndex topLeft;
        TileIndex bottomRight;
        getTileIndexRangeForRect(repaintRectInTileCoords, topLeft, bottomRight);

        for (int y = topLeft.y(); y <= bottomRight.y(); ++y) {
            for (int x = topLeft.x(); x <= bottomRight.x(); ++x) {
                TileIndex tileIndex(x, y);

                TileMap::iterator it = m_tiles.find(tileIndex);
                if (it != m_tiles.end())
                    setTileNeedsDisplayInRect(tileIndex, it->value, repaintRectInTileCoords, m_primaryTileCoverageRect);
            }
        }
        return;
    }

    for (TileMap::iterator it = m_tiles.begin(), end = m_tiles.end(); it != end; ++it)
        setTileNeedsDisplayInRect(it->key, it->value, repaintRectInTileCoords, m_primaryTileCoverageRect);
}

void Channel::read_bottommost_tiles_in_range(Range times,
                                             bool (*callback)(const Tile &t, Range times)) const {
  ChannelInfo info;
  bool success = read_info(info);
  if (!success) return;
  if (!info.times.intersects(times)) return;

  double time = times.min;
  TileIndex ti = TileIndex::null();
  while (time < times.max) {
    if (ti.is_null()) {
      ti = find_lowest_child_overlapping_time(info.nonnegative_root_tile_index, times.min);
    } else {
      ti = find_lowest_successive_tile(info.nonnegative_root_tile_index, ti);
    }
    if (ti.is_null() || ti.start_time() >= times.max) break;

    Tile t;
    assert(read_tile(ti, t));
    if (!(*callback)(t, times)) break;
  }
}

TileIndex Channel::find_successive_tile(TileIndex root, TileIndex ti, int desired_level) const {
  // Move upwards until parent has a different end time
  while (1) {
    if (ti.parent().is_null()) return TileIndex::null();
    if (ti.parent().end_time() != ti.end_time()) break;
    ti = ti.parent();
    if (ti.level >= root.level) {
      // No more underneath the root
      return TileIndex::null();
    }
  }
  // We are now the left child of our parent;  skip to the right child
  ti = ti.sibling();

  return find_child_overlapping_time(ti, ti.start_time(), desired_level);
}

bool Channel::delete_tile(TileIndex ti) {
  return m_kvs.del(tile_key(ti));
  if (verbosity) log_f("Channel: delete_tile %s %s", 
                       descriptor().c_str(), ti.to_string().c_str());
}

IntRect TileGrid::ensureTilesForRect(const FloatRect& rect, CoverageType newTileType)
{
    if (m_controller.unparentsOffscreenTiles() && !m_controller.isInWindow())
        return IntRect();

    FloatRect scaledRect(rect);
    scaledRect.scale(m_scale);
    IntRect rectInTileCoords(enclosingIntRect(scaledRect));

    TileIndex topLeft;
    TileIndex bottomRight;
    getTileIndexRangeForRect(rectInTileCoords, topLeft, bottomRight);

    TileCohort currCohort = nextTileCohort();
    unsigned tilesInCohort = 0;

    IntRect coverageRect;

    for (int y = topLeft.y(); y <= bottomRight.y(); ++y) {
        for (int x = topLeft.x(); x <= bottomRight.x(); ++x) {
            TileIndex tileIndex(x, y);

            IntRect tileRect = rectForTileIndex(tileIndex);
            TileInfo& tileInfo = m_tiles.add(tileIndex, TileInfo()).iterator->value;

            coverageRect.unite(tileRect);

            bool shouldChangeTileLayerFrame = false;

            if (!tileInfo.layer) {
                tileInfo.layer = m_controller.createTileLayer(tileRect, *this);
                ASSERT(!m_tileRepaintCounts.contains(tileInfo.layer.get()));
            } else {
                // We already have a layer for this tile. Ensure that its size is correct.
                FloatSize tileLayerSize(tileInfo.layer->bounds().size());
                shouldChangeTileLayerFrame = tileLayerSize != FloatSize(tileRect.size());

                if (shouldChangeTileLayerFrame) {
                    tileInfo.layer->setBounds(FloatRect(FloatPoint(), tileRect.size()));
                    tileInfo.layer->setPosition(tileRect.location());
                    tileInfo.layer->setNeedsDisplay();
                }
            }

            if (newTileType == CoverageType::SecondaryTiles && !tileRect.intersects(m_primaryTileCoverageRect)) {
                tileInfo.cohort = currCohort;
                ++tilesInCohort;
            }

            bool shouldParentTileLayer = (!m_controller.unparentsOffscreenTiles() || m_controller.isInWindow()) && !tileInfo.layer->superlayer();

            if (shouldParentTileLayer)
                m_containerLayer.get().appendSublayer(*tileInfo.layer);
        }
    }

    if (tilesInCohort)
        startedNewCohort(currCohort);

    return coverageRect;
}

std::string Channel::dump_tile_summaries_internal(TileIndex ti, int level) const {
  Tile tile;
  if (!read_tile(ti, tile)) return "";
  std::string ret = string_printf("%*s%d.%d: %zd samples\n", level, "", ti.level, ti.offset, tile.double_samples.size());
  return ret + dump_tile_summaries_internal(ti.left_child(), level+1) + dump_tile_summaries_internal(ti.right_child(), level+1);
}