Blog-Archiv

Dienstag, 27. Dezember 2016

Every Two Years' LINUX Upgrade

This Blog is about my impressions of an LINUX operating-system upgrade on my Netbook (= small weak laptop) from Lubuntu 14.04 LTS to 16.04. "LTS" means long-term-support, they guarantee you 5 years of minor upgrades. Nevertheless all two years a new major Ubuntu is released, and with it all its variants like Lubuntu (L = "Light").

The LINUX Experiment

LINUX somehow is like an experiment that tries out how many people can work together before the software they produce collapses (like the Tower of Babel did). They are working on a complex and living thing, it's an operating-system. Permanently new hardware has to be integrated and old to be maintained, permanently applications require new capabilities, to be provided by new and (!) old hardware.

Because I believe in this experiment, I always drive my computer by LINUX. It is fast, it is useful, it is free!

Just one thing frightens me periodically, and that's the major version upgrade. With Ubuntu, the currently leading free UNIX, this happens all two years. It was more than once that my LINUX did not boot any more after such an upgrade.

Why Upgrade?

Now you could say "Why being afraid? Just stay on your old version that works perfectly for your hardware!".

No, you can't. Because what you want to do most of all with your computer is use the internet, browse pages containing videos, and be on the always growing communication facilities. Internet applications demand more and more resources, and change technologies quickly and relentlessly.

  • Web browsers claim the operating system.
  • The operating system claims the hardware to do more and more,
  • and this claims us to upgrade.

So an operating system upgrade may not be enough, at some point in time you will even need to buy a new computer, just to be able to use the internet!

Version Information

First thing you want to find out is what operating system version you have. But there is not just one version, there are two versions.

  1. LINUX kernel version, e.g. 4.4.0-34-generic
  2. Ubuntu version, e.g. 16.04

These versions rarely can be seen together:

  • any UNIX kernel version can be displayed by the command-line 
    uname -a
  • the Ubuntu version can be displayed by clicking system-menu "System Settings" - "Details".
    In Lubuntu, this can be found in system-menu under "System Tools" - "System Performance and Benchmark" - "Operating System".

Online Upgrade

Already having a LINUX on your computer, you can upgrade online over the internet. Just search for the "Software Update" menu item in your system menu. It will automatically search for updates as soon as launched, and present you a list of updates. And it will also report possible kernel upgrades.

Before you make a major version upgrade, be sure that all minor updates are installed. Also make a backup of /boot/grub/grub.cfg, in case you modified this to get a smarter boot menu.

When you started the major upgrade, it runs the same way as the minor upgrade, with the difference that a restart is required after.

Be aware that your computer is now in a critical state, make sure this upgrade is not interrupted, and your internet connection can endure this!

Some Upgrade Observations

The upgrade-tool told me that it's installing the new Ubuntu, not Lubuntu. Which was not nice, because I know that Ubuntu does not work on my Netbook, the hardware is too weak. Finally it turned out that it was NOT an upgrade to Ubuntu ....

To watch upgrade-progress, I clicked into the dialog to open the log messages terminal. Strange things appeared here: 

....

This likely means that your installation is broken. Try running the command
....

So some upgrade author decided to break the whole installation?!
These messages seem to not mean what they say. A common appearance in software development. It looks like LINUX experts are already used to such wrong alerts. I decided to ignore them, because the terminal messages are not even visible by default.

Another thing are these GUI-dialogs suddenly coming up and asking you for "Yes" or "No". You have been going to the kitchen while these downloads proceed so slowly, being back you find it not continued.

So still you need to attend such an upgrade, you can not simply let it run.

While watching the terminal log messages I suddenly saw red and blue text on bottom, and no more progress. A closer look showed me that the upgrader again is waiting for my decision, this time not through a GUI-dialog but a terminal-dialog (programmed using the curses-library, the Debian guys do such things). You can not commit such a dialog by mouse. You need to navigate to the OK button using the TAB key, and then press ENTER on it.

So be prepared for all kinds of oddities here. Considering that the log messages terminal not even is visible by default, this is quite demanding!

Summary

After all, my desktop survived the upgrade, and even the boot menu was not again filled with unneeded old version items.
So far the experiment ran quite well :-)

LINUX upgrades always grew stabler over the years, especially since Ubuntu. Hope this will keep on, without LINUX this planet would be a lot darker.




Keine Kommentare:

Sonntag, 4. Dezember 2016

Java TreeMap Comparator Gotcha

You use the Java Comparator interface when you need a certain sort-order in some container. But Comparator does not only declare compare(o1, o2), it implicitly also declares equality of o1 and o2, which is the case when the comparator returns zero (0).

This will not affect you as long as you don't reuse your comparators with different kinds of containers like ArrayList or TreeMap. But when, you may experience the TreeMap gotcha:

Example Source


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.Comparator;
import java.util.TreeMap;

public class TreeMapComparatorTest
{
    public static void main(String[] args) throws Exception {
        final String[] toSort = {
                "start",
                "end",
                "employee.name",
                "job.name",
        };

        final Comparator<String> comparator = new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return removeAllPrefixes(s1).compareTo(removeAllPrefixes(s2));
            }

            private String removeAllPrefixes(String s) {
                final int i = s.lastIndexOf(".");
                return (i >= 0) ? s.substring(i + 1) : s;
            }
        };

        final TreeMap treeMap = new TreeMap(comparator);

        for (String s : toSort)
            treeMap.put(s, "dummy-value");

        if (treeMap.size() != toSort.length)
            throw new IllegalStateException(
                    "Lost some values (" + toSort.length +
                    ") when using TreeMap (" + treeMap.size() + ") !");
    }
}

What I do here is sort some strings which represent property-names. But I want the "xxx.name" properties to stay together, which would not be the case when using an alphabetical sort order, because then "end" would go between "employee.name" and "job.name". Following is the order I want to achieve (whereby the order of "xxx.name" properties does not matter):

  • "end"
  • "employee.name"
  • "job.name"
  • "start"

So I implemented a Comparator that generates such a sort order. It cuts away anything before the last dot, and only then compares the two elements. And it actually works when used with an ArrayList!

But not with TreeMap. When you try out the source code above, you'll see that it throws the IllegalStateException: 

Exception in thread "main" java.lang.IllegalStateException: Lost some values (4) when using TreeMap (3) !
 at TreeMapComparatorTest.main(TreeMapComparatorTest.java:32)

When you output the keys of the map, you'll see that one of the "name" properties is missing:

  • "end"
  • "employee.name"
  • "start"

What's happening here?

Responsibilities

I had in mind that comparators are responsible for sorting. That's true, but not the whole truth.

Let's look at the JavaDoc of the compare(T o1, T o2) method of interface Comparator<T>:

Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

In the foregoing description, the notation sgn(expression) designates the mathematical signum function, which is defined to return one of -1, 0, or 1 according to whether the value of expression is negative, zero or positive.

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.)

The implementor must also ensure that the relation is transitive: ((compare(x, y) > 0) && (compare(y, z) > 0)) implies compare(x, z) > 0.

Finally, the implementor must ensure that compare(x, y) == 0 implies that sgn(compare(x, z)) == sgn(compare(y, z)) for all z.

It is generally the case, but not strictly required that (compare(x, y) == 0) == (x.equals(y)). Generally speaking, any comparator that violates this condition should clearly indicate this fact. The recommended language is "Note: this comparator imposes orderings that are inconsistent with equals."

That's how responsibilities are defined by scientists. Maybe you did as me and stopped reading that complicated text at about 50%. Then you missed the important part that partially explains what happens in the TreeMap gotcha.

It is generally the case, but not strictly required that (compare(x, y) == 0) == (x.equals(y)).

Consequence

What does that mean? You'll find clarity only when you debug TreeMap.put(). Here is an excerpt of its source code: 

                int cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);

You see that this implementation uses the comparator (variable cpr) to detect equal keys. A Map does not allow duplicate keys. Thus it replaces the old value of the key by the new one. And - as a side effect - you lost one element!

As recommended above, you should have added some JavaDoc to your comparator:

"Note: this comparator imposes orderings that are inconsistent with equals."

But would this really have helped :-?

Responsibility Meets Context

You can find a discussion of this gotcha also on stackoverflow. As I said, it will happen when you use Comparator implementations in different contexts:

  • in the context of an ArrayList that allows duplicates, the comparator will work,
  • but in the a context of TreeMap that allows no duplicates, it might not work.

This "might" is the stuff that unreproducible bugs are made of.

Solution

Following is a workaround: 

        final Comparator<String> comparator = new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                final int result = removeAllPrefixes(s1).compareTo(removeAllPrefixes(s2));
                return (result == 0 && s1.equals(s2) == false) ? 1 : result;
            }

            .....
        };

