faster parent() and indexFromItem() with index guess

implemented files

4 files changed, 251 insertions, 41 deletions

diff --git a/src/filetreeitem.cpp b/src/filetreeitem.cpp
index 33a70798..3b18cf54 100644
--- a/src/filetreeitem.cpp
+++ b/src/filetreeitem.cpp
@@ -6,11 +6,12 @@
 using namespace MOBase;
 using namespace MOShared;
 
+
 FileTreeItem::FileTreeItem(
   FileTreeItem* parent, int originID,
   std::wstring dataRelativeParentPath, std::wstring realPath, Flags flags,
   std::wstring file, std::wstring mod) :
-    m_parent(parent),
+    m_parent(parent), m_indexGuess(NoIndexGuess),
     m_originID(originID),
     m_virtualParentPath(QString::fromStdWString(dataRelativeParentPath)),
     m_realPath(QString::fromStdWString(realPath)),
@@ -35,6 +36,7 @@ void FileTreeItem::insert(std::unique_ptr<FileTreeItem> child, std::size_t at)
     return;
   }
 
+  child->m_indexGuess = at;
   m_children.insert(m_children.begin() + at, std::move(child));
 }
 
diff --git a/src/filetreeitem.h b/src/filetreeitem.h
index 2819afbd..e060f63a 100644
--- a/src/filetreeitem.h
+++ b/src/filetreeitem.h
@@ -29,6 +29,7 @@ public:
 
   void add(std::unique_ptr<FileTreeItem> child)
   {
+    child->m_indexGuess = m_children.size();
     m_children.push_back(std::move(child));
   }
 
@@ -37,6 +38,11 @@ public:
   template <class Itor>
   void insert(Itor begin, Itor end, std::size_t at)
   {
+    std::size_t nextRowGuess = m_children.size();
+    for (auto itor=begin; itor!=end; ++itor) {
+      (*itor)->m_indexGuess = nextRowGuess++;
+    }
+
     m_children.insert(m_children.begin() + at, begin, end);
   }
 
@@ -54,6 +60,23 @@ public:
     return m_children;
   }
 
+  int childIndex(const FileTreeItem& item) const
+  {
+    if (item.m_indexGuess < m_children.size()) {
+      if (m_children[item.m_indexGuess].get() == &item) {
+        return static_cast<int>(item.m_indexGuess);
+      }
+    }
+
+    for (std::size_t i=0; i<m_children.size(); ++i) {
+      if (m_children[i].get() == &item) {
+        item.m_indexGuess = i;
+        return static_cast<int>(i);
+      }
+    }
+
+    return -1;
+  }
 
   FileTreeItem* parent()
   {
@@ -171,7 +194,11 @@ public:
   QString debugName() const;
 
 private:
+  static constexpr std::size_t NoIndexGuess =
+    std::numeric_limits<std::size_t>::max();
+
   FileTreeItem* m_parent;
+  mutable std::size_t m_indexGuess;
 
   const int m_originID;
   const QString m_virtualParentPath;
diff --git a/src/filetreemodel.cpp b/src/filetreemodel.cpp
index 3be58f05..f5877dbb 100644
--- a/src/filetreemodel.cpp
+++ b/src/filetreemodel.cpp
@@ -78,16 +78,13 @@ QModelIndex FileTreeModel::parent(const QModelIndex& index) const
     return {};
   }
 
-  if (auto* item=itemFromIndex(index)) {
-    if (auto* parent=item->parent()) {
-      return indexFromItem(*parent);
-    } else {
-      return {};
-    }
+  auto* parentItem = static_cast<FileTreeItem*>(index.internalPointer());
+  if (!parentItem) {
+    log::error("FileTreeModel::parent(): no internal pointer");
+    return {};
   }
 
-  log::error("FileTreeModel::parent(): no internal pointer");
-  return {};
+  return indexFromItem(*parentItem);
 }
 
 int FileTreeModel::rowCount(const QModelIndex& parent) const
@@ -221,19 +218,16 @@ QModelIndex FileTreeModel::indexFromItem(FileTreeItem& item) const
     return {};
   }
 
-  const auto& cs = parent->children();
+  const int index = parent->childIndex(item);
+  if (index == -1) {
+    log::error(
+      "FileTreeMode::indexFromItem(): item {} not found in parent",
+      item.debugName());
 
-  for (std::size_t i=0; i<cs.size(); ++i) {
-    if (cs[i].get() == &item) {
-      return createIndex(static_cast<int>(i), 0, parent);
-    }
+    return {};
   }
 
-  log::error(
-    "FileTreeMode::indexFromItem(): item {} not found in parent",
-    item.debugName());
-
-  return {};
+  return createIndex(index, 0, parent);
 }
 
 void FileTreeModel::update(
@@ -252,6 +246,7 @@ void FileTreeModel::update(
   }
 
   updateDirectories(parentItem, path, parentEntry, FillFlag::None);
+  updateFiles(parentItem, path, parentEntry);
 
   parentItem.setLoaded(true);
 }
