1// Copyright 2011 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef CC_TREES_LAYER_SORTER_H_
6#define CC_TREES_LAYER_SORTER_H_
7
8#include <vector>
9
10#include "base/basictypes.h"
11#include "base/containers/hash_tables.h"
12#include "cc/base/cc_export.h"
13#include "cc/layers/layer_impl.h"
14#include "ui/gfx/point3_f.h"
15#include "ui/gfx/quad_f.h"
16#include "ui/gfx/rect_f.h"
17#include "ui/gfx/vector3d_f.h"
18
19#if defined(COMPILER_GCC)
20namespace cc { struct GraphEdge; }
21
22namespace BASE_HASH_NAMESPACE {
23template <>
24struct hash<cc::GraphEdge*> {
25  size_t operator()(cc::GraphEdge* ptr) const {
26    return hash<size_t>()(reinterpret_cast<size_t>(ptr));
27  }
28};
29}  // namespace BASE_HASH_NAMESPACE
30#endif  // COMPILER
31
32namespace gfx {
33class Transform;
34}
35
36namespace cc {
37struct GraphEdge;
38
39// Holds various useful properties derived from a layer's 3D outline.
40struct CC_EXPORT LayerShape {
41  LayerShape();
42  LayerShape(float width, float height, const gfx::Transform& draw_transform);
43  ~LayerShape();
44
45  float LayerZFromProjectedPoint(const gfx::PointF& p) const;
46
47  gfx::Vector3dF layer_normal;
48  gfx::Point3F transform_origin;
49  gfx::QuadF projected_quad;
50  gfx::RectF projected_bounds;
51};
52
53struct GraphNode {
54  explicit GraphNode(LayerImpl* layer_impl);
55  ~GraphNode();
56
57  LayerImpl* layer;
58  LayerShape shape;
59  std::vector<GraphEdge*> incoming;
60  std::vector<GraphEdge*> outgoing;
61  float incoming_edge_weight;
62};
63
64struct GraphEdge {
65  GraphEdge(GraphNode* from_node, GraphNode* to_node, float weight)
66      : from(from_node),
67        to(to_node),
68        weight(weight) {}
69
70  GraphNode* from;
71  GraphNode* to;
72  float weight;
73};
74
75
76
77class CC_EXPORT LayerSorter {
78 public:
79  LayerSorter();
80  ~LayerSorter();
81
82  void Sort(LayerImplList::iterator first, LayerImplList::iterator last);
83
84  enum ABCompareResult {
85    ABeforeB,
86    BBeforeA,
87    None
88  };
89
90  static ABCompareResult CheckOverlap(LayerShape* a,
91                                      LayerShape* b,
92                                      float z_threshold,
93                                      float* weight);
94
95 private:
96  typedef std::vector<GraphNode> NodeList;
97  typedef std::vector<GraphEdge> EdgeList;
98  NodeList nodes_;
99  EdgeList edges_;
100  float z_range_;
101
102  typedef base::hash_map<GraphEdge*, GraphEdge*> EdgeMap;
103  EdgeMap active_edges_;
104
105  void CreateGraphNodes(LayerImplList::iterator first,
106                        LayerImplList::iterator last);
107  void CreateGraphEdges();
108  void RemoveEdgeFromList(GraphEdge* graph, std::vector<GraphEdge*>* list);
109
110  DISALLOW_COPY_AND_ASSIGN(LayerSorter);
111};
112
113}  // namespace cc
114#endif  // CC_TREES_LAYER_SORTER_H_
115