Polymorphism, Java : Sets and Maps ... any ideas?
Fred Mikkelsen's Blog |
December 30, 2007 8:42 PM
|
Comments (3)
Background ... Over the holidays, I have been working on a binary representation for XML that is queryable and compressed. This doesn't particuarly clarify the set-up, but it's a start !!
In the organization of the XML, text, meta tags, attributes, and all the other parts of XML would be represented by a unique number. Text that is repeated would have a smaller number. Meta tags could provide mapping for concatenated values, and each of the constituent parts would be mapped to a unique integer. Integers are mapped to integers automatically, the mapping for these would not need to be provided. However, if a 12-digit number occurred 100 times in one XML document, it would be more compressed to map a 2-digit number to it.
Numbers would ideally map to numbers, and Strings would ideally map to their hash values, and in most cases, the specifics of what is mapped can be worked out by these simple rules. For the data gathering phase, I envisioned using Set operations to note that a value was seen and how it was mapped. For this I would like my class to implement the java.util.Set interface. Then, the caller of the class does not need to determine what the value will map to and can perform a set "add()" operation.
When the value is dropped into my java.util.Set-enabled class, there is a small chance that the ideal form cannot be selected. When rendering the value later, I would need to determine what it was really mapped to. For that, I would also like my class to implement the java.util.Map interface.
I had never used this aspect of the API, and it hadn't occured to me, but the "remove" method defined on these two classes has a different signature. java.util.Set.remove(Object) returns "true" if the element was in the set, and java.util.Map.remove(Object) returns the value Object was mapped to, null if otherwise. Due to the rules of Java which do not allowing return types to be different with the other aspects of the signature the same on inherited methods, I could not make a class that implements something that behaves both a Map, and as a Set because of that one signature.
The approach I'm taking is to construct a class "SetMap" that implements the union of all methods in the Set and Map interfaces, choosing the favored form for remove() to be the Map signature. Then, I created two other classes, "SetMapAsSet" and "SetMapAsMap" to provide an identity mask to allow the data to be viewed with the proper polymorphic prism.
Ultimately ... I may just use the Map signature and require the user of the class to know during the tag and data gathering phase that they need to map to values explicitly. However, it did bring an interesting thought experiment to bear about how to implement polymorphism in situations where things line up logically (like an Airplane that is also an Asset) but not exactly at the technical level of the signature.
Addendum A:
Wikipedia's Reference to the Liskov substitution principle, is an interesting discussion point. I'm not sure how it applies to multiple inheritence or multiple interface inheritenace as supported in java in general where you're explicitly desiring to present two object personalities.Having stepped through every method of each interface, everything was aligned with my unified definition except "remove()". Which then got me wondering, if you were in a situation where you had to present two different interfaces, and a minor technical conflict on a return type (that you never used) was the only thing preventing it, what would you do?
rev 1.1
Comments
Comments are listed in date ascending order (oldest first) | Post Comment
-
Fred,
Have you considered using Huffman Coding?
(Reference: http://en.wikipedia.org/wiki/Huffman_coding)
It won't solve your Set and Map problem but it will help with the compression.
Keith Danekind
danekind@bea.com
Posted by: danekind on January 4, 2008 at 10:30 AM
-
paston's comment encouraged me to go back and add "Addendum A" to clarify the issue. His approaches are very good when you have the control over the code that I currently do. My example about Map and Set provoked a thought discussion using interfaces we're familiar with. Suppose you could provide a constractually-consistent definition for every method in two or more interfaces, and one annoying nit like the return value of "remove(o)" differed and blocked you from actually exposing both? And suppose you couldn't ignore one of the interefaces and implement this as a minor extension of one of the others because other code, elsewhere in the system, was depending on receiving specific interface presentations? How would you provide the means to illicit each of these interfaces in a compact, maintainable, extensible, and clear manner?
Posted by: fmikkels on December 31, 2007 at 11:32 AM
-
Inheritance can work well when the universe to which you apply it is
understood, unambiguous, and mostly static. Otherwise, it is broken
and best avoided in favour of composition. An Airplane is only an
Asset in the field of airline corporate accounting, and there you may
indeed be able to make the signatures line up.
If I understand correctly, you want a map like collection which
calculates its own values. This has no use for a put(k, v)
operation, so it is not a java.util.Map. The classic "Java
Collections" answer to have you interface extend Map, add an add(k)
operation, and throw an UnsupportedOperationException for
put(k, v). This bends the Liksov substitution principle to
breaking point, and is ugly. Alternatively, you might extend
java.util.Set, and add getValue(k).
Personally, I would define my own interface that extends neither
j.u.Set nor j.u.Map.
Posted by: paston on December 31, 2007 at 5:29 AM
|
