Simple light barrier – Part 2

Currently, until August, I’m writing on my Bachelor thesis, so I have not much spare time for researching and writing blog posts.

I tested out my light barrier circuit as described in Simple light barrier ā€“ Part 1, but it did not work. The LED I used to inidicate the signal was always off. So I will have to rework it and then I will post another part of this series.

Implementing an efficient Linked List

Currently I’m doing some refactoring on my Circuit Simulator. For this, I sourced out the graph functionality into an own library, which currently relies on the Java Collections. A problem is, that the Java Collections size() method returns an Integer. That means, if I have more than ~2 billion elements in the list – Javas Integers are signed 32 bit values – the returned size value will be invalid. Because there is no technical limit to the size of the graph to be stored by the graph library except available main memory, I had to find a solution.
so decided to write my own library, called HugeCollections, being able to correctly handle such an amount of elements. One part of it was an implementation of a Linked List which should be as efficient as possible.

Data structure

In a Linked List, there exists an anchor element pointing to the first entry and each entry itself points to the next entry in the list. For my implementation if have chosen the data structure of a doubly Linked List, which means that each entry also points to its predecessor.

This slideshow requires JavaScript.

The pointer of the anhor, which points to the last element is not mandatory, but I used it in my Linked List implementation for speeding up adding elements to the end of the list. Without it, the function which adds the element would have to iterate through the whole list to find the reference to the last element of the list. This approach also allows optimizing the way of reversing the iteration direction of the list.

Another small optimization is related to the size() method. This method returns the amount of elements currently being stored in the list. One approach would be to iterate through each element of the list while counting them on demand. But a more optimal way for implementation is the use of a field in the class managing the list, which stores the current size of the list. each time the add() or remove() method of the list is called, the value of this field gets updated. So when the size of the list shall be determined, the related function only have to return the value of this field instead of counting all elements on demand.

Initialization

When the constructor of the Linked List class is called, a new anchor is created and the size field is set to zero.

this.anchor = new ListEntry<>();
this.size = BigInteger.ZERO;

For simplifying the implementation, I reused the ListEntry class with a element pointer which points to null instead of creating a specialized ListAnchor class. For completeness I attached the source code of the ListEntry class:

protected class ListEntry {
    private E element;
    private ListEntry previous;
    private ListEntry next;

    private ListEntry(){
        this.element = null;
        this.next = null;
        this.previous = null;
    }

    private ListEntry(E element, ListEntry previous, ListEntry next) {
        this.element = element;
        this.previous = previous;
        this.next = next;
    }

    public E getElement() {
        return element;
    }

    public ListEntry getPrevious() {
        return previous;
    }

    public ListEntry getNext() {
        return next;
    }

    public void setElement(E element) {
        assert element != null;
        this.element = element;
    }

    public void setPrevious(ListEntry previous) {
        this.previous = previous;
    }

    public void setNext(ListEntry next) {
        this.next = next;
    }
}

Adding elements to the list

  • Go to the position at which the new element shall be inserted
    • If the current element has a predecessor do the following steps:
      • create a new entry having the current one as ist successor and the predecessor of the current entry as ist predecessor
      • set the successor of the curent elements predecessor to the newly created entry
    • Else do this steps:
      • create a new entry having no predecessor and the current element as its successor
      • set the next-pointer of the anchor to the newly created element
  • Increment the size field by one
public boolean add(BigInteger index, V element) {
    assert index != null;
    assert element != null;
    checkIndex(index);
    BigInteger i = BigInteger.ZERO;
    HugeLinkedListIterator iterator = (HugeLinkedListIterator) iterator();
    while (iterator.hasNext()){
        assert i.compareTo(index) <= 0;
        V elem = iterator.next();
        if (i.compareTo(index) == 0){
            break;
        }
    }
    ListEntry current = iterator.getCurrent();
    if (iterator.hasPrevious()){
        ListEntry entry = new ListEntry<>(element, iterator.getPrevious(), current);
        iterator.getPrevious().setNext(entry);
    }
    else {
        ListEntry entry = new ListEntry<>(element, null, current);
        getAnchor().setNext(entry);
    }
    setSize(size().add(BigInteger.ONE));
    return true;
}

private void checkIndex(BigInteger index) {
    if (index.compareTo(BigInteger.ZERO) < 0){         throw new IndexOutOfBoundsException("Negative index values are not allowed");     }     if (index.compareTo(this.size()) > 0){
        throw new IndexOutOfBoundsException(String.format("No such index number: %s", index));
    }
}

Removing an element from the list

  • If the element to remove has a predeccessor do the following steps:
    • If the element has a successor do following:
      • Set the next-pointer of the predecessor to the successor of the element to delete
      • Set the previous-pointer of the successor to the predecessor of the element to delete
    • Else set the next-pointer of the predecessor to null
    • Decrement the size field by one
  • Else do following steps:
    • If the element to delete have a successor do the following steps:
      • Decrement the size field by one
      • Set the next-pointer of the anchor to the successor of the element to delete
      • Set the previous-pointer of the succesor of the element to delete to null
    • Else do following:
      • Set the next-pointer of the anchor to null
      • Set the size field to zero
      • Set the previous-pointer of the anchor to null
public void remove() {
    HugeLinkedList<E>.ListEntry<E> previous;
    HugeLinkedList<E>.ListEntry<E> next;

    if (current.previous != null){
        previous = current.previous;
        if (hasNext()){
            next = current.next;
            previous.next = next;
            next.previous = previous;
        }
        else {
            previous.next = null;
        }
        assert list.size.compareTo(BigInteger.ZERO) > 0;
        this.list.size = this.list.size.subtract(BigInteger.ONE);
    }
    else {
        if (current.next != null){
            HugeLinkedList<E>.ListEntry<E> nextEntry = current.next;
            assert this.list.size.compareTo(BigInteger.ZERO) > 0;
            this.list.size = this.list.size.subtract(BigInteger.ONE);
            this.list.anchor.next = nextEntry;
            nextEntry.setPrevious(null);
            return;
        }
        this.list.anchor.next = null;
        this.list.size = BigInteger.ZERO;
        this.list.anchor.previous = null;
    }
}

Iterating through the list

When iterating in forward direction, start with the anchor and follow the next-pointers until the next-pointer of the current element is null. Iterating in reverse direction is similar, but you have to follow the previous-pointers instead and stop when the previous-pointer of the current elemen is null.

public boolean hasNext() {
    if (moveForward){
        return current.next != null;
    }
    return current.previous != null;
}

public E next() {
    if (!hasNext()){
        throw new NoSuchElementException("There is no next element");
    }
    if (moveForward){
        current = current.next;
    }
    else {
        current = current.previous;
    }
    return current.element;
}

 

Maybe the lookup of an entry in the list could further be optimized by segmenting the List and storing a reference to the first element and some metainformation (smallest value, highest value, smallest index and highest index) in an Array of fixed size. When the list grows, the segments are realigned and the metainformation will be updated. This would increase the time needed for adding or removing elements, but should speed up finding elements in the list. At some time I will make an implementation and check this out.

Setting up KVM on Debian Stretch

Since a few months I have Debian 9 (“Stretch”) running on my notebook. Yesterday I wanted to install a virtual machine with Windows 7 running on it for testing some applications. So I tried to install VirtualBox through the Debian repository but I had to find out, that VirtualBox no longer is contained in the repository. So I tried to make it run by installing the .deb package provided on oracles website, but I did not make it. Because of this I decided to check out KVM. This is a virtualisation software being contained in the linux kernel and some forum entries on google claim it is as fast as VirtualBox, but on my system it took some configuration before I was able to successfully start a VM on with it.

First of all, you need to check if your System has the Intel-VT or AMD-V instruction set, because KVM will not be able to run without it. According to stackoverflow.com, this can be done the following way:

# sudo apt-get install msr-tools
# sudo modprobe msr
# sudo rdmsr 0x3a

If the result of this call is 3 or 5, the instruction set is supported. Now install the client software:

# sudo apt-get install qemu-kvm

You also should add a GUI for more comfortable configuration:

# sudo apt-get install virt-manager

When you now try to start the VM, you maybe will get following message:

failed to initialize: permission denied

As stated out on issue #1095, You solve this by restarting the KVM kernel modules:

# sudo rmmod kvm_intel
# sudo rmmod kvm
# sudo modprobe kvm
# sudo modprobe kvm_intel

Now you can create a new virtual machine and starting it using virt-manager.

Simple light barrier – Part 1

For a project I’m currently working on I need a light barrier. For maximum efficiency the light barrier should have a high resistance in idle state and in triggered state it should have a low resistance, because it will be most time in idle state. There were some building kits for light barriers in my favourite electronic shop, but they need too much space for my project so I need something more compact. Another point is that they use relays for switching which are too sluggish for my application, need too much electrical power and are too expensive for me because I need many of them. So I decided to design it own my own:

Lichtschranke (bei Dunkelheit leitend)

In Idle state, the light, emitted by the LED is being catched by the photo diode (can also be a photo transistor if necessary), so a high current flows through the photo diode and the resistor Rn. This results in a positive gate-source voltage of the p-chanel MOSFET, so it locks the current flow through the consumer Rv. For reducing enegy loss, the resistance Rn should be as high as possible. In triggered state, nearly no current flows through the photo diode, so the gate-source voltage of the MOSFET is negative, so the MOSFET will turn on and let the current flow through the consumer Rv. The resistance Rb is just a base resistance for protecting the LED from overvoltage.

I will build a prototype of this circuit at the end of this month and will post my test results on this blog.

Simple light barrier ā€“ Part 2

How to use mocks

At this weekend I decided to refactor some parts of the circuit simulator, because its source slowly becomes confusing. In detail I began to extract the graph package of the simulator into a new module which can also be used in other projects relying on a graph library. While I was doing this I found out how I can use Mockito for improving my unit tests.

Mockito is a framework for mock creation. This means it wraps classes which your unit tests depend on into dummy classes returning some hardcoded values.

The advantage of this is, that you don’t need working implementations of interfaces which are dependencies of your unit tests but not being part of the functionality you want to test.

Here is an example of an unit test using mocks:

class DijkstraAlgorithmTest {
    private Graph<Integer> graph;
    private List<Node<Integer>> nodes;

    @BeforeEach
    void setUp() throws EdgeException {
        nodes = new LinkedList<>();
        for (int i = 0; i < 10; i++){
            Node<Integer> node = mock(Node.class);
            nodes.add(node);
            when(node.getData()).thenReturn(i);
            when(node.toString()).thenReturn(String.valueOf(i));
        }

        List<Edge<Integer>> edges = new ArrayList<>();
        Edge<Integer> edge;
        edge = mock(Edge.class); //0
        when(edge.getTarget(nodes.get(0))).thenReturn(nodes.get(1));
        when(edge.getTarget(nodes.get(1))).thenReturn(nodes.get(0));
        when(edge.getSource(nodes.get(1))).thenReturn(nodes.get(0));
        when(edge.getSource(nodes.get(0))).thenReturn(nodes.get(1));
        edges.add(edge);
        edge = mock(Edge.class); //1
        when(edge.getTarget(nodes.get(1))).thenReturn(nodes.get(4));
        when(edge.getTarget(nodes.get(4))).thenReturn(nodes.get(1));
        when(edge.getSource(nodes.get(4))).thenReturn(nodes.get(1));
        when(edge.getSource(nodes.get(1))).thenReturn(nodes.get(4));
        edges.add(edge);
        edge = mock(Edge.class); //2
        when(edge.getTarget(nodes.get(4))).thenReturn(nodes.get(6));
        when(edge.getTarget(nodes.get(6))).thenReturn(nodes.get(4));
        when(edge.getSource(nodes.get(6))).thenReturn(nodes.get(4));
        when(edge.getSource(nodes.get(4))).thenReturn(nodes.get(6));
        edges.add(edge);
        edge = mock(Edge.class); //3
        when(edge.getTarget(nodes.get(0))).thenReturn(nodes.get(6));
        when(edge.getTarget(nodes.get(6))).thenReturn(nodes.get(0));
        when(edge.getSource(nodes.get(6))).thenReturn(nodes.get(0));
        when(edge.getSource(nodes.get(0))).thenReturn(nodes.get(6));
        edges.add(edge);
        edge = mock(Edge.class); //4
        when(edge.getTarget(nodes.get(6))).thenReturn(nodes.get(2));
        when(edge.getTarget(nodes.get(2))).thenReturn(nodes.get(6));
        when(edge.getSource(nodes.get(2))).thenReturn(nodes.get(6));
        when(edge.getSource(nodes.get(6))).thenReturn(nodes.get(2));
        edges.add(edge);
        edge = mock(Edge.class); //5
        when(edge.getTarget(nodes.get(2))).thenReturn(nodes.get(1));
        when(edge.getTarget(nodes.get(1))).thenReturn(nodes.get(2));
        when(edge.getSource(nodes.get(1))).thenReturn(nodes.get(2));
        when(edge.getSource(nodes.get(2))).thenReturn(nodes.get(1));
        edges.add(edge);
        edge = mock(Edge.class); //6
        when(edge.getTarget(nodes.get(2))).thenReturn(nodes.get(3));
        when(edge.getTarget(nodes.get(3))).thenReturn(nodes.get(2));
        when(edge.getSource(nodes.get(3))).thenReturn(nodes.get(2));
        when(edge.getSource(nodes.get(2))).thenReturn(nodes.get(3));
        edges.add(edge);
        edge = mock(Edge.class); //7
        when(edge.getTarget(nodes.get(1))).thenReturn(nodes.get(3));
        when(edge.getTarget(nodes.get(3))).thenReturn(nodes.get(1));
        when(edge.getSource(nodes.get(3))).thenReturn(nodes.get(1));
        when(edge.getSource(nodes.get(1))).thenReturn(nodes.get(3));
        edges.add(edge);

        graph = mock(Graph.class);
        when(graph.getAllNodes()).thenReturn(new HashSet<>(nodes));
        when(graph.getAllEdges()).thenReturn(new HashSet<>(edges));
        when(graph.getEdges(nodes.get(0))).thenReturn(new HashSet<>(Arrays.asList(
                edges.get(0),
                edges.get(3)
        )));
        when(graph.getEdges(nodes.get(1))).thenReturn(new HashSet<>(Arrays.asList(
                edges.get(0),
                edges.get(1),
                edges.get(5),
                edges.get(7)
        )));
        when(graph.getEdges(nodes.get(2))).thenReturn(new HashSet<>(Arrays.asList(
                edges.get(4),
                edges.get(5),
                edges.get(6)
        )));
        when(graph.getEdges(nodes.get(3))).thenReturn(new HashSet<>(Arrays.asList(
                edges.get(6),
                edges.get(7)
        )));
        when(graph.getEdges(nodes.get(4))).thenReturn(new HashSet<>(Arrays.asList(
                edges.get(1),
                edges.get(2)
        )));
        when(graph.getEdges(nodes.get(6))).thenReturn(new HashSet<>(Arrays.asList(
                edges.get(2),
                edges.get(3),
                edges.get(4)
        )));
    }

    @Test
    void apply1() {
        assertEquals(new Path<>(Arrays.asList(
                nodes.get(0),
                nodes.get(1),
                nodes.get(3)
        )), new DijkstraAlgorithm<Integer>().apply(graph, new DijkstraAlgorithm.Parameters<>(nodes.get(0), nodes.get(3))));
    }

    @Test
    void apply2() {
        assertEquals(new Path<>(Arrays.asList(
                nodes.get(4),
                nodes.get(1),
                nodes.get(3)
        )), new DijkstraAlgorithm<Integer>().apply(graph, new DijkstraAlgorithm.Parameters<>(nodes.get(4), nodes.get(3))));
    }
}

 

Let’s take a more detailed look into what happens in this piece of code. First a list of mocked objects of type Node is created. Node is an interface representing nodes in a graph.

nodes = new LinkedList<>();
        for (int i = 0; i < 10; i++){
            Node<Integer> node = mock(Node.class);
            nodes.add(node);
            when(node.getData()).thenReturn(i);
            when(node.toString()).thenReturn(String.valueOf(i));
        }

The mock(Node.class) instruction creates a new instance of an anonymous class implementing the interface Node.At this point, all methods of the created instance will return null. To be able to work with that instance, it is necessary to specify for each function the unit test will use what it should do.

This is done by the when(…).then(…) instructions:

when(node.getData()).thenReturn(i);

This specifies, that the value of the loop counter i shall be returned when the function getData() of the Node instance is called.

when(node.toString()).thenReturn(String.valueOf(i));

I included this for debugging purposes. It returns the loop counter i formatted into a String when the toString() method of the instance is called. The unit test itself does not use this function, but it make debugging easier because I better can see which node I have when looking at the variables stack of my IDE.

After this it is necessary to mock some edge instances for the graph to be tested:

List<Edge<Integer>> edges = new ArrayList<>();
        Edge<Integer> edge;
        edge = mock(Edge.class); //0
        when(edge.getTarget(nodes.get(0))).thenReturn(nodes.get(1));
        when(edge.getTarget(nodes.get(1))).thenReturn(nodes.get(0));
        when(edge.getSource(nodes.get(1))).thenReturn(nodes.get(0));
        when(edge.getSource(nodes.get(0))).thenReturn(nodes.get(1));
        edges.add(edge);
        ...

Create a new mocked instance of an Edge by calling mock(Edge.class). Now specify the getTarget(…) and getSource(…) functions of the Edge:

when(edge.getTarget(nodes.get(0))).thenReturn(nodes.get(1));

This specifies that the node at position 1 of the list nodes shall be returned when getTarget(…) is called for the Edge with the node at position 0 of the list nodes.

when(edge.getSource(nodes.get(1))).thenReturn(nodes.get(0));

This specifies that the node at position 0 of the list nodes is being returned when calling getSource(…) for the Edge with the node at position 1 of the list nodes.

The same way the a mocked instance of Graph is created. Then the actual test is created:

@Test
    void apply1() {
        assertEquals(new Path<>(Arrays.asList(
                nodes.get(0),
                nodes.get(1),
                nodes.get(3)
        )), new DijkstraAlgorithm<Integer>().apply(graph, new DijkstraAlgorithm.Parameters<>(nodes.get(0), nodes.get(3))));
    }

As you can see, you now can use the mocked instances like normal implementations of Graph, Edge and Node.

Priorized Voltage Source Switch

I have been asked by a workmate if I could design a circuit which dynamically switches to another voltage source if the voltage of the primary source has dropped. He wants to install Solarpanels and would like to have a circuit which primarly uses the batteries being loaded by solar panels, for powering some lightening, but when the batteries are low, the power should be taken from the energy network. So I did some google research and some thinking and finally got the following circuit:

Schematics

The red bordered area represents the batteries (the capacitor on the left) and the solar panels (the 12 Volt voltage source on the right and the switch on the top, simulating the sun shining on the solar panels). The 12 Volt voltage source left next to the red bordered area represents the power from the energy network after it has been transformed down to 12 Volt and having passed a rectifier. When the batteries are loaded, the P-Channel MOSFET is turned off, so the power is taken from the batteries. The diode which is passed by the current from the batteries, prevents the current to flow from the energy net to the batteries, so the batteries only will be loaded by the solar panels.

The part on the left (consisting of the bipolar transistor, the base resistance, the TVS diode and the consumer resistance) is a simple voltage regulator circuit as it can be found on wikipedia. The TVS diode of the circuit limits the voltage of the consumer to a fixed value. So if you choose a TVS diode with a breakthrough voltage of 12 Volt, the consumer will get a maximum voltage of 12 Volt. The bipolar transistor regulates the current flow in a way that it will be constant for the consumer.

When the voltage of the batteries drop, the P-Channel MOSFET will turn on, so the reduce in voltage and current flow will be compensated by the energy network. The lower the battery get, the more power will be taken from the energy network. In my simulation, the voltage of the batteries dropped from 12 Volt to ~9 Volt, then no more power was taken from the batteries and all power flowed from the energy network.

The PathStar-Algorithm

For the circuit simulator I need a way to find parallel paths in a graph. To prepare the actual parallel path detection I first need to split a given path into a set of subpaths wich start and end at nodes spawning multiple branches. After some thinking I found out following algorithm:

public Set<Path<V>> apply(Graph<V> graph, PathStar.Parameters<V>... parameters) {
    assert graph != null;
    assert parameters != null;
    assert parameters.length > 0;

    PathStar.Parameters<V> params = parameters[0];
    Set<Path<V>> paths = new HashSet<>();

    List<Node<V>> subPath = new LinkedList<>();
    Iterator<Node<V>> pathIterator = params.getPathToSplit().iterator();
    while (pathIterator.hasNext()){
        Node<V> node = pathIterator.next();
        subPath.add(node);
        Set<Edge<V>> edges = new HashSet<>(graph.getEdges(node));
        if (pathIterator.hasNext()){
            Iterator<Edge<V>> iterator = edges.iterator();
            while (iterator.hasNext()){
                Edge<V> edge = iterator.next();
                Node<V> previousNode = params.getPathToSplit().getPredecessor(node);
                try {
                    if (previousNode != null && edge.getTarget(node).equals(previousNode)){
                        iterator.remove();
                    }
                } catch (DestinationNotExistsException ignored){
                }
                catch (EdgeException e) {
                    throw new RuntimeException(e);
                }
            }
        }
        if (edges.size() > 1){
            if (subPath.size() > 1){
                paths.add(new Path<>(subPath));
            }
            if (!pathIterator.hasNext()){
                subPath = new LinkedList<>();
                break;
            }
            subPath = new LinkedList<>(Collections.singleton(node));
        }
    }
    if (subPath.size() > 0){
        subPath.add(params.getPathToSplit().iterator().next());
        paths.add(new Path<>(subPath));
    }

    return paths;
}

 

How it works

  1. Init new list of nodes representing the current subpath
  2. For every node of the given path do following steps:
    1. Add the node to the subpath
    2. If the currrent node is not the end node to the following steps:
      1. If the current node has multiple successors:
        1. Add current subpath to the list of found subpaths
        2. If the current node is the end node do the following steps:
          1. Create new empty subpath
          2. If the current subpaths has more than 1 node, add it to the list of found subpaths
          3. Return the list of found subpaths
        3. Create new subpath containing current node as its starting node
  3. If the current subpaths has more than 1 node, add it to the list of found subpaths
  4. Return the list of found subpaths