Win a copy of Murach's Python Programming this week in the Jython/Python forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Not sure how to use generics  RSS feed

 
Michael Quatrani
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is a stupid question but I am trying to start working with binary search trees and was hoping someone could point me in the write direction. I guess I don't have a good handle on generics. What is the syntax to declare and instantiate an object from this class?

 
Ulf Dittmer
Rancher
Posts: 42970
73
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Should be something like this:

Using nulls instead of valid objects, because in order to instantiate a BTNode object you have to have two BTNode objects. So either "null" is an OK value, or there must be some other way to obtain non-null BTNode objects than this constructor.
 
Campbell Ritchie
Sheriff
Posts: 53742
127
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Alternative:-
You would have methods which replace the nulls at left and right whenever real values become available.
 
Rob Spoor
Sheriff
Posts: 20893
81
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ulf Dittmer wrote:Should be something like this:

With Java 7 and beyond you can make it even shorter:
 
Michael Quatrani
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Still not sure what FooBar really is.. My understanding of generics (like I said I need to read more) is that I need to replace whats in <> with my data type i.e. <String>, <Integer> etc. So I'm really still not sure about the syntax


What is FooBar supposed to be, a data type? Additionally, when you pass a parameter FooBar() what is that, is it an object? Do I have to declare objects elsewhere and pass them in? I am posting my entire class for clarity. I suspect I may have to use an data structure, be it an array, linked list, Queue, Stack etc to use with the binary tree class. Obviously, I'm not sure what i'm doing, but, I would at least like to start running the class with some examples so I can start to understand it better. My book doesn't specify any client code only implementation of the Binary Tree Class. Here is all of the code.

 
Paul Clapham
Sheriff
Posts: 22185
38
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Michael Quatrani wrote:What is FooBar supposed to be, a data type?

Yes.
Additionally, when you pass a parameter FooBar() what is that, is it an object?

Yes. The "new" operator creates an object in Java.
Do I have to declare objects elsewhere and pass them in?

Yes.

With respect to your code (which I just looked at the opening comments of) -- if you're going to declare BTNode<E> as a class, that means you're declaring a node which contains an object of type E. The node doesn't know what E is and it doesn't care what E is, because it isn't responsible for creating E objects, only for containing them. Somebody else will create them.
 
Rico Felix
Ranch Hand
Posts: 411
5
IntelliJ IDE Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In order to weave the concept of generics into your neocortex, you must first fully comprehend the notion of a concrete type...

Before I try to illuminate the concept to you, I would like for you to hold unto the following statement in short term memory:
Generics is about making specifications to satisfy a requirement that are independent to something specific in mind at present (My personal definition)

When you think about creating a class that can store attributes and behaviours you first think of it at a specific level as illustrated in the following snippet:


For this type of class (Myself) its only reasonable to store its attributes which specific types in mind...

As for the type of class such that it will be used to store a collection of something its better to store its elements without a specific type in mind...

Why you may ask, lets conclude...

Class types that store a collection of something can be thought of as GladĀ® Food Storage Containers... When you purchase such containers you wont buy them thinking I will use this one only for carrots and this other for tomatoes...

No.. you purchase them thinking along the lines as being able to store anything that can fit appropriately into it over the lifetime of the product... Such is the case in the software world also...

If you think along the lines as purchasing containers to store only specific things then you end like the following snippets:




Inspecting these classes we realize that, hey all I am trying to do is store something in a container so why not make one that can store anything I desire...

Thinking along this line we end up with the following:


Things is a stand in for anything that can be stored in the container at any given time...

So to use it we state what we want to store in the container when we are about to use it as follows:


And that my friend is the idea behind the notion of generics...
 
Michael Quatrani
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for the analogies and the code. I do understand that in concept, why rewrite your code for every type when you can make it generic. Voila, less work but then you must be cautious about type errors. What I'm really having trouble wrapping my head around is how to implement a data structure over a binary search tree (isn't a binary search tree a structure in and of itself like a linked list etc.??). I have found other examples and am working my way through but it is confusing at the moment.

I feel like I need to take a separate Queue class (bear in mind i'm not using the api for this stuff) or a Node class from a linked list, or even a simple array and use that to store some data (say some ints for simplicity) Then, I have to pass those objects into my BTNode class and then I can generate a tree and work from there. I am just not sure how everything interacts with each other. And, I am having a really hard time visualizing what is going on.

For example take this code



I don't get any errors here... but this is obviously incorrect. I don't understand what the starting point is for initializing the tree. Or, is the idea that I have an unsorted array or something and then I can put those values in a tree and they will populate the tree according to the rules for a binary search tree. In other words it determines where things belong so that we can search (more quickly) according to the rules of the tree later.

I realize I am all over the place here, but, I would really like to start experimenting with the code to get a grasp of how it is supposed to work. That is kinda hack-y, but, reading doesn't do me much good.. playing with code and then trying to write it from memory is really what solidifies my understanding of these concepts.
 
Rico Felix
Ranch Hand
Posts: 411
5
IntelliJ IDE Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So its the data structure in particular and not generics you are having problems comprehending... I see

A binary search tree is simply a tree turned upside down that's used for fast look-up... And yes its a self referential type

If you go outside and observe a physical tree carefully you would realize that's what you are trying to implement virtually in software...

A tree starts at the root and when it reaches at joint, it spans out in different directions creating alternative paths... Think of it as if you were an ant or some small creature trying to go up a tree to get to something... You have to start at the root and when you reach a joint decide which of the alternative paths to choice from to get to your destination...

The only difference with the real tree and the virtual tree is that the virtual tree is refined in the case of a binary tree to split into only two alternative parts when you reach a joint...

The specification for a binary search tree states that you insert an element at the root... lets use the number 7

When you want to insert another value into the tree (the tree grows) you make considerations... If the current value you would like to insert is greater than the value at the joint you insert the element to the right (a branch shoots out from the joint heading to the right), if its a lesser value then you insert it to the left (a branch shoots out from the joint heading to the left)...

So it goes as follows:
7 <- root
Would like to insert 9 which is greater than 7 so insert it into the right branch
Would like to insert 4 which is less than 7 so insert it into the left branch
Would like to insert 15 which is greater than 7 so go up the right branch which we find a 9 which is less than 15 so insert 15 into a new branch on the right

Follow this logic until you end up with a tree full of branches...

The branches containing 4 and 15 would be considered as a leaves since it does not go on any further... Just like a real tree where a leaf does not have any further extensions...
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!