Module "SetRBT0.curry"

OLD (OBSOLETE) Version of a library with an implementation of sets as red-black trees.

All the operations on sets are generic, i.e., one has to provide an explicit order predicate ("cmp" below) on elements.

Author: Johannes Koj, Michael Hanus

Version: May 2001

Datatypes:
SetRBT

Functions:
elemRBT | emptySetRBT | insertMultiRBT | insertRBT | intersectRBT | setRBT2list | sortRBT | unionRBT

emptySetRBT  :: SetRBT a              Returns an empty set, i.e., an empty red-black tree.

elemRBT  :: (a -> a -> Bool) -> a -> SetRBT a -> Bool              Returns true if an element is contained in a (red-black tree) set.

insertRBT  :: (a -> a -> Bool) -> a -> SetRBT a -> SetRBT a              Inserts an element into a set if it is not already there.

insertMultiRBT  :: (a -> a -> Bool) -> a -> SetRBT a -> SetRBT a              Inserts an element into a multiset.

setRBT2list  :: SetRBT a -> [a]              Transforms a (red-black tree) set into an ordered list of its elements.

unionRBT  :: (a -> a -> Bool) -> SetRBT a -> SetRBT a -> SetRBT a              Computes the union of two (red-black tree) sets.

intersectRBT  :: (a -> a -> Bool) -> SetRBT a -> SetRBT a -> SetRBT a              Computes the intersection of two (red-black tree) sets.

sortRBT  :: (a -> a -> Bool) -> [a] -> [a]              Generic sort based on insertion into red-black trees.

SetRBT

The structure of red-black trees.

Constructors:

---

---

Exported functions:

---

emptySetRBT :: SetRBT a   

Returns an empty set, i.e., an empty red-black tree.

Further infos:

• solution complete, i.e., able to compute all solutions

---

elemRBT :: (a -> a -> Bool) -> a -> SetRBT a -> Bool   

Returns true if an element is contained in a (red-black tree) set.

Example call:  (elemRBT cmp e s)

Parameters:

cmp - order predicate on elements

e - an element to be checked for containment

s - a set (represented as a red-black tree)

Returns:

True if e is contained in s

Further infos:

• incompletely defined

---

insertRBT :: (a -> a -> Bool) -> a -> SetRBT a -> SetRBT a   

Inserts an element into a set if it is not already there. The first argument is the order on elements.

---

insertMultiRBT :: (a -> a -> Bool) -> a -> SetRBT a -> SetRBT a   

Inserts an element into a multiset. Thus, the same element can have several occurrences in the multiset.

---

setRBT2list :: SetRBT a -> [a]   

Transforms a (red-black tree) set into an ordered list of its elements.

Further infos:

• solution complete, i.e., able to compute all solutions

---

unionRBT :: (a -> a -> Bool) -> SetRBT a -> SetRBT a -> SetRBT a   

Computes the union of two (red-black tree) sets. This is done by inserting all elements of the first set into the second set.

---

intersectRBT :: (a -> a -> Bool) -> SetRBT a -> SetRBT a -> SetRBT a   

Computes the intersection of two (red-black tree) sets. This is done by inserting all elements of the first set contained into the second set into a new set.

---

sortRBT :: (a -> a -> Bool) -> [a] -> [a]   

Generic sort based on insertion into red-black trees.

---

---

Generated by CurryDoc (Version 0.4.1 of June 7, 2007) at Jun 16 17:15:42 2009