// Copyright 2014 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 "cc/resources/eviction_tile_priority_queue.h"

namespace cc {

namespace {

class EvictionOrderComparator {
 public:
  explicit EvictionOrderComparator(TreePriority tree_priority)
      : tree_priority_(tree_priority) {}

  bool operator()(
      const EvictionTilePriorityQueue::PairedPictureLayerQueue* a,
      const EvictionTilePriorityQueue::PairedPictureLayerQueue* b) const {
    // Note that in this function, we have to return true if and only if
    // b is strictly lower priority than a. Note that for the sake of
    // completeness, empty queue is considered to have lowest priority.
    if (a->IsEmpty() || b->IsEmpty())
      return b->IsEmpty() < a->IsEmpty();

    WhichTree a_tree = a->NextTileIteratorTree(tree_priority_);
    const PictureLayerImpl::LayerEvictionTileIterator* a_iterator =
        a_tree == ACTIVE_TREE ? &a->active_iterator : &a->pending_iterator;

    WhichTree b_tree = b->NextTileIteratorTree(tree_priority_);
    const PictureLayerImpl::LayerEvictionTileIterator* b_iterator =
        b_tree == ACTIVE_TREE ? &b->active_iterator : &b->pending_iterator;

    const Tile* a_tile = **a_iterator;
    const Tile* b_tile = **b_iterator;

    const TilePriority& a_priority =
        a_tile->priority_for_tree_priority(tree_priority_);
    const TilePriority& b_priority =
        b_tile->priority_for_tree_priority(tree_priority_);
    bool prioritize_low_res = tree_priority_ == SMOOTHNESS_TAKES_PRIORITY;

    // If the priority bin differs, b is lower priority if it has the higher
    // priority bin.
    if (a_priority.priority_bin != b_priority.priority_bin)
      return b_priority.priority_bin > a_priority.priority_bin;

    // Otherwise if the resolution differs, then the order will be determined by
    // whether we prioritize low res or not.
    // TODO(vmpstr): Remove this when TilePriority is no longer a member of Tile
    // class but instead produced by the iterators.
    if (b_priority.resolution != a_priority.resolution) {
      // Non ideal resolution should be sorted higher than other resolutions.
      if (a_priority.resolution == NON_IDEAL_RESOLUTION)
        return false;

      if (b_priority.resolution == NON_IDEAL_RESOLUTION)
        return true;

      if (prioritize_low_res)
        return a_priority.resolution == LOW_RESOLUTION;
      return a_priority.resolution == HIGH_RESOLUTION;
    }

    // Otherwise if the occlusion differs, b is lower priority if it is
    // occluded.
    bool a_is_occluded = a_tile->is_occluded_for_tree_priority(tree_priority_);
    bool b_is_occluded = b_tile->is_occluded_for_tree_priority(tree_priority_);
    if (a_is_occluded != b_is_occluded)
      return b_is_occluded;

    // b is lower priorty if it is farther from visible.
    return b_priority.distance_to_visible > a_priority.distance_to_visible;
  }

