Consider this scenario. You are fed up with Internet Explorer. You don't love Opera, and you are not even very happy with Mozilla (you must be really hard to please, eh?). So, you decided to take the brave step of building your own Web browser...and you immediately faced a problem with frames.
The user clicks on the window of your browser. Your browser needs to know which frame this click fell into, so that it could be delegated to the proper frame. This is the problem we will be handling now.
To repeat the problem a bit more formally: given a location on the window (X,Y), we need to know to which frame this click belongs. Pretty simple, right? First, let me give you a quick overview on frames, in case you haven't met them before.
Frames are used to display multiple views in an HTML document. You can split the document horizontally or vertically, and in each pane you can display a different HTML document. Look at the page below for an example.
Frames can be nested, which results in pretty complex shapes. We can end up with something that looks like this (or even more complex):
Now, again, our problem is, given an HTML document and a mouse location, we need to know to which frame any particular click belongs.
Before solving this problem, we have to stop and ask ourselves an important question. Specifically, how are we going to represent the frames in our program? What kind of data will be needed to hold the information about the frames? Believe it or not, it looks like trees are going to be an ideal choice for this task. Every node in the tree will represent one division (horizontal or vertical). We can imagine that every node in the tree splits one frame into two frames.
If it is still notl very clear, let's support it with some examples. For example, a frameset like this:
can be represented by a single node like this:
Fig 13b. ...will end up as a single node like this
The letter describes the type of division (horizontal, vertical). The ratio is the ratio of total length at which the division occurs.
will also be represented by a single node like this:
Note that every node holds the type of division (horizontal or vertical), as well as the ratio at which the division occurs. The left child points to the frame that comes first (if it is a horizontal frame, the left child points to the frame on top, if it is a vertical frame, the left child points to the frame to the left). To avoid marrying ourselves to a certain resolution of window size, we are using normalized coordinates. This means that the divisions are all ratios of the whole width. For example "H", 0.3. means a horizontal division at 0.3 of the height.
Here's a more complex example:
Fig 15a. Web designers can sometimes be overly creative!
The letter names at the end of the tree are just there for the purpose of illustration. I hope they help clarify the idea behind using the tree. The very first node ("H", 0.2) represents the very first horizontal frame. The window is split into "A", "B" at a side, and the rest of the frames are on the other side.
Now, a whole lot of problems arise. How can we parse the frameset tags to construct the tree? How can we delegate the clicks to the appropriate frames? What happens when the user resizes the window?
So, how do we solve this problem? This will sound very similar to our dictionary example. We start at the root, and see which side to move to, depending on the click location. With every new level we do the same thing until we reach a node that has no children (leaf node), and we can determine which frame to go to.
Let's take a look at the frames in our previous example, figure 15 above. Now, assume the user clicked at point (0.8, 0.7). Remember, to avoid problems with screen size, we assume all numbers are ratios of window width and height. So, (0.8,0.7) means the user clicked at a point that is 0.8 from the window width, and 0.7 from the window height.
First, starting at the root, we find that the point 0.8, 0.7 must lie near the bottom. This is because the first frame dictates that the screen is split horizontally at 0.4. Which means the y coordinate of the point 0.7 must be at the bottom.
I hope this makes sense. Try to trace for yourself what happens if the user clicks at point (0.9, 0.1). Can you get it? Did you end up at frame "B"? Great, let's move on…
Now comes the good part, how do we write the code for this? Believe it or not, it is extremely easy. Take a look.
And that was it, our second example with trees. I hope you didn't find it too complex.
You have now seen two applications for trees. I sincerely hope I have succeeded in arousing your interest in using trees.
blog comments powered by Disqus