CODEWITHSUNDEEP
javascriptdata-structures
simone
simone

Reputation: 5221

What's the best data structure for grouping and ungrouping shapes

I need to implement group/ungroup functionality in a graphic application. The aim is to be similar to the group/ungroup functionality in Adobe Illustrator or Microsoft PowerPoint.

Groups can be nested (i.e.: a group can contain both elements and other groups, which in turn contain elements or groups)

I am wondering what is the best data structure for doing that.

It should be possible to tell quickly:

I am thinking of something like this:

{
    groups: {
        g1: ['n1', 'n2', 'n3'],
        g2: ['n4', 'n5', 'g1'],
        g3: ['g2', 'n6', 'n7']
    },
    nodes {
        n1: 'g1',
        n2: 'g1',
        n3: 'g1',
        n4: 'g2',
        n5: 'g2',
        g1: 'n1',
        g2: 'g3',
        n6: 'g3',
        n7: 'g3'
    }
}

With group containing the groups themselves, and nodesacting as a lookup table to tell if a node is in a group. I could tell nodes and groups apart from their ID's (nodes are always numbers). Recursing through groups would provide lists of siblings.

This would be encapsulated in an object that would then handle group, ungroup and checking - in JavaScript.

Is this sane? Is there a better way?

Upvotes: 0

Views: 1262

Answers (1)

philipp
philipp

Reputation: 16495

Why not use a tree structure? Using Nodes like so:

function Node (value, parent) {
  this.value = value;
  this.children = [];
  this.parent = parent || null
}

Node.prototype.addChild = function (node) { … }

Node.prototype.traverse = function (fx) {
  fx(this);
  this.children.forEach(function (child) {
    child.traverse(fx);
  });
}
…

var root = new Node({id: 100}, null);

With that you add more pointers/references for faster tree traversals. To test if a Node is in a group, you just need to check if its parent is not null. Many other tests/query can be performed by simple tree traversals.

Upvotes: 1

Related Questions