CODEWITHSUNDEEP
c++
McNumber
McNumber

Reputation: 177

Tracking modifications in a huge tree of objects

I develop a graphical editor in C++/Qt, that uses a tree of objects as its data model. The object's classes also form a class hierarchy. You can think of a tree of widgets in some kind of GUI framework, like Java Swing or Qt. Now I want to implement an undo/redo-functionality. Therefore I need to track every modification to both the tree nodes (e.g. changing object properties) and also the tree itself (e.g. adding, deleting nodes). Unfortunately the tree objects will also be modified by third party code and I have to ensure, that this code does not break my application.

So, considering that the tree will be HUGE (several 100,000 nodes) how can I ensure, that I can see every modification to the tree? It should also be noted, that the tree nodes contain a lot of modifiable properties.

Upvotes: 1

Views: 272

Answers (2)

Millianz
Millianz

Reputation: 161

I have no experience in /Qt, but while this is rather complicated in standard c++ it is possible.

Before you take what I'm about to say here to literally, please be advised that I did not try this in code before posting. This should be understood like the general concept, not copy pasted (there are probably errors in it)

First of all you would need a base class to represent your node, let's call it Node. The node should provide a mutator for any value.

class Node
{
public: // Methods
  template <typename Type>
  void Set(const char* name, GenericData& attribute) const
  {
    // Note that GenericData now is required to have an implemented copy constructor
    m_Attributes[name] = new Type(dynamic_cast<Type>(attribute));
    // Note the dynamic cast to prevent slicing

    // Call back some function to let it now the node changed here
  }

private: // Data
  // I just used a map for simplicity's sake. You should probably use
  // another container more adequate to your needs.
  std::map<std::string, GenericData*> m_Attributes;
}

Then we need to generically address all kinds of different types, something that has to be accomplished using inheritance as well.

class GenericData
{
public:
  virtual ~GenericData() {}
}

// Example Data
template <typename T>
class Data : public GenericData
{
public:
  ~Data(void) { delete m_Data; }
  T* get(void) const { return m_Data; }
  void set(T& dat)
  {
    delete m_Data;
    m_Data = new Data(); // Note: All data is now required to have default ctor
  }

private:
 T* m_Data;
}

The client would then type something like this:

Data<int> MyDat = 5; // Should be optimized to copy construction, therefore work
YourTree[TheNode].Set<int>("AttributeName", MyDat);

Like I said, this is more pseudo code than implementation, but it should give an idea of the concept.

Upvotes: 0

Martin Stone
Martin Stone

Reputation: 13007

The Command Pattern is one way to do it. However every modification to the data needs to be done via a Command object and logged by the undo system. It's the sort of thing that is best included from the beginning. It could be quite a pain to retrofit.

If you can't intercept the modifications by the third-party code and turn them into Commands, you'll probably just have to take a snapshot of everything before each change. There are obvious problems with this if your data structure is large. You could have a special Command on your undo stack for these that only stores such snapshots for third-party modifications.

Upvotes: 3

Related Questions