Complex object comparison

[trickster321]

Hi all,

I'm trying to write some code to compare two complex objects, by which I mean objects that contain other objects that contain other objects and so on (I guess that makes them composite objects). I need to know what differences there are either in the properties of each object or in the child objects and the child object properties.

For example, I have a Product object that has a property of users that is a collection of user objects, now each user has a property of addresses which is a collection of address objects and so on. Is there a design pattern that can be applied to compare two product objects?

I work in .NET and C# so was thinking whether I can apply reflectance to analyse my object properties first and then use that information somehow in the comparison.

Any advice gratefully received as at the moment I'm having to iterate over the object tree on both objects comparing each property as I go. This seems to be a lot of hard work for something that feels like it should be a relatively straight forward object comaprison.

Rick Edwards

 

[stevexff]

You want to compare a whole graph of objects with another whole graph of objects, at the property level. What makes you think this is a 'relatively straightforward comparison'?

Reflection is only useful here if you don't know what the objects are or what their properties are at compile time. But that doesn't seem to be the case here.

Perhaps if you tell us why you need to do this, rather than how, maybe we can come up with some easier alternative?

Steve

[small]"Every program can be reduced by one instruction, and every program has at least one bug. Therefore, any program can be reduced to one instruction which doesn't work." (Object:erlDesignPatterns)[/small]

 

[cpjust]

Do each of the sub-objects have their own comparison functions?
You should only need to compare each of the objects that are direct members of that class, then each of those member objects should have their own comparison functions for each of their members...

 

[stevexff]

The nested comparison route would be OK for a simple boolean result, but he wants to know what the differences are, not just simply that they are different...

Steve

[small]"Every program can be reduced by one instruction, and every program has at least one bug. Therefore, any program can be reduced to one instruction which doesn't work." (Object:erlDesignPatterns)[/small]

 

[trickster321]

Hi steve, thanks for the reply.

I don't really want to go too deeply into the business case behind the functionality but I basically have a "product" which a user can own an instance of. Now a product instance can have, for example, several other users and/or several items associated with it. Each user can have ca. several addresses and each item can in turn have several users associated with it (who can have several addresses) and so on and so forth. All these are base business entity objects in my domain (user, address, item, etc) and related to each other through the database model. So a product instance is actually a heirachical tree of other objects.

Think of an insurance policy, I can insure a car, a building, some other "item". Now I take out my policy (my product instance) for a car, the car might have several named drivers (users) who live somewhere else and it might be stored somewhere other than my house. So you can see how a complex object tree can quickly build up.

