/*
 * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
 *           (C) 1999 Antti Koivisto (koivisto@kde.org)
 *           (C) 2007 David Smith (catfish.man@gmail.com)
 * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 Apple Inc.
 * All rights reserved.
 * Copyright (C) Research In Motion Limited 2010. All rights reserved.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public License
 * along with this library; see the file COPYING.LIB.  If not, write to
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
 */

#ifndef THIRD_PARTY_BLINK_RENDERER_CORE_LAYOUT_FLOATING_OBJECTS_H_
#define THIRD_PARTY_BLINK_RENDERER_CORE_LAYOUT_FLOATING_OBJECTS_H_

#include "base/dcheck_is_on.h"
#include "base/types/pass_key.h"
#include "third_party/blink/renderer/platform/geometry/layout_rect.h"
#include "third_party/blink/renderer/platform/heap/collection_support/clear_collection_scope.h"
#include "third_party/blink/renderer/platform/heap/collection_support/heap_hash_map.h"
#include "third_party/blink/renderer/platform/heap/collection_support/heap_linked_hash_set.h"
#include "third_party/blink/renderer/platform/heap/garbage_collected.h"
#include "third_party/blink/renderer/platform/wtf/linked_hash_set.h"
#include "third_party/blink/renderer/platform/wtf/pod_free_list_arena.h"
#include "third_party/blink/renderer/platform/wtf/pod_interval_tree.h"

namespace blink {

class LayoutBlockFlow;
class LayoutBox;
class RootInlineBox;

class FloatingObject : public GarbageCollected<FloatingObject> {
 public:
#ifndef NDEBUG
  // Used by the PODIntervalTree for debugging the FloatingObject.
  template <class>
  friend struct WTF::ValueToString;
#endif

  // Note that Type uses bits so you can use FloatLeftRight as a mask to query
  // for both left and right.
  enum Type { kFloatLeft = 1, kFloatRight = 2, kFloatLeftRight = 3 };

  static FloatingObject* Create(LayoutBox*, Type);

  FloatingObject* CopyToNewContainer(LayoutSize,
                                     bool should_paint = false,
                                     bool is_descendant = false) const;

  FloatingObject* UnsafeClone() const;

  Type GetType() const { return static_cast<Type>(type_); }
  LayoutBox* GetLayoutObject() const { return layout_object_; }

  bool IsPlaced() const { return is_placed_; }
  void SetIsPlaced(bool placed = true) {
    is_placed_ = placed;
#if DCHECK_IS_ON()
    has_geometry_ = placed;
#endif
  }

#if DCHECK_IS_ON()
  void SetHasGeometry() { has_geometry_ = true; }
#endif

  bool HasGeometry() const {
#if DCHECK_IS_ON()
    return has_geometry_;
#else
    return true;
#endif
  }

  LayoutUnit X() const {
    DCHECK(HasGeometry());
    return frame_rect_.X();
  }
  LayoutUnit MaxX() const {
    DCHECK(HasGeometry());
    return frame_rect_.MaxX();
  }
  LayoutUnit Y() const {
    DCHECK(HasGeometry());
    return frame_rect_.Y();
  }
  LayoutUnit MaxY() const {
    DCHECK(HasGeometry());
    return frame_rect_.MaxY();
  }
  LayoutUnit Width() const { return frame_rect_.Width(); }
  LayoutUnit Height() const { return frame_rect_.Height(); }

  void SetX(LayoutUnit x) {
    DCHECK(!IsInPlacedTree());
    frame_rect_.SetX(x);
  }
  void SetY(LayoutUnit y) {
    DCHECK(!IsInPlacedTree());
    frame_rect_.SetY(y);
  }
  void SetWidth(LayoutUnit width) {
    DCHECK(!IsInPlacedTree());
    frame_rect_.SetWidth(width);
  }
  void SetHeight(LayoutUnit height) {
    DCHECK(!IsInPlacedTree());
    frame_rect_.SetHeight(height);
  }

  const LayoutRect& FrameRect() const {
    DCHECK(HasGeometry());
    return frame_rect_;
  }

  bool IsInPlacedTree() const { return is_in_placed_tree_; }
  void SetIsInPlacedTree(bool value) { is_in_placed_tree_ = value; }

