diff --git a/src/timeline2/model/groupsmodel.cpp b/src/timeline2/model/groupsmodel.cpp
index 14a0fb4e1..b68c5cd63 100644
--- a/src/timeline2/model/groupsmodel.cpp
+++ b/src/timeline2/model/groupsmodel.cpp
@@ -1,537 +1,537 @@
/***************************************************************************
* 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 "groupsmodel.hpp"
#include "macros.hpp"
#include "timelineitemmodel.hpp"
#include
#include
#include
#include
GroupsModel::GroupsModel(std::weak_ptr parent)
: m_parent(std::move(parent))
, m_lock(QReadWriteLock::Recursive)
{
}
Fun GroupsModel::groupItems_lambda(int gid, const std::unordered_set &ids, bool temporarySelection, int parent)
{
QWriteLocker locker(&m_lock);
return [gid, ids, parent, temporarySelection, this]() {
createGroupItem(gid);
if (temporarySelection) {
Q_ASSERT(m_selectionGroup == -1);
m_selectionGroup = gid;
}
if (parent != -1) {
setGroup(gid, parent);
}
Q_ASSERT(m_groupIds.count(gid) == 0);
m_groupIds.insert(gid);
auto ptr = m_parent.lock();
if (ptr) {
ptr->registerGroup(gid);
} else {
qDebug() << "Impossible to create group because the timeline is not available anymore";
Q_ASSERT(false);
}
std::unordered_set roots;
std::transform(ids.begin(), ids.end(), std::inserter(roots, roots.begin()), [&](int id) { return getRootId(id); });
for (int id : roots) {
setGroup(getRootId(id), gid);
if (!temporarySelection && ptr->isClip(id)) {
QModelIndex ix = ptr->makeClipIndexFromID(id);
ptr->dataChanged(ix, ix, {TimelineItemModel::GroupedRole});
}
}
return true;
};
}
int GroupsModel::groupItems(const std::unordered_set &ids, Fun &undo, Fun &redo, bool temporarySelection, bool force)
{
QWriteLocker locker(&m_lock);
Q_ASSERT(!ids.empty());
if (ids.size() == 1 && !force) {
// We do not create a group with only one element. Instead, we return the id of that element
return *(ids.begin());
}
int gid = TimelineModel::getNextId();
auto operation = groupItems_lambda(gid, ids, temporarySelection);
if (operation()) {
auto reverse = destructGroupItem_lambda(gid);
UPDATE_UNDO_REDO(operation, reverse, undo, redo);
return gid;
}
return -1;
}
bool GroupsModel::ungroupItem(int id, Fun &undo, Fun &redo, bool temporarySelection)
{
QWriteLocker locker(&m_lock);
int gid = getRootId(id);
if (m_groupIds.count(gid) == 0) {
// element is not part of a group
return false;
}
return destructGroupItem(gid, true, undo, redo, temporarySelection);
}
void GroupsModel::createGroupItem(int id)
{
QWriteLocker locker(&m_lock);
Q_ASSERT(m_upLink.count(id) == 0);
Q_ASSERT(m_downLink.count(id) == 0);
m_upLink[id] = -1;
m_downLink[id] = std::unordered_set();
}
Fun GroupsModel::destructGroupItem_lambda(int id)
{
QWriteLocker locker(&m_lock);
return [this, id]() {
auto ptr = m_parent.lock();
if (m_groupIds.count(id) > 0) {
if (ptr) {
ptr->deregisterGroup(id);
m_groupIds.erase(id);
} else {
qDebug() << "Impossible to ungroup item because the timeline is not available anymore";
Q_ASSERT(false);
}
}
removeFromGroup(id);
for (int child : m_downLink[id]) {
m_upLink[child] = -1;
if (ptr->isClip(child)) {
QModelIndex ix = ptr->makeClipIndexFromID(child);
ptr->dataChanged(ix, ix, {TimelineItemModel::GroupedRole});
}
}
m_downLink.erase(id);
m_upLink.erase(id);
if (m_selectionGroup == id) {
m_selectionGroup = -1;
}
return true;
};
}
bool GroupsModel::destructGroupItem(int id, bool deleteOrphan, Fun &undo, Fun &redo, bool temporarySelection)
{
QWriteLocker locker(&m_lock);
Q_ASSERT(m_upLink.count(id) > 0);
int parent = m_upLink[id];
auto old_children = m_downLink[id];
auto operation = destructGroupItem_lambda(id);
if (operation()) {
auto reverse = groupItems_lambda(id, old_children, temporarySelection, parent);
UPDATE_UNDO_REDO(operation, reverse, undo, redo);
if (parent != -1 && m_downLink[parent].empty() && deleteOrphan) {
return destructGroupItem(parent, true, undo, redo, temporarySelection);
}
return true;
}
return false;
}
bool GroupsModel::destructGroupItem(int id)
{
QWriteLocker locker(&m_lock);
return destructGroupItem_lambda(id)();
}
int GroupsModel::getRootId(int id) const
{
READ_LOCK();
std::unordered_set seen; // we store visited ids to detect cycles
int father = -1;
do {
Q_ASSERT(m_upLink.count(id) > 0);
Q_ASSERT(seen.count(id) == 0);
seen.insert(id);
father = m_upLink.at(id);
if (father != -1) {
id = father;
}
} while (father != -1);
return id;
}
bool GroupsModel::isLeaf(int id) const
{
READ_LOCK();
Q_ASSERT(m_downLink.count(id) > 0);
return m_downLink.at(id).empty();
}
bool GroupsModel::isInGroup(int id) const
{
READ_LOCK();
Q_ASSERT(m_downLink.count(id) > 0);
return getRootId(id) != id;
}
std::unordered_set GroupsModel::getSubtree(int id) const
{
READ_LOCK();
std::unordered_set result;
result.insert(id);
std::queue queue;
queue.push(id);
while (!queue.empty()) {
int current = queue.front();
queue.pop();
for (const int &child : m_downLink.at(current)) {
result.insert(child);
queue.push(child);
}
}
return result;
}
std::unordered_set GroupsModel::getLeaves(int id) const
{
READ_LOCK();
std::unordered_set result;
std::queue queue;
queue.push(id);
while (!queue.empty()) {
int current = queue.front();
queue.pop();
for (const int &child : m_downLink.at(current)) {
queue.push(child);
}
if (m_downLink.at(current).empty()) {
result.insert(current);
}
}
return result;
}
std::unordered_set GroupsModel::getDirectChildren(int id) const
{
READ_LOCK();
Q_ASSERT(m_downLink.count(id) > 0);
return m_downLink.at(id);
}
void GroupsModel::setGroup(int id, int groupId)
{
QWriteLocker locker(&m_lock);
Q_ASSERT(m_upLink.count(id) > 0);
Q_ASSERT(groupId == -1 || m_downLink.count(groupId) > 0);
Q_ASSERT(groupId == -1 || m_selectionGroup != id);
Q_ASSERT(id != groupId);
removeFromGroup(id);
m_upLink[id] = groupId;
if (groupId != -1) m_downLink[groupId].insert(id);
}
void GroupsModel::removeFromGroup(int id)
{
QWriteLocker locker(&m_lock);
Q_ASSERT(m_upLink.count(id) > 0);
Q_ASSERT(m_downLink.count(id) > 0);
int parent = m_upLink[id];
if (parent != -1) {
m_downLink[parent].erase(id);
}
m_upLink[id] = -1;
}
std::unordered_map GroupsModel::groupsData()
{
return m_upLink;
}
std::unordered_map> GroupsModel::groupsDataDownlink()
{
return m_downLink;
}
bool GroupsModel::mergeSingleGroups(int id, Fun &undo, Fun &redo)
{
// The idea is as follow: we start from the leaves, and go up to the root.
// In the process, if we find a node with only one children, we flag it for deletion
QWriteLocker locker(&m_lock);
Q_ASSERT(m_upLink.count(id) > 0);
auto leaves = getLeaves(id);
std::unordered_map old_parents, new_parents;
std::vector to_delete;
std::unordered_set processed; // to avoid going twice along the same branch
for (int leaf : leaves) {
int current = m_upLink[leaf];
int start = leaf;
while (current != m_upLink[id] && processed.count(current) == 0) {
processed.insert(current);
if (m_downLink[current].size() == 1) {
to_delete.push_back(current);
} else {
if (current != m_upLink[start]) {
old_parents[start] = m_upLink[start];
new_parents[start] = current;
}
start = current;
}
current = m_upLink[current];
}
if (current != m_upLink[start]) {
old_parents[start] = m_upLink[start];
new_parents[start] = current;
}
}
auto parent_changer = [this](const std::unordered_map &parents) {
auto ptr = m_parent.lock();
if (!ptr) {
qDebug() << "Impossible to create group because the timeline is not available anymore";
return false;
}
for (const auto &group : parents) {
int old = m_upLink[group.first];
setGroup(group.first, group.second);
if (old == -1 && group.second != -1 && ptr->isClip(group.first)) {
QModelIndex ix = ptr->makeClipIndexFromID(group.first);
ptr->dataChanged(ix, ix, {TimelineItemModel::GroupedRole});
}
}
return true;
};
Fun reverse = [this, old_parents, parent_changer]() { return parent_changer(old_parents); };
Fun operation = [this, new_parents, parent_changer]() { return parent_changer(new_parents); };
bool res = operation();
if (!res) {
bool undone = reverse();
Q_ASSERT(undone);
return res;
}
UPDATE_UNDO_REDO(operation, reverse, undo, redo);
for (int gid : to_delete) {
Q_ASSERT(m_downLink[gid].size() == 0);
res = destructGroupItem(gid, false, undo, redo, false);
if (!res) {
bool undone = undo();
Q_ASSERT(undone);
return res;
}
}
return true;
}
bool GroupsModel::split(int id, const std::function &criterion, Fun &undo, Fun &redo)
{
QWriteLocker locker(&m_lock);
// This function is valid only for roots (otherwise it is not clear what should be the new parent of the created tree)
Q_ASSERT(m_upLink[id] == -1);
// We do a BFS on the tree to copy it
// We store corresponding nodes
std::unordered_map corresp; // keys are id in the original tree, values are temporary negative id assigned for creation of the new tree
corresp[-1] = -1;
// These are the nodes to be moved to new tree
std::vector to_move;
// We store the groups (ie the nodes) that are going to be part of the new tree
// Keys are temporary id (negative) and values are the set of children (true ids in the case of leaves and temporary ids for other nodes)
std::unordered_map> new_groups;
std::queue queue;
queue.push(id);
int tempId = -10;
while (!queue.empty()) {
int current = queue.front();
queue.pop();
if (!isLeaf(current) || criterion(current)) {
if (isLeaf(current)) {
to_move.push_back(current);
new_groups[corresp[m_upLink[current]]].insert(current);
} else {
corresp[current] = tempId;
if (m_upLink[current] != -1) new_groups[corresp[m_upLink[current]]].insert(tempId);
tempId--;
}
}
for (const int &child : m_downLink.at(current)) {
queue.push(child);
}
}
// First, we simulate deletion of elements that we have to remove from the original tree
// A side effect of this is that empty groups will be removed
for (const auto &leaf : to_move) {
destructGroupItem(leaf, true, undo, redo, false);
}
// we artificially recreate the leaves
Fun operation = [this, to_move]() {
for (const auto &leaf : to_move) {
createGroupItem(leaf);
}
return true;
};
Fun reverse = [this, to_move]() {
for (const auto &group : to_move) {
destructGroupItem(group);
}
return true;
};
bool res = operation();
if (!res) {
return false;
}
UPDATE_UNDO_REDO(operation, reverse, undo, redo);
// We prune the new_groups to remove empty ones
bool finished = false;
while (!finished) {
finished = true;
int selected = INT_MAX;
for (const auto &it : new_groups) {
if (it.second.size() == 0) { // empty group
finished = false;
selected = it.first;
break;
}
for (int it2 : it.second) {
if (it2 < -1 && new_groups.count(it2) == 0) {
// group that has no reference, it is empty too
finished = false;
selected = it2;
break;
}
}
if (!finished) break;
}
if (!finished) {
new_groups.erase(selected);
for (auto it = new_groups.begin(); it != new_groups.end(); ++it) {
(*it).second.erase(selected);
}
}
}
// We now regroup the items of the new tree to recreate hierarchy.
// This is equivalent to creating the tree bottom up (starting from the leaves)
// At each iteration, we create a new node by grouping together elements that are either leaves or already created nodes.
std::unordered_map created_id; // to keep track of node that we create
while (!new_groups.empty()) {
int selected = INT_MAX;
for (const auto &group : new_groups) {
// we check that all children are already created
bool ok = true;
for (int elem : group.second) {
if (elem < -1 && created_id.count(elem) == 0) {
ok = false;
break;
}
}
if (ok) {
selected = group.first;
break;
}
}
Q_ASSERT(selected != INT_MAX);
std::unordered_set group;
for (int elem : new_groups[selected]) {
group.insert(elem < -1 ? created_id[elem] : elem);
}
int gid = groupItems(group, undo, redo, false, true);
created_id[selected] = gid;
new_groups.erase(selected);
}
mergeSingleGroups(id, undo, redo);
mergeSingleGroups(created_id[corresp[id]], undo, redo);
return res;
}
void GroupsModel::setInGroupOf(int id, int targetId, Fun &undo, Fun &redo)
{
Q_ASSERT(m_upLink.count(targetId) > 0);
Fun operation = [ this, id, group = m_upLink[targetId] ]()
{
setGroup(id, group);
return true;
};
Fun reverse = [ this, id, group = m_upLink[id] ]()
{
setGroup(id, group);
return true;
};
operation();
UPDATE_UNDO_REDO(operation, reverse, undo, redo);
}
bool GroupsModel::processCopy(int gid, std::unordered_map &mapping, Fun &undo, Fun &redo)
{
qDebug() << "processCopy" << gid;
if (isLeaf(gid)) {
qDebug() << "it is a leaf";
return true;
}
bool ok = true;
std::unordered_set targetGroup;
for (int child : m_downLink.at(gid)) {
ok = ok && processCopy(child, mapping, undo, redo);
if (!ok) {
break;
}
targetGroup.insert(mapping.at(child));
}
qDebug() << "processCopy" << gid << "success of child" << ok;
- if (ok) {
+ if (ok && gid != m_selectionGroup) {
int id = groupItems(targetGroup, undo, redo);
qDebug() << "processCopy" << gid << "created id" << id;
if (id != -1) {
mapping[gid] = id;
return true;
}
}
- return false;
+ return ok;
}
bool GroupsModel::copyGroups(std::unordered_map &mapping, Fun &undo, Fun &redo)
{
Fun local_undo = []() { return true; };
Fun local_redo = []() { return true; };
// destruct old groups for the targets items
for (const auto &corresp : mapping) {
ungroupItem(corresp.second, local_undo, local_redo);
}
std::unordered_set roots;
std::transform(mapping.begin(), mapping.end(), std::inserter(roots, roots.begin()),
[&](decltype(*mapping.begin()) corresp) { return getRootId(corresp.first); });
bool res = true;
qDebug() << "found" << roots.size() << "roots";
for (int r : roots) {
qDebug() << "processing copy for root " << r;
res = res && processCopy(r, mapping, local_undo, local_redo);
if (!res) {
bool undone = local_undo();
Q_ASSERT(undone);
return false;
}
}
UPDATE_UNDO_REDO(local_redo, local_undo, undo, redo);
return true;
}