User:Jenny Harlow/Design study/Initial design detail

Navigation shortcuts: Wiki users:Jenny Harlow:Jenny Harlow Design study

---

Initial design detail

The 'initial design' was a bit uneven - I had thought out quite a lot on the Sequences but not for the Bags. On this page I will discuss the design as it was at that stage. Just thinking about it and looking at the diagrams here I could see some improvements I should make, and when I implemented it I found more.

Main interfaces and types

The MiniCollection interfaces (operation signatures not shown)

I called the collection MiniCollection. The main types are specified with interfaces: the IMiniCollection base type for collections, subtyped with IMiniSequence, IMiniBagOfSingles, IMiniBagOfPairs. I found it helpful to have interface names starting with 'I' to identify my files. The actual names are not user-friendly, but at the design stage I was thinking very literally about them.

An IMiniCollection, specified using the generic type <E>, is a container of elements E. IMiniCollection specifies operations I though should be common to all containers. The big problem for me, as for the Java Collections Framework, was to try to find a way to provide a collections framework that did not sprawl over hundreds of collection types, all doing their own thing in their own way. I wanted to do better than Java at establishing what key behaviour made a type and then abiding by that contract, but I also wanted to avoid the type sprawl. My approach was to write the main interface contracts in a way that anticipated some 'modifications' in behaviour from the subtypes, and ensure that the client can query any characteristic which would lead to these modifications (interrogation methods, discussed below). This is still a fudge, just not as extreme a fudge as 'optional' methods, and I hope that the way that I have used it does not push the boundaries of design by contract too far.

• The disadvantage of this approach is the large grey area between genuine added behaviour and unsubstitutable behaviour.
• The main advantage is that it enables the client to only have to know about a smaller number of interfaces. I could not find another way to avoid a sprawl of types which specified enough behaviour to be useful to the client.
• The other advantage is that more dynamic changes in behaviour can be accommodated.
• I decided that the approach was justified in order to give an more accessible, flexible and usable framework.
  • Interrogation methods are not used for type switches - at no point does an implementation check its own state with respect to one of these interrogation methods to determine its behaviour
  • I could have used tag interfaces instead but I wanted to keep the flexibility to allow IMiniCollection objects to able to change these characteristics dynamically.
  • I wondered briefly about using the State pattern, but it is unsuitable (I explicitly did not want the fancy type-switch that State allows, and there would have had to have been states reflecting all possible combinations of characteristics which is messy and hard to maintain).
  • I used Enums for interrogation methods (more flexible and informative than booleans, typesafe alternatives to numeric coding).

All IMiniCollections are iterable: IMiniCollection and implements IMiniIterable and IMiniIterable types have a factory method miniIterator() returning an IMiniIterator type iterator to the collection. This is just a copy of the way in which a Java Collection implements Iterable, but I wanted my own iterators.

• IMiniCollection subtypes have an equivalent subtype of IMiniIterator. This gives a parallel hierarchy problem which the use of the factory method to allow each IMiniCollection subtype to make its own iterator helps to resolve (as it does in the Java Collections Framework).

IMiniPair is not a subtype of IMiniCollection. This is a general pair type (which I think should be part of the general Java API). Mine is very basic and the main point is to be able to subtype it to the IMiniKeyValuePair type. An IMiniPair provides read access to the first and second members in the pair thought the getters but no write access. An IMiniGeneralPair subtype adds write access to both but the IMiniKeyValuePair only adds write access to the second member in the pair (the 'value' member). Thus both IMiniGeneralPair and IMiniKeyValuePair support the IMiniPair contract and can be substituted when a client expects an IMiniPair with no unpleasant surprises. The IMiniKeyValuePairs are used by the bags.

An IMiniCollection:

• can report its membership mode (using enum MembershipMode). This is an example of an "interrogation method". Some objects of the IMiniCollection type will only permit unique members.
• can report its size (the number of elements in it), whether it is is empty, whether it contains a specified element, and count of the the number of copies of a specified element it contains.
• has two 'destructive' operations: clearing (emptying) the entire container and removing all duplicate elements.
  • I had decided not to try to deal with unmodifiable collections and could not see any reason why subtypes would want to not support these operations, and I thought that these operations could be appropriately applied at the level of a very general collection of elements.
  • As you would expect, removeDuplicates() subsequently caused trouble (when it came to Bags, it is not necessarily obvious to clients what an 'element' of the collection is as far as the IMiniCollection type is concerned). This probably should not have been an IMiniCollection operation.

The iterator

MiniIterator design

This diagram shows the sorry state of the IMiniIterator family at the time of my initial design. At that point, I thought that I had sorted out how the IMiniSequenceIterator type (the specialist iterator for Sequences) would work and - I thought - how I could actually implement this by adapting adapting the Java ListIterator. I have included these on the diagram.

• The IMiniIterator type separates the command next() from the query 'what element are you pointing to?'.
  • next() moves the iterator to point to the next element in the collection if there is one, or to point to null if there is no next element to move to.
  • The existence of a next element to move to can be queried with hasNext(), which returns a boolean true if calling next() would move the current element of the iterator to another member of the collection, false otherwise.
• current() returns the element currently pointed to, or null if there is no current element. There will be no current element if what was the current element has been removed using the iterator, or if the iterator has been moved off the ends of the collection (eg, with next())
• the idiom for iterating through a collection with an IMiniIterator it is

    (while it.current != null) {
        //do something with it
        it.next();
    }

• This initial design gave the IMiniIterator the capability to remove the current element (removeCurrent()). I subsequently decided that this restricted subtyping of IMiniIterator (was not very open for extension) and moved it down the type hierarchy.
• When I was designing the IMiniIterator I was also thinking about how I could adapt the Java Iterator to use it in my implementations. Since the Java Iterator ListIterator subtype's behaviour depends on whether its last call was next() or previous(), I thought that I should build something into my IMiniIterator which could change behaviour based on direction using the State pattern. This was very muddled thinking (there is probably some anti-pattern term for trying to do design by fussing about details) and the IMiniIterator state was a clear case of YAGNI. I removed it when I realised I just did not need it.

The AbstractMiniIterator layer is there to simplify implementing the IMiniIterator, and to control sub-class behaviour, by dealing with the generalizable required behaviour while leaving the details up to its implementing classes. AbstractMiniIterator:

• maintains a private reference to the element currently pointed to by the iterator, and implements the getter current() which returns this value.
• provides a protected setter to allow subclasses to set the current element (I could just have made current protected but providing protected getters and setters is my preferred way allowing subclasses read and write access to data they inherit from superclasses).
• uses template methods to allow the AbstractMiniIterator to define the outline of what happens in next() and removeCurrent() while deferring the details to subclasesses.
  • The primitive_next() operation is expected to return the element just iterated over, which then becomes the current element; the actual implementation of primitive_next() is up to the subclasses.
  • The primitive_removeCurrent() operation is expected to just remove the current element in the The interface next(), implemented
• The state-related operations are obsolete, as explained above.

The IMiniSequenceIterator type adds the capabilities to go backwards.

• previous() moves the iterator to point to the previous element in the collection if there is one, or to point to null if there is no previous element to move to.
• The existence of a previous element to move to can be queried with hasPrevious(), which returns a boolean true if calling previous() would move the current element of the iterator to another member of the collection, false otherwise.

Like AbstractMiniIterator, the AbstractMiniSequenceIterator layer is there to simplify implementing the IMiniSequenceIterator, and to control sub-class behaviour:

• AbstractMiniSequenceIterator uses another template method for previous() to allow the AbstractMiniIterator to define the outline of what happens in previous():
  • The primitive_previous() operation is expected to return the element just iterated (backwards) over, which is passed up to the superclass to become the current element; primitive_previous() details are up to the subtypes.

ImplJCIteratorAdaptor (yes, I know, the names are a bit out of control but that's the way I think and the client never has to see or think about them - 'JC' stands for JavaCollections!) is an implementation of the IMiniIterator which adapts the Java Iterator. The adapter pattern can be implemented in two ways: an object adaptor (adaptor inherits from target and composes adaptee) and a class adaptor (adaptor inherits from target and also inherits [its implementation] from adaptee) . I have used object adaptors throughout this design, not because I want to be able to adapt several existing subclasses with the same adaptor but because I don't feel comfortable with the class adaptor idea.

Similarly, ImplJCIteratorListAdaptor is an implementation of the IMiniSequenceIterator which adapts the Java ListIterator, again by composing a ListIterator.

• using an object adaptor allows me to just ignore the totally unwanted operations of the adaptee (Iterator or ListIterator), like the index-related methods of ListIterator (and, when I moved removedCurrent() down the type hierarchy, the remove() method of Iterator). I implement the target interface (IMiniIterator or IMiniSequenceIterator) operations by calling operations of the composed adaptee.

The Sequences

The MiniSequenceCollection design

Implementation of the adaptors for Sequences

Implementation and adaptor classes for the MiniSequenceCollection