At work, I needed to fix logging of changes in a tree structure. The language was unfortunately Java, but I started with a Perl prototype to test the approaches and border cases. The Java solution was more challenging for me, but the Perl implementation was still interesting enough to share. For those bored or interested, I present the problem below. The original domain was different, but I'm probably not allowed to speak about it outside of the firm.
We'll use the famous animal tree:
Reptile - Snake - Python
- Lizard - Salamander
- Bird - Pigeon
Mammal - Equine - Horse
- Canine - Dog
- Bovine - Cow
All the leaves are on the same level.
Let's have a module Zoo.pm which implements the following methods:
Static method. 'Zoo'->Parent($node) returns the parent of the given node in the tree, e.g. 'Zoo'->Parent('Owl') is 'Bird', 'Zoo'->Parent('Bird') is 'Reptile'.
The constructor. Use a list of tree leaves as arguments:
my $zoo = 'Zoo'->new(qw( Cobra Pigeon Zebra ));
For a given object, returns the list it was constructed from (order is not guaranteed).
print join ' ', $zoo->get_leaves; # Cobra Pigeon Zebra
When comparing too different zoos, we aren't interested in the animals only, but in their categories, too.
Our task is to implement a static method 'Zoo'->diff($zoo1, $zoo2) which returns two array references, $add and $delete, such that:
- Imagine we build trees above both of the objects, containing all their $_->get_leaves and their ancestors.
- If we start from the tree built above $zoo1, add all the nodes from $add and remove all nodes from $delete, we get $zoo2.
- Both the lists @$add and @$delete are minimal.
( [qw[ Fox Canine Mammal ]],
[qw[ Cobra Snake Reptile ]]
'Zoo'->diff( 'Zoo'->new(qw( Dog Fox Wolf )),
'Zoo'->new(qw( Fox )));
[ 'Dog', 'Wolf' ]
Updates: Please, use <readmore> tags for the code.
Use only the documented API in the solution (i.e. Parent and get_leaves). The tree structure is not accessible directly (in reality, it was stored in a database).
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
Read Where should I post X? if you're not absolutely sure you're posting in the right place.
Please read these before you post! —
Posts may use any of the Perl Monks Approved HTML tags:
You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
- a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.
| & || & |
| < || < |
| > || > |
| [ || [ |
| ] || ] |