Now if I go and change my policy (add/remove a driver, add another car, move house, whatever then I need to maintain a record of the changes made. In my environment I work with a product instance object that I store in my session state and manipulate through the web UI, adding objects, changing object properties, removing objects, etc.

So right before I save my "updated" product instance to the database (i.e. overwrite the original records) I need to compare it to the original and work out what has changed to maintain some form of "change log". The product instance object is "flattened" by the business tier and fed to the DAL which updates the records as necessary. It's here that we are currently doing the object comparison which seems like a logical place.

Interestingly because this is data driven we don't actually know the item type until runtime, we build up a collection of items associated to a product instance through meta data associated with the product (i.e. this is a car insurance product therefore any instance of it deals with items of type vehicle). Hence my thinking along the lines of reflection, but don't worry about that, it's just confusing the issue.

So back to my original question. Comparing complex object trees "feels" like it's something that would happen a lot in the real world so I was wondering whether there are any design approaches that I should look into that might cater for this. Having analysed the problem further I now appreciate that it isn't at all straight forward and I doubt there's a "magic bullet".

Regards

Rick Edwards

 

[cpjust]

I still think my previous comment would be the way I'd do it (but return a 'diff' object instead of a boolean). Each object should do its own diff, then pass it up to the object that requested the diff... The hard part might be coming up with a good way of logging the differences the same way for all objects.

 

[stevexff]

Rick

You might want to have a look at the .NET Dataset object. AFAIK it behaves kind of like a mini database engine in memory, with tables and relationships either defined programmatically or loaded from your database. You can make changes to it, and I'm fairly sure that it has a method to return a new Dataset containing only the changes. Which might take some of the grind out of what you want to do. The idea is that you create and populate your object from a subset of rows from various tables in your database, stuff it into session, interact with it, and then finally use the changes to update the database. Quite how it manages optimistic locking failures, I don't know...

You might have to do some more reading, it's quite a heavyweight object. I suspect whole doorstep-sized books have been produced on using Datasets.

Given your preference for a data-centric approach (see other thread ) this might appeal to your sensibilities.

HTH

Steve

[small]"Every program can be reduced by one instruction, and every program has at least one bug. Therefore, any program can be reduced to one instruction which doesn't work." (Object:erlDesignPatterns)[/small]

 

[stevexff]

My apologies, it's DataSet, not Dataset. And it does have a GetChanges() method, see docs here

http://msdn2.microsoft.com/en-us/library/system.data.dataset.getchanges.aspx

Sounds like it might do what you need.

Steve

[small]"Every program can be reduced by one instruction, and every program has at least one bug. Therefore, any program can be reduced to one instruction which doesn't work." (Object:erlDesignPatterns)[/small]

 

[trickster321]

We've done a little more work on this and have written a comparator class that takes two objects that are of the same type and uses reflection to get a list of object properties. We then iterate over the property array and use the object equal method to see if there are any differences between them. This works well until we hit a property that is in fact a typed collection containing our custom business objects, then the object equal method always seems to report a difference, even when the collections are in reality identical.

So the next chapter in the saga is to develop a method that will compare typed collections. This is not as trivial as it sounds. We need to be able to iterate over one collection and compare each object with every other object in the comparison collection (the objects in each list are not necessarily in the same order so a straight comparison based on index won't work).

We've done this, but the solution is far from elegant as we have to explicitely check we have a collection and then what type of objects the collection contains. This leads to a bunch of case statements and tightly couples the comparator to our business entities. Not good.

So anyone done anything similar?

We thought about the dataset approach but given our model that would probably lead to us having to put the comparator code in the data access objects which wasn't desirable. If we start to add datasets to the business tier then we break our typed business object model which again was something we didn't want to do.

Still, watch this space.....

Rick Edwards

 

[chiph]

What's wrong with implementing IComparer on both your entity and collection objects? The implementation on the entity is straightforward -- compare the values you care about and return the comparison result.

Implementing it on a collection is trickier -- you want to iterate over the contents and invoke their IComparer implementation. The question (which only you can answer, since you know the needs of your app) is what happens when 20% of your items return -1, 38% return 0, and the remaining 42% return 1 ?? Does that make the whole collection "greater" ?

Or maybe you specify that if any of the items are "less", they're all considered to be less.

Chip H.


____________________________________________________________________
If you want to get the best response to a question, please read FAQ222-2244 first

 

[trickster321]

Hi chiph,

we've aready discussed using ICompare earlier in the thread. I need to know what the differences are, not just that the objects are different. So for example in my collection of item objects I need to know exactly what are the differences in each item, are there any new items, has an item been deleted, etc. Not simply is the collection bigger, smaller or has the object at index 1 changed. I require a much deeper comparison than a simple boolean.

Regards

Rick Edwards

 

[chiph]

In that case (sorry!) I would return a Dictionary<> that contains the property names & their values of the properties that were different.

To implement this, you can use reflection. It won't be fast, but at least you'll only need to write the code once.

Alternatively, you can write a datatype-specific comparer that is significantly faster (because it knows the properties to inspect), but is not reusable.

Chip H.


____________________________________________________________________
If you want to get the best response to a question, please read FAQ222-2244 first

 

[BobRodes]

By the way, this sounds like a textbook example of the Composite pattern. I like this page:

http://www.exciton.cs.rice.edu/JavaResources/DesignPatterns/composite.htm

A quote from the page: "Composite patterns are often used to represent recursive data structures. The recursive nature of the Composite structure naturally gives way to recursive code to process that structure."

Bob

 

[trickster321]

Cheers Bob,

will investigate this further. Unfortunately, as with everything the project has moved on and the deadline is looming so no time to refactor now.

Just been (briefly) reading the gang of four book on composites, looks like its useful for calling common methods on objects that may (or may not) be part of a composite, it effectivley flattens the object tree, calling an operation on each object. Not sure how to apply this for object comparison, especialy for objects in a collection property of a parent.

Looks like some bedtime reading for me

Rick Edwards

 

[BobRodes]

Well, I was thinking you could drill down from the top until you get to a leaf.