Trie Trie again

I finally got to refactor the Trie.  It bugged me that the interface was a bit complicated.  Then I realised that the Trie was doing two distinct jobs and that these could be separated.

The first job the trie was doing was creating a hierarchy of elements that stored objects according to a sequence of offsets.  In the case of a string, these offsets were the values of the characters in the string.

The second job was the creation of the sequence of offsets.  In the case of the string this is easy – iterate the characters of the string.  But in other circumstances we may wish to do differently.  For example dates could be represented as a series of integers: year, month, day, hour, minute, second.

Separating these jobs has simplified the interface, and made the code more versatile.  The sequence of indices is conveniently represented by a standard Iterator<Integer>.  For a string this is trivial:

public final class TrieStringIndexer implements Iterator<Integer> {
    private final String string;
    private int index = 0;

    public TrieStringIndexer(final String string) {
        this.string = string;
    }

    @Override
    public final boolean hasNext() {
        return this.index < this.string.length();
    }

    @Override
    public final Integer next() {
        return this.string.charAt(this.index++);
    }
}

Now with a string indexer we can store an object:

IndexTrie trie = new MutableIndexTrie();
Iterator<Integer> indexer = new TrieStringIndexer("abc etc");
trie.put(indexer, new Object());

You noticed the word ‘mutable’ did you?  IndexTrie is an abstract class with two concrete subclasses, one mutable one immutable.  The immutable version will never change existing data, but will return a new trie containing the same data as the original.  Any unchanged structure from the original is kept unchanged in the new trie.  The mutable one is, of course,  faster than the immutable one.

While we are on the subject of performance, I implemented a StringTrie – an ordered collection of strings implementing the Set interface. I compared the performance of this to the performance of TreeSet<String> which is the nearest equivalent standard class.  StringTrie was generally faster – up to five times as fast.

As usual the code is available at https://bitbucket.org/drphill/trie

State Modeling

State modeling is another very old software design technique.  It aims to model the way behaviour changes as a result of external input.

Now, the word ‘State’ is used in many ways when talking about software, and perhaps needs some definition first.  One way to think of  ‘state’ is as the perceived state of the system as judged from outside, perhaps called aggregate state.  Since facile analogies help here is one.  When the car is in the state ‘engine off’ then no amount of pressing the accelerator will get the car to move.  It does not matter if the handbrake is on, or the wheels are pointing straight ahead.  The handbrake setting and the wheel direction may be part of a complete description of the state of the car, but they matter little to us when deciding what to do next.  The ‘aggregate state’ is ‘engine off’ and there is only one trigger that will get us to the state of ‘engine running’.

Did you see that? I snuck in a new term – ‘trigger’.  A trigger is anything that causes (or could cause) the system to change state.  State modeling is about describing how the system responds to triggers.  Different combinations of trigger and state will have different results.  When a document editor is in the ‘editing’ state it will respond to key presses (‘triggers’) by changing the document,  but when it is in read-only mode it will ignore the same triggers (key presses).  Of course there is a special trigger that moves the editor from ‘read-only’ state to ‘editing’ state, and another that moves it back.  So you can see that triggers can change the state of the system, and the state determines its response to the triggers.

I have written a simple tool to illustrate this:  State Modeler.  It is written in java and requires Java 8 or higher.

The thing that I find most fascinating about state modeling is that, within a limited domain, a state model can be such a complete description that the behaviour can be automatically converted to code.  State Modeler does this, just to prove my contention, and will even generate a small testing class to demonstrate.

I will describe how to use the State Modeler in another post.  Please feel free to try it out before then if you wish.

 

 

DataFlow Modelling

DataFlow Modelling is a very old technique, at least in the computing world.  It seems to have fallen out of favour, replaced by more trendy state models or object models.  This is a shame as data flow diagrams are so simple and intutitive that they can be used without explanation, even with people that have not encountered them before.  Try that with a State model or an object model…….

One reason that data flow diagrams are not used so often is that the tools to draw them do not seem to be available readily.  To remedy this I have written a simple DataFlowModeller in Java for all to use.  It requires Java 8 to run.

Some notes here on how to use the tool.  Let us start to define a calculator:

The first task is to create a ‘Context Diagram’. This defines the way the calculator will interact with its environment. The large circle in the middle represents the program.

  • ‘Long press’ on the large circle and when the dialogue pops up choose the name ‘Caculator’.
  • Right click on the empty space and choose ‘New External’, select a name for it (e.g. User)and press ‘ok’. The user of the program is now represented in the design.
  • Click on the user to select it.  See that an arrow appears on the right hand side.  Drag the arrow to the ‘Calculator’ circle until the arrow and the circle glow green. Drop the arrow.
  • Name the data flow ‘Sums’.  You now show the user presenting sums to the calculator.
  • Now create a new external called ‘Screen’
  • Create a flow from the calculator to the screen, and call it results.

If you want to make a flow into a pleasing curve, then select it and drag part of the line.  This will create a ‘way-point’ in the flow that affects the curve of the line.  You can have as may way-points as you like in a flow.  You can remove a way-point by making it unnecessary. Do this by moving it to a position where it is on a straight line between the points either side. It will then disappear .

When you have designed the way that your calculator will interact with the world you can drill down to the detail of what goes on inside it.  To do this double click on the circle.  You will initially see a screen with a collection of arrows.  (These arrow may be sitting on top of each other, so you may need to drag them to different locations).  The arrows are the flows entering and leaving ‘Calculator’.

You can leave this view and go back to the context diagram either by double-clicking the empty background, or by pressing the up arrow in the menu bar.

In the exploded view you can add transforms (things that act on and change data) and data stores (places that the data rests, like files and databases).  You can connect these with flows to the entering and leaving flows.

Any transform you add can be ‘opened’ by double clicking and fleshed out in detail……

Enjoy