• 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Bear Bibeault
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Paul Clapham
  • Devaka Cooray
  • Knute Snortum
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Frits Walraven
Bartenders:
  • Carey Brown
  • salvin francis
  • Claude Moore

Empty nodes in a tree  RSS feed

 
Ranch Hand
Posts: 104
Java Linux Monad
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

How do you handle or what pattern do you use for a object that occurs all through a tree but is unique? I don't want to create this object every time I need one because every instance of this object is identical and all I need is a reference to that object.

A classic example would be an empty node in a binary tree. We use this empty node all through the tree, but they are identical so all we need is one empty node and many references to it. How do I manage that in Java?
 
Sheriff
Posts: 24374
55
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That sounds a lot like the Flyweight pattern. Although the Java example in that Wikipedia page is very unrelated to your specific example.

In your example I would say, just create an empty node as a public object in your Tree class and then just use references to that specific object rather than creating new empty nodes.

Of course that Tree.emptyNode object would have to be immutable. But perhaps all your nodes are immutable?
 
Gerard Gauthier
Ranch Hand
Posts: 104
Java Linux Monad
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Its a Btree and all the nodes are immutable. I'm basically starting with the concept that the Btree contains Nodes and Nodes is abstract with two subclasses Empty and Node. It worked great until I realized that creating a new instance of Empty was wasteful and I should have one instance of Empty which is referenced many times.
 
Gerard Gauthier
Ranch Hand
Posts: 104
Java Linux Monad
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I found a solution or at least a starting point. I created a Btree class which is basically a wrapper that contains a final instance of the empty node and an inner class which contains the functionality for a Btree. It works, well it creates one empty node that is shared across all nodes.

I'll have to do a lot more contemplating/reading before I settle on a real solution.
 
Gerard Gauthier
Ranch Hand
Posts: 104
Java Linux Monad
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I dropped the wrapper solution! I just pushed the functionality down to my nodes and everything just works. It uses one empty node and the Btree(which uses the nodes) becomes very simple.

Nodes.java


Empty.java


Node.java


It's surprising how straightforward the code became when I pushed the functionality down to the nodes.
 
Paul Clapham
Sheriff
Posts: 24374
55
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Gerard Gauthier wrote:It's surprising how straightforward the code became when I pushed the functionality down to the nodes.



Yeah, that's how object-oriented design works. A Node should know how to add a new Node underneath it, for example, rather than having something outside the class be responsible for that.

Just a comment: I looked at your code for quite a while trying to understand why Node was a subclass of Nodes. To me a Nodes object should represent a collection of nodes, and it took a while before I realized that your Nodes class doesn't do that. Instead it's an abstract class which specifies what methods a class should implement if it's supposed to represent a node. So I would have called it AbstractNode.
 
Paul Clapham
Sheriff
Posts: 24374
55
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And it looks like you don't have any use for the Empty class any more!

 
Gerard Gauthier
Ranch Hand
Posts: 104
Java Linux Monad
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Paul Clapham wrote:And it looks like you don't have any use for the Empty class any more!



I don't see how you arrived at that conclusion... The Empty object is used to terminate Node objects in a type safe way.
 
Gerard Gauthier
Ranch Hand
Posts: 104
Java Linux Monad
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If I had a single Node with a value of 1234, its left and right Nodes would be terminated with the single object Empty.
 
Paul Clapham
Sheriff
Posts: 24374
55
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Gerard Gauthier wrote:

Paul Clapham wrote:And it looks like you don't have any use for the Empty class any more!



I don't see how you arrived at that conclusion... The Empty object is used to terminate Node objects in a type safe way.



I arrived at that conclusion because I didn't see any code which created Empty objects.
 
Gerard Gauthier
Ranch Hand
Posts: 104
Java Linux Monad
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Paul Clapham wrote:

I arrived at that conclusion because I didn't see any code which created Empty objects.



I guess I should've included the Btree class in the post.
 
Paul Clapham
Sheriff
Posts: 24374
55
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Gerard Gauthier wrote:I guess I should've included the Btree class in the post.



Yes, that would have helped. I looked up B-trees and it seems to me that you are designing a binary search tree. It wasn't obvious to me why any nodes in such a tree would be empty. Which is why I wasn't surprised that you didn't use the Empty class anywhere.

Edit: Never mind, I just scrolled back and read your explanation of that. Now I'm confused by the fact that your Node and Empty classes are immutable, but I expect the Btree class would explain that.
 
Gerard Gauthier
Ranch Hand
Posts: 104
Java Linux Monad
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Paul Clapham wrote:
.....Now I'm confused by the fact that your Node and Empty classes are immutable, but I expect the Btree class would explain that.



Not sure why an immutable tree would confuse you?
 
Marshal
Posts: 64166
215
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Gerard Gauthier wrote:. . . Not sure why an immutable tree would confuse you?

Please explain how you would populate your immutable tree.
 
Gerard Gauthier
Ranch Hand
Posts: 104
Java Linux Monad
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:

Gerard Gauthier wrote:. . . Not sure why an immutable tree would confuse you?

Please explain how you would populate your immutable tree.



Branch re-building.
 
Gerard Gauthier
Ranch Hand
Posts: 104
Java Linux Monad
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You'll note the add method builds a new branch when it adds a new value to the tree.

 
Campbell Ritchie
Marshal
Posts: 64166
215
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Got it
 
I yam what I yam and that's all that I yam - the great philosopher Popeye. Tiny ad:
Create Edit Print & Convert PDF Using Free API with Java
https://coderanch.com/wiki/703735/Create-Convert-PDF-Free-Spire
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!