1 |
|
2 |
|
3 |
|
4 | 'use strict';
|
5 |
|
6 | const Base = require('./Base');
|
7 |
|
8 | module.exports = class DependentOrder extends Base {
|
9 |
|
10 | constructor (config) {
|
11 | super({
|
12 | keyAttr: 'id',
|
13 | dependsAttr: 'depends',
|
14 | ...config
|
15 | });
|
16 | }
|
17 |
|
18 | sort (items) {
|
19 | this.createItems(items);
|
20 | this.setItemIndexes();
|
21 | this.sortByIndex();
|
22 | this._orders = [];
|
23 | for (const item of this._items) {
|
24 | this._chain = [];
|
25 | this.orderItem(item);
|
26 | }
|
27 | return this._orders.map(item => item.source);
|
28 | }
|
29 |
|
30 | createItems (items) {
|
31 | this._items = [];
|
32 | this._itemMap = {};
|
33 | for (let i = 0; i < items.length; ++i) {
|
34 | const item = this.createItem(items[i], i);
|
35 | this._items.push(item);
|
36 | this._itemMap[item.id] = item;
|
37 | }
|
38 | }
|
39 |
|
40 | createItem (source, index) {
|
41 | return {
|
42 | id: this.getItemId(source),
|
43 | depends: this.getItemDepends(source),
|
44 | source,
|
45 | index
|
46 | };
|
47 | }
|
48 |
|
49 | setItemIndexes () {
|
50 | for (const item of this._items) {
|
51 | item.index = this.getItemIndex(item);
|
52 | }
|
53 | }
|
54 |
|
55 | getItemIndex (item) {
|
56 | if (item.depends.includes('#start')) {
|
57 | return item.index - this._items.length;
|
58 | }
|
59 | if (item.depends.includes('#end')) {
|
60 | return item.index + this._items.length;
|
61 | }
|
62 | return item.index;
|
63 | }
|
64 |
|
65 | sortByIndex () {
|
66 | this._items.sort((a, b) => a.index - b.index);
|
67 | }
|
68 |
|
69 | orderItem (item) {
|
70 | this._chain.push(item);
|
71 | if (item.sorting) {
|
72 | throw new Error('Circular dependency: '+ this._chain.map(item => item.id));
|
73 | }
|
74 | item.sorting = true;
|
75 | this.orderItemDepends(item);
|
76 | if (!this._orders.includes(item)) {
|
77 | this._orders.push(item);
|
78 | }
|
79 | item.sorting = false;
|
80 | this._chain.pop();
|
81 | }
|
82 |
|
83 | orderItemDepends (item) {
|
84 | for (let master of item.depends) {
|
85 | master = this.getItem(master);
|
86 | if (master) {
|
87 | this.orderItem(master);
|
88 | }
|
89 | }
|
90 | }
|
91 |
|
92 | getItem (id) {
|
93 | return Object.prototype.hasOwnProperty.call(this._itemMap, id) ? this._itemMap[id] : null;
|
94 | }
|
95 |
|
96 | getItemId (item) {
|
97 | return item[this.keyAttr];
|
98 | }
|
99 |
|
100 | getItemDepends (item) {
|
101 | const depends = item[this.dependsAttr];
|
102 | return Array.isArray(depends) ? depends : depends ? [depends] : [];
|
103 | }
|
104 | }; |
\ | No newline at end of file |