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 FIFO queue based on a fact containing an algebraic queue

• 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).