CODEWITHSUNDEEP
pythonpython-3.xdictionaryrecursion
madik_atma
madik_atma

Reputation: 799

Recursively locate nested dictionary containing a target key and value

There are many questions about this problem, but in my case they are not working. I'm trying to find a nested dictionary given a target key and value pair. My recursive function returned none (after fix, max depth recursive error).

def recursive_lookup(k, sv, d):
    if k in d: return d[k]
    for v in d.values():
        if isinstance(v, dict):
            a = recursive_lookup(k, sv, v)
            if a == sv:
                if a is not None:
                    return d
    return None


def run():
    maly = {'_id': "ObjectId('5def7e8c4802b906dd067f97')", 'METADATA': {'Tags': {'AcquisitionTime': '2019-02-05T15:59:37.5862118Z', 'ImageScaling': {'ImageScaling': {'ImagePixelSize': '4.54,4.54'}}, 'DetectorState': {'CameraState': {'ApplyCameraProfile': 'false', 'ApplyImageOrientation': 'true', 'ExposureTime': '2200000', 'Frame': '0,0,2752,2208', 'ImageOrientation': '3'}}, 'StageXPosition': '+000000141526.5820', 'StageYPosition': '+000000189329.5000', 'FocusPosition': '+000000002097.2550', 'RoiCenterOffsetX': '+000000000000.0000', 'RoiCenterOffsetY': '+000000000000.0000'}, 'DataSchema': None, 'AttachmentSchema': None}}

    returned_value = recursive_lookup("FocusPosition", "+000000002097.2550", maly)
    print(returned_value)


run()

If I change return d to recursive_lookup(k, sv, d) it is also not working. It should return the maly dictionary, but it returned None.

How can I fix that problem?

Upvotes: 2

Views: 131

Answers (3)

Mohamed Ali Mani
Mohamed Ali Mani

Reputation: 41

i think the problem is when you call recursive_search() for the second time it just keeps looking for sv in the same dictionary which is maly and doesn't search deeper inside the rest that's why it returns None

Upvotes: 0

ggorlen
ggorlen

Reputation: 57145

This is the right idea, but a matched result isn't being passed up the call stack correctly. You can also simplify logic by checking key and value on the same call frame--this should also eliminate a bug where the target key-value are on the top level of the dict (there's no previous frame to fall back on to check the value).

def recursive_lookup(target_key, target_val, dictionary):
    if target_key in dictionary and dictionary[target_key] == target_val:
        return dictionary

    for value in dictionary.values():
        if isinstance(value, dict):
            if result := recursive_lookup(target_key, target_val, value): 
                return result

if __name__ == "__main__":
    maly = {'_id': "ObjectId('5def7e8c4802b906dd067f97')", 'METADATA': {'Tags': {'AcquisitionTime': '2019-02-05T15:59:37.5862118Z', 'ImageScaling': {'ImageScaling': {'ImagePixelSize': '4.54,4.54'}}, 'DetectorState': {'CameraState': {'ApplyCameraProfile': 'false', 'ApplyImageOrientation': 'true', 'ExposureTime': '2200000', 'Frame': '0,0,2752,2208', 'ImageOrientation': '3'}}, 'StageXPosition': '+000000141526.5820', 'StageYPosition': '+000000189329.5000', 'FocusPosition': '+000000002097.2550', 'RoiCenterOffsetX': '+000000000000.0000', 'RoiCenterOffsetY': '+000000000000.0000'}, 'DataSchema': None, 'AttachmentSchema': None}}
    print(recursive_lookup("FocusPosition", "+000000002097.2550", maly))

Here's a more-easily verifiable version that uses a simple dictionary and doesn't use the 3.8 assignment expression:

def recursive_lookup(target_key, target_val, dictionary):
    if target_key in dictionary and dictionary[target_key] == target_val:
        return dictionary

    for value in dictionary.values():
        if isinstance(value, dict):
            result = recursive_lookup(target_key, target_val, value)

            if result: return result

if __name__ == "__main__":
    dictionary = {
        "a": "foo",
        "b": {
            "c": "bar",
            "d": "baz",
            "e": {
                "f": "quux",
                "g": "garply"
            }
        }
    }

    print(recursive_lookup("c", "bar", dictionary)) # => {'c': 'bar', 'd': 'baz', 'e': {'f': 'quux', 'g': 'garply'}}
    print(recursive_lookup("g", "garply", dictionary)) # => {'f': 'quux', 'g': 'garply'}

Upvotes: 2

sciroccorics
sciroccorics

Reputation: 2427

This sample code performs a recursive search in a hierarchy of dictionaries. So I guess it may correspond to what you are looking for:

def rec_search(key, dic):
  if key in dic:
    return dic[key]
  for d in dic.values():
    if isinstance(d, dict):
      val = rec_search(key, d)
      if val is not None: return val
  return None

maly = {1:'a',
        2:'b',
        3:{4:'d',
           5:'e',
           6:{7:'g',
              8:'h'}
          },
        9:{10:'i',
           11:'j',
           12:{13:'l',
               14:'m'}
          }
        }

print(rec_search(2,maly)) # --> 'b'
print(rec_search(7,maly)) # --> 'g'
print(rec_search(10,maly)) # --> 'i'
print(rec_search(15,maly)) # --> None

EDIT: Corrected code after Sylwester's comment

Upvotes: 0

Related Questions