This implementation of compare() avoids to return zero when the given arguments are not equal. Thus "job.name" would not be considered to be equal to "employee.name", and not be removed as duplicate. Nevertheless the sort order is sufficient now:

  • "end"
  • "employee.name"
  • "job.name"
  • "start"



Keine Kommentare:

Sonntag, 27. November 2016

Framework as seen from Java, Part 3

Frameworks consist of a number of classes working together, containing some reusable logic, be it presentation-, business- or persistence-logic. In this Blog I will present an example framework that builds homes of any kind, in other words, the framework's logic is "building houses".

As you may guess, the classes working together here will be walls, roofs, doors and so on. To be able to build homes of any type, any new operator in the framework must be encapsulated into a protected factory method. Only that way the framework can be customized and reused entirely. (Exception is the allocation of standard data types like Integer, String, Boolean etc.)

How to Build a Home

The encapsulated home-building business logic is

  • creating 4 walls
  • erecting them
  • making a door into one of them
  • covering them with a roof.

Homes can be houses, tents, wooden huts, ... all of them will be built the same way.

So here is that logic in an abstract class. To make it short, I left out the imports and JavaDoc (mind that you always should write documentation for public and protected classes, methods and fields!). 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public abstract class Home
{
    public final void build()    {
        System.out.println("==== Starting to build "+this+" ====");
        
        final List<Wall> walls = new ArrayList<>();
        for (int i = 1; i <= 4; i++)
            walls.add(newWall(i));
        
        erectWalls(walls);
        
        walls.get(0).setDoor();
        
        final Roof roof = newRoof();
        coverWithRoof(walls, roof);
        
        System.out.println("==== Finished building "+this+" ====");
    }
    

    protected abstract Wall newWall(int number);
    
    protected abstract Roof newRoof();
    
    
    private void erectWalls(List<Wall> walls) {
        for (Wall wall : walls)
            System.out.println("Erecting wall "+wall);
    }
    
    private void coverWithRoof(List<Wall> walls, Roof roof) {
        System.out.println("Covering with "+roof+": "+walls);
    }

    @Override
    public String toString() {
        return getClass().getSimpleName();
    }
}

These are the factory methods, creating walls and roof: 

    protected abstract Wall newWall(int number);
    
    protected abstract Roof newRoof();

Here comes an abstract wall for that home. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public abstract class Wall
{
    public interface Door
    {
    }
    
    protected final int number;
    
    protected Wall(int number) {
        this.number = number;
    }
    
    protected void setDoor()    {
        final Door door = newDoor();
        System.out.println("Building "+door+" into "+this);
    }
    
    protected abstract Door newDoor();

    @Override
    public String toString() {
        return getClass().getSimpleName()+" "+number;
    }
}

Any wall could have a door, modelled as inner interface. Again a factory method is responsible for creating it, in case setDoor() gets called: 

    protected abstract Door newDoor();

Here comes the roof, as interface, so that walls also could implement roofs, useful for tents. 

1
2
3
public interface Roof
{
}

We could set a material property into this, to show the roof's reliability.

Frameworking a House

Until now we just got abstract classes and interfaces. Not a very good shelter, time to get concrete :-) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public class House extends Home
{
    @Override
    protected Wall newWall(int number) {
        return new BrickWall(number);
    }
 
    @Override
    protected Roof newRoof() {
        return new TiledRoof();
    }
}

Just the factory methods are implemented, and the according classes. Very short and concise. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
public class BrickWall extends Wall
{
    private static class WoodenDoor implements Door
    {
        @Override
        public String toString() {
            return getClass().getSimpleName();
        }
    }
    
    
    public BrickWall(int number) {
        super(number);
    }
    
    @Override
    protected Door newDoor() {
        return new WoodenDoor();
    }
    
}

This wall is made of bricks and got a wooden door. The following roof is covered with tiles. 

1
2
3
4
5
6
7
public class TiledRoof implements Roof
{
    @Override
    public String toString() {
        return getClass().getSimpleName();
    }
}

Test code: 

1
2
3
4
5
6
public class Demo
{
    public static void main(String[] args) {
        new House().build();
    }
}

Output is: 

