artree
Array Tree
The code
artree.tar.gz which consists mainly out of
the artree header file
and the artree implementation
Purpose
The main purpose of this library is to create a general purpose container
that is a suitable replacement for vectors, queues, sets and other
containers implemented in the STL. Because it's implemented as a balanced
tree, inserting, deleting or finding an element only takes O(log N) time.
And it's much more useful because it can be accessed like a vector.
The second purpose is to demonstrate how programs and libraries can
interface without using callbacks. Callbacks make programs much more
difficult to write because program writers must move local variables into
structures (objects), or even worse, make them global. It also makes
programs more difficult to read, because of the non linear program
flow.
Imagine that you need to list points according to their distance from a
central location (x,y). If you want to use 'qsort' you would either have to
make x and y global variables or create a new vector with the distance to the
central location as an additional entry. With the STL you can pass x and y
in the compare object, but you still need to write a callback
function.
With artree, all comparing takes place as part of the caller's code, so x
and y are available. The library achieves this by returning to the caller
every time another comparison needs to be made and a while loop in the
caller's function makes sure the compare function is called the correct
number of times. For more details, look at the .h file.
A callbackless GUI toolkit
A larger challenge will be to make a graphical user interface toolkit
(library) that is callbackless. Similar to artree, the trick will be that the
toolkit return to the caller whenever a user event arrives that it cannot or
should not handle. The big difference will be that the application program
will have many threads (e.g. one per window), all polling the toolkit. When
an event arrives, the toolkit will return to the thread that is capable
of handling that event.
So you may have one thread that sequentially calls a toolkit function to pop
up dialog boxes with multiple choice questions to the user. The function
returns a simple code to indicate which choice was made. In between expose
(invalidate) events may arrive for a customized widget. In that case the
library returns to the thread that is capable of redrawing that widget, and
that thread is executed until it waits for another event.
To reduces (eliminate) the need for semaphores (mutexes), all the threads
should be mutually exclusive. This means another thread may only be resumed
when all exsisting threads are waiting for toolkit events. In fact the
threading needs no help from the operating system and can be implemented
with multiple stacks and long jumps.
Copyright
Public domain. Just like libbitap.