In this new post, I’ll be describing the process of implementing an OO library in the H++ language; first, I’ll detail the classes that interact in the problem of sorting. The subject will be : sorting automobiles by year and cost, with priority in cost in Ascending mode. The Sorting algorithms can be implemented in Descending mode, by just changing the implementation for the ProxyObject::Compare member function.
The SorterEx class
This new abstract class, is the base class for all the OO Sorting algorithms that will be presented here in this post.
As you noted, this class rely on a new abstract type called Array; this class only implements the Swap member, and the behavior can be changed in new concrete sorting classes.
The H++ Array base class
Here is the definition of the base class Array:
This class contains a pointer member to the ProxyObject type; the idea is to create an dynamically allocated array of objects, and have an internal pointer refer to the address of the first object in memory.
The properties are :
- length, a read only property to let to users to know the items count in the array.
- item_size, this can be used to know the size of each object contained in the array.
The other member functions are self descriptive, and will be implemented in a concrete class called ArrayOfAutomobile in the same H++ unit.
Now, let’s set our attention to the Automobile class, the real top character in this post, the Automobile class:
This class has the following properties:
- Model, to represent the name of the brand of the vehicule.
- Cost, to represent the price to acquire on auto of this model (these data are demo, and does not reflect the actual prices of these brands mentioned in this post).
- Year, this is the year of emition of the vehicule.
Also, includes a default constructor, required by the new operator when it’s creating a new instance of this type of objects in the heap.
The most important member is Compare, which is virtual, and is overriden here to show a specific behavior (Polymorphism).
Finally, a destructor to show when the object is being destroyed.
The Array concrete class
Next, is the concrete array class, ArrayofAutomobile, created to hold and manage the array of Autombile objects:
This class possesses a constructor which expects the number of items to construct in itself. Here you can also see the getAt member, which returns an instance of ProxyObject as an upcast, from the array of automobiles. As you can see, all it takes to create an array of any object, that can be sorted with the H++ OO Sorting classes, is just to inherit from Array class, and implement the virtual abstract members.
Now, let’s take a look at the sorting algorithms.
Simple Sorting Algorithms
Here is the implementation of the Insertion Sort algorithm:
In languages like C++ or C#, you can overload the operators [], >, <, ==, and also !=; but in H++, you can’t, obviously, because I have not implemented that language facility yet; that will be part of version 2.0 of the H++ Compiler, I promise that; because I know the importance of having overloaded these operators I mention here.
For now, we have the Array::getAt() member, to access the objects in the internal array, and the ProxyObject::Compare(), to compare against other objects.
The ProxyObject::Compare(), return the following int values, based on the results of the tests that perform this virtual function:
- -1, when the current object is less than the object compared with
- 1, when the current object is greater than the object compared with
- 0, when both objects are equals
When I implemented these sorting classes I show here, I had a conflict with the class names, because besides they belong to different namespaces, they cannot live in the same place when they are instanced in the program; so the H++ Compiler reacted yelling the following ambiguity errors:
>TestSorting.hpp:
TestSorting.hpp{153} : error: Identifier is ambiguous in the current scope ; which do you want to use: ‘Algorithms::Sorting::InsertionSort’ or ‘Algorithms::Sorting::Proxy::InsertionSort’ ?
TestSorting.hpp{154} : error: Incompatible types : cannot convert from ‘Algorithms::Sorting::Proxy::InsertionSort’ to ‘Algorithms::Sorting::Sorter’ for parameter: sorter
TestSorting.hpp{183} : error: Identifier is ambiguous in the current scope ; which do you want to use: ‘Algorithms::Sorting::BinaryInsertionSort’ or ‘Algorithms::Sorting::Proxy::BinaryInsertionSort’ ?
TestSorting.hpp{184} : error: Incompatible types : cannot convert from ‘Algorithms::Sorting::Proxy::BinaryInsertionSort’ to ‘Algorithms::Sorting::Sorter’ for parameter: sorter
TestSorting.hpp{191} : error: Identifier is ambiguous in the current scope ; which do you want to use: ‘Algorithms::Sorting::InsertionSort’ or ‘Algorithms::Sorting::Proxy::InsertionSort’ ?
TestSorting.hpp{209} : error: Identifier is ambiguous in the current scope ; which do you want to use: ‘Algorithms::Sorting::BinaryInsertionSort’ or ‘Algorithms::Sorting::Proxy::BinaryInsertionSort’ ?
729 source lines.
x syntax errors.
Here is the compiler errors live:
This is something similar that happens with the C++ compiler; the problem came to light because I included both namespaces to the same unit; like this:
To solve the problem, I just changed the OO classes ‘ names, so that no collision would occur; another way to solve the problem, is to explicitly specify the namespace Proxy prefixed to the OO sorting classes like:
Proxy::InsertionSort sorter;
TestSortingEx(sorter, “\nTesting INSERTION SORT Algorithm: O(n^2) – faster”);
Another error you can receive when compiling would be from trying to pass as a parameter, an Array’s concrete object, to one of the previous algorithms from the Part I of this post; here is what you get:
>TestSorting.hpp:
importing: algorithms.sorting.hpp
c:\testsource\algorithms.sorting.hpp{597} : error: Incompatible types : cannot convert from ‘Algorithms::Sorting::Proxy::Array’ to ‘double[]’ for parameter: array
c:\testsource\algorithms.sorting.hpp{597} : error: Wrong number of arguments
c:\testsource\algorithms.sorting.hpp{597} : error: Function does not take 1 parameters. Unknown function signature.
729 source lines.
x syntax errors.
![Array and double[] are incompatibles](https://hplusplus.wordpress.com/wp-content/uploads/2009/03/incompatible-types.png?w=700 "Array and double[] are incompatibles")
The Bubble Sort Algorithm
The Selection Sort Algorithm
Advanced Sorting Algorithms in H++
The next algorithm, is the Binary Insertion sort, now acting on ProxyObjects subclass’s instances:
You can note, that most of the implementations require that before doing anything, that the _array member be assigned before doing anything; this is needed because the SorterEx::Swap member function rely on this field to have access to the array object.
The Heap Sort Algorithm
This algorithm is pretty similar to the version over an array of scalar types:
The final part in implementation of the Heap Sort is this below:
The H++ implementation of the QuickSort Algorithm
The Quick Sort algorithm is one of the most popular sorting algorithms, and because of that, it has multiple different implementations; the one that we are using now, is the called Median of Three Quick Sort, and you can find it in the Bruno Preiss book of Data Structures and Algorithms with C++:
I chose this implementation because is beautyful and very powerful; you can note, that this class is also abstract; you may wonder how can this class be instantiated then? The problem is that this class is abstract, and requires a concrete class to finish the implementation of the QuickSortEx::selectPivot() abstract member function, like in the class below:
Now, the QuickSort algorithm is fully implemented thanks to the concrete class above; another QuickSort implementations can be found on the internet, and implemented in H++ the same way as you can see here.
The most difficult to implement in H++: the Merge Sort
As the subject suggest, this algorithm is very complex to implement; but that does not means that cannot be implemented in H++:
The problem with this implementation, is noted in the next image:
Because this algorithm requires to have a temp array to hold the sorted list, the problem arrives in that H++ at that moment did not supported the H++ pointer_cast operator, so that you can call the malloc function alias to allocate memory from the heap, and make the algorithm completely generic; that will be solved in the next build of H++.
The CopyTo and CopyFrom members, for the Array concrete classes, should look something like this for the ArrayOfAutomobile class:
These members are required to make the Merge Sort implementation possible in H++.
The H++ Test Program
Here is how the new implementation would look:
This fragment shows how the array of objects are iterated in the two loops: Before Sorting, and After Sorting.
As you can see, the new algorithm classes are named with the postfix Ex, to avoid the name collisions between the two imported namespaces in this test program. Here is the new implementation of the Program::main() static member function:
The Compilation of TestSorting.hpp source
The runs of each H++ Unit Testing
As you can see, the autos are sorted by year, but with the priority by Cost, as you can see from the rectangle above, that highlights the Costs before and after sorting.
As you also have noted, the objects are destroyed every time the function goes out of scope, but this time because of the H++ destroy operator.
What’s Next?
In the next post, I’ll be presenting part of the Intel x86 32-bits Assembly generated by the H++ Compiler, for the TestSorting.hpp and Algorithms.Sorting.hpp files.
See you all in the next post!
The H++ Programming Language 