Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
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 - Cobra - Lizard - Salamander - Chameleon - Bird - Pigeon - Canary - Owl Mammal - Equine - Horse - Zebra - Pony - Canine - Dog - Fox - Wolf - Bovine - Cow - Bison

All the leaves are on the same level.

Let's have a module Zoo.pm which implements the following methods:

Parent

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'.

new

The constructor. Use a list of tree leaves as arguments:

my $zoo = 'Zoo'->new(qw( Cobra Pigeon Zebra ));

get_leaves

For a given object, returns the list it was constructed from (order is not guaranteed).

print join ' ', $zoo->get_leaves; # Cobra Pigeon Zebra

The Task

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:

  1. Imagine we build trees above both of the objects, containing all their $_->get_leaves and their ancestors.
  2. If we start from the tree built above $zoo1, add all the nodes from $add and remove all nodes from $delete, we get $zoo2.
  3. Both the lists @$add and @$delete are minimal.

For example,

'Zoo'->diff( 'Zoo'->new('Cobra'), 'Zoo'->new('Fox') )

should return

( [qw[ Fox Canine Mammal ]], [qw[ Cobra Snake Reptile ]] )

Similarly,

'Zoo'->diff( 'Zoo'->new(qw( Dog Fox Wolf )), 'Zoo'->new(qw( Fox )));

should return

( [], [ '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).

($q=q:Sq=~/;[c](.)(.)/;chr(-||-|5+lengthSq)`"S|oS2"`map{chr |+ord }map{substrSq`S_+|`|}3E|-|`7**2-3:)=~y+S|`+$1,++print+eval$q,q,a,

In reply to Tree Structure Challenge by choroba

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (3)
As of 2022-08-08 22:46 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?