==== Starting to build House ====
Erecting wall BrickWall 1
Erecting wall BrickWall 2
Erecting wall BrickWall 3
Erecting wall BrickWall 4
Building WoodenDoor into BrickWall 1
Covering with TiledRoof: [BrickWall 1, BrickWall 2, BrickWall 3, BrickWall 4]
==== Finished building House ====

With this house we are ready for the rainy season :-)

Frameworking a Tent

In summer we prefer to enjoy fresh air by living in a tent. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public class Tent extends Home
{
    @Override
    protected Wall newWall(int number) {
        return new TextileWall(number);
    }

    @Override
    protected Roof newRoof() {
        return new TextileWall(0);
    }

}

A wall is used also as roof of the tent. There is no separate door, it is cut into the wall, thus the setDoor() override. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public class TextileWall extends Wall implements Roof
{
    public TextileWall(int number) {
        super(number);
    }
    
    @Override
    protected void setDoor() {
        System.out.println("Cutting a zipper door into "+this);
    }
    
    @Override
    protected Door newDoor() {
        return null;
    }
}

Test code: 

1
2
3
4
5
6
public class Demo
{
    public static void main(String[] args) {
        new Tent().build();
    }
}

This outputs: 

==== Starting to build Tent ====
Erecting wall TextileWall 1
Erecting wall TextileWall 2
Erecting wall TextileWall 3
Erecting wall TextileWall 4
Cutting a zipper door into TextileWall 1
Covering with TextileWall 0: [TextileWall 1, TextileWall 2, TextileWall 3, TextileWall 4]
==== Finished building Tent ====

Frameworking a Phantasy Home

What can be done with named classes can also be done using anonymous classes. Following example shows the real power of overriding.

Thanks to factory-methods you can customize the framework down to any level, here down to the wall's door. Mind how overrides nest into other overrides. Method overrides contain anonymous class overrides, that again contain method overrides.

Might be a little hard to read, but this is the framework style. Summit of OO in my opinion, because you can reuse not just one class but a whole set of them. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Demo
{
    public static void main(String[] args) {
        new Home()  {
            @Override
            protected Roof newRoof() {
                return new Roof() {
                    public String toString() {
                        return "Phantasy Roof";
                    }
                };
            }
            
            @Override
            protected Wall newWall(int number) {
                return new Wall(number) {
                    @Override
                    protected Door newDoor() {
                        return new Door()   {
                            public String toString() {
                                return "Phantasy Door";
                            }
                        };
                    }
                    public String toString() {
                        return "Phantasy Wall "+number;
                    }
                };
            }
            
            public String toString() {
                return "Phantasy Home";
            }
        }.build();
    }
}

Output is: 

==== Starting to build Phantasy Home ====
Erecting wall Phantasy Wall 1
Erecting wall Phantasy Wall 2
Erecting wall Phantasy Wall 3
Erecting wall Phantasy Wall 4
Building Phantasy Door into Phantasy Wall 1
Covering with Phantasy Roof: [Phantasy Wall 1, Phantasy Wall 2, Phantasy Wall 3, Phantasy Wall 4]
==== Finished building Phantasy Home ====

So, isn't frameworking an alternative to networking :-?
You just need to state what you want, the framework will call you and make something of whatever you return.




Keine Kommentare:

Montag, 21. November 2016

Framework as seen from Java, Part 2

This is the continuation of my recent article about frameworks where I showed the problems when trying to reuse the three lines of Swap code with different types of containers.

In this Blog, Swap will be rewritten to become a real framework with abstraction and code-reusage.

Swap Abstraction

Here comes an abstract Swap that will work for any type of Java container. This base class is abstract because it makes no sense to use it standalone. It defines the responsibilities of the outer world using an inner interface Container. Every sub-class needs to implement that interface to be able to reuse Swap. There will be a sub-class per container type, like array, list, linked set. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public abstract class Swap<T>
{
    /** Clients of Swap must implement this. */
    public interface Container<E>
    {
        E get(int index);
        
        void set(int index, E element);
        
        int size(); // needed just for index-assertions
        
        void close();   // extra for LinkedHashSet that must reorganize completely
    }
    
    protected final void performSwap(Container<T> container, int index1, int index2)  {
        if (index1 == index2)   // fast and easy: nothing to do
            return;
        
        // uncover mistakes early
        if (index1 < 0 || index2 < 0 || index1 >= container.size() || index2 >= container.size())
            throw new IllegalArgumentException("Swap-indexes out of bounds!");
        
        // perform swapping
        final T element1 = container.get(index1);
        container.set(index1, container.get(index2));
        container.set(index2, element1);

        container.close();
    }
}

