Reputation: 2587
{
"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
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
push
with unshift
to get a depth-first search instead of a breadth-first search.Upvotes: 3