Collection library

A collection is a value that contains a number (i.e. from zero to infinite) of other values.

Lists, sets, dictionaries, arrays, hash tables, (nondeterm) fact databases, etc are all collections.

A collection can also contain one value, but data types that by nature always contains exactly one value is not a collection. So a list with one element is a collection, but a variable which also contains one element is not a collection.

Collections can be persistent or modifiable:

Persistent

A persistent collection never changes members. Meaning that when you insert or remove a member from persistent collection, you will receive a new collection and the old one will stay unchanged. Prolog lists is a characteristic example of persistent data types: When you match a list against a pattern to get the head and the tail, the original list stays intact; when you create a list from a new head and an existing list, both the new and the old list will exist.

Modifiable

Members can be added to and removed from a modifiable collection. Meaning that when you insert or remove a member from a modifiable collection, the old value of the collection is lost only the one exists. I.e. modifiable collections are updated destructively. Visual Prolog fact databases is a characteristic example of modifiable data types. When you assert or retract facts the database is modified and the original fact database is no longer accessible.

PFC contains an object oriented collection library with both persistent and modifiable collections. The collection library is based around a set of generic interfaces defining various conceptual collection types, and a number of classes implementing these interfaces.

There is no fundamental difference in retrieving data from persistent and modifiable collection so retrieval. The difference lies in the updating of the collections.

Therefore retrieval is done through interfaces that are shared by persistent and modifiable collections, whereas updating is done through separate persistent and modifiable interfaces.

collection is most fundamental interface for retrieving inspecting collections all collections supports this interface. It contains methods:

• isEmpty determining whether the collection is empty
• contains testing whether a certain element is in the collection
• tryGetFirst obtaining the first element in the collection.
• getAll_nd enumerating all elements in the collection.
• asList getting the collection in list form.

Notice that first means different things in different kinds of collections. In a hash table it may for example be the element with the first hash key.

Likewise, the order in which getAll_nd enumerates its elements depends on the collection kind.

Also notice that the performance of some operations may be very poor in some kind of collections. contains is for example a bad operation on a priority queue, because a priority queue not designed to determine membership.

All persistent collections also support the interface persistent and all modifiable collections supports the interface modifiable. persistent and modifiable have predicates with same names but different types, because the persistent version returns a new collection and the modifiable version doesn't return anything. These interfaces have methods:

• insert, insertList and insertCollection for inserting elements
• remove, removeList and removeCollection for removing elements
• tryRemoveFirst for removing the first element
• clear for removing all elements in the collection

set

A set is a collection of elements, which cannot contain duplicates. The fundamental set operation is test of membership. As such a set simply supports the collection interface and one of the interfaces persistent and modifiable.

• setP_redBlack implements persistent sets based on a red black tree representation.
• setM_redBlack implements modifiable sets based on a red black tree representation.

queue

A queue is a collection of elements which are ordered. THe fundamental operation is getting the first element is the queue. Membership testing is typically inefficient. The interfaces of queues is similar to that of sets, supporting collection and one of the interfaces persistent and modifiable. The names are different to stress the difference in intension and efficeincy. And in future they may evolve differently. PFC contains two kinds of queues:

• queue is a "regular" FIFO (first-in-first-out) queue.
  • queueP_fact implements a persistent FIFO queue based on a fact containing an algebraic queue
  • queueM_fact implements a modifiable FIFO queue based on a nondeterm fact database

• priority queue is a queue where the first element is alwasy the element with hightst priority (i.e. the least, the greates or based on a custom comparison).
  • priorityQueueP_leftist implements a persistent priority queue
  • priorityQueueM_leftist implements a modifiable priority queue

Both are based on a leftist tree.

map

A map is a functionfrom keys to values. Not all keys need have a value. The basic operations is setting, getting and try-getting the value associated with a certain key. When the value of a key is set the previous value of that key is "lost".

A map is a collection of (key,value)-tuples,so the collection predicates all deal with such tuples.

map is the basic interface for inspecting maps (persistent as well as modifiable). It supports collection of (key,value)-tuples and extends with predicates/properties:

• get and tryGet for getting the value associated with a key
• getKey_nd and getValue_nd for iterating the keys and values
• keyList and valueList for obtaining all the keys and values as lists.

mapP (persistent maps) and mapM (modifiable maps) supports map and either persistent or modifiable, and extends with:

• set for setting the value associated with a key (the previous value associated with that key is "lost")
• removeKey for removing a key and its associated value
• removeKeyList and removeKeyCollection for removing a number of keys and their associated values)

PFC contains persistent and modifiable map classes based on red-black trees:

• mapP_redBlack
• mapM_redBlack