  bool ShouldPaint() const { return should_paint_; }
  void SetShouldPaint(bool should_paint) { should_paint_ = should_paint; }
  bool IsDescendant() const { return is_descendant_; }
  void SetIsDescendant(bool is_descendant) { is_descendant_ = is_descendant; }
  bool IsLowestNonOverhangingFloatInChild() const {
    return is_lowest_non_overhanging_float_in_child_;
  }
  void SetIsLowestNonOverhangingFloatInChild(
      bool is_lowest_non_overhanging_float_in_child) {
    is_lowest_non_overhanging_float_in_child_ =
        is_lowest_non_overhanging_float_in_child;
  }

  // FIXME: Callers of these methods are dangerous and should be removed.
  RootInlineBox* OriginatingLine() const { return originating_line_; }
  void SetOriginatingLine(RootInlineBox* line) { originating_line_ = line; }

  using PassKey = base::PassKey<FloatingObject>;
  FloatingObject(PassKey, LayoutBox*, Type);
  FloatingObject(PassKey,
                 LayoutBox*,
                 Type,
                 const LayoutRect&,
                 bool should_paint,
                 bool is_descendant,
                 bool is_lowest_non_overhanging_float_in_child);
  FloatingObject(const FloatingObject&) = delete;
  FloatingObject& operator=(const FloatingObject&) = delete;
  void Trace(Visitor*) const;

 private:
  Member<LayoutBox> layout_object_;
  Member<RootInlineBox> originating_line_;
  LayoutRect frame_rect_;

  unsigned type_ : 2;  // Type (left or right aligned)
  unsigned should_paint_ : 1;
  unsigned is_descendant_ : 1;
  unsigned is_placed_ : 1;
  unsigned is_lowest_non_overhanging_float_in_child_ : 1;
  unsigned is_in_placed_tree_ : 1;

#if DCHECK_IS_ON()
  // If set, it's safe to read out position data for this float. For LayoutNG
  // this will always be true, while for legacy layout, it depends on whether
  // the float IsPlaced() or not.
  unsigned has_geometry_ : 1;
#endif
};

struct FloatingObjectHashFunctions {
  STATIC_ONLY(FloatingObjectHashFunctions);
  static unsigned GetHash(FloatingObject* key) {
    return DefaultHash<LayoutBox*>::Hash::GetHash(key->GetLayoutObject());
  }
  static unsigned GetHash(const Member<FloatingObject>& key) {
    return GetHash(key.Get());
  }
  static bool Equal(const Member<FloatingObject>& a, FloatingObject* b) {
    return a->GetLayoutObject() == b->GetLayoutObject();
  }
  static bool Equal(const Member<FloatingObject>& a,
                    const Member<FloatingObject>& b) {
    return Equal(a, b.Get());
  }

  static const bool safe_to_compare_to_empty_or_deleted = false;
};
struct FloatingObjectHashTranslator {
  STATIC_ONLY(FloatingObjectHashTranslator);
  static unsigned GetHash(LayoutBox* key) {
    return DefaultHash<LayoutBox*>::Hash::GetHash(key);
  }
  static bool Equal(FloatingObject* a, LayoutBox* b) {
    return a->GetLayoutObject() == b;
  }
  static bool Equal(const Member<FloatingObject>& a, LayoutBox* b) {
    return a->GetLayoutObject() == b;
  }
};

typedef HeapLinkedHashSet<Member<FloatingObject>,
                          HashTraits<Member<FloatingObject>>,
                          FloatingObjectHashFunctions>
    FloatingObjectSet;
typedef FloatingObjectSet::const_iterator FloatingObjectSetIterator;
typedef WTF::PODInterval<LayoutUnit, FloatingObject*> FloatingObjectInterval;
typedef WTF::PODIntervalTree<LayoutUnit, FloatingObject*> FloatingObjectTree;
typedef WTF::PODFreeListArena<
    WTF::PODRedBlackTree<FloatingObjectInterval>::Node>
    IntervalArena;
typedef HeapHashMap<Member<LayoutBox>, Member<FloatingObject>>
    LayoutBoxToFloatInfoMap;

class FloatingObjects final : public GarbageCollected<FloatingObjects> {
 public:
  FloatingObjects(const LayoutBlockFlow*, bool horizontal_writing_mode);
  FloatingObjects(const FloatingObjects&) = delete;
  FloatingObjects& operator=(const FloatingObjects&) = delete;
  ~FloatingObjects();
  void Trace(Visitor*) const;

