How To Program A PM1 Quadtree

or How To Only Waste A Single Weekend On This Nasty Project

By Kevin Conroy
Back to the Main Page
Last updated September 15, 2004

Description

This short essay/page/rant describes the process that I, an average programmer, used to write a PM1 quadtree in two days and have it work on the second full compile. I am not attempting to teach the entire process of software engineering or object-oriented programming in a single HTML file; rather, I am attempting to briefly describe a process that worked for me at the time given my programming abilities. If I were to do it all over again, I would do things a little differently now that I understand myself as a programmer a little better. That's the point: knowing your own strengths and weaknesses and creating a process that supports and protects you from them, respectively. (For instance, all of my text editors need to have spell check... and even then I should check for errors.) I share my experiences with the PM1 quadtree in the hopes that it may help some of you.

Introduction

Like many of you, I've known the principles of object-oriented programming for several years. And I've known the importance of testing your programs ever since I started coding in QBasic when I was 10 or 12. I've written countless programs in an object-oriented fashion, including 7,000 lines of code during the summer of 2002 for a direct-mail response system. Despite my knowledge of OOP, it was not until the CMSC420 projects came along that I really tried to adhere to OOP. I stopped thinking in terms of "how can I get a program to get the output that I want right now?" and started thinking "Okay, what are the objects that really best represent the data we'll be dealing with." For the first time the underlying data structures and their methods of interaction received my focus rather than the output of the program. As a result, I was able to write classes that performed their task well and without many errors or bugs.

After my Part 1 project got a 60%, I started writing functions ("isValid()") for all of my major objects and a few minor ones that checked all of my assumptions (fill-factors, making sure child pointers had matching parent pointers, checking that nodes were maximal, verifying my math in partitioning, etc.). I wrote isValid() functions for each of my objects (leaf nodes, internal nodes, and the tree as a whole). I integrated this sanity check into my print function and then whenever I would get incorrect results, I would simply look for the failed assertions of my isValid functions to see where the problem occurred. If I had just launched a debugger and used print statements or watches/breakpoints I would have taken me DAYS to figure out that my B+ tree wasn't storing its parent pointers correct. But one little function which I had taken 10 minutes to code my assumptions into told me exactly when the error was occurring and I was able to fix it in under an hour.

NOTE: "isValid" is a term I coined for my code at the time I was taking CMSC420. Java has a full suite called JUnit which allows you to do unit testing. I strongly urge you to look into that rather than rolling your own error checking structure (although rolling your own may help you catch design flaws more quickly... depends on how you approach everything). My "isValid" function was really an integrated unit test.

My Experience with the PM1

When it came time for the PM1 quadtree, I spent a week or two doing nothing but design work and research. I read Hanan Samet's notes. I reviewed the class lecture notes. I looked for other tutorials on the web. I also drew out my objects over and over again, each time getting a better revision and figuring out what objects I needed to get the job done. Then, after about two weeks of NOT TOUCHING THE COMPUTER for my 420 project, I sat down and in a single programming marathon weekend (12 hours a day), I had a nearly working insert function. I took two days off to clear my head and then in one evening I completed PM1 insert and delete with support for intersecting lines/edges. What I found even more amazing what the fact that I only had syntax errors. Everything worked perfectly on the first try. It was amazing. It wasn't intelligence, Jolt cola (TM), or divine intervention that allowed me to get a PM1 quadtree to work on the first try - it was just lots and lots of time spent designing my objects, making sure it was as object oriented as possible, and adding isValid functions to check my assumptions/preconditions/postconditions that allowed me to get it to work.

Although I didn't actually need the isValid to find any errors in my code, it was a preventative measure. To write the isValid function I had to make sure that I was testing all of the right assumptions about the structure, and in doing so, I was able to mentally determine if my structure actually fulfilled those properties or not. There were several times while I was writing my isValid function that I realized my object design didn't handle something so I'd stop, redesign it, and continue. Along the way, I wrote a small test program to test each object (unit testing for those who are familiar with the concept) so as I finished each object, I compiled it along with the test harness and checked to make sure that it worked. Each test found a few minor errors which were easy to fix thanks to the many hours I had spent designing it. When I did a full compile of all of the pieces and parts of the PM1 quadtree, it worked on the second compile (first one found a syntax error).

That's never happened. Not for a program of that size. I've had "Hello World" programs that haven't worked on the first try. But I got a PM1 to work.

And in for those of you who don't know me, I'm a terrific programmer. I spend a huge amount of time trying to get my code to work. Well, I did, until I started practicing these basic design techniques that I'm describing here. Note: I'm not trying to brag - I'm just trying to make you realize that all of this stuff WORKS!

Sure, I thoroughly tested my PM1 after it compiled and I did find a couple of very minor problems for some of the boundary cases (extreme partitioning, crossing through the center, etc) but it only took about 10 seconds to fix each error since my objects were playing so well together. My code wasn't 100% perfect... but I wrote in such a way that made it easy to debug, fix, test, and retest.

That's not to say that the PM1 was easy to make... it took a lot of time and energy. The point is that if you spend a lot of time using all of those "silly" design techniques that "take too much time/energy" that you too can get a PM1 quadtree to work on your second full compile. (And yes, I compiled each individual class as I was working on it to check for syntax errors)

Why You Should Try OOP/Software Engineering Methods

In order to really do this project and still maintain your sanity, you need to adopt good programming techniques which will allow you to make fault tolerant (or at least, fault friendly) objects which can be modularly tested and implemented. This doesn't just apply to the PM1 quadtree - it applies to all of the programs that you write!

Also, it turns out that my experience with writing isValid first is actually the idea of Test Driven Development (by Kent Beck). The idea is to write your tests first and then your code. The benefits include that you know when your code works (because it will pass the tests), you can refactor your design before you even implement your code because you can see how easy it is to work with when writing your tests, and you have a good idea of the kinds of boundary conditions to check for because you wrote the tests before hand and were in a better mindset of thinking about odd cases. It's very interesting stuff and if you're interested in it you should read Beck's book on it.

I strongly encourage you all to grab a pad of paper, Samet's notes, and to walk away from this blasted machine for a few days and don't come back until you've got everything designed on paper. Know what your classes will be (including private data members and exactly what their types are), be able to describe your assumptions about these private members (i.e. all child pointers will either be all null or they will all point to a valid node), and know how all of these objects will be able to fit together logistically to create a working PM1 quadtree. You could take it even one step further and write out function prototypes.

Conclusion

It may seem like overkill, but it works. My PM1 quadtree is proof.

And regardless of what you may think, I believe each and everyone person in CMSC420 has the intellectual capabilities to get a PM1 quadtree to work without too much pain. It's really a question of being able to stay away from the computer long enough and being willing to design and redesign until you get something that works.

And remember talk to each other. You can share and trade pictures (PICTURES!!!) as much as you want. You can even trade the names of your classes (just don't write code together).

Sadly, only a few of you will listen to me, but that's okay - it's your grade, not mine ;-)

By Kevin Conroy
Back to the Main Page
Last updated September 15, 2004