The Container interface requires get() to retrieve an element at a specified index, set() to put an element to a specified index, size() to assert given indexes, and it also demands close() to give problematic containers like LinkedSet a chance to reorganize completely.

The method performSwap() is there to be called by sub-classes, not to be overridden, thus it is final. It provides nice assertions that are done here once-and-only-once. Then it performs the famous three swap statements. Finally it calls close() on the container interface.

Now let's see if we can derive swaps for all container types from this with acceptable effort.

Array Swap


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class SwapInArray<T> extends Swap<T>
{
    private class ArrayContainer implements Container<T>
    {
        private T [] array;
        
        public ArrayContainer(T [] array) {
            this.array = array;
        }
        
        @Override
        public int size() {
            return array.length;
        }
        @Override
        public T get(int index)   {
            return array[index];
        }
        @Override
        public void set(int index, T element)   {
            array[index] = element;
        }
        @Override
        public void close() {
        }
    }
    
    public void swap(T [] array, int index1, int index2)  {
        performSwap(new ArrayContainer(array), index1, index2);
    }
}

The ArrayContainer implementation adapts an array to be a Swap.Container. Accessing indexes is easy, size also, close is not needed. All this class does is wrapping the given array into an ArrayContainer and call super.performSwap().

List Swap


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.List;

public class SwapInList<T> extends Swap<T>
{
    private class ListContainer implements Container<T>
    {
        private List<T> list;
        
        public ListContainer(List<T> list) {
            this.list = list;
        }
        
        @Override
        public int size() {
            return list.size();
        }
        @Override
        public T get(int index)   {
            return list.get(index);
        }
        @Override
        public void set(int index, T element)   {
            list.set(index, element);
        }
        @Override
        public void close() {
        }
    }
    
    public void swap(List<T> list, int index1, int index2)  {
        performSwap(new ListContainer(list), index1, index2);
    }
}

The ListContainer implementation was also very easy to implement. Nearly the same as array, but using get() and set() methods. You can see at a glance that there are no errors in that code.

Linked Set Swap


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.ArrayList;
import java.util.List;
import java.util.Set;

public class SwapInLinkedSet<T> extends Swap<T>
{
    private class LinkedSetContainer implements Container<T>
    {
        private Set<T> linkedSet;
        private List<T> clone;
        
        public LinkedSetContainer(Set<T> linkedSet) {
            this.linkedSet = linkedSet;
            this.clone = new ArrayList<T>(linkedSet);
        }
        
        @Override
        public int size() {
            return linkedSet.size();
        }
        @Override
        public T get(int index)   {
            return clone.get(index);
        }
        @Override
        public void set(int index, T element)   {
            clone.set(index, element);
        }
        @Override
        public void close() {
            linkedSet.clear();
            
            for (T element : clone)
                linkedSet.add(element);
        }
    }
    
    public void swap(Set<T> linkedSet, int index1, int index2)  {
        performSwap(new LinkedSetContainer(linkedSet), index1, index2);
    }
    
}

Here we have the problematic LinkedHashSet that does not support access to indexes, it just provides iteration. But all the loops and conditions from its recent implementation are gone, replaced by a backing ArrayList that performs the index access. The ArrayList constructor receiving the Set adds all elements of the set, in their iteration-order. This implementation can not work without the close() call, because it must clear and rebuild the entire collection after swapping. But it does this elegantly by looping the backing list.

Mind that this solution is safe just for one swap. When the Set would be changed, the backing list would be out-of-date.

Demo Code

To close the swap story, here is some code that you can use to test above classes. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class Demo
{
    public static void main(String[] args) {
        new Demo();
    }

    private Demo() {
        arrayDemo();
        listDemo();
        linkedSetDemo();
    }

    private void arrayDemo() {
        final Integer[] integerArray = new Integer[] { 0, 1, };
        System.out.println("Before array swap: "+Arrays.asList(integerArray));
        
        new SwapInArray<Integer>().swap(integerArray, 0, 1);
        
        System.out.println("After array swap: "+Arrays.asList(integerArray));
    }

    private void listDemo() {
        final List<String> stringList = new ArrayList<>();
        stringList.add("A");
        stringList.add("B");
        stringList.add("C");
        stringList.add("D");
        stringList.add("E");
        System.out.println("Before list swap: "+stringList);
        
        new SwapInList<String>().swap(stringList, 1, 3);
        
        System.out.println("After list swap: "+stringList);
    }

    private void linkedSetDemo() {
        final Set<Float> floatList = new LinkedHashSet<>();
        floatList.add(1.0f);
        floatList.add(100.0f);
        floatList.add(10000.0f);
        System.out.println("Before linkedSet swap: "+floatList);
        
        new SwapInLinkedSet<Float>().swap(floatList, 1, 2);
        
        System.out.println("After linkedSet swap: "+floatList);
    }
}

