CODEWITHSUNDEEP
javascriptarraysalgorithmdata-structures
Haris Muzaffar
Haris Muzaffar

Reputation: 441

What is a good algorithm and a data structure for rearrangement of items?

Let's say I have some items, every item has a sequence - lesser sequences means items are above. An item can have a dependency/dependencies on other items. Also, an item can have dependables - i.e. some other items might depend on it. The below item list(i have used an associated array here) lists the items - the property 'dep' of each item lists dependencies and dependables.


var dependencyDict = {
  item1: {dependsOn: [], dependable: ['item3']},
  item2: {dependsOn: [], dependable: []},
  item3: {dependsOn: ['item1'], dependable: ['item4']},
  item4: {dependsOn: ['item3'], dependable: []}
}

var itemList  = {
  item1: {
    name: 'item1',
    seq: 1,
    dep: dependencyDict['item1']
  },
  item2: {
    name: 'item2',
    seq: 2,
    dep: dependencyDict['item2']
  },
  item3: {
    name: 'item3',
    seq: 3,
    dep: dependencyDict['item3']
  },
  item4: {
    name: 'item4',
    seq: 4,
    dep: dependencyDict['item4']
  }
}

According to the above, items in the order of their sequence are so:

item1
item2
item3
item4

My goal is to reorder the items i.e. change sequence(if possible) so that dependencies are intact.

Validation: an item can move only if dependencies remain intact: i.e.

For example, if I say move(item3, 2) - I am asking to move item3 to position 2 so that new item list should be so:

{
  item1: {
    name: 'item1',
    seq: 1,
    dep: dependencyDict['item1']
  },
  item2: {
    name: 'item2',
    seq: 3,
    dep: dependencyDict['item2']
  },
  item3: {
    name: 'item3',
    seq: 2,
    dep: dependencyDict['item3']
  },
  item4: {
    name: 'item4',
    seq: 4,
    dep: dependencyDict['item4']
}

notice the change of sequences

But if I say move(item3, 1), it will not, because item3 depends on item1 - if it moves to position 1, item1 will go to position 2 which invalidates the rule that the item can depend only on the items that are above it.

My code is in working condition but I have used more if-elses than a proper algorithm

Flexibility: itemlist can be put in any data structure and any algorithm can be used

Upvotes: 0

Views: 221

Answers (2)

trincot
trincot

Reputation: 350766

Some suggestions:

  • If your data is large with many dependencies, it may be more efficient to use a Set for registering the dependencies instead of an array.
  • Eliminate one of dependsOn or dependable, as one can be derived from the other
  • Don't store seq, but just rely on the index an item has in an array. True, this means you have to scan an array with indexOf, but on the other hand you'll not have to make updates on all the seq properties involved in a move.
  • Use zero-based indexes, instead of positions starting at 1.

Here is a class implementation of the data structure I'd propose.

class OrderedGraph {
    constructor(pairs) {
        this._dep = new Map;
        this._order = [];
        if (pairs) for (let [item, dependsOn] of pairs) this.add(item, dependsOn);
    }
    add(item, dependsOn=[]) {
        for (let ref of dependsOn) if (!this._dep.has(ref)) throw ref + " not found";
        this._dep.set(item, new Set(dependsOn));
        this._order.push(item);
    }
    move(item, toIdx) {
        let fromIdx = typeof item === "number" ? item : this._order.indexOf(item);
        if (fromIdx < 0) throw "not found: " + item
        if (typeof item === "number") item = this._order[item];
        let dep = this._dep.get(item);
        let ok = fromIdx > toIdx
            ? !this._order.slice(toIdx, fromIdx).some(it => dep.has(it))
            : !this._order.slice(fromIdx+1, toIdx+1).some(it => this._dep.get(it).has(item));
        if (ok) this._order.splice(toIdx, 0, ...this._order.splice(fromIdx, 1));
        return ok;
    }
    indexOf(item)  { return this._order.indexOf(item) }
    includes(item) { return this._dep.has(item) }
    * values()     { yield * this._order }
    [Symbol.iterator]() { return this.values() }
}

// Example use
let data = new OrderedGraph([
    ["item1", []],
    ["item2", []],
    ["item3", ["item1"]],
    ["item4", ["item3"]]
]);

// Some actions on the data object:
console.log(JSON.stringify(Array.from(data)));
console.log("success moving 'item3' to 0? ", data.move("item3", 0));
console.log(JSON.stringify(Array.from(data)));
console.log("success moving 'item3' to 1? ", data.move("item3", 1));
console.log(JSON.stringify(Array.from(data)));
console.log("success moving 'item3' to 1? ", data.move("item3", 1));
console.log(JSON.stringify(Array.from(data)));
console.log("success moving 'item3' to 2? ", data.move("item3", 2));
console.log(JSON.stringify(Array.from(data)));
console.log("index of 'item3': ", data.indexOf("item3"));

Upvotes: 1

Nina Scholz
Nina Scholz

Reputation: 386728

You could check the dependencies with their index of the wanted new node list.

function move(node, position) {
    var nodes = Object.keys(itemList).sort(({ seq: a }, { seq: b }) => a - b);

    nodes.splice(position - 1, 0, ...nodes.splice(itemList[node].seq - 1, 1));

    var valid = nodes.every((n, i) =>
            dependencyDict[n].dependsOn.every(m => nodes.indexOf(m) <= i) &&
            dependencyDict[n].dependable.every(m => nodes.indexOf(m) >= i)
        );

    console.log(valid);
    if (valid) nodes.forEach((node, i) => itemList[node].seq = i + 1);
    console.log(nodes);
    console.log(itemList);
}

var dependencyDict = {
        item1: {dependsOn: [], dependable: ['item3']},
        item2: {dependsOn: [], dependable: []},
        item3: {dependsOn: ['item1'], dependable: ['item4']},
        item4: {dependsOn: ['item4'], dependable: []}
    },
    itemList  = {
        item1: { name: 'item1', seq: 1, dep: dependencyDict['item1'] },
        item2: { name: 'item2', seq: 2, dep: dependencyDict['item2'] },
        item3: { name: 'item3', seq: 3, dep: dependencyDict['item3'] },
        item4: { name: 'item4', seq: 4, dep: dependencyDict['item4'] }
    };

move('item3', 1);
move('item3', 2);
.as-console-wrapper { max-height: 100% !important; top: 0; }

Upvotes: 0

Related Questions