This isn"t infinitely recursive is it?

I'm cleaning up some inherited code in our data import module. For a
variety of reasons we have to support old standards of the import
format. Since some of those old versions were created we have since
renamed some fields in our data structure. So right now I've a hard
map for some field names...

function GetMappedField($Field)
{
$FieldMap["A"] = "B";
$FieldMap["C"] = "D";

return isset($FieldMap[$Field])?$FieldMap[$Field]:$Field);
}

But I've just spent a while tracking down a bug where someone mapped A
to B and then someone else mapped B to C.

I'm thinking of changing the return to...

return isset($FieldMap[$Field])?GetMappedField($FieldMap[$Field]):$ Field);

....but I'm worried about the recursion. (Which isn't a strength of mine)

I don't THINK I need to worry about circular mappings... but I'm not
sure how to check for it if I did...

Any suggestions? Thanks!

Matt

--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

Re: This isn"t infinitely recursive is it?

Hi,

Well, you will have an infinite recursion there if the mapping has
cycles, something like A->B, B->C, C->A would generate an invite
recursion.

Checking if the mapping has cycles is pretty simple: you have to
create a directed graph and then go through the graph in DFS marking
each visited node, if you have to mark a node already marked then you
have a cycle. Tarjan's algorithm does that and a little more, see
here: http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_c omponents=
_algorithm

Hope that helps.

Jonathan

On Thu, Jul 30, 2009 at 8:38 PM, Matt Neimeyer wrote:
> I'm cleaning up some inherited code in our data import module. For a
> variety of reasons we have to support old standards of the import
> format. Since some of those old versions were created we have since
> renamed some fields in our data structure. So right now I've a hard
> map for some field names...
>
> function GetMappedField($Field)
> =A0 {
> =A0 $FieldMap["A"] =3D "B";
> =A0 $FieldMap["C"] =3D "D";
>
> =A0 return isset($FieldMap[$Field])?$FieldMap[$Field]:$Field);
> =A0 }
>
> But I've just spent a while tracking down a bug where someone mapped A
> to B and then someone else mapped B to C.
>
> I'm thinking of changing the return to...
>
> =A0 return isset($FieldMap[$Field])?GetMappedField($FieldMap[$Field]):$ Fi=
eld);
>
> ...but I'm worried about the recursion. (Which isn't a strength of mine)
>
> I don't THINK I need to worry about circular mappings... but I'm not
> sure how to check for it if I did...
>
> Any suggestions? Thanks!
>
> Matt
>
> --
> PHP General Mailing List (http://www.php.net/)
> To unsubscribe, visit: http://www.php.net/unsub.php
>
>

--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

Re: This isn"t infinitely recursive is it?

> I don't THINK I need to worry about circular mappings... but I'm not
> sure how to check for it if I did...
>
> Any suggestions? Thanks!

Would the following work? It avoids recursion entirely and also checks for
circular mappings. You can plug in your own code where the comments are to do
whatever is appropriate when a circular mapping is detected.

function GetMappedField($Field)
{
$OriginalField = $Field;

while (isset($FieldMap[$Field]) {
$Field = $FieldMap[$Field];

if ($Field === $OriginalField) {
/*
* circular mapping has been detected;
* report an error or explode or whatever
*/
break;
}
}

return $Field;
}


Ben

--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

Re: This isn"t infinitely recursive is it?

> while (isset($FieldMap[$Field]) {

Oops, left out the final close-parenthesis. I always do that with isset() for
some reason.

Ben

--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

Re: This isn"t infinitely recursive is it?

I like it... Thanks!

On Thu, Jul 30, 2009 at 8:04 PM, Ben Dunlap wro=
te:
>> I don't THINK I need to worry about circular mappings... but I'm not
>> sure how to check for it if I did...
> Would the following work? It avoids recursion entirely and also checks fo=
r
> circular mappings. You can plug in your own code where the comments are t=
o do
> whatever is appropriate when a circular mapping is detected.
>
> function GetMappedField($Field)
> {
> =A0 =A0$OriginalField =3D $Field;
>
> =A0 =A0while (isset($FieldMap[$Field])) {
> =A0 =A0 =A0 =A0$Field =3D $FieldMap[$Field];
>
> =A0 =A0 =A0 =A0if ($Field ===3D $OriginalField) {
> =A0 =A0 =A0 =A0 =A0 =A0/*
> =A0 =A0 =A0 =A0 =A0 =A0 * circular mapping has been detected;
> =A0 =A0 =A0 =A0 =A0 =A0 * report an error or explode or whatever
> =A0 =A0 =A0 =A0 =A0 =A0 */
> =A0 =A0 =A0 =A0 =A0 =A0 break;
> =A0 =A0 =A0 =A0}
> =A0 =A0}
>
> =A0 =A0return $Field;
> }
>
>
> Ben
>

--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php