This outputs: 

Before array swap: [0, 1]
After array swap: [1, 0]
Before list swap: [A, B, C, D, E]
After list swap: [A, D, C, B, E]
Before linkedSet swap: [1.0, 100.0, 10000.0]
After linkedSet swap: [1.0, 10000.0, 100.0]

Resume

Defining the responsibilities of the outer world as an inner interface or abstract class is a really useful technique. That way the responsibilities are tightly coupled to the class. Any implementation is then free to fulfill them in its own way.

None of the shown classes contains long and hacky methods with complicated loops and conditions. Thus they will contain no mistakes. I call this a clean solution, easy to read and simple to verify.

So, I was able to create a Swap framework with real abstraction and reusage. But there is more to frameworks, because not everything can be done so simply. Frameworks also provide access to the sometimes complex interactions between classes.

My next example framework will contain several classes playing together. It will demonstrate the importance of a fundamental framework technique called Factory Method. There is no real framework without this pattern, because the object of one class allocates objects of other classes, and you want to determine those classes by overrides. This is possible only by encapsulating the new operator into a protected factory method.

You guessed right, I will do this in my next Blog article about frameworks as seen by Java (end titles music playing :-).




Keine Kommentare:

Sonntag, 20. November 2016

Framework as seen from Java, Part 1

The term "Framework" is somehow overburdened with individual and company-specific meanings. When you hear this word, it could designate ....

  • an expensive software product of a big company that solves every problem everywhere when experts of that company configure it to do so
  • a software engine that you can build houses with, but also igloos or space ships
  • a set of template sources for Copy & Paste Programming
  • a class the chief programmer implemented, to be extended by any application class instead of java.lang.Object
  • the API of a set of libraries
  • for example, the Java Development Kit
  • and also the Java Collections library

Little bit of truth in all of them?
Wikipedia states that it is ....

  • an abstraction in which software providing generic functionality can be selectively changed by additional user-written code

  • a universal, reusable software environment that provides particular functionality as part of a larger software platform to facilitate development

  • may include support programs, compilers, code libraries, tool sets, and application programming interfaces

A Framework must be something big and complex. That's the impression you get from literature. I believe that "Framework" expresses the undefined hopes and visions of software thinkers, similar to "Component". There is no precise and generally accepted definition of this term. I stick to the old Catalysis way to understand it. But they talk on UML level, and I want to give the view of a Java developer. For me, framework means Reusability by Abstraction.

The Smallest Framework Ever

"Swapping" abstracts the interchange of two elements in an ordered container. Widely used in books about software to explain generic types. Swapping is needed for example in sort-algorithms. Its responsibility:

  1. In a container (array, list, ...) you have two elements at certain indexes, and you want to exchange them, so that element 1 is where element 2 was before, and vice versa.
  2. It is not possible to return a new container, swapping must be done directly in the given container
 
        final Integer[] array = ....;
        final int index1 = ....;
        final int index2 = ....;

        final Integer element1  = array[index1];
        array[index1] = array[index2];
        array[index2] = element1;

The problem is that you want to implement the swapping of two elements generically once-and-only-once, and you want it strongly typed. But there is a small problem in the few lines of code to do that.

  • When you replace element 1 by element 2, you need to remember element 1, because you need to put it on the place where element 2 has been.
  • For this you need a local variable that remembers element 1, and that variable needs to have the same type as the element, else it would not be possible to set it into the strongly typed container.

So you either need to hard-code swapping for every thinkable element-type that may need such, or you have a language mechanism that allows generic types. Generic types were introduced in Java 1.5. They make it possible to use an arbitrary (generic) type T instead of a specific type Integer. In older Java-versions you could have done this using the "generic" Java super-class java.lang.Object, but this would not have been type-safe. When using Java generics, the compiler checks the type of the elements that should be in the container, and all related code working on them.

