Maintainer
Jeffrey Kingston
Description
Kingston's Eiffel Data Structures and Algorithms Library contains multiple implementations of many common abstract data types, plus sorting algorithms and graph algorithms.
Categories
Versions
Links
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.
Supported compilers
Licensing
