Data Structures.
It seems as though I'm destined to work on these forever just because I've changed my design for them so many times, but I think I've finally hit on an architecture that pays off dividends. So, how have I designed them this time around? Let me explain with pictures!
So here's my original data structure design for a LinkedList. It's pretty simple, but that's what I miss about it. I really like the idea of manipulating objects by an explicitly declared interface, and this takes that interface to two different levels: IContainer and IList. I specifically split my interfaces this way because it allows me to share test cases across my data structures. I can talk about that another time, but my test framework works on interfaces, so I can use one set of IContainer test cases on my LinkedList, ArrayList, BinarySearchTree, and anything else that implements the IContainer interface. It's pretty cool and it's saved me a lot of time. Anyways, this was the original design. However, the more I worked with LinkedList and ArrayList, I realized that they shared a bit of code, especially things like checking bounds on the list. So, I decided that they should both inherit from an abstract base class that would implement that functionality and they could use the inherited version.
Tada! ListBase (and several other DataStructureType-Base classes) were born. It was right about this time that I read Effective C++ by Scott Meyers, which I highly recommend to any serious C++ developer. It definitely gave me a more in-depth knowledge of C++. One thing that it also introduced me to was the idea that a class's public interface should be non-overridable by its subclasses and that the functions that a class would override would be protected. I quickly implemented that because I saw the value in pushing error checking higher up the inheritance tree. I don't have it drawn, but a ContainerBase was born out of this design, and it quickly had its own error checking functionality so that by the time a function got down to LinkedList or ArrayList I knew that I had a valid state. It was pretty nice. It led me to discover the dreaded inheritance diamond that gave life to virtual inheritance in C++, but I feel as though I understand that topic now, and I'm once again a happy camper. Then, I began to have some more issues.
I try to test my code with my testing framework that I talked about earlier as much as I can. One caveat with my testing strategies is that I loathe friend classes. I think they're pretty much the devil of computer programming, at least in C++. I don't know if it's my engineering background, but I don't like exceptions to rules, and a friend class is just that: an exception. However, sometimes when you're testing, you really would like to test the internals of a class to make sure that they are working properly. What is a developer to do? One option is to reveal those internals as public functions so that the test code can access and test them, but doesn't that kind of defeat the purpose of making them "internal functions"? I don't want to reveal them on purpose! What's a programmer to do? Enter my latest design strategy:
I call it the crazy-big-and-complicated-architecture-that-is-so-very-nice-but-takes-forever-to-implement data structure pattern! As you can see, the number of classes that I had at the beginning has doubled to get to this structure, but now I can reveal the ArrayList classes to the programmer who will use QubLib and then I can reveal ArrayListImpl to my test cases. ArrayList essentialy defers to ArrayListImpl for everything and it maintains a clean API for a developer to work with. I actually also ended up creating a ContainerBase that functions like ListBase, except on the IContainer level. It's complex, but I think it's worth it. This design also lets me add another class that I cleverly call "List" on the same level as ArrayList and LinkedList. Its sole job is to defer to the fastest default IList data structure in my library. That means that I can swap implementations under the hood, and no one will have to change their code. They'll see an improvement in their library performance just because I changed the backend. I love programming. I was once told that every computer science problem can be solved by just adding another layer of indirection, and boy does that seem to be the case here.
Anyways, that's what I've been working on now. I'm planning on taking this architecture to my smart pointers next and getting a really clean interface there too, and then onto my strings. Lots of work, but I think it'll really pay off once I get this project moving more.
That's all for today. I'll be back next week (hopefully). Keep coding!
No comments:
Post a Comment