ashishsony
ashishsony

Reputation: 2587

how to find a key and return its path through the hierarchy in a JSON using perl

{

  "root1" : {
      "sub1" : null,
      "sub2" : {
         "subsub1" : {
            "key1" : {

            },
            "key2" : {

            },
            "key3" : {

            },
            "key4" : {

            }
         }
      },
      "sub3" : {
         "subsub2" : {
            "key5" : {

            }
         }
      }
  },
  "root2" : {
      "sub1" : null,
      "sub2" : {
         "subsub1" : {
            "key1" : {

            },
            "key2" : {

            },
            "key3" : {

            },
            "key4" : {

            }
         }
      },
      "sub3" : {
         "subsub2" : {
            "key8" : {

            }
         }
      }
  }
}

consider the above json. How to know if 'key8' exists in this json and also find the path where its found in the json.

e.g if searched for 'key8' need to get output similar to :

root2->sub3->subsub2->key8

Upvotes: 0

Views: 109

Answers (1)

ikegami
ikegami

Reputation: 386361

It's just a straightforward tree traversal. The following returns as soon as a match is found (rather than looking for all matches).

sub key_search {
    my $target = $_[1];   
    my @todo = [ $_[0] ];
    while (@todo) {
        my ($val, @path) = @{ shift(@todo) };
        my $reftype = ref($val);
        if (!$reftype) {
           # Nothing to do
        }
        elsif ($reftype eq 'HASH') {
           for my $key (keys(%$val)) {
              return @path, $target if $key eq $target;

              push @todo, [ $val->{$key}, @path, $key ];
           }
        }
        elsif ($reftype eq 'ARRAY') {
           for my $i (0..$#$val) {
              push @todo, [ $val->[$i], @path, $i ];
           }
        }
        else {
           die("Invalid data.\n");
        }
    }

    return;
}

my @path = key_search($data, 'key8')
   or die("Not found.\n");

Notes

  • The result is ambiguous if the data can contain arrays, and if any of the hashes can have integers for keys. Steps can be taken to disambiguate them.
  • The above doesn't check for cycles, but those can't exist in JSON.
  • Replace push with unshift to get a depth-first search instead of a breadth-first search.

Upvotes: 3

Related Questions