We will first consider the list container since in some ways it is the simplest. Here is its specification interspersed with some explanation

The two generic parameters are the type of the elements in the list and the definition of equality for comparing elements. This equality relation must be such that x = y and y = x always have the same value.

A list container is an object of the type List. It is tagged since it will inevitably be implemented as a controlled type. The fact that it is visibly tagged means that all the advantages of object oriented programming are available. For one thing it enables the use of the prefixed notation so that we can write operations such as 

rather than 

The type Cursor is an important concept. It provides the means of access to individual elements in the container. Not only does it contain a reference to an element but it also identifies the container as well. This enables various checks to be made to ensure that we don't accidentally meddle with an element in the wrong container.

The constants Empty_List and No_Element are as expected and also provide default values for objects of types List and Cursor respectively.

The function "=" compares two lists. It only returns true if both lists have the same number of elements and corresponding elements have the same value as determined by the generic parameter "=" for comparing elements. The subprograms Length, Is_Empty and Clear are as expected.

Note that A_List = Empty_List, Is_Empty(A_List) and Length(A_List) = 0 all have the same value.

These are the first operations we have met that use a cursor. The function Element takes a cursor and returns the value of the corresponding element (remember that a cursor identifies the list as well as the element itself). The procedure Replace_Element replaces the value of the element identified by the cursor by the value given; it makes a copy of course.

Note carefully that Replace_Element has both the list and cursor as parameters. There are two reasons for this concerning correctness. One is to enable a check that the cursor does indeed identify an element in the given list. The other is to ensure that we do have write access to the container (the parameter has mode in out). Otherwise it would be possible to modify a container even though we only had a constant view of it. So as a general principle any operation that modifies a container must have the container as a parameter whereas an operation that only reads it such as the function Element does not.

These procedures provide in situ access to an element. One parameter is the cursor identifying the element and another is an access to a procedure to be called with that element as parameter. In the case of Query_Element, we can only read the element whereas in the case of Update_Element we can change it as well since the parameter mode of the access procedure is in out. Note that Update_Element also has the container as a parameter for reasons just mentioned when discussing Replace_Element.

The reader might wonder whether there is any difference between calling the function Element to obtain the current value of an element and using the seemingly elaborate mechanism of Query_Element. The answer is that the function Element makes a copy of the value whereas Query_Element gives access to the value without making a copy. (And similarly for Replace_Element and Update_Element.) This wouldn't matter for a simple list of integers but it would matter if the elements were large or of a controlled type (maybe even lists themselves).

This moves the list from the source to the target after first clearing the target. It does not make copies of the elements so that after the operation the source is empty and Length(Source) is zero.

These three procedures enable one or more identical elements to be added anywhere in a list. The place is indicated by the parameter Before – if this is No_Element, then the new elements are added at the end. The second procedure is similar to the first but also returns a cursor to the first of the added elements. The third is like the second but the new elements take their default values. Note the default value of one for the number of elements.

These add one or more new elements at the beginning or end of a list respectively. Clearly these operations can be done using Insert but they are sufficiently commonly needed that it is convenient to provide them specially.

These delete one or more elements at the appropriate position. In the case of Delete, the parameter Position is set to No_Element upon return. If there are not as many as Count elements to be deleted at the appropriate place then it just deletes as many as possible (this clearly results in the container becoming empty in the case of Delete_First and Delete_Last).

This does the obvious thing. It would have been nice to call this procedure Reverse but sadly that is a reserved word.

This handy procedure swaps the values in the two elements denoted by the two cursors. The elements must be in the given container otherwise Program_Error is raised. Note that the cursors do not change.

This performs the low level operation of swapping the links rather than the values which can be much faster if the elements are large. There is no analogue in the vectors package.

These three procedures enable elements to be moved (without copying). The place is indicated by the parameter Before – if this is No_Element, then the elements are added at the end. The first moves all the elements of Source into Target at the position given by Before; as a consequence, like the procedure Move, after the operation the source is empty and Length(Source) is zero. The second moves a single element at Position from the list Source to Target and so the length of target is incremented whereas that of source is decremented; Position is updated to its new location in Target. The third moves a single element within a list and so the length remains the same (note the formal parameter is Container rather than Target in this case). There are no corresponding operations in the vectors package because, like Swap_Links, we are just moving the links and not copying the elements.

Hopefully the purpose of these is almost self-evident. The function Find searches for an element with the given value starting at the given cursor position (or at the beginning if the position is No_Element); if no element is found then it returns No_Element. Reverse_Find does the same but backwards. Note that equality used for the comparison in Find and Reverse_Find is that defined by the generic parameter "=".

This returns False if the cursor does not identify an element; for example if it is No_Element.

These apply the procedure designated by the parameter Process to each element of the container in turn in the appropriate order.

This generic package performs sort and merge operations using the order specified by the generic formal parameter. Note that we use generics rather than access to subprogram parameters when the formal process is given by an operator. This is because the predefined operations have convention Intrinsic and one cannot pass an intrinsic operation as an access to subprogram parameter. The function Is_Sorted returns True if the container is already sorted. The procedure Sort arranges the elements into order as necessary – note that no copying is involved since it is only the links that are moved. The procedure Merge takes the elements from Source and adds them to Target. After the merge Length(Source) is zero. If both lists were sorted before the merge then the result is also sorted.

