• Coding

  • [Exercise] Iterative traversal of nested mappings

We define a nested mapping as a data structure where each element is either:
  • a value. For the sake of simplicity, we'll say a string.
  • a nested mapping.
For instance this is a valid example:
data = {
    a: '1',
    b: '2',
    c: { 
        d: '3',
        e: { f: '4' },
        g: { h: '5' },
        i: '6'
    },
    j: '7'   
};
The goal of this exercise is to write a function that takes a nested mapping, replacing every value (string) with the word "replaced". Note that you cannot make any assumption about the depth of the nesting, the following being another example of a valid nested mapping:
deeper_mapping = {
    a: {
        b: {
            c: {
                d: {
                    e: {
                        f: '1'
}}}}}}
Challenge
Solving this problem with a recursive function is fairly easy. Try to do it without using recursion.
It can be solved using recursion very easily, or if you don't want us to use recursion, we can implement recursion using a stack...
What I did is maybe "cheating" but it does the job in Javascript: 
data = JSON.stringify(data);
data = data.replace(/:[\s\t\n\r]*\"([^\"\\]|\\\"|\\)*\"/g, ":\"replaced\"");
data = JSON.parse(data);
See in action
var iterative_escape = function(data, action)
{
    var result = {};
    var node_stack = [data];
    var parent_stack = [result];
    
    while(node_stack.length){
        var node = node_stack.pop();
        var parent = parent_stack.pop();
        
        for(var k in node){
            if(is_string(node[k])) 
                parent[k] = action(node[k]);
            else { 
                parent[k] = {};
                node_stack.push(node[k]);                
                parent_stack.push(parent[k]);
            }
        }
    }
    
    return result;
};

var esc = function(what) { return 'replaced'; }
console.log(iterative_escape(data, esc));
a month later
Nice to see xterm switch from Java :P (I've been away a while)

Python solution, doesn't use stacks(just a simple queue) and does the replacing inline(doable not in-line but would unnecessarily complicate the code for now):
def inplace_iterative_action(data, action):
    result = {}
    queue = [data]
    while queue:
        node = queue.pop(0)
        for key,value in node.items():
            if type(value) == str:
                node[key] = action(value)
            else:
                queue.append(value)
    return data
Full example to see it in action:
import pprint

data = {
    'a': '1',
    'b': '2',
    'c': { 
        'd': '3',
        'e': { 'f': '4' },
        'g': { 'h': '5' },
        'i': '6'
    },
    'j': '7'   
}

def inplace_iterative_action(data, action):
    result = {}
    queue = [data]
    while queue:
        node = queue.pop(0)
        for key,value in node.items():
            if type(value) == str:
                node[key] = action(value)
            else:
                queue.append(value)
    return data

pprint.pprint(data)
print
inplace_iterative_action(data, lambda a:"replaced")
pprint.pprint(data)
Result:
{'a': '1',
 'b': '2',
 'c': {'d': '3', 'e': {'f': '4'}, 'g': {'h': '5'}, 'i': '6'},
 'j': '7'}

{'a': 'replaced',
 'b': 'replaced',
 'c': {'d': 'replaced',
       'e': {'f': 'replaced'},
       'g': {'h': 'replaced'},
       'i': 'replaced'},
 'j': 'replaced'}
raja wroteNice to see xterm switch from Java :P (I've been away a while)
Low blow Raja! >.< I dare you to find a single block of java code I've written here on LebGeeks ;)

Groovy was my prototyping choice before python.