Javascript - Traverse object while tracking index and depth-CodePudding

Background Info

I have an object containing some data from a network log. Here is what it looks like.

 {
  "meta_data": {
  },
  "network_log": [
    {
      "request_id": "",
      "request": {
        "url": "https://stackoverflow.com/"
      },
      "response": {
        "status": 200,
        "redirectURL": "",
        "redirect": []
      }
    },
    {
      "request_id": "",
      "request": {
        "url": "https://stackoverflow.com/page-that-redirects"
      },
      "response": {
        "status": 302,
        "redirectURL": "https://stackoverflow.com/another-page-that-redirects",
        "redirect": [
          {
            "request_id": "",
            "request": {
              "url": "https://stackoverflow.com/another-page-that-redirects"
            },
            "response": {
              "status": 302,
              "redirectURL": "https://stackoverflow.com/final-page",
              "redirect": [
                {
                  "request_id": "",
                  "request": {
                    "url": "https://stackoverflow.com/final-page"
                  },
                  "response": {
                    "status": 200,
                    "redirectURL": "",
                    "redirect": []
                  }
                }
              ]
            }
          }
        ]
      }
    },
    {
      "request_id": "",
      "request": {
        "url": "https://stackoverflow.com/page-that-redirects"
      },
      "response": {
        "status": 200,
        "redirectURL": "https://stackoverflow.com/page-that-was-redirect-to",
        "redirect": []
      }
    }
  
  ]
}

The network_log element will always exist. Each item in network_log is an anonymous object, but for the purposes of this question let's call it a ReqResp object.

ReqResp.response.redirect is a list of ReqResp objects. It can have 0 or more items in the list.

Desired Output

I need to navigate this object and populate all of the request_id fields. The request_id field will be a string value that follows a format like "Request.Num.Num.Num..." where there is an unlimited amount of possible "Num" values depending on the depth of the object. The "Num" value should start at 1, not 0.

Taking the sample above, here is what the expected output would be:

 {
  "meta_data": {
  },
  "network_log": [
    {
      "request_id": "Request.1",
      "request": {
        "url": "https://stackoverflow.com/"
      },
      "response": {
        "status": 200,
        "redirectURL": "",
        "redirect": []
      }
    },
    {
      "request_id": "Request.2",
      "request": {
        "url": "https://stackoverflow.com/page-that-redirects"
      },
      "response": {
        "status": 302,
        "redirectURL": "https://stackoverflow.com/another-page-that-redirects",
        "redirect": [
          {
            "request_id": "Request.2.1",
            "request": {
              "url": "https://stackoverflow.com/another-page-that-redirects"
            },
            "response": {
              "status": 302,
              "redirectURL": "https://stackoverflow.com/final-page",
              "redirect": [
                {
                  "request_id": "Request.2.1.1",
                  "request": {
                    "url": "https://stackoverflow.com/final-page"
                  },
                  "response": {
                    "status": 200,
                    "redirectURL": "",
                    "redirect": []
                  }
                }
              ]
            }
          }
        ]
      }
    },
    {
      "request_id": "Request.3",
      "request": {
        "url": "https://stackoverflow.com/page-that-redirects"
      },
      "response": {
        "status": 200,
        "redirectURL": "https://stackoverflow.com/page-that-was-redirect-to",
        "redirect": []
      }
    }
  
  ]
}

I have looked up some recursive functions in similar questions, but I'm struggling to understand how I would track the "Num" values for each item.

CodePudding user response：

You could do either a breadth-first search or a depth-first search. Both can be implemented iteratively or recursively. While the iterative solution will be more efficient the recursive solution might be easier to implement. The complexity for both algorithms will be O(|V| |E|) with V being the set of nodes and E being the set of edges.

A simple solution using depth-first search could look like this.

const input = {
  meta_data: {},
  network_log: [
    {
      request_id: "",
      request: {
        url: "https://stackoverflow.com/",
      },
      response: {
        status: 200,
        redirectURL: "",
        redirect: [],
      },
    },
    {
      request_id: "",
      request: {
        url: "https://stackoverflow.com/page-that-redirects",
      },
      response: {
        status: 302,
        redirectURL: "https://stackoverflow.com/another-page-that-redirects",
        redirect: [
          {
            request_id: "",
            request: {
              url: "https://stackoverflow.com/another-page-that-redirects",
            },
            response: {
              status: 302,
              redirectURL: "https://stackoverflow.com/final-page",
              redirect: [
                {
                  request_id: "",
                  request: {
                    url: "https://stackoverflow.com/final-page",
                  },
                  response: {
                    status: 200,
                    redirectURL: "",
                    redirect: [],
                  },
                },
              ],
            },
          },
        ],
      },
    },
    {
      request_id: "",
      request: {
        url: "https://stackoverflow.com/page-that-redirects",
      },
      response: {
        status: 200,
        redirectURL: "https://stackoverflow.com/page-that-was-redirect-to",
        redirect: [],
      },
    },
  ],
};

const depthFirstSearchRec = (input, path = []) => {
  return input.map((req, idx) => {
    const newPath = [...path, idx   1]
    req.request_id = `Request.${newPath.join(".")}`
    const redirect = req.response.redirect;
    if (
      redirect &&
      Array.isArray(redirect) &&
      redirect.length !== 0
    ) req.response.redirect = depthFirstSearchRec(req.response.redirect, newPath);
    return req;
  })
};

// this mutates the input! NOT immutable!
depthFirstSearchRec(input.network_log);
console.log(JSON.stringify(input, null, 4));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Please note: this solution mutates the input!

CodePudding user response：

Here is an immutable approach, returning a new object:

const convertLog = (xs, path = "Request") =>
  xs .map (({request_id, response: {redirect, ...more}, ...rest}, i) => ({
    request_id: `${path}.${i   1}`,
    ...rest,
    response: {
      ...more,
      redirect: convertLog (redirect, `${path}.${i   1}`)
    }
  }))

const convert = ({network_log, ...rest}) => 
  ({...rest, network_log: convertLog (network_log)})

const data = {"meta_data": {}, "network_log": [{"request": {"url": "https://stackoverflow.com/"}, "request_id": "", "response": {"redirect": [], "redirectURL": "", "status": 200}}, {"request": {"url": "https://stackoverflow.com/page-that-redirects"}, "request_id": "", "response": {"redirect": [{"request": {"url": "https://stackoverflow.com/another-page-that-redirects"}, "request_id": "", "response": {"redirect": [{"request": {"url": "https://stackoverflow.com/final-page"}, "request_id": "", "response": {"redirect": [], "redirectURL": "", "status": 200}}], "redirectURL": "https://stackoverflow.com/final-page", "status": 302}}], "redirectURL": "https://stackoverflow.com/another-page-that-redirects", "status": 302}}, {"request": {"url": "https://stackoverflow.com/page-that-redirects"}, "request_id": "", "response": {"redirect": [], "redirectURL": "https://stackoverflow.com/page-that-was-redirect-to", "status": 200}}]}

console .log (convert (data))

.as-console-wrapper {max-height: 100% !important; top: 0}

Our main function, convert, handles the shell of the object, just copying all properties except network_log, which it delegates to our significant function,convertLog. This recursive function will be called on the redirect array of the response property, passing the current path (e.g. Request.2.1) and tacking on the current index.