Internet Browser - Practices

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.

 
Fig 11. An example of a Web page with three frames

Frames can be nested, which results in pretty complex shapes. We can end up with something that looks like this (or even more complex):

 
Fig 12. More complex frames

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:

 
Fig 13a. This easy one…

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.

Of course, the horizontal example below:

 
Fig 14a. The horizontal case…

will also be represented by a single node like this:

Fig 14b. …is no different

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!

 
But it can easily be represented like this…

 Fig 15b. The above example represented using a tree

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, the beauty of binary trees become apparent. It doesn't matter how many frames, or how complex they are, they can always be represented using just a single binary tree. If a page has only two frames, it is the same as having 20 levels of nested frames. It can always be represented as a single binary tree, without any additional complexities.

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?
For the purpose of this article, we are going to pick the problem that illustrates the work of trees best. Namely, given a click, determine which frame the click fell into.

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.

Next, at this point, we move to the node  "V", 0.3 (the right child). We know the point must be at either frame C, D or E (we eliminated "A" and "B" after 1 comparison).

Third, we compare at the new node, and because this is a vertical split, we compare the x of the point we have (which is 0.8), to the point of the split (which is 0.3). Now we know we have to move to the right, because 0.8 is larger than 0.3. We know we are in a frame that is to the right.

So, we move to the third node "H", 0.8. Because this is a horizontal split, we compare the y value of the point (0.7) to the y value of the split (0.8), and we know we have to move up (take the left child), and we end up at the D frame, which is correct.

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. 

class frameNode
{
 boolean isHorizontal;
 float ratio;
 frameNode Left;
 frameNode Right;
 
}

class FrameSet
{
 frameNode FrameTree;
 void findFrame(float x,float y)
 {
  frameNode frame=FrameTree;
  frameNode prev=null;
  while(frame!=null)
  {
   prev=frame;
   if(frame.isHorizontal)
   {
    if(frame.ratio<y)
     frame= frame.Left;
    else
     frame = frame.Right;
   }
   else
   {
    if(frame.ratio<x)
     frame = frame.Left;
    else
     frame = frame.Right;
   }
  }
  //here, prev is the node splitting the last frame to 2.
  //One of them is the frame we want.  
 }
}

The code simply checks every node to see if it is horizontal or vertical, and decides whether to check the x or y cords of the click point. Note, by the way, that we didn't actually use the information we obtained. We just found the frame we wanted, and then did nothing. This is, of course, because it is just an example. If this was a real life application, some modifications would have to be made. For instance, we could put in an extra level of nodes to contain real information about the frame.

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. 

>>> More Practices Articles          >>> More By Mohamed Saad

blog comments powered by Disqus