Patterns: the Decorator pattern

[JosAH]

Greetings,

last week we talked a bit about the Visitor design pattern. This week we'll
talk a bit about additional functionality that is sometimes wanted, i.e.
the functionality is optional. Assume there is a lot of optional functionality
that people want.

This article discusses the Decorator (or 'Wrapper') pattern. For the sake of
the example we'll use array manipulation. People always fiddle diddle with
arrays, i.e. they copy values from one array to another, move elements around
in arrays etc. etc. as if there were no Object Oriented programming.

Since the early days of Fortran people have been messing around with arrays
and mutilating those poor processors that have to copy data over and over
all the time.

Let's do something about it: The following interface is an abstraction of
an array:

public interface Sequence<T> {
    public int length();
    public T get(int idx);
    public void set(T, int idx);
}

A Sequence has a length and we can get and set elements in a Sequence; nothing
spectacular. Note that this interface is a generic interface: the Sequence
manipulates elements of type 'T'.

Let's encapsulate a simple array:

public class ArraySequence<T> implements Sequence<T> {
 
    // the encapsulated array:
    private T[] array;
 
    // the constructor:
    public ArraySequence(T[] array) { this.array= array; }
 
    // interface implementation:
    public int length() { return array.length; }
    public T get(int idx) { return array[idx]; }
    public void set(T elem, int idx) { array[idx]= elem; }
}

Why build all that code for just a simple array? We could've used the array
itself in the first place, so why all this complicated stuff? This is why:
sometimes we want to manipulate arrays but we don't want to copy and move
and swap all those elements over and over again: we build Decorators for it
instead. The ArraySequence class does nothing special: it simply encapsulates
an array for us. Let's build an abstract class from which we can easily build
other concrete Sequence implementations:

public abstract class AbstractSequence<T> implements Sequence<T> {
    // another sequence:
    protected Sequence<T> seq;
 
    // an abstract method that gives us an index value:
    protected abstract int index(int idx);
 
    // the constructor:
    public AbstractSequence(Sequence<T> seq) { this.seq= seq; }
 
    // interface implementation:
    public int length() { return seq.length(); }
    public T get(int idx) { return seq.get(index(idx)); }
    public void set(T elem, int idx) { seq.set(elem, index(idx)); }
}

The class by itself can't do anything (it's abstract), but it gives us all
the functionality we need for concrete Sequence implementations. The following
Sequence treats all elements of a Sequence in reverse order:

public class ReverseSequence<T> extends AbstractSequence<T> {
    // implementation of index() method:
    protected int index(int idx) { return seq.length()-idx-1; }
 
    // the constructor:
    public ReverseSequence(Sequence<T> seq) { super(seq); }
}

You see no interface implementation in this class because everything already
was implemented by the AbstractSequence; all that this class implements is
the index() method which gives the additional functionality. Note that the
encapsulated 'seq' Sequence is passed to the superclass in the constructor.

If you create a ReverseSequence, given another Sequence you can treat the
other Sequence as if it were reversed (i.e. last element first and vice versa).
The added functionality is implemented in the index() method. Here's a bit
of code that shows how it's used:

    Integer[] a= { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
    Sequence rev= new ReverseSequence<Integer>(
                new ArraySequence<Integer>(a));
    ...
    for (int i= 0, n= rev.length(); i < n; i++)
        System.out.print(rev.get(i)+" ");
    System.out.println();

The output is: 9 8 7 6 5 4 3 2 1 0
From the snippet above you can see why a Decorator is also named a Wrapper:
the Sequence objects 'wrap' other Sequence objects (passed to the constructors).
Also note from the snippet above that our code didn't touch the array directly
anymore after we've wrapped it in a Sequence.

Here's another Sequence implementation: it puts the elements from the first
part of the other Sequence interleaved with the elements from the last part
of the sequence:

public class MergeSequence<T> extends AbstractSequence<T> {
    // implementation of index() method:
    protected int index(int idx) { 
        if ((idx&1) == 0) return idx/2; // idx is even
        return (seq.length()+idx)/2; // idx is odd
    }
 
    // the constructor:
    public MergeSequence(Sequence<T> seq) { super(seq); }
}

If you use the code snippet above but use a MergeSequence instead of a
ReverseSequence the output will be: 0 5 1 6 2 7 3 8 4 9. I leave it up to
you what the output will be if you wrap your original array in both an
MergeSequence and a ReverseSequence as in:

Sequence magic= new MergeSequence<Integer>(
            new ReverseSequence<Integer>(
                new ArraySequence<Integer>(a)));

I also leave it up to you to figure out if it would make any difference if
you'd used this wrapping order instead:

Sequence magic= new ReverseSequence<Integer>(
            new MergeSequence<Integer>(
                new ArraySequence<Integer>(a)));

Note that if you wanted to do what these two Wrappers do using just a simple
array you have to play clever tricks and/or use temporary array(s) to hold the
intermediate results.

Here's a bit more complicated Sequence: it catenates two other sequences as
if they were just one bigger Sequence. We do have some work to do in the
implementation of the interface methods for this class so we don't
extend from the AbstractSequence. Here goes:

public class CatenateSequence<T> implements Sequence<T> {
    // the first and second Sequence:
    private Sequence<T> first, second;
 
    // little helper method:
    private boolean isFirst(int idx) { return idx < first.length(); }
 
    // implementation of index() method:
    private int index(int idx) { 
        if (isFirst(idx)) return idx;
        return idx-first.length();
    }
 
    // the constructor:
    public CatenateSequence(Sequence<T> first, Sequence<T> second) {
        this.first = first;
        this.second= second;
    }
 
    // interface implementation:
    public int length() { return first.length()+second.length(); }
    public T get(int idx) { 
        if (isFirst(idx)) return first.get(index(idx));
        return second.get(index(idx)); 
    }
    public void set(T elem, int idx) {
        if (isFirst(idx)) first.set(elem, index(idx));
        else second.set(elem, index(idx));
    }
}

The last piece of code shows how we can catenate three arrays together
using the CatenateSequence Wrapper:

Integer[] a= { 0, 1, 2 };
Integer[] b= { 3, 4, 5 };
Integer[] c= { 6, 7, 8, 9 };
...
Sequence cat= new CatenateSequence<Integer>(
            new ArraySequence<Integer>(a),
            new CatenateSequence<Integer>(
                new ArraySequence<Integer>(b),
                new ArraySequence<Integer>(c)));

If you print this Sequence, the output again will be: 0 1 2 3 4 5 6 7 8 9.

Note that sneakily I used another design pattern too for the CatenateSequence
class: the Composite pattern. But we'll talk in a next tip about that one.

Guess what a mess we can make if we wrap the CatenateSequence in the other
Sequences again. Note that not a single array element is moved or copied.
We add functionality at will by wrapping up a Sequence in another Sequence
that implements the functionality for us. We can wrap Sequences in any
order we want and thus we can accomplish any functionality we want. We now
have three classes:

1: ReverseSequence
2: MergeSequence
3: CatenateSequence

If we had implemented any or all of those functionalities using separate
classes we would've ended up with a big number of classes. Now we only
have three of them which we can combine in any order we want and as many
as we want. (I've excluded the ArraySequence class in the count because we
always need it to encapsulate raw, simple arrays).

The Readers, Writers, InputStreams and OutputStreams in the Java core classes
are implemented in a similar way: you wrap (or 'decorate') byte or character
streams using all these wrappers. Each wrapper adds a bit of functionality if
you need it.

Next time we talk a bit about the why and when we can or cannot use inheritance
of implementation (extend a class from another one). The results may be
surprising now and then.

kind regards,

Jos