User:Jenny Harlow/Design study/Final design detail

Revision as of 04:04, 31 August 2010

Sequences

I do not discuss the design patterns used here in detail because these have already been covered in the initial design detail.

Main types and classes

After adding the IMiniSequenceFlexiAdd type that allows addition, resetting and removal at specified index positions, and other improvements discussed in relation to the initial design, the design for sequences looks like this:

Sequences

IMiniSequence has an operation to reset the access mode (random access or sequential) which will presumably be ultimately implemented by changing from one underlying container to another: this is facilitated in my design by the use of bridges.

AbstractMiniSequenceDecorator composes an IMiniSequence and is used in this design to provide the sorted sequences. Factories take responsibility for type checking and other details for naturally sorted sequences so we only need one concrete MiniSequenceCustomSortedDecorator and this adds sorting on add() and on a change in access mode (in case that causes a change in the order of the sequence)

The decorator adding unique-elements-only wraps an IMiniSequenceFlexiAdd type. IMiniSequenceFlexiAdd is a subtype of IMiniSequence. We can therefore use a factory to provide a uniques-only IMiniSequence (composing an IMiniSequence and returning an IMiniSequence type), as well being able to make uniques-only IMiniSequenceFlexiAdd sequences using this decorator. Using factories we can spare clients hopeless attempts to instantiate make a type which is a subtype of the wrapped type.

One problem I did encounter here was how to arrange the inheritance for the AbstractMiniSequenceFlexiAddDecorator. Ideally, I would not have had to replicate the operations in common with AbstractMiniSequenceDecorator, but I could not have AbstractMiniSequenceFlexiAddDecorator extending both AbstractMiniSequenceDecorator and AbstractMiniSequenceFlexiAdd. I thought about composing an AbstractMiniSequenceDecorator but as well as being complicated, this would either mean two copies of the composed sequence or AbstractMiniSequenceDecorator allowing AbstractMiniSequenceFlexiAddDecorator access to its inner sequence which was horrible. So I ended up by replicating the decorator operations. There is probably a nicer way to do this but I am not sure what it is.

Bridges and implementations

The final bridge and implementation design is shown below.

Sequence adaptors

The addition of the IMiniSequenceFlexiAdd type did cause many problems for the bridges and implementations because I did not change the specification of the IMiniSequenceImplementation type: any implementation has to be able to provide an implementation for addAtIndex, resetAtIndex and removeAtIndex. The AbstractMiniSequenceBridge uses what it needs and is extended by AbstractMiniSequenceFlexiAddBridge which uses the remaining operations through a protected getter for the implementation (getImpl()). This worked for my small design and concrete implementations using adaptors of the Java List interface, but it does restrict what can be used as an implementation and means that AbstractMiniSequenceBridge is not using all the operations of its implementation. I am not very happy with this aspect of the design - I suspect that I was just tired of it by the time I got it working and did not want to have to think about it any more.

Iteration

Sequences

The IMiniSequenceIterator can remove the currently-pointed to element in the sequence and go backwards as well as forwards: other than the transfer of removeCurrent() from IMiniterator to the subtypes, the sequence iterator is essentially the same as in the initial design.

• the idiom for iterating through a sequence removing each element as you go with an IMiniSequenceIterator it is:

    (while it.current != null) {
        it.removeCurrent();
        it.next();
    }

• or going backwards:

    (while it.current != null) {
        it.removeCurrent();
        it.previous();
    }

For my sequence implementations I use adaptations of the Java ListIterator. I added an adaptation of my iterator back into the Java Iterator interface so that I could use the for-each construct. This was not strictly necessary for sequences - I could have just provided the Iterator on the adapted List, but I also wanted to nobble the Java Iterator remove() operation. I did this by taking shameless advantage of fact that Java marked remove() as 'optional'. I think that this is justified because implementing Iterable is not really part of the design, it is just to be able to show that we can use a for-each construct with the MiniCollection collections.

Bags of singles

Main types and classes

The generic type IMiniBagSingles is the subtype of IMiniCollection that represents a collection of objects with no ordering. In a sequence, duplicate copies of the 'same' object (ie comparing using equals()) are distinguished by their index position. In a bag, duplicate copies may exist but cannot be distinguished from each other. The collection can therefore be represented using (key, cardinality) pairs (represented with IMiniKeyValuePair types), where the cardinality is the number of copies of the key in the collection.

Bags of Singles