  void Clear();
  void MoveAllToFloatInfoMap(LayoutBoxToFloatInfoMap&);
  FloatingObject* Add(FloatingObject*);
  void Remove(FloatingObject*);
  void AddPlacedObject(FloatingObject&);
  void RemovePlacedObject(FloatingObject&);
  void SetHorizontalWritingMode(bool b = true) { horizontal_writing_mode_ = b; }

  bool HasLeftObjects() const { return left_objects_count_ > 0; }
  bool HasRightObjects() const { return right_objects_count_ > 0; }
  const FloatingObjectSet& Set() const { return set_; }
  FloatingObjectSet& MutableSet() { return set_; }
  void ClearLineBoxTreePointers();

  LayoutUnit LogicalLeftOffset(LayoutUnit fixed_offset,
                               LayoutUnit logical_top,
                               LayoutUnit logical_height);
  LayoutUnit LogicalRightOffset(LayoutUnit fixed_offset,
                                LayoutUnit logical_top,
                                LayoutUnit logical_height);

  LayoutUnit LogicalLeftOffsetForPositioningFloat(LayoutUnit fixed_offset,
                                                  LayoutUnit logical_top,
                                                  LayoutUnit* height_remaining);
  LayoutUnit LogicalRightOffsetForPositioningFloat(
      LayoutUnit fixed_offset,
      LayoutUnit logical_top,
      LayoutUnit* height_remaining);

  LayoutUnit LogicalLeftOffsetForAvoidingFloats(LayoutUnit fixed_offset,
                                                LayoutUnit logical_top,
                                                LayoutUnit logical_height);
  LayoutUnit LogicalRightOffsetForAvoidingFloats(LayoutUnit fixed_offset,
                                                 LayoutUnit logical_top,
                                                 LayoutUnit logical_height);

  LayoutUnit FindNextFloatLogicalBottomBelow(LayoutUnit logical_height);
  LayoutUnit FindNextFloatLogicalBottomBelowForBlock(LayoutUnit logical_height);

  LayoutUnit LowestFloatLogicalBottom(FloatingObject::Type);
  FloatingObject* LowestFloatingObject();

 private:
  bool HasLowestFloatLogicalBottomCached(bool is_horizontal,
                                         FloatingObject::Type float_type) const;
  LayoutUnit GetCachedlowestFloatLogicalBottom(
      FloatingObject::Type float_type) const;
  void SetCachedLowestFloatLogicalBottom(bool is_horizontal,
                                         FloatingObject::Type float_type,
                                         FloatingObject*);
  void MarkLowestFloatLogicalBottomCacheAsDirty();

  void ComputePlacedFloatsTree();
  const FloatingObjectTree& PlacedFloatsTree() {
    if (!placed_floats_tree_.IsInitialized())
      ComputePlacedFloatsTree();
    return placed_floats_tree_;
  }
  void IncreaseObjectsCount(FloatingObject::Type);
  void DecreaseObjectsCount(FloatingObject::Type);
  FloatingObjectInterval IntervalForFloatingObject(FloatingObject&);

  FloatingObjectSet set_;
  FloatingObjectTree placed_floats_tree_;
  unsigned left_objects_count_;
  unsigned right_objects_count_;
  bool horizontal_writing_mode_;
  Member<const LayoutBlockFlow> layout_object_;

  struct FloatBottomCachedValue {
    DISALLOW_NEW();
    FloatBottomCachedValue();
    void Trace(Visitor*) const;
    Member<FloatingObject> floating_object;
    bool dirty = true;
  };
  FloatBottomCachedValue lowest_float_bottom_cache_[2];
  bool cached_horizontal_writing_mode_;
};

}  // namespace blink

namespace WTF {
#ifndef NDEBUG
// These structures are used by PODIntervalTree for debugging purposes.
template <>
struct ValueToString<blink::LayoutUnit> {
  static String ToString(const blink::LayoutUnit value);
};
template <>
struct ValueToString<blink::FloatingObject*> {
  static String ToString(const blink::FloatingObject*);
};
#endif
}  // namespace WTF

#endif  // THIRD_PARTY_BLINK_RENDERER_CORE_LAYOUT_FLOATING_OBJECTS_H_