And finally we have

If the reader has got this far they have probably understood how to use this package so extensive examples are unnecessary. However, as a taste, here is a simple stack of floating point numbers 

This barely needs any explanation. The lists package is instantiated in the package Stack and the object The_Stack is of course the list container. The rest is really straightforward. We could of course use the prefixed notation throughout as indicated in Push.

An important point should be mentioned concerning lists (and containers in general). This is that attempts to do foolish things typically result in Constraint_Error or Program_Error being raised. This especially applies to the procedures Process in Query_Element, Update_Element, Iterate and Reverse_Iterate. The concepts of tampering with cursors and elements are introduced in order to dignify a general motto of "Thou shalt not violate thy container".

Tampering with cursors occurs when elements are added to or deleted from a container (by calling Insert and so on) whereas tampering with elements means replacing an element (by calling Replace_Element for example). Tampering with elements is a greater sin and includes tampering with cursors. The procedure Process in Query_Element and Update_Element must not tamper with elements and the procedure Process in the other cases must not tamper with cursors. The reader might think it rather odd that Update_Element should not be allowed to tamper with elements since the whole purpose is to update the element; this comes back to the point mentioned earlier that update element gives access to the existing element in situ via the parameter of Process and that is allowed – calling Replace_Element within Process would be tampering. Tampering causes Program_Error to be raised.

We will now consider the vectors package. Its specification starts

This is similar to the lists package except for the additional generic parameter Index_Type (note that this is an integer type and not a discrete type). This additional parameter reflects the idea that a vector is essentially an array and we can index directly into an array.

In fact the vectors package enables us to access elements either by using an index or by using a cursor. Thus many operations are duplicated such as 

If we use an index then there is always a distinct parameter identifying the vector as well. If we use a cursor then the vector parameter is omitted if the vector is unchanged as is the case with the function Element. Remember that we stated earlier that a cursor identifies both an element and the container but if the container is being changed as in the case of Replace_Element then the container has to be passed as well to ensure write access and to enable a check that the cursor does identify an element in the correct container.

There are also functions First_Index and Last_Index thus 

These return the values of the index of the first and last elements respectively. The function First_Index always returns Index_Type'First whereas Last_Index will return No_Index if the vector is empty. The function Length returns Last_Index–First_Index+1 which is zero if the vector is empty. Note that the irritating subtype Extended_Index has to be introduced in order to cope with end values. The constant No_Index has the value Extended_Index'First which is equal to Index_Type'First–1.

There are operations to convert between an index and a cursor thus 

It is perhaps slightly messier to use the index and vector parameters because of questions concerning the range of values of the index but probably slightly faster and maybe more familiar. And sometimes of course using an index is the whole essence of the problem. In the chapter on access types (see 3.4) we showed a use of the procedure Update_Element to double the values of those elements of a vector whose index was in the range 5 to 10. This would be tedious with cursors.

But an advantage of using cursors is that (provided certain operations are avoided) it is easy to replace the use of vectors by lists.

For example here is the stack package rewritten to use vectors 

So the changes are very few indeed and can be quickly done with a simple edit.

Note that the index parameter has been given as Natural rather than Integer. Using Integer will not work since attempting to elaborate the subtype Extended_Index would raise Constraint_Error when evaluating Integer'First–1. But in any event it is more natural for the index range of the container to start at 0 (or 1) rather than a large negative value such as Integer'First.

There are other important properties of vectors that should be mentioned. One is that there is a concept of capacity. Vectors are adjustable and will extend if necessary when new items are added. However, this might lead to lots of extensions and copying and so we can set the capacity of a container by calling

There is also 

which naturally returns the current capacity. Note that Length(V) cannot exceed Capacity(V) but might be much less.

If we add items to a vector whose length and capacity are the same then no harm is done. The capacity will be expanded automatically by effectively calling Reserve_Capacity internally. So the user does not need to set the capacity although not doing so might result in poorer performance.

There is also the concept of "empty elements". These are elements whose values have not been set. There is no corresponding concept with lists. It is a bounded error to read an empty element. Empty elements arise if we declare a vector by calling 

as in 

There is also the much safer 

which sets all the elements to the value New_Item.

There is also a procedure

This changes the length of a vector. This may require elements to be deleted (from the end) or to be added (in which case the new ones are empty).

The final way to get an empty element is by calling one of 

These insert the number of empty elements given by Count at the place indicated. Existing elements are slid along as necessary. These should not be confused with the versions of Insert which do not provide an explicit value for the elements – in those cases the new elements take their default values.

Care needs to be taken if we use empty elements. For example we should not compare two vectors using "=" if they have empty elements because this implies reading them. But the big advantage of empty elements is that they provide a quick way to make a large lump of space in a vector which can then be filled in with appropriate values. One big slide is a lot faster than lots of little ones.

For completeness, we briefly mention the remaining few subprograms that are unique to the vectors package.

There are further versions of Insert thus 

These insert copies of a vector into another vector (rather than just single elements).

There are also corresponding versions of Prepend and Append thus 

Finally, there are four functions "&" which concatenate vectors and elements by analogy with those for the type String. Their specifications are 

Note the similarity between 

The result is the same but using "&" is less efficient because of the extra copying involved. But "&" is a familiar operation and so is provided for convenience.

© 2005, 2006 John Barnes Informatics.

Sponsored in part by: