User:Jenny Harlow/Design study/Initial design detail

Revision as of 05:41, 30 August 2010

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

IMiniSequence is the subtype of IMiniCollection that has a notion of an ordering of its elements.

• getOrderingMode() is an interrogation method. It returns an OrderingMode enum indicating the ordering currently found within the sequence (naturally ordered, ordered with a custom comparator, ordered by the order of insertion, or a mixture of these). At this stage in the I think that this operation might be a YAGNI, but I can also see that it might be useful to find out what ordering currently holds in a sequence. Implementations of the type will need to ensure that an up-to-date response can be given to this query, ie that changes in ordering as a result of operations like sort() or add() can be recognised and reflected in the response.
• I toyed with the state pattern again here - clearly I wanted to get that in somewhere - but there is no clear life-cycle of ordering states and it was very complicated to try to do it this way.
• getAccessMode() returns an AccessMode enum describing the access mode of the underlying implementation of the sequence (random access or sequential access).
• add(E e) adds an element to the end of the sequence and returns an InsertCheck enum indicating the outcome of the operation:
  • FAILED indicates that the addition failed due to some failure in the underlying implementation - I am not quite sure what this might actually be but I wanted to have the facility to indicate failure even though the IMiniSequence does not expect any implementing class to deliberately fail to try to add the element.
  • NEW indicates that the element is added as a new element in the sequence (the size of sequence has increased by one)
  • OVERWRITTEN indicates that the element has overwritten an existing member of the sequence which was equal to the added element (eg is used by sequences which require their members to be unique).
• remove(E e) removes all occurrences of the element e. I subsequently changed remove(E e) to removeAll(E e) to make it clearer what the operation did.
• there are two sort methods sort() and sort(Comparator<? super E> c).
  • sort() one uses natural sorting and will give a run-time error if E does not implement Comparable. It would be better not to have a run-time error but it seems unavoidable if sort is an IMiniSequence operation. I don't want to have to have a special IMiniSequence type for Es which implement Comparable. It might be better not to have sort() at all. I can see why Java made their sort() a static operation and did not put it in the List<E> interface.
  • sort(Comparator<? super E> c) takes an ordering strategy as a parameter and sorts the members of the sequence according to this ordering.
  • addAtIndex(int i, E e) adds e at index i provided 0 < i =< size(), and shuffles existing members of the sequence to accommodate the addition if necessary. addAtIndex returns an InsertCheck value, like add, indicating the outcome of the operation.
• the getAtIndex, resetAtIndex, and removeAtIndex operations allow the client to read, reset, or remove at a specified index position provided that index position is within the current index range 0 - size().
• the firstIndexOf(E e) and lastIndexOf(E e) operations allow the client to find the first and last occurrences of an element e and return the required index position or -1 if the element is not in the sequence.
• nextIndexOf(int i, E e) returns the next index of the specified element at or after index i, or -1 if the element e does not occur in the sequence at or after index i, both providing that 0 < i < size().
• IMiniSequence.begin() uses a factory method to return an IMiniSequenceIterator whose current() element is the first element in the sequence.
• Similarly, end() returns an IMiniSequenceIterator whose current element is the last element in the sequence.
• seqIterator(int i) returns an IMiniSequenceIterator whose current element is the element at the specified index position in the sequence providing that 0 < i < size().

My intention was to have three flavours of Sequence: the plain sequence, a sequence that only contains unique members, and a sequence that maintained a sorted order, where sorting could be by the element's natural ordering or a 'custom sorting' using a supplied Comparator ordering strategy.

I intended to use the decorator pattern for the uniques-only and sorted sequences. The decorated objects are IMiniSequence types, wrapping an IMiniSequence and providing added behaviour in the wrapper that augmented the behaviour specified in IMiniSequence contract. The advantage of using the Decorator pattern are:

• combinations of added behaviour can be made without more subclassing (eg, sorted unique only sequences)
• the added behaviour can be added and withdrawn dynamically

However, the decorated objects have to be able to substitutable for an IMiniSequence: no withdrawn behaviour, no nasty surprises.

In the case of the MiniSequenceUniqueOnlyDecorator, the added behaviour is effectively to remove existing members of the sequence which compare equal to the new member after any add or reset operations.

• add(E e) checks if element is already there and overwrites the existing member if so. The post condition is that the specified member is added to the sequence, and if there existed an element e' such that e.equals(e') == true then this has been overwritten and the operation has returned InsertCheck.OVERWRITTEN, else (no existing equal member) the operation has returned InsertCheck.NEW.
• addAtIndex(int i, E e) checks if the sequence contains an element e' such that e.equals(e') == true. If not, the element e is added at the specified index. If so, the element e is added at the specified index and the other elements of the sequence are shuffled to overwrite the existing equal member e'. The post condition is that the specified member is added to the sequence at the specified index, and if there existed an element e' such that element.equals(e') == true then this has been overwritten and the operation has returned InsertCheck.OVERWRITTEN, else (no existing equal member) the operation has returned InsertCheck.NEW.
• resetAtIndex(int i, E e) checks if the sequence contains an element e' such that e.equals(e') == true with index value i' not equal to i. If not, the element currently at index i is replaced with the element e. If so, the element at index i is replaced with the element e and the duplicate occurrence e' is removed from the sequence. The post condition is that the element at the specified index has been replaced by e and if there existed an element e' such that element.equals(e') == true at a different index then this has been removed.

In the case of the AbstractMiniSequenceSortedDecorator (subclassed to the custom sorted and naturally sorted variants), my intention was that the decorator added behaviour was to sort the sequence in the required way after any operation like add which altered the membership or ordering of the sequence and ensure that the sequence's getOrderingMode reflected the kind of sorting being applied.

• Initially I had intended to apply this to the two IMiniSequence sort operations as well, ie the behaviour would be 'sort as requested by sort and then resort according to how the sorted sequence is sorted'. This is just the equivalent of ignoring the IMiniSequence sort operation.
  • After the initial design I decided that this was not good enough - it broke the contract for IMiniSequence. So, instead I decided that in this case the added behaviour would be ignored, ie sort() or sort(Comparator<? super E> c) would do exactly the same for a sorted sequence as they would for a plain sequence, but that a subsequent operation that changed the membership of the sequence would reassert the sorted order.
  • I justified this by reasoning that clients expect a sort operation to have a one-off effect and that if this is followed by an addition, the result will depend on the addition strategy of sequence - when this (implicitly) is to add at back of the sequence the client will end up with some sorted and some unsorted members, and when the addition strategy is to add and resort the whole thing then the whole sequence will be resorted.
  • A client with a sorted sequence can use getOrderingMode to check the current kind of ordering, although this does not say what kind of custom comparator is used.

A far bigger problem is that decorator pattern shown in this initial design diagram is unworkable because it is impossible to be able to adhere to the IMiniSequence contract for addAtIndex or resetAtIndex and then apply sorting: a sorted sequence was unsubstitutable for a IMiniSequence because the element added (or the element reset to) will not necessarily end up at the specified index position after sorting.

The design choices at this stage seemed to be:

• to forget sorted sequences entirely:
  • cop-out, not to mention that I really wanted them.
• take the addAtIndex and resetAtIndex operations out of IMiniSequence:
  • but they are good useful operations - I can't just remove any functionality that gets in the way of the design.
• make sorted sequences a separate subtype of IMiniCollection (with no addAtIndex or resetAtIndex operations, nor any sort operations):
  • just felt wrong - lots of duplicate operations, my beautiful uniques only decorator has have a twin, it would all be messy ...
• to add another type at a lower level
  • ie, have an IMiniSequence without addAtIndex and resetAtIndex and have a subtype of IMiniSequence with this extended behaviour.
  • the sorted sequence decorator wraps an IMiniSequence, not the extended type.

My redesign used the final option above. I took addAtIndex and resetAtIndex and removeAtIndex() out of IMiniSequence and added an IMiniSequenceFlexiAdd subtype (not shown in the initial design diagram, and it needs a better name). I think that this is a better design for the whole thing because these three operations are particularly relevant to linked-list implementations. I did then have to resolve a few issues about how to actually implement things without duplicating too much code. This is discussed further later.

Under the new design I still had a type-safety issue with the naturally sorted sequence. To have a compile-time check on whether E implements Comparable, I needed a sorted sequence class specified in terms of <E extends Comparable<? super E>. This meant that it did not appear that I could just have one sorted sequence decorator class which could take a Comparator strategy or use a default strategy of natural sorting (Java really should have made all objects comparable with a default compareTo equivalent to the default equals, then we could override compareTo but always be able to use 'natural' sorting ...). Initially I has two concrete sorted sequence classes, MiniSequenceSelfSortedDecorator and MiniSequenceCustomSortedDecorator, so that I could do the type checking. When I started to look at the factories I wanted clients to use to create all the collections, I realised that I could put the type check in at the factory end. The generic naturally sorted sequence factory then enforces the type check on E and makes a Comparator using E's toCompare, and then passes this to a custom sorted sequence factory to instantiate a MiniSequenceCustomSortedDecorator sorted sequence. All the MiniSequenceCustomSortedDecorator needs is the Comparator. Factories are discussed in more detail later.

I will discuss the other sequence classes in the initial design as far as is relevant, given the redesign discussed above.

AbstractMiniSequence provides a generalised 'stub' implementation of a sequence, making extensive use of template methods to check the index values supplied for any operations taking index parameters.

• The template methods check the index value using private index checking operations. I changed the visibility to protected later so that subclasses could use the methods as well 'open for extension ...'. It is pity that Java allows package access to protected class members - I try not to take advantage of this. Actual implementation of the operations once the index value has been checked is deferred to subclasses via the primitive methods. This means that all subclasses of AbstractMiniSequence can concentrate on the methods can do not have to deal with these pre-conditions. I could have just allowed all the index-out-of-bounds-related exceptions to bubble up out of the layers of abstractions, decorators, implementations, adaptors, ... but I thought that it was better to provide an efficient top-level check and consistent response.
• I later realised that I should add an OrderingMode data member (getOrderingMode is then effectively a getter for this) and turn the two sort operations into template methods which updated the ordering mode appropriately and then called primitive sort methods.

AbstractMiniSequenceBridge is the bridge between the abstraction - the IMiniSequence - and the actual implementation. The bridge pattern decouples an abstraction from its implementation. My main motivation for using a bridge here was to be able to have different implementations which could be plugged into the bridge rather than different subclasses for each implementation (extend the hierarchies independently), and be able to change the implementation dynamically.

• The bridge composes an instance of an IMiniSequenceImplementation and uses the IMiniSequenceImplementation operations to carry out its own responsibilities.
• The initial design did not deal properly with the replaceImplementation operation: it was not until I tried to code it that I could see how to manage this. In the later design, the IMiniSequence type gains a resetAccessMode(AccessMode am) operation which replaces replaceImplementation so that all IMiniSequences have to be able to change their access mode (random access or sequential). This restricts possible implementations of the type (they have to be able to change access mode) but gives flexibility to the client and this was part of the original design aim.
• The bridge pattern leaves it open how and when implementations are instantiated. I describe my initial design for this in the next section. Sufficed to say, the initial design was not very good and in the end factories rode to the rescue and took care of everything.

Implementation of the adaptors for Sequences

Implementation and adaptor classes for the MiniSequenceCollection