[ Home Page ] [ Eiffel Archive ] [ Eiffel Classes and Clusters ]

Kedsal

Written by Jeffrey H. Kingston

• 8 May 1996.

kedsal_1_0.zip (150,033 bytes)

Kingston's Eiffel Data Structures and Algorithms Library v1.0

KEDSAL is a library of data structures and algorithms written in Eiffel and available free under the GNU Public License. The library contains multiple implementations of many common abstract data types, plus sorting algorithms and graph algorithms (see the end of this blurb for the complete list).

Some features:

• KEDSAL is very cleanly organized. It is based on a two-level inheritance structure. At the top level are the abstract specifications in the form of deferred classes; at the lower level are multiple implementations of each abstract specification.
• KEDSAL is engineered for correctness. Every abstract specification contains a complete executable precondition and postcondition for every operation. Every implementation contains a complete executable class invariant. Every implementation that uses arrays resizes them as needed, so there are no "data structure full" errors.
• KEDSAL is optimized for time and space efficiency, both by employing the most efficient methods and by containing carefully tuned code. Precondition, postcondition, and invariant checks must be disabled if efficiency is required.
• Although KEDSAL is not on the scale of, say, LEDA, it does contain some data structures that might be difficult to find in Eiffel elsewhere, e.g. splay trees, Fibonacci heaps. Furthermore the structure makes it easy to add other implementations.
• KEDSAL maximizes code re-use within itself. For example, LIST is used within FOREST, which is used within PRIQUEUE_FIBHEAP, etc. All the algorithms use the ADTs as appropriate.
• KEDSAL comes with a simple testing scaffold. Every data structure and algorithm can be tested interactively (although not graphically) using code that comes with KEDSAL and explains itself to the user when it is run; the testing code permits you to view clearly the current value, concrete and abstract, at any time.
• KEDSAL has been compiled and tested under ISE Eiffel 3. Ports to other implementations of Eiffel should be trivial; the author is willing to assist with any problems.

The complete list of ADTs and their implementations in this version is:

BINTREE_ADT     BINTREE_LINKED BINTREE_EXTENDED_ADT     BINTREE_EXTENDED_LINKED     BINTREE_EXTENDED_COUNTED DIGRAPH_ADT     DIGRAPH_LISTS DISJSETS_ADT     DISJSETS_LINKED FOREST_ADT     FOREST_LINKED LIST_ADT     LIST_DLL LIST_INDEXED_ADT     LIST_INDEXED_SPLAY PRIQUEUE_ADT     PRIQUEUE_SLL     PRIQUEUE_BST     PRIQUEUE_ARRAY     PRIQUEUE_HEAP PRIQUEUE_EXTENDED_ADT     PRIQUEUE_EXTENDED_SLL     PRIQUEUE_EXTENDED_HEAP     PRIQUEUE_EXTENDED_FIBHEAP     PRIQUEUE_EXTENDED_BST     PRIQUEUE_EXTENDED_ARRAY

QUEUE_ADT     QUEUE_SLL     QUEUE_ARRAY SIMPLESET_ADT     SIMPLESET_SLL     SIMPLESET_ARRAY STACK_ADT     STACK_SLL     STACK_ARRAY SORT_ADT     SORT_SELECTION_RECURSIVE     SORT_SELECTION_ARRAY     SORT_SELECTION_ABSTRACT     SORT_RADIXSORT_QUEUE     SORT_QUICKSORT_QUEUE     SORT_QUICKSORT_ARRAY     SORT_MERGESORT_QUEUE     SORT_INSERTION_BINARY     SORT_INSERTION_ARRAY     SORT_INSERTION_ABSTRACT     SORT_HEAPSORT     SORT_BUBBLE SYMTAB_ADT     SYMTAB_HASHCHAINS SYMTAB_ORDERED_ADT     SYMTAB_ORDERED_BST

KEDSAL was designed and implemented by Jeffrey H. Kingston (jeff@cs.su.edu.au) of the Basser Department of Computer Science at the University of Sydney.

[ Home Page ] [ Eiffel Archive ] [ Eiffel Classes and Clusters ]