ANN: SPARK: A red-black tree with correctness proofs

[Phil Thornley <phil.jpthornley@gmail.com>]

A SPARK package implementing a red-black tree is now available and 
correctness proofs have been completed for the code. (SPARK correctness 
is, of course, partial correctness as there are no proofs of termination 
of the operations.)

The archive can be downloaded from the Data Structures page at:
http://www.sparksure.com/

The readme for the release is:
http://www.sparksure.com/resources/rb_tree_V0_1_ReadMe.txt

In this version the Ada code is complete and all the mandatory SPARK 
annotations for information flow analysis are included, but the optional 
proof annotations within the operations in the package body have been 
excluded. (I have completed these, but they are not yet in a publishable 
form.)

The tree elements store a single integer value. A skelton implementation 
of an Ordered_Set package is included to show how the tree package can 
be used to create ordered containers for arbitrary element types. The 
only additional requirement is for a Key function for the element type, 
returning an integer value, where equivalent elements are defined as 
those that have the same value for Key.

If you find this code useful then please let me know (there is an email 
address with the material in the archive). In particular I am keen to 
know whether anyone would like to have the annotations and rules that 
complete the correctness proofs.


Cheers,

Phil Thornley