 private:
  TreePriority tree_priority_;
};

}  // namespace

EvictionTilePriorityQueue::EvictionTilePriorityQueue() {
}

EvictionTilePriorityQueue::~EvictionTilePriorityQueue() {
}

void EvictionTilePriorityQueue::Build(
    const std::vector<PictureLayerImpl::Pair>& paired_layers,
    TreePriority tree_priority) {
  tree_priority_ = tree_priority;

  for (std::vector<PictureLayerImpl::Pair>::const_iterator it =
           paired_layers.begin();
       it != paired_layers.end();
       ++it) {
    paired_queues_.push_back(
        make_scoped_ptr(new PairedPictureLayerQueue(*it, tree_priority_)));
  }

  paired_queues_.make_heap(EvictionOrderComparator(tree_priority_));
}

void EvictionTilePriorityQueue::Reset() {
  paired_queues_.clear();
}

bool EvictionTilePriorityQueue::IsEmpty() const {
  return paired_queues_.empty() || paired_queues_.front()->IsEmpty();
}

Tile* EvictionTilePriorityQueue::Top() {
  DCHECK(!IsEmpty());
  return paired_queues_.front()->Top(tree_priority_);
}

void EvictionTilePriorityQueue::Pop() {
  DCHECK(!IsEmpty());

  paired_queues_.pop_heap(EvictionOrderComparator(tree_priority_));
  PairedPictureLayerQueue* paired_queue = paired_queues_.back();
  paired_queue->Pop(tree_priority_);
  paired_queues_.push_heap(EvictionOrderComparator(tree_priority_));
}

EvictionTilePriorityQueue::PairedPictureLayerQueue::PairedPictureLayerQueue() {
}

EvictionTilePriorityQueue::PairedPictureLayerQueue::PairedPictureLayerQueue(
    const PictureLayerImpl::Pair& layer_pair,
    TreePriority tree_priority)
    : active_iterator(
          layer_pair.active
              ? PictureLayerImpl::LayerEvictionTileIterator(layer_pair.active,
                                                            tree_priority)
              : PictureLayerImpl::LayerEvictionTileIterator()),
      pending_iterator(
          layer_pair.pending
              ? PictureLayerImpl::LayerEvictionTileIterator(layer_pair.pending,
                                                            tree_priority)
              : PictureLayerImpl::LayerEvictionTileIterator()) {
}

EvictionTilePriorityQueue::PairedPictureLayerQueue::~PairedPictureLayerQueue() {
}

bool EvictionTilePriorityQueue::PairedPictureLayerQueue::IsEmpty() const {
  return !active_iterator && !pending_iterator;
}

Tile* EvictionTilePriorityQueue::PairedPictureLayerQueue::Top(
    TreePriority tree_priority) {
  DCHECK(!IsEmpty());

  WhichTree next_tree = NextTileIteratorTree(tree_priority);
  PictureLayerImpl::LayerEvictionTileIterator* next_iterator =
      next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
  DCHECK(*next_iterator);

  Tile* tile = **next_iterator;
  DCHECK(std::find(returned_shared_tiles.begin(),
                   returned_shared_tiles.end(),
                   tile) == returned_shared_tiles.end());
  return tile;
}

void EvictionTilePriorityQueue::PairedPictureLayerQueue::Pop(
    TreePriority tree_priority) {
  DCHECK(!IsEmpty());

  WhichTree next_tree = NextTileIteratorTree(tree_priority);
  PictureLayerImpl::LayerEvictionTileIterator* next_iterator =
      next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
  DCHECK(*next_iterator);
  returned_shared_tiles.push_back(**next_iterator);
  ++(*next_iterator);

  if (IsEmpty())
    return;

  next_tree = NextTileIteratorTree(tree_priority);
  next_iterator =
      next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
  while (std::find(returned_shared_tiles.begin(),
                   returned_shared_tiles.end(),
                   **next_iterator) != returned_shared_tiles.end()) {
    ++(*next_iterator);
    if (IsEmpty())
      break;
    next_tree = NextTileIteratorTree(tree_priority);
    next_iterator =
        next_tree == ACTIVE_TREE ? &active_iterator : &pending_iterator;
  }
}

WhichTree
EvictionTilePriorityQueue::PairedPictureLayerQueue::NextTileIteratorTree(
    TreePriority tree_priority) const {
  DCHECK(!IsEmpty());

  // If we only have one iterator with tiles, return it.
  if (!active_iterator)
    return PENDING_TREE;
  if (!pending_iterator)
    return ACTIVE_TREE;

  const Tile* active_tile = *active_iterator;
  const Tile* pending_tile = *pending_iterator;
  if (active_tile == pending_tile)
    return ACTIVE_TREE;

  const TilePriority& active_priority =
      active_tile->priority_for_tree_priority(tree_priority);
  const TilePriority& pending_priority =
      pending_tile->priority_for_tree_priority(tree_priority);

  if (pending_priority.IsHigherPriorityThan(active_priority))
    return ACTIVE_TREE;
  return PENDING_TREE;
}

}  // namespace cc