• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Data Structure & Problem Solving using JAVA

 
Bartender
Posts: 962
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
<pre>Author/s : Mark Allen Weiss
Publisher : Addison-Wesley
Category : Advanced
Review by : Peter Tran
Rating : 7 horseshoes
</pre>
It's amazing how many people who develop software for a living and have no concept of data structures. More often than not, these developers will either write unmaintainable code or fall into the write everything from scratch syndrome resulting in very inefficient and buggy code. Anyone who is serious about becoming a professional developer should learn the fundamental data structure such as link list, hash map, trees, etc. The prior incarnation of this book was written in C, C++, Ada, and JAVA (1st ed.). The 2nd edition builds on Mark�s experience with this subject and does a commendable job of referencing the JAVA Collections classes where appropriate. Data structure is only one step above automata and formal language analysis in dry subject matter, but nevertheless, it's just as important. For most people, the subject matter isn't consider a pleasant night reading, but the next time you apply for a job and the interviewer asks you to describe how a hash map is implemented in JAVA, you can confidently answer the question. Personally, I think everyone should be familiar with data structure and Mark A. Weiss's book is as good a book as any on the subject matter.
More info at Amazon.com || More info at Amazon.co.uk
 
Sheriff
Posts: 7001
6
Eclipse IDE Python C++ Debian Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
So what does he say about trees, then?
I'm still looking for "java.util.Tree" - I can find Map, List, Set, but no Tree ! I naively thought that trees were as fundamental as the others
 
High Plains Drifter
Posts: 7289
Netbeans IDE VI Editor
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Oooh, a chance to show some ignorance: isn't a Tree equivalent to a map of lists? I always thought of a tree as a compound data structure, not a fundamental one.
 
Frank Carver
Sheriff
Posts: 7001
6
Eclipse IDE Python C++ Debian Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well, a tree could be a map of lists, but then a map could just be a set of lists each constrained to two elements, and a set is just a list with a uniqueness constraint. So we started at Java and ended up with LISP
In practice the basic set of operations on a tree node: ( get parent, get value, get children )don't line up very well with any of the other java.util types, which is why we have:
java.io.File, XML DOM, javax.swing.TreeModel, all of JNDI, JDOM etc. etc. all of which implement different, completely incompatible tree structures. And more are being written every day.
Let's stop this madness. Imagine if there was a simple, very minimal Tree (a.k.a TreeNode, since trees are by nature recursive) interface in java.util defining the above three basic operations.
All those treelike APIs could implement this basic interface, then we could write generic tree-traversal algorithms, and (for example) simply switch at runtime whether tre-structured config information comes from XML via DOM or JDOM, or from JNDI, or from a file system of properties files, or from an IMAP server mailbox structure via JavaMail ...
 
Michael Ernest
High Plains Drifter
Posts: 7289
Netbeans IDE VI Editor
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I can think of one good reason why this doesn't happen, and that is that trees have radically different performance benefits depending on how you design them. The value of a generic design, to hear some of my hardcore programming friends tell it, is *far* outweighed by the benefits of a custom design.
That doesn't negate the idea of a standard interface, but the real work is in the details.
Even JTree seems optimized for a very particular kind of use.
 
Frank Carver
Sheriff
Posts: 7001
6
Eclipse IDE Python C++ Debian Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I agree. I don't want a standard implementation of a tree structure, just a standard interface so my code can change tree type when necessary.
I have ranted many times that the standard Java APIs don't make nearly enough use of interfaces. Some newer APIs seem more thought out (Collections is, on the whole, good), but the majority of the APIs still only provide classes, not interfaces. Some even commit the horror of making these classes final
 
Ranch Hand
Posts: 130
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Frank Carver:
So what does he say about trees, then?


Trees can best be seen as a set of treenodes, a treenode has a link to all its children and to his parent. if the treenode has no parent, it is the root. If the treenode has no children it's a leaf.
I hope this suits you enough.
 
Frank Carver
Sheriff
Posts: 7001
6
Eclipse IDE Python C++ Debian Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sure, that's how I tend to build trees, but that's not really the issue.
My complaint is still that there should be some sort of Tree/TreeNode interface in java.util along with Set, Map, List and so on.
Trees are everywhere, these days, and yet all these differenrt tree APIs have no common interfaces, so we have no way of writing common code which will work with more than one Tree-like API.
 
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
http://jakarta.apache.org/commons/collections.html
 
Frank Carver
Sheriff
Posts: 7001
6
Eclipse IDE Python C++ Debian Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That's interesting. I guess it must have been a long time ago that I last looked at Jakarta Commons. Some of the things in the Collections section look quite neat. But still no Tree or TreeNode interfaces, though.
 
reply
    Bookmark Topic Watch Topic
  • New Topic