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 (full 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' when I was trying to keep track of 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.

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

The capabilities of the IMiniCollection are discussed here:

• enforcesUniqueness() is an 'interrogation' method (which enable a user to query the MiniCollection about characteristics which could influence the way that it performs its type behaviour, as discussed above). Some objects of the IMiniCollection type will only permit unique members. How this can be achieved within the IMiniCollections contract is discussed further below.
  • 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 subsequently changed to using Enums for all responses to interrogation methods because enums are more flexible and informative than booleans.
• An IMiniCollection can report on the number of elements in it (size()), whether it is is empty, whether it contains a specified element, the number of copies of a specified element it contains (count(E e)).
• An IMiniCollection also provides two 'destructive' operations: clearing (emptying) the entire container and removing all duplicate elements.
  • I had decided not to try to deal with unmodifiable collections (isUnmodifiable() not withstanding) 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 be an IMiniCollection operation.

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.

• The IMiniIterator type separates the command next() (moves the iterator to the next element in the collection) from the query (what element are you pointing to) current(). The existence of a next element to move to can be queried with hasNext().
• This initial design gave the IMiniIterator the capability to remove the current element (removeHere()). I subsequently decided that this restricted subtyping of IMiniIterator (was not very open for extension) and moved it down the type hierarchy (and changed the method name).
• 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.
• IMiniCollection subtypes have an equivalent subtype of IMiniIterator. This gives a parallel hierarchy which the use of the factory method to allow each IMiniCollection subtype to make its own iterator helps to resolve (as it does on 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 subclass 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.

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

• isCustomSorted() and isRandomAccess() are interrogation methods, discussed further below under the detail for the IMiniSequence types.
• add(E e) adds an element to the end of the sequence, 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.
• the getAtIndex, resetAtIndex, addAtIndex and removeAtIndex operations allow the client to read, reset, add or remove at a specified index position.
• the firstIndexOf, nextIndexOf, and lastIndexOf operations allow the client to find, successively, all occurrences of an element (one nextIndexOf starts from the beginning of the sequence, the other from a specified index).
• IMiniSequence has its own iterator subtype, IMiniSequenceIterator. This can go backwards as well as forwards. 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 index) returns an IMiniSequenceIterator whose current element is the element at the specified index position in the sequence.

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.

• The size() operation returns the total number of elements in the collection (ie a figure which would equal the cardinalities summed over all the keys) and is therefore consistent with the IMiniCollection contract.
• removeDuplicates() should effectively change the cardinality in each pair to 1.
• The IMiniBagSingles interface provides a way for clients to interact with the collection without having always think in terms of key-value pairs.
• add(K k) adds a copy of the key to the collection. If the key already exists, this effectively just increases the cardinality count by 1.
• remove(K k) was insufficiently clear to the client and I subsequently replaced this with removeOne(K k)(reduce cardinality by 1; remove from the collection if only one) and removeAll(K k) (remove (key k, cardinality) pair from the collection entirely).
• keySize() returns the number of unique elements (keys) in the collection (subsequently renamed to uniqueKeySize for clarity).
• getKeyCounts() returned a collection of (key,cardinality) pairs. I subsequently changed the name to getKeysAndCounts for clarity. The collection is returned as an IMiniSequence because I think that Sequences are the most straightforward collections to work with.
• bagIterator() should return an IMiniBagSingles-specific subtype of the IMiniIterator. I had not got my head around this type at the initial design stage so there is no actual interface for it shown.

IMiniBagPairs is the subtype of IMiniCollection that represents a collection of associations between objects ((key,value) pairs), with no ordering. As with an IMiniBagSingles, duplicate copies of the same association ((key,value) pair) can be present, but are indistinguishable. The elements of the collection can therefore be represented using ((key,value), cardinality) pairs (pairs within pairs), where the cardinality is the number of copies of the association in the collection.

• The size() operation returns the total number of associations in the collection (ie a figure which would equal the cardinalities summed over all the associations) and is consistent with the IMiniCollection contract.
• removeDuplicates() showed that I should have thought more carefully about having this as an IMiniCollections operation. To be consistent with the description of the collection and the behaviour of the operation for other subtypes, it should change the cardinality of each unique association to 1 but allow more than one association for each key.
• I altered most of the IMiniBagPairs added behaviour operations after this initial design. I found that it was only when I was implementing them that I could think through what they should do and how they fitted in with the supertype IMiniCollections contract. These other operations in the original design are therefore not discussed in detail here.
• bagIterator() should return an IMiniBagPairs-specific subtype of the IMiniIterator. As with IMiniBagSinglesIterator, I had not got my head around this type at the initial design stage so there is no actual interface for it shown.

The iterator

MiniIterator design

The Sequences

The MiniSequenceCollection design

Implementation of the adaptors for Sequences

Implementation and adaptor classes for the MiniSequenceCollection