In the following, I use Java generics to implement a type-safe and though generic swap. 

public class Swap<T>
{
    public void swap(T [] array, int index1, int index2)  {
        final T element1  = array[index1];
        array[index1] = array[index2];
        array[index2] = element1;
    }
}

Here is some test-code to try this out. 

public class Demo
{
    public static void main(String[] args) {
        final Integer[] integerArray = new Integer[] { 0, 1, };
        System.out.println("Before array swap: "+Arrays.asList(integerArray));
        
        new Swap<Integer>().swap(integerArray, 0, 1);
        
        System.out.println("After array swap: "+Arrays.asList(integerArray));
    }
}

Output is: 

Before array swap: [0, 1]
After array swap: [1, 0]

Extensions

You might ask now "Where is reusability and abstraction?". Abstraction was done by the Java generics. In case of reusability, you're right. I can not reuse these three lines of code for e.g. List. Nevertheless I can write another Swap that cares about java.util.List. It makes no sense to extend Swap, because there is nothing reusable in it.

List

import java.util.List;

public class SwapInList<T>
{
    public void swap(List<T> list, int index1, int index2)  {
        final T element1  = list.get(index1);
        list.set(index1, list.get(index2));
        list.set(index2, element1);
    }
}

Test-code: 

        final List<String> stringList = new ArrayList<>();
        stringList.add("A");
        stringList.add("B");
        stringList.add("C");
        stringList.add("D");
        stringList.add("E");
        System.out.println("Before list swap: "+stringList);
        
        new SwapInList<String>().swap(stringList, 1, 3);
        
        System.out.println("After list swap: "+stringList);

Outputs: 

Before list swap: [A, B, C, D, E]
After list swap: [A, D, C, B, E]

Unfortunately there is no Java interface that makes array and list interchangeable. I must access the array by indexing, and the list by calling get() and set().

Linked Set

There is another ordered Java container that may need swapping. Other than List, a Set contains no duplicates, and has no order. LinkedHashSet is different, it keeps the order in which elements were added.

Working with Set means you have no get() and set(). Again we need another implementation for swapping elements. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.LinkedHashSet;
import java.util.Set;

public class SwapInLinkedSet<T>
{
    public void swap(Set<T> linkedSet, int index1, int index2)  {
        if (index1 == index2)   // fast and easy: nothing to do
            return;
        
        // uncover mistakes early
        if (index1 < 0 || index2 < 0 || index1 >= linkedSet.size() || index2 >= linkedSet.size())
            throw new IllegalArgumentException("Swap-indexes out of bounds!");
        
        // retrieve elements at given indexes
        int i = 0;
        T element1 = null;
        T element2 = null;
        for (final T element : linkedSet) {
            if (i == index1)
                element1 = element;
            else if (i == index2)
                element2 = element;
            
            i++;
        }
        
        // create a clone and clear the original set
        final LinkedHashSet<T> clone = new LinkedHashSet<>(linkedSet);
        linkedSet.clear();
        
        // establish new order in original set
        i = 0;
        for (final T element : clone) {
            if (i == index1)
                linkedSet.add(element2);
            else if (i == index2)
                linkedSet.add(element1);
            else
                linkedSet.add(element);
            
            i++;
        }
    }
}

Oops, these are definitely more than three lines. Unfortunately the nature of Java Set makes it impossible to access specific indexes. That is the reason why we need two loops: first loop retrieves the elements to be swapped, second loop (over a clone) establishes the new order after having cleared the set completely. 

        final Set<Float> floatList = new LinkedHashSet<>();
        floatList.add(1.0f);
        floatList.add(100.0f);
        floatList.add(10000.0f);
        System.out.println("Before linkedSet swap: "+floatList);
        
        new SwapInLinkedSet<Float>().swap(floatList, 1, 2);
        
        System.out.println("After linkedSet swap: "+floatList);

This test code outputs: 

Before linkedSet swap: [1.0, 100.0, 10000.0]
After linkedSet swap: [1.0, 10000.0, 100.0]

Summary

These swaps maybe were examples for the abstraction that Java generics provide, but not for implementation abstraction, and definitely not for reusability. We had to use three different implementations for three different Java container types. Can we do better? You guessed right, I will try this in my next Blog article about frameworks as seen by Java.




Keine Kommentare:
Abonnieren Posts (Atom)