1  // UTILS
  2  
  3  function splitArray(arr, predicate) {
  4    let lastArr = [];
  5    const multiArr = [lastArr];
  6    arr.forEach(item => {
  7      if (predicate(item)) {
  8        if (lastArr.length > 0) {
  9          lastArr = [];
 10          multiArr.push(lastArr);
 11        }
 12      } else {
 13        lastArr.push(item);
 14      }
 15    });
 16    return multiArr;
 17  }
 18  
 19  function joinArrays(arrays, joiner) {
 20    const joinedArr = [];
 21    arrays.forEach((arr, i) => {
 22      if (i > 0 && arr.length > 0) {
 23        joinedArr.push(joiner);
 24      }
 25      joinedArr.push(...arr);
 26    });
 27    return joinedArr;
 28  }
 29  
 30  const pushOntoMultiMap = (map, key, value) => {
 31    if (!map.has(key)) {
 32      map.set(key, []);
 33    }
 34    map.get(key).push(value);
 35  };
 36  
 37  function indexOfGroupContainingCommand(groups, command, ignoreGroup) {
 38    return groups.findIndex(
 39      candiateGroup =>
 40        candiateGroup !== ignoreGroup &&
 41        candiateGroup.some(candidateItem => candidateItem.command === command)
 42    );
 43  }
 44  
 45  // Sort nodes topologically using a depth-first approach. Encountered cycles
 46  // are broken.
 47  function sortTopologically(originalOrder, edgesById) {
 48    const sorted = [];
 49    const marked = new Set();
 50  
 51    function visit(id) {
 52      if (marked.has(id)) {
 53        // Either this node has already been placed, or we have encountered a
 54        // cycle and need to exit.
 55        return;
 56      }
 57      marked.add(id);
 58      const edges = edgesById.get(id);
 59      if (edges != null) {
 60        edges.forEach(visit);
 61      }
 62      sorted.push(id);
 63    }
 64  
 65    originalOrder.forEach(visit);
 66    return sorted;
 67  }
 68  
 69  function attemptToMergeAGroup(groups) {
 70    for (let i = 0; i < groups.length; i++) {
 71      const group = groups[i];
 72      for (const item of group) {
 73        const toCommands = [...(item.before || []), ...(item.after || [])];
 74        for (const command of toCommands) {
 75          const index = indexOfGroupContainingCommand(groups, command, group);
 76          if (index === -1) {
 77            // No valid edge for this command
 78            continue;
 79          }
 80          const mergeTarget = groups[index];
 81          // Merge with group containing `command`
 82          mergeTarget.push(...group);
 83          groups.splice(i, 1);
 84          return true;
 85        }
 86      }
 87    }
 88    return false;
 89  }
 90  
 91  // Merge groups based on before/after positions
 92  // Mutates both the array of groups, and the individual group arrays.
 93  function mergeGroups(groups) {
 94    let mergedAGroup = true;
 95    while (mergedAGroup) {
 96      mergedAGroup = attemptToMergeAGroup(groups);
 97    }
 98    return groups;
 99  }
100  
101  function sortItemsInGroup(group) {
102    const originalOrder = group.map((node, i) => i);
103    const edges = new Map();
104    const commandToIndex = new Map(group.map((item, i) => [item.command, i]));
105  
106    group.forEach((item, i) => {
107      if (item.before) {
108        item.before.forEach(toCommand => {
109          const to = commandToIndex.get(toCommand);
110          if (to != null) {
111            pushOntoMultiMap(edges, to, i);
112          }
113        });
114      }
115      if (item.after) {
116        item.after.forEach(toCommand => {
117          const to = commandToIndex.get(toCommand);
118          if (to != null) {
119            pushOntoMultiMap(edges, i, to);
120          }
121        });
122      }
123    });
124  
125    const sortedNodes = sortTopologically(originalOrder, edges);
126  
127    return sortedNodes.map(i => group[i]);
128  }
129  
130  function findEdgesInGroup(groups, i, edges) {
131    const group = groups[i];
132    for (const item of group) {
133      if (item.beforeGroupContaining) {
134        for (const command of item.beforeGroupContaining) {
135          const to = indexOfGroupContainingCommand(groups, command, group);
136          if (to !== -1) {
137            pushOntoMultiMap(edges, to, i);
138            return;
139          }
140        }
141      }
142      if (item.afterGroupContaining) {
143        for (const command of item.afterGroupContaining) {
144          const to = indexOfGroupContainingCommand(groups, command, group);
145          if (to !== -1) {
146            pushOntoMultiMap(edges, i, to);
147            return;
148          }
149        }
150      }
151    }
152  }
153  
154  function sortGroups(groups) {
155    const originalOrder = groups.map((item, i) => i);
156    const edges = new Map();
157  
158    for (let i = 0; i < groups.length; i++) {
159      findEdgesInGroup(groups, i, edges);
160    }
161  
162    const sortedGroupIndexes = sortTopologically(originalOrder, edges);
163    return sortedGroupIndexes.map(i => groups[i]);
164  }
165  
166  function isSeparator(item) {
167    return item.type === 'separator';
168  }
169  
170  function sortMenuItems(menuItems) {
171    // Split the items into their implicit groups based upon separators.
172    const groups = splitArray(menuItems, isSeparator);
173    // Merge groups that contain before/after references to eachother.
174    const mergedGroups = mergeGroups(groups);
175    // Sort each individual group internally.
176    const mergedGroupsWithSortedItems = mergedGroups.map(sortItemsInGroup);
177    // Sort the groups based upon their beforeGroupContaining/afterGroupContaining
178    // references.
179    const sortedGroups = sortGroups(mergedGroupsWithSortedItems);
180    // Join the groups back
181    return joinArrays(sortedGroups, { type: 'separator' });
182  }
183  
184  module.exports = { sortMenuItems };