Container Data Types

Container data types are data types which are used to hold and organize other data. Since lisp is a dynamically typed language, any container data type can hold any other data type or a mix of other data types. This is contrary to the case for C or C++ where all data in a typical container must be of the same type.

As a convention do all names of the functions handling a certain container data type begin in <type>-, i.e. the functions implementing the container data type foo all start with foo-.

• Stack: The Stack data type.
• Queue: The Queue data type.
• Doubly Linked List: The Doubly Linked List Data Type.
• Binary tree: An ordinary binary tree.
• AVL tree: A balanced binary tree (AVL tree).

The Stack Data Type

The stack data type provides a simple LIFO stack. There are two implementations of a stack in Elib, one using macros and one using functions. The names of the functions/macros in the two implementations are the same, but the efficiency of using one or the other vary greatly under different circumstances.

The implementation using macros should be used when you want to byte-compile your own elisp program. This will be most efficient since byte-compiling an elisp function using macros has the same effect as using inline code in C.

To use the stack data type, put the line

(require 'stack-f)

in your own elisp source file if you want to use the implementation using functions or

(require 'stack-m)

if you want to use the implementation using macros. This is the only difference between them, so it is easy to switch between them during debugging.

The following functions are provided by the stack:

(stack-create)

Create a new empty stack.

(stack-p stack)

Return t if stack is a stack, otherwise return nil.

(stack-push stack element)

Push element onto stack.

(stack-pop stack)

Remove the topmost element from stack and return it. If stack is empty, return nil.

(stack-empty stack)

Return t if stack is empty, otherwise return nil.

(stack-top stack)

Return the top element of stack, but don't remove it from the stack. Return nil if stack is empty.

(stack-nth stack n)

Return the nth element of stack where the top stack element has number 0. If stack is not that long, return nil. The element is not removed from the stack.

(stack-all stack)

Return a list of all entries in stack with the topmost element first.

(stack-copy stack)

Return a copy of stack. All entries in stack are also copied.

(stack-length stack)

Return the number of elements in stack.

(stack-clear stack)

Remove all elements from stack.

The Queue Data Type

The queue data type provides a simple FIFO queue. There are two implementations of a queue in Elib, one using macros and one using functions. The names of the functions/macros in the two implementations are the same, but the efficiency of using one or the other vary greatly under different circumstances.

The implementation using macros should be used when you want to byte-compile your own elisp program. This will be most efficient since byte-compiling an elisp function using macros has the same effect as using inline code in C.

To use the queue data type, put the line

(require 'queue-f)

in your own elisp source file if you want to use the implementation using functions or

(require 'queue-m)

if you want to use the implementation using macros. This is the only difference between them, so it is easy to switch between them during debugging.

Not all functions in `queue-m.el' are implemented as macros, only the short ones. This does not make it less recommendable to use the macro version in your compiled code.

The following functions are provided by the queue:

(queue-create)

Create a new empty queue.

(queue-p queue)

Return t if queue is a queue, otherwise return nil.

(queue-enqueue queue element)

Enter element last into queue.

(queue-dequeue queue)

Remove the first element from queue and return it.

(queue-empty queue)

Return t if queue is empty, otherwise return nil.

(queue-first queue)

Return the first element of queue or nil if it is empty. The element is not removed from the queue.

(queue-nth queue n)

Return the nth element of queue, where the first element of queue has number 0. If the length of queue is less than n, return nil. The element is not removed from the queue.

(queue-last queue)

Return the last element of queue or nil if it is empty. The element is not removed from the queue.

(queue-all queue)

Return a list of all elements in queue. Return nil if queue is empty. The oldest element in the queue is the first in the list.

(queue-copy queue)

Return a copy of queue. All entries in queue are also copied.

(queue-length queue)

Return the number of elements in queue.

(queue-clear queue)

Remove all elements from queue.

The Doubly Linked List Data Type

The doubly linked list is an efficient data structure if you need to traverse the elements on the list in two directions, and maybe insert new elements in the middle of the list. You can efficiently delete any element, and insert new elements, anywhere on the list.

A doubly linked list (dll for short) consists of a number of nodes, each containing exactly one element. Some of the functions operate directly on the elements, while some manipulate nodes. For instance, all of the functions that let you step forward and backwards in the list handle nodes. Use the function dll-element to extract the element of a node.

To use the doubly linked list provided by Elib you must put the line

(require 'dll)

in your elisp source file.

• Creating a dll: Creating a Doubly Linked List
• Entering elements: Entering elements in a dll
• Accessing elements: Accessing elements of a dll
• Removing nodes: Removing nodes from a dll
• Predicates: Predicates on a dll
• Maps and Filters: Maps and Filters on a dll
• Misc dll operations: Miscellaneous dll operations
• Debugging dll applications: Debugging dll applications

Creating a Doubly Linked List

(dll-create)

Create an empty doubly linked list.

(dll-create-from-list list)

Given the ordinary lisp list list, create a doubly linked list with the same elements.

(dll-copy dll &optional element-copy-fnc)

Return a copy of the doubly linked list dll. If optional second argument element-copy-fnc is non-nil it should be a function that takes one argument, an element, and returns a copy of it. If element-copy-fnc is not given the elements themselves are not copied.

Entering elements in a dll

(dll-enter-first dll element)

Add an element first on a doubly linked list.

(dll-enter-last dll element)

Add an element last on a doubly linked list.

(dll-enter-after dll node element)

In the doubly linked list dll, insert a node containing element after node.

(dll-enter-before dll node element)

In the doubly linked list dll, insert a node containing element before node.

Accessing elements of a dll

(dll-element dll node)

Get the element of a node in a doubly linked list dll.

(dll-first dll)

Return the first element on the doubly linked list dll. Return nil if the list is empty. The element is not removed.

(dll-nth dll n)

Return the nth node from the doubly linked list dll. n counts from zero. If dll is not that long, nil is returned. If n is negative, return the -(n+1)th last element. Thus, (dll-nth dll 0) returns the first node, and (dll-nth dll -1) returns the last node.

(dll-last dll)

Return the last element on the doubly linked list dll. Return nil if the list is empty. The element is not removed.

(dll-next dll node)

Return the last element on the doubly linked list dll. Return nil if the list is empty. The element is not removed.

(dll-previous dll node)

Return the node before node, or nil if node is the first node.

(dll-all dll)

Return all elements on the double linked list dll as an ordinary list.

Removing nodes from a dll

(dll-delete dll node)

Delete node from the doubly linked list dll. Return the element of node.

(dll-delete-first dll)

Delete the first node from the doubly linked list dll. Return the element. Returns nil if dll was empty.

(dll-delete-last dll)

Delete the last node from the doubly linked list dll. Return the element. Returns nil if dll was empty.

(dll-clear dll)

Clear the doubly linked list dll, i.e. make it completely empty.

Predicates on a dll

(dll-p object)

Return t if object is a doubly linked list, otherwise return nil.

(dll-empty dll)

Return t if the doubly linked list dll is empty, nil otherwise.

Maps and Filters on a dll

(dll-map map-function dll)

Apply map-function to all elements in the doubly linked list dll. The function is applied to the first element first.

(dll-map-reverse map-function dll)

Apply map-function to all elements in the doubly linked list dll. The function is applied to the last element first.

(dll-filter dll predicate)

Remove all elements in the doubly linked list dll for which predicate returns nil.

Miscellaneous dll operations

(dll-length dll)

Returns the number of elements in the doubly linked list dll.

(dll-sort dll predicate)

Sort the doubly linked list dll, stably, comparing elements using predicate. Returns the sorted list. dll is modified by side effects. predicate is called with two elements of dll, and should return t if the first element is "less" than the second.

Debugging dll applications

The data structure used by the dll package contains both forward and backward pointers. The primitives in Emacs, such as print, know nothing about dlls, so when Emacs tries to print out a dll it will think that it found a circular structure. Fortunately it detects this situation and gives an error message, instead of getting stuck in an eternal loop.

The error message can be quite annoying when you are developing an application that uses dlls. Suppose your code has an error, and you type `(setq debug-on-error t)' to try to figure out exactly what the error is. If any function in the backtrace has a dll as an argument, Emacs will abort printing the entire backtrace and only respond with a "Back at top level" message (or something similar, depending on exactly what you are doing) in the echo area.

There are two solutions to this problem: patch your emacs so that it detects circular structures (there have been patches for this floating around the net) or use `dll-debug.el'.

The file `dll-debug.el' implements all of the functionality that are present in `dll.el', but it uses a normal, singly linked list instead. This makes some operations, like `dll-previous', dreadfully slow, but it makes it possible to debug dll applications. `dll-debug.el' also has more built-in sanity tests than `dll.el'.

NOTE: To use the debug package, you must load the library `dll-debug' before you load any of the libraries (such as cookie) or your program that use dll. You must also make sure that you don't load any byte-compiled version of any file that was compiled with the normal dll library. Since it contains some macros very strange results will occur otherwise...

When the debug package is loaded, you simply run your code normally, and any bugs should be easier to trace.

The Binary Tree Data Type

The binary tree is sometimes an efficient way to store data. When a binary tree is created a compare function is given to the create function (bintree-create). This function is used throughout all data entry and deletions into and out of the tree.

To use the binary tree in Elib you must put the line

(require 'bintree)

in your elisp source file.

The following functions are provided by the binary tree in the library:

(bintree-create compare-function)

Create a new empty binary tree. The argument compare-function is a function which compares two instances of the data type which is to be entered into the tree. The call (compare-function data1 data2) should return non-nil if data1 is less than data2, and nil otherwise.

(bintree-p tree)

Return t if tree is an bintree, otherwise return nil.

(bintree-compare-function tree)

Return compare-function given to bintree-create when tree was created.

(bintree-empty tree)

Return t if tree is empty, otherwise return nil.

(bintree-enter tree data)

Enter data into tree. If there already is a data element which is considered equal to data by compare-function given to bintree-create, the new element will replace the old one in the tree.

(bintree-delete tree data)

Delete the element which is considered equal to data by compare-function given to bintree-create. If there is no matching element within the tree, nothing is done to the tree.

(bintree-member tree data)

Return the element in tree which is considered equal to data by compare-function given to bintree-create. If there is no such element in the tree, return nil.

(bintree-map map-function tree)

Apply map-function to all elements in tree. The function is applied in the order in which the tree is sorted.

(bintree-first tree)

Return the first element of tree, i.e. the one who is considered first by compare-function given to bintree-create. If the tree is empty, return nil.

(bintree-last tree)

Return the last element of tree, i.e. the one who is considered last by compare-function given to bintree-create. If the tree is empty, return nil.

(bintree-copy tree)

Return a copy of tree.

(bintree-flatten tree)

Return a sorted list containing all elements of tree.

(bintree-size tree)

Return the number of elements in tree.

(bintree-clear tree)

Clear tree, i.e. make it totally empty.

The AVL Tree Data Type

The AVL tree data types provides a balanced binary tree. The tree will remain balanced throughout its entire life time, regardless of in which order elements are entered into or deleted from the tree.

Although an AVL tree is not perfectly balanced, it has almost the same performance as if it was. The definition of an AVL tree is that the difference in depth of the two branches of a particular node is at most 1. This criterium is enough to make the performance of searching in an AVL tree very close to a perfectly balanced tree, but will simplify the entering and deleting of data significantly.

All data that is entered into an AVL tree should be of the same type. If they are not, there are no way to compare two elements and this is essential for entering and deleting data from the tree. When a tree is created, a compare function is given to the create function. This function is used throughout the life of the tree in all subsequent insertions and deletions.

To use the Elib AVL tree, you must put the line

(require 'avltree)

in your elisp source file.

The following functions are provided by the AVL tree in the library:

(avltree-create compare-function)

Create a new empty AVL tree. The argument compare-function is a function which compares two instances of the data type which is to be entered into the tree. The call (compare-function data1 data2) should return non-nil if data1 is less than data2, and nil otherwise.

(avltree-p tree)

Return t if tree is an avltree, otherwise return nil.

(avltree-compare-function tree)

Return compare-function given to avltree-create when tree was created.

(avltree-empty tree)

Return t if tree is empty, otherwise return nil.

(avltree-enter tree data)

Enter data into tree. If there already is a data element which is considered equal to data by compare-function given to avltree-create, the new element will replace the old one in the tree.

(avltree-delete tree data)

Delete the element which is considered equal to data by compare-function given to avltree-create. If there is no matching element within the tree, nothing is done to the tree.

(avltree-member tree data)

Return the element in tree which is considered equal to data by compare-function given to avltree-create. If there is no such element in the tree, return nil.

(avltree-map map-function tree)

Apply map-function to all elements in tree. The function is applied in the order in which the tree is sorted.

(avltree-first tree)

Return the first element of tree, i.e. the one who is considered first by compare-function given to avltree-create. If the tree is empty, return nil.

(avltree-last tree)

Return the last element of tree, i.e. the one who is considered last by compare-function given to avltree-create. If the tree is empty, return nil.

(avltree-copy tree)

Return a copy of tree.

(avltree-flatten tree)

Return a sorted list containing all elements of tree.

(avltree-size tree)

Return the number of elements in tree.

(avltree-clear tree)

Clear tree, i.e. make it totally empty.