@@ -266,13 +261,13 @@ void FileTreeModel::updateDirectories(
   // use this to figure out if a directory is new or not
   std::unordered_set<std::wstring_view> seen;
 
-  removeDisappearingDirectories(parentItem, parentEntry, seen);
+  removeDisappearingDirectories(parentItem, parentEntry, parentPath, seen);
   addNewDirectories(parentItem, parentEntry, parentPath, seen);
 }
 
 void FileTreeModel::removeDisappearingDirectories(
   FileTreeItem& parentItem, const MOShared::DirectoryEntry& parentEntry,
-  std::unordered_set<std::wstring_view>& seen)
+  const std::wstring& parentPath, std::unordered_set<std::wstring_view>& seen)
 {
   auto& children = parentItem.children();
   auto itor = children.begin();
@@ -295,25 +290,29 @@ void FileTreeModel::removeDisappearingDirectories(
     auto d = parentEntry.findSubDirectory(item->filenameWsLowerCase(), true);
 
     if (d) {
-      trace([&]{ log::debug("{} still there", item->filename()); });
+      trace([&]{ log::debug("dir {} still there", item->filename()); });
 
       // directory is still there
-      seen.insert(item->filenameWs());
+      seen.emplace(item->filenameWs());
 
       // if there were directories before this row that need to be removed,
       // do it now
       if (removeStart != -1) {
         removeRange(parentItem, removeStart, row - 1);
 
-        removeStart = -1;
-
         // adjust current row to account for those that were just removed
         row -= (row - removeStart);
         itor = children.begin() + row;
+
+        removeStart = -1;
+      }
+
+      if (item->areChildrenVisible()) {
+        update(*item, *d, parentPath);
       }
     } else {
       // directory is gone from the parent entry
-      trace([&]{ log::debug("{} is gone", item->filename()); });
+      trace([&]{ log::debug("dir {} is gone", item->filename()); });
 
       if (removeStart == -1) {
         // start a new contiguous sequence
@@ -356,7 +355,7 @@ void FileTreeModel::addNewDirectories(
       }
     } else {
       // this is a new directory
-      trace([&]{ log::debug("new {}", QString::fromStdWString(d->getName())); });
+      trace([&]{ log::debug("new dir {}", QString::fromStdWString(d->getName())); });
 
       auto item = std::make_unique<FileTreeItem>(
         &parentItem, 0, parentPath, L"", FileTreeItem::Directory,
@@ -412,3 +411,189 @@ void FileTreeModel::addRange(
 
   endInsertRows();
 }
+
+
+void FileTreeModel::updateFiles(
+  FileTreeItem& parentItem, const std::wstring& parentPath,
+  const MOShared::DirectoryEntry& parentEntry)
+{
+  // removeDisappearingFiles() will add files that are in the tree and still on
+  // the filesystem to this set; addNewFiless() will use this to figure out if
+  // a file is new or not
+  std::unordered_set<FileEntry::Index> seen;
+
+  int firstFileRow = 0;
+
+  removeDisappearingFiles(parentItem, parentEntry, firstFileRow, seen);
+  addNewFiles(parentItem, parentEntry, parentPath, firstFileRow, seen);
+}
+
+void FileTreeModel::removeDisappearingFiles(
+  FileTreeItem& parentItem, const MOShared::DirectoryEntry& parentEntry,
+  int& firstFileRow, std::unordered_set<FileEntry::Index>& seen)
+{
+  auto& children = parentItem.children();
+  auto itor = children.begin();
+
+  // keeps track of the contiguous directories that need to be removed to
+  // avoid calling beginRemoveRows(), etc. for each item
+  int removeStart = -1;
+  firstFileRow = 0;
+
+  // directories are always first, so find the first file item
+  while (itor != children.end()) {
+    const auto& item = *itor;
+
+    if (!item->isDirectory()) {
+      break;
+    }
+
+    ++firstFileRow;
+    ++itor;
+  }
+
+  if (itor == children.end()) {
+    // no file items
+    return;
+  }
+
+  int row = firstFileRow;
+
+  // for each item in this tree item
+  while (itor != children.end()) {
+    const auto& item = *itor;
+
+    auto f = parentEntry.findFile(item->key());
+
+    if (f) {
+      trace([&]{ log::debug("file {} still there", item->filename()); });
+
+      // file is still there
+      seen.emplace(f->getIndex());
+
+      // if there were files before this row that need to be removed,
+      // do it now
+      if (removeStart != -1) {
+        removeRange(parentItem, removeStart, row - 1);
+
+        // adjust current row to account for those that were just removed
+        row -= (row - removeStart);
+        itor = children.begin() + row;
+
+        removeStart = -1;
+      }
+    } else {
+      // file is gone from the parent entry
+      trace([&]{ log::debug("file {} is gone", item->filename()); });
+
+      if (removeStart == -1) {
+        // start a new contiguous sequence
+        removeStart = row;
+      }
+    }
+
+    ++row;
+    ++itor;
+  }
+
+  // remove the last file range, if any
+  if (removeStart != -1) {
+    removeRange(parentItem, removeStart, row -1 );
+  }
+}
+
+void FileTreeModel::addNewFiles(
+  FileTreeItem& parentItem, const MOShared::DirectoryEntry& parentEntry,
+  const std::wstring& parentPath, const int firstFileRow,
+  const std::unordered_set<FileEntry::Index>& seen)
+{
+  // keeps track of the contiguous files that need to be added to
+  // avoid calling beginAddRows(), etc. for each item
+  std::vector<std::unique_ptr<FileTreeItem>> toAdd;
+  int addStart = -1;
+  int row = firstFileRow;
+
+  // for each directory on the filesystem
+  parentEntry.forEachFileIndex([&](auto&& fileIndex) {
+    if (seen.contains(fileIndex)) {
+      // already seen in the parent item
+
+      // if there were directories before this row that need to be added,
+      // do it now
+      if (addStart != -1) {
+        addRange(parentItem, addStart, toAdd);
+        toAdd.clear();
+        addStart = -1;
+      }
+    } else {
+      const auto file = parentEntry.getFileByIndex(fileIndex);
+
+      if (!file) {
+        log::error(
+          "FileTreeModel::addNewFiles(): file index {} in path {} not found",
+          fileIndex, parentPath);
+
+        return true;
+      }
+
+      // this is a new file
+      trace([&]{ log::debug("new file {}", QString::fromStdWString(file->getName())); });
+
+      bool isArchive = false;
+      int originID = file->getOrigin(isArchive);
+
+      FileTreeItem::Flags flags = FileTreeItem::NoFlags;
+
+      if (isArchive) {
+        flags |= FileTreeItem::FromArchive;
+      }
+
+      if (!file->getAlternatives().empty()) {
+        flags |= FileTreeItem::Conflicted;
+      }
+
+      auto item = std::make_unique<FileTreeItem>(
+        &parentItem, originID, parentPath, file->getFullPath(), flags,
+        file->getName(), makeModName(*file, originID));
+
+      item->setLoaded(true);
+
+      toAdd.push_back(std::move(item));
+
+      if (addStart == -1) {
+        // start a new contiguous sequence
+        addStart = row;
+      }
+    }
+
+    ++row;
+
+    return true;
+  });
+
+  // add the last file range, if any
+  if (addStart != -1) {
+    addRange(parentItem, addStart, toAdd);
+  }
+}
+
+std::wstring FileTreeModel::makeModName(
+  const MOShared::FileEntry& file, int originID) const
+{
+  static const std::wstring Unmanaged = UnmanagedModName().toStdWString();
+
+  const auto origin = m_core.directoryStructure()->getOriginByID(originID);
+
+  if (origin.getID() == 0) {
+    return Unmanaged;
+  }
+
+  std::wstring name = origin.getName();
+
+  const auto& archive = file.getArchive();
+  if (!archive.first.empty()) {
+    name += L" (" + archive.first + L")";
+  }
+
+  return name;
+}
diff --git a/src/filetreemodel.h b/src/filetreemodel.h
index af24c70d..70291b61 100644
--- a/src/filetreemodel.h
+++ b/src/filetreemodel.h
@@ -81,7 +81,7 @@ private:
 
   void removeDisappearingDirectories(
     FileTreeItem& parentItem, const MOShared::DirectoryEntry& parentEntry,
-    std::unordered_set<std::wstring_view>& seen);
+    const std::wstring& parentPath, std::unordered_set<std::wstring_view>& seen);
 
   void addNewDirectories(
     FileTreeItem& parentItem, const MOShared::DirectoryEntry& parentEntry,
@@ -95,22 +95,18 @@ private:
     std::vector<std::unique_ptr<FileTreeItem>>& items);
 
 
-  void fill(
-    FileTreeItem& parentItem, const MOShared::DirectoryEntry& parentEntry,
-    const std::wstring& parentPath);
-
-  void fillDirectories(
-    FileTreeItem& parentItem, const std::wstring& path,
-    DirectoryIterator begin, DirectoryIterator end, FillFlags flags);
-
-  void fillFiles(
+  void updateFiles(
     FileTreeItem& parentItem, const std::wstring& path,
-    const std::vector<MOShared::FileEntry::Ptr>& files, FillFlags flags);
+    const MOShared::DirectoryEntry& parentEntry);
 
+  void removeDisappearingFiles(
+    FileTreeItem& parentItem, const MOShared::DirectoryEntry& parentEntry,
+    int& firstFileRow, std::unordered_set<MOShared::FileEntry::Index>& seen);
 
-  void updateFiles(
-    FileTreeItem& parentItem, const std::wstring& path,
-    const MOShared::DirectoryEntry& parentEntry, FillFlags flags);
+  void addNewFiles(
+    FileTreeItem& parentItem, const MOShared::DirectoryEntry& parentEntry,
+    const std::wstring& parentPath, int firstFileRow,
+    const std::unordered_set<MOShared::FileEntry::Index>& seen);
 
   std::wstring makeModName(const MOShared::FileEntry& file, int originID) const;