Sorting/Manipulating an array of objects

Question

I need help in writing a function to sort an array of objects

1. all objects with xid are bottom in array
2. object (assume A) which has options array might contain xid in step object, This xid is also present in other object at root level (assume B), in such case B should be placed below A

example:

object with the text "Looking for online" has options key and on 0th index, it has step object with xid = "1",

{
    type: 'radio',
    text: "Looking for online",
    options: [
       {
           text: "Yes",
           step: {
              text: "Select City",
              xid: 1
           }
        },
        {
            text: "No"
        }
    ]
}

now object which as xid = 1 on root level i.e object with text "Select City" should be placed below 1st object

{
    type: 'radio',
    text: "Looking for online",
    options: [
       {
           text: "Yes",
           step: {
              text: "Select City",
              xid: 1
           }
        },
        {
            text: "No"
        }
    ]
},
{
    type: 'radio',
    text: "Select City",
    xid: 1,
    options: [
        {
            text: "Mumbai",
            step: {
                text: "Select Area",
                xid: 2
            }
        },
        {
            text: "Delhi",
        }
    ]
}

Likewise object with text ="Select Area" has xid = 2, it should be placed below 2nd

{
    type: 'radio',
    text: "Looking for online",
    options: [
       {
           text: "Yes",
           step: {
              text: "Select City",
              xid: 1
           }
        },
        {
            text: "No"
        }
    ]
},
{
    type: 'radio',
    text: "Select City",
    xid: 1,
    options: [
        {
            text: "Mumbai",
            step: {
                text: "Select Area",
                xid: 2
            }
        },
        {
            text: "Delhi",
        }
    ]
},
{
    type: 'radio',
    text: "Select Area",
    xid: 2,
    options: [
        {
            text: "Yes",
        },
        {
            text: "No"
        }
    ]
}

Input :

let array = [
    {
        type: 'radio',
        text: "Looking for online",
        options: [
            {
                text: "Yes",
                step: {
                    text: "Select City",
                    xid: 1
                }
            },
            {
                text: "No"
            }
        ]
    },
    {
        type: "single",
        text: "First Name",
    },
    {
        type: "single",
        text: "Last Name"
    },
    {
        type: 'radio',
        text: "Select Area",
        xid: 2,
        options: [
            {
                text: "Yes",
            },
            {
                text: "No"
            }
        ]
    },
    {
        type: 'radio',
        text: "Select City",
        xid: 1,
        options: [
            {
                text: "Mumbai",
                step: {
                    text: "Select Area",
                    xid: 2
                }
            },
            {
                text: "Delhi",
            }
        ]
    },
]

Expected Output:

let array = [
    {
        type: "single",
        text: "First Name",
    },
    {
        type: "single",
        text: "Last Name"
    },
    {
        type: 'radio',
        text: "Looking for online",
        options: [
            {
                text: "Yes",
                step: {
                    text: "Select City",
                    xid: 1
                }
            },
            {
                text: "No"
            }
        ]
    },
    {
        type: 'radio',
        text: "Select City",
        xid: 1,
        options: [
            {
                text: "Mumbai",
                step: {
                    text: "Select Area",
                    xid: 2
                }
            },
            {
                text: "Delhi",
            }
        ]
    },
    {
        type: 'radio',
        text: "Select Area",
        xid: 2,
        options: [
            {
                text: "Yes",
            },
            {
                text: "No"
            }
        ]
    },
];

I tried writing a quick for loop to manipulate the object index, but it breaks when updating position of multiple object at a single time

const filteredArray = [...array];
for(let index = 0; index < filteredArray?.length; index++) {
  if (filteredArray[index]?.type === 'radio' && filteredArray[index].options && filteredArray[index]?.options?.length) {
    const length = (filteredArray[index].options && filteredArray[index]?.options?.length) || 0;
    for(let index1 = 0; index1 < length; index1++) {
      const option = filteredArray[index]?.options?.[index1];
      if (option && option?.step && option?.step?.xid){
        const idx = array.findIndex(item => item?.xid === option?.step?.xid);
        if (idx >= 0 && idx !== index + 1) {
          const removedItem = array.splice(idx, 1)[0];
          array.splice(index, 0, removedItem);
        } 
      }
    }
  }
}

Sorry in advance as English is not my first lang, I tried explaining as much in the example part

Answer 1

This looks like a tree structure, where every node might have a few options/steps. I will build a tree from it, where children are the corresponding [step]. Then I will flatten it by order of appearance of items (a depth first search).

There might be other requirements for the sorting which you didn't provide (what if several "A" items? or dangling "B" items) but this can be modified, the tree structure is very flexible.

The functions buildTree and flattenTree are pretty much self explantory.

let arr = [{
    type: 'radio',
    text: "Looking for online",
    options: [{
        text: "Yes",
        step: {
          text: "Select City",
          xid: 1
        }
      },
      {
        text: "No"
      }
    ]
  },
  {
    type: "single",
    text: "First Name",
  },
  {
    type: "single",
    text: "Last Name"
  },
  {
    type: 'radio',
    text: "Select Area",
    xid: 2,
    options: [{
        text: "Yes",
      },
      {
        text: "No"
      }
    ]
  },
  {
    type: 'radio',
    text: "Select City",
    xid: 1,
    options: [{
        text: "Mumbai",
        step: {
          text: "Select Area",
          xid: 2
        }
      },
      {
        text: "Delhi",
      }
    ]
  },
]

function buildTree(items) {
  var result = []
  var lookup = {}

  // prepare lookup for fast access by xid
  items.forEach(item => lookup[item.xid] = item);

  // make all option.steps into array of children or []
  items.forEach(item => {
    var steps = (item.options || []).filter(item => item.step && item.step.xid).map(item => item.step.xid)
    item.children = steps.map(item => lookup[item])
  })

  // the roots of the tree are the items without xid (A items)
  items.forEach(item => {
    if (!item.xid) {
      result.push(item)
    }
  })

  // items without children should come first
  result.sort(function(a, b) {
    return a.children.length - b.children.length
  })

  return result
}

function flattenTree(tree) {
  const result = [];

  function dfs(node) {
    result.push(node);

    if (node.children) {
      node.children.forEach(child => dfs(child));
    }
  }

  tree.forEach(root => dfs(root));

  result.forEach (item => delete item.children)
  
  return result;
}


var tree = buildTree(arr)
var result = flattenTree(tree)

console.log(result)

.as-console-wrapper {
  min-height: 100%
}

Answer 2

This is what is called a topological sort.

There are several algorithms for it, like depth-first.

With the specifics of your input and the requirement that non xid nodes (and then non options nodes) should come first, here is an implementation of the algorithm described in the above-linked article:

function topoSort(arr) {
    function dfs(node) {
        if (!node || visited.has(node)) return;
        visited.add(node);
        for (const {step} of node.options ?? []) {
            if (step) dfs(nodeByXid.get(step.xid));
        }
        // Add node to the appropriate result set (depending on xid presence)
        result[+(node.xid !== undefined || !!node.options)].push(node);
    }

    // Create a map to get a node by its xid
    const nodeByXid = new Map(arr.map(node => [node.xid, node]));
    // Create two result sets: one for nodes without xid (should come first)
    //    and those with xid
    const result = [[], []];
    // Nodes will be marked visited during a depth-first search
    const visited = new Set;
    // At each node launch a depth-first traversal
    arr.forEach(dfs);
    // Reverse the result of nodes with xid
    return [...result[0], ...result[1].reverse()];
}

// The exemple input from the question:
const array = [{type: 'radio',text: "Looking for online",options: [{text: "Yes",step: {text: "Select City",xid: 1}}, {text: "No"}]}, {type: "single",text: "First Name",}, {type: "single",text: "Last Name"}, {type: 'radio',text: "Select Area",xid: 2,options: [{text: "Yes",}, {text: "No"}]}, {type: 'radio',text: "Select City",xid: 1,options: [{text: "Mumbai",step: {text: "Select Area",xid: 2}}, {text: "Delhi",}]}];
const result = topoSort(array);
console.log(result);