// Copyright 2016 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.

#ifndef CustomElementUpgradeSorter_h
#define CustomElementUpgradeSorter_h

#include "core/CoreExport.h"
#include "platform/heap/Handle.h"

namespace blink {

class Element;
class Node;

// Does a shadow-including tree order sort of a subset of elements.
// https://dom.spec.whatwg.org/#concept-shadow-including-tree-order
class CORE_EXPORT CustomElementUpgradeSorter {
    STACK_ALLOCATED();
public:
    CustomElementUpgradeSorter();

    // Record an element of interest. The DOM tree must not be
    // modified between calls to add and the call to sorted.
    void add(Element*);

    // Adds shadow-including descendents of parent to result in
    // shadow-including tree order. This operation is destroys the
    // state of this sorter; after calling sorted, you must not call
    // add or sorted again with this object.
    void sorted(HeapVector<Member<Element>>* result, Node* parent);

private:
    using ChildSet = HeapHashSet<Member<Node>>;
    using ParentChildMap = HeapHashMap<Member<Node>, ChildSet>;

    enum AddResult {
        kParentAlreadyExistsInMap,
        kParentAddedToMap
    };

    AddResult addToParentChildMap(Node* parent, Node* child);
    void visit(
        HeapVector<Member<Element>>* result,
        ChildSet&,
        const ChildSet::iterator&);

    Member<HeapHashSet<Member<Element>>> m_elements;

    // This is the subset of the tree, from root node (usually
    // document) through elements and shadow roots, to candidates.
    Member<ParentChildMap> m_parentChildMap;
};

} // namespace blink

#endif // CustomElementUpgradeSorter_h