As an IMiniCollection, an IMiniBagSingle provides all the IMiniCollection operations. The size() operation returns the total number of keys in the bag, ie the sum over the unique keys of the number of copies of each unique keys. removeDuplicates() removes any duplicate copies of the keys so that the cardinality associated with each key is 1. The IMiniBagSingle operations are:

• Add keys to the bag using add(K k).
  • If the key is added as a new member of the bag them this operation returns an InsertCheck.NEW. If the operation resulted in an existing key k' where k.equals(k') == true being overwritten, the operation returns InsertCheck.OVERWRITTEN. If the operation fails because of the problem in the underlying implementation the operation can return InsertCheck.FAILED.
• Remove one copy of a specified key, or all copies of a specified key. If there is only one copy of the key in the collection, removeOne has the same result as removeAll.
• Report the number of unique keys in the collection with uniqueKeySize() (size() returns the total number of keys, counting duplicate copies).
• Return a collection of the unique keys in the bag, or a collection of the (key,count) pairs. I have used IMiniSequences for return type.
• Return an IMiniBagSinglesIterator using a factory method.

AbstractMiniBagSingles provides a stub abstract class for implementors to extend. As for sequences, my implementation is through a bridge.

I use the decorator pattern again to be able to have concrete subclasses adding variations to the IMiniBagSingles behaviour. AbstractMiniBagSinglesDecorator composes an IMiniBagSingles (noting the GoF] stricture to keep the component class lightweight when using the decorator pattern).

MiniBagSinglesUniqueOnlyDecorator is the only concrete decorator in the design. The added behaviour is to remove existing members of the bag which compare equal to the new member after an add operation and thus ensure that there is only one copy of each unique key in the bag.

• add(K k) checks if the bag already contains a duplicate of the specified key and overwrites the existing copy if so. The post condition is that the specified key is added to the bag, and if there existed an element k' such that k.equals(k') == true then this has been overwritten and the operation has returned InsertCheck.OVERWRITTEN, else (no existing copy) the operation has returned InsertCheck.NEW.

Bridges and implementations

As with sequences, I wanted the flexibility to be able to use different bag implementations and to be able to change implementations dynamically if needed, so again I used a bridge pattern. AbstractMiniBagSinglesBridge composes an IMiniBagSinglesImplementation type and delegates its IMiniBagSingles operations to it. The bridge does not have to know what concrete implementation it is using. IMiniBagSinglesImplementation extends IMiniCollectionImplementation: the combined interface has to mirror the IMiniBagSingles interface. One consequence of the bridge pattern that the GoF do not mention is that it's better to work on the bridge only when the design of the abstraction you want to provide the implementation for is stable, or you end up having to make a lot of duplicate adjustments.

To get an implementation I adapt a Java Map to the IMiniBagSinglesImplementation interface, where the Map maps the key type K to Integer counts. To keep the flexibility to use adaptations of different Java Map subclasses I use an abstract object adaptor AbstractImplJCBagSinglesAdaptor which composes an instance of the Java Map adaptee type. The only concrete subclass I included will supply the HashMap implementation, and the details of instantiation of the concrete bridge and concrete implementation adaptors are delegated to the factories.

Iteration

An IMiniIterator iterating over an IMiniBagSingles will iterate over the (key, cardinality) pairs in the bag (ie current() will return an IMiniKeyValue pair of key and cardinality, or null if the iterator does not point to any current pair). The IMiniBagSinglesIterator extends IMiniIterator to add operations to return the currentKey and currentCount separately, and be able to remove the current (key,cardinality) pair - equivalent to calling removeAll for the current key. IMiniSequenceIterator is implemented by adapting a java.util.Iterator over the java.util.Set of Java.util.Map.Entry objects returned by the adaptee Map's entrySet() operation. The adaptation itself is clumsy and I am sure it could have been done better but I really just wanted to be able to use and test the design the the Bags of Singles. To get a java.util.Iterator type to return for the iterator() operation inherited from Iterable, and thus be able to for-each through the pairs in the bag, I adapted the IMiniBagSinglesIterator back to the Iterator interface, again using an object adaptor. I could have used the java.util.Iterator over the java.util.Set of Java.util.Map.Entry objects again but I would still have have had to do the work converting the Map.Entry types into my IMiniKeyValue pairs so that the type used by the for-each construct is the same as the type for IMiniBagSinglesIterator.current(), so it was more interesting to adapt the IMiniBagSinglesIterator type. As with the for-each Iterator for sequences, my ImplJCIteratorForBagSinglesAdaptor does not implement remove().