diff --git a/src/abstractmodel/treeitem.cpp b/src/abstractmodel/treeitem.cpp index 61a95d3fb..281767009 100644 --- a/src/abstractmodel/treeitem.cpp +++ b/src/abstractmodel/treeitem.cpp @@ -1,272 +1,286 @@ /*************************************************************************** * Copyright (C) 2017 by Nicolas Carion * * This file is part of Kdenlive. See www.kdenlive.org. * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) version 3 or any later version accepted by the * * membership of KDE e.V. (or its successor approved by the membership * * of KDE e.V.), which shall act as a proxy defined in Section 14 of * * version 3 of the license. * * * * This program 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 General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program. If not, see . * ***************************************************************************/ #include "treeitem.hpp" #include "abstracttreemodel.hpp" #include #include #include TreeItem::TreeItem(const QList &data, const std::shared_ptr &model, bool isRoot, int id) : m_itemData(data) , m_model(model) , m_depth(0) , m_id(id == -1 ? AbstractTreeModel::getNextId() : id) , m_isInModel(false) , m_isRoot(isRoot) { } std::shared_ptr TreeItem::construct(const QList &data, std::shared_ptr model, bool isRoot, int id) { std::shared_ptr self(new TreeItem(data, std::move(model), isRoot, id)); baseFinishConstruct(self); return self; } // static void TreeItem::baseFinishConstruct(const std::shared_ptr &self) { if (self->m_isRoot) { registerSelf(self); } } TreeItem::~TreeItem() { deregisterSelf(); } std::shared_ptr TreeItem::appendChild(const QList &data) { if (auto ptr = m_model.lock()) { auto child = construct(data, ptr, false); appendChild(child); return child; } qDebug() << "ERROR: Something went wrong when appending child in TreeItem. Model is not available anymore"; Q_ASSERT(false); return std::shared_ptr(); } bool TreeItem::appendChild(std::shared_ptr child) { if (hasAncestor(child->getId())) { // in that case, we are trying to create a cycle, abort return false; } if (auto oldParent = child->parentItem().lock()) { if (oldParent->getId() == m_id) { // no change needed return true; } else { // in that case a call to removeChild should have been carried out qDebug() << "ERROR: trying to append a child that alrealdy has a parent"; return false; } } if (auto ptr = m_model.lock()) { ptr->notifyRowAboutToAppend(shared_from_this()); child->updateParent(shared_from_this()); int id = child->getId(); auto it = m_childItems.insert(m_childItems.end(), child); m_iteratorTable[id] = it; registerSelf(child); ptr->notifyRowAppended(child); return true; } qDebug() << "ERROR: Something went wrong when appending child in TreeItem. Model is not available anymore"; Q_ASSERT(false); return false; } void TreeItem::moveChild(int ix, std::shared_ptr child) { if (auto ptr = m_model.lock()) { auto parentPtr = child->m_parentItem.lock(); if (parentPtr && parentPtr->getId() != m_id) { parentPtr->removeChild(child); } else { // deletion of child auto it = m_iteratorTable[child->getId()]; m_childItems.erase(it); } ptr->notifyRowAboutToAppend(shared_from_this()); child->updateParent(shared_from_this()); int id = child->getId(); auto pos = m_childItems.begin(); std::advance(pos, ix); auto it = m_childItems.insert(pos, child); m_iteratorTable[id] = it; ptr->notifyRowAppended(child); m_isInModel = true; } else { qDebug() << "ERROR: Something went wrong when moving child in TreeItem. Model is not available anymore"; Q_ASSERT(false); } } void TreeItem::removeChild(const std::shared_ptr &child) { if (auto ptr = m_model.lock()) { ptr->notifyRowAboutToDelete(shared_from_this(), child->row()); // get iterator corresponding to child Q_ASSERT(m_iteratorTable.count(child->getId()) > 0); auto it = m_iteratorTable[child->getId()]; // deletion of child m_childItems.erase(it); // clean iterator table m_iteratorTable.erase(child->getId()); child->m_depth = 0; child->m_parentItem.reset(); child->deregisterSelf(); ptr->notifyRowDeleted(); } else { qDebug() << "ERROR: Something went wrong when removing child in TreeItem. Model is not available anymore"; Q_ASSERT(false); } } bool TreeItem::changeParent(std::shared_ptr newParent) { Q_ASSERT(!m_isRoot); if (m_isRoot) return false; std::shared_ptr oldParent; if ((oldParent = m_parentItem.lock())) { oldParent->removeChild(shared_from_this()); } bool res = true; if (newParent) { res = newParent->appendChild(shared_from_this()); if (res) { m_parentItem = newParent; } else if (oldParent) { // something went wrong, we have to reset the parent. bool reverse = oldParent->appendChild(shared_from_this()); Q_ASSERT(reverse); } } return res; } std::shared_ptr TreeItem::child(int row) const { Q_ASSERT(row >= 0 && row < (int)m_childItems.size()); auto it = m_childItems.cbegin(); std::advance(it, row); return (*it); } int TreeItem::childCount() const { return (int)m_childItems.size(); } int TreeItem::columnCount() const { return m_itemData.count(); } QVariant TreeItem::dataColumn(int column) const { return m_itemData.value(column); } std::weak_ptr TreeItem::parentItem() const { return m_parentItem; } int TreeItem::row() const { if (auto ptr = m_parentItem.lock()) { // we compute the distance in the parent's children list auto it = ptr->m_childItems.begin(); return (int)std::distance(it, (decltype(it))ptr->m_iteratorTable.at(m_id)); } return -1; } int TreeItem::depth() const { return m_depth; } int TreeItem::getId() const { return m_id; } bool TreeItem::isInModel() const { return m_isInModel; } void TreeItem::registerSelf(std::shared_ptr self) { for (const auto &child : self->m_childItems) { registerSelf(child); } if (auto ptr = self->m_model.lock()) { ptr->registerItem(self); self->m_isInModel = true; } else { qDebug() << "Error : construction of treeItem failed because parent model is not available anymore"; Q_ASSERT(false); } } void TreeItem::deregisterSelf() { for (const auto &child : m_childItems) { child->deregisterSelf(); } if (m_isInModel) { if (auto ptr = m_model.lock()) { ptr->deregisterItem(m_id, this); m_isInModel = false; } } } bool TreeItem::hasAncestor(int id) { if (m_id == id) { return true; } if (auto ptr = m_parentItem.lock()) { return ptr->hasAncestor(id); } return false; } bool TreeItem::isRoot() const { return m_isRoot; } void TreeItem::updateParent(std::shared_ptr parent) { m_parentItem = parent; if (parent) { m_depth = parent->m_depth + 1; } } + +std::vector> TreeItem::getLeaves() +{ + if (childCount() == 0) { + return {shared_from_this()}; + } + std::vector> leaves; + for (const auto &c : m_childItems) { + for (const auto &l : c->getLeaves()) { + leaves.push_back(l); + } + } + return leaves; +} diff --git a/src/abstractmodel/treeitem.hpp b/src/abstractmodel/treeitem.hpp index 8b94e19a5..4b6a0ad19 100644 --- a/src/abstractmodel/treeitem.hpp +++ b/src/abstractmodel/treeitem.hpp @@ -1,173 +1,176 @@ /*************************************************************************** * Copyright (C) 2017 by Nicolas Carion * * This file is part of Kdenlive. See www.kdenlive.org. * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) version 3 or any later version accepted by the * * membership of KDE e.V. (or its successor approved by the membership * * of KDE e.V.), which shall act as a proxy defined in Section 14 of * * version 3 of the license. * * * * This program 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 General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program. If not, see . * ***************************************************************************/ #ifndef TREEITEM_H #define TREEITEM_H #include "definitions.h" #include #include #include #include /* @brief This class is a generic class to represent items of a tree-like model It works in tandem with AbstractTreeModel or one of its derived classes. There is a registration mechanism that takes place: each TreeItem holds a unique Id that can allow to retrieve it directly from the model. A TreeItem registers itself to the model as soon as it gets a proper parent (the node above it in the hierarchy). This means that upon creation, the TreeItem is NOT registered, because at this point it doesn't belong to any parent. The only exception is for the rootItem, which is always registered. Note that the root is a special object. In particular, it must stay at the root and must not be declared as the child of any other item. */ class AbstractTreeModel; class TreeItem : public enable_shared_from_this_virtual { public: /* @brief Construct a TreeItem @param data List of data elements (columns) of the created item @param model Pointer to the model to which this elem belongs to @param parentItem address of the parent if the child is not orphan @param isRoot is true if the object is the topmost item of the tree @param id of the newly created item. If left to -1, the id is assigned automatically @return a ptr to the constructed item */ static std::shared_ptr construct(const QList &data, std::shared_ptr model, bool isRoot, int id = -1); friend class AbstractTreeModel; protected: // This is protected. Call construct instead explicit TreeItem(const QList &data, const std::shared_ptr &model, bool isRoot, int id = -1); public: virtual ~TreeItem(); /* @brief Creates a child of the current item @param data: List of data elements (columns) to init the child with. */ std::shared_ptr appendChild(const QList &data); /* @brief Appends an already created child Useful for example if the child should be a subclass of TreeItem @return true on success. Otherwise, nothing is modified. */ bool appendChild(std::shared_ptr child); void moveChild(int ix, std::shared_ptr child); /* @brief Remove given child from children list. The parent of the child is updated accordingly */ void removeChild(const std::shared_ptr &child); /* @brief Change the parent of the current item. Structures are modified accordingly */ virtual bool changeParent(std::shared_ptr newParent); /* @brief Retrieves a child of the current item @param row is the index of the child to retrieve */ std::shared_ptr child(int row) const; + /* @brief Returns a vector containing a pointer to all the leaves in the subtree rooted in this element */ + std::vector> getLeaves(); + /* @brief Return the number of children */ int childCount() const; /* @brief Return the number of data fields (columns) */ int columnCount() const; /* @brief Return the content of a column @param column Index of the column to look-up */ QVariant dataColumn(int column) const; /* @brief Return the index of current item amongst father's children Returns -1 on error (eg: no parent set) */ int row() const; /* @brief Return a ptr to the parent item */ std::weak_ptr parentItem() const; /* @brief Return the depth of the current item*/ int depth() const; /* @brief Return the id of the current item*/ int getId() const; /* @brief Return true if the current item has been registered */ bool isInModel() const; /* @brief This is similar to the std::accumulate function, except that it operates on the whole subtree @param init is the initial value of the operation @param is the binary op to apply (signature should be (T, shared_ptr)->T) */ template T accumulate(T init, BinaryOperation op); /* @brief Return true if the current item has the item with given id as an ancestor */ bool hasAncestor(int id); /* @brief Return true if the item thinks it is a root. Note that it should be consistent with what the model thinks, but it may have been messed up at some point if someone wrongly constructed the object with isRoot = true */ bool isRoot() const; protected: /* @brief Finish construction of object given its pointer This is a separated function so that it can be called from derived classes */ static void baseFinishConstruct(const std::shared_ptr &self); /* @brief Helper functions to handle registration / deregistration to the model */ static void registerSelf(std::shared_ptr self); void deregisterSelf(); /* @brief Reflect update of the parent ptr (for example set the correct depth) This is meant to be overriden in derived classes @param ptr is the pointer to the new parent */ virtual void updateParent(std::shared_ptr parent); std::list> m_childItems; std::unordered_map>::iterator> m_iteratorTable; // this logs the iterator associated which each child id. This allows easy access of a child based on its id. QList m_itemData; std::weak_ptr m_parentItem; std::weak_ptr m_model; int m_depth; int m_id; bool m_isInModel; bool m_isRoot; }; template T TreeItem::accumulate(T init, BinaryOperation op) { T res = op(init, shared_from_this()); return std::accumulate(m_childItems.begin(), m_childItems.end(), res, op); } #endif