Android coding techniques II

Implementation of some useful algorithms

Power Set

A power set is the set containing all the possible sub-sets from a given set. It’s useful for resolving problems where we need all possible combinations of the elements in a set.

Our implementation of the PowerSet returns an ArrayList where each element in it is an ArrayList containing one of the possible sub-sets of the original ArrayList.

package com.callforward.powerset;

import android.support.v7.app.AppCompatActivity;
import android.os.Bundle;
import android.util.Log;

import java.util.ArrayList;
import java.util.Iterator;

public class MainActivity extends AppCompatActivity {

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        ArrayList<String> arrayList = new ArrayList<>();

        arrayList.add("a");
        arrayList.add("b");
        arrayList.add("c");
        arrayList.add("d");
        arrayList.add("e");

        PowerSet p = PowerSet.createPowerSet(arrayList);

        p.list();

        Log.v("Test","size = "+p.size());
    }


    public static class PowerSet {

        private ArrayList set,result;

        private PowerSet(ArrayList set) {

            this.set = set;
            this.result = new ArrayList();

        }

        public static PowerSet createPowerSet(ArrayList set) {

            PowerSet powerSet = new PowerSet(set);
            powerSet.calculate();

            return powerSet;

        }

        private void calculate() {

            for (Object o:set) {

                ArrayList[] content = (ArrayList[]) this.result.toArray(new ArrayList[]{});

                for (ArrayList arrayList:content){

                    ArrayList aux = new ArrayList(arrayList);

                    aux.add(o);
                    this.result.add(aux);
                }

                ArrayList aux = new ArrayList();
                aux.add(o);
                this.result.add(aux);
            }
        }

        public Iterator<ArrayList> iterator() {

            return result.iterator();
        }

        public int size() {
            return result.size();
        }

        public void list() {

            Iterator i = this.iterator();

            while (i.hasNext()) {

                ArrayList aux = (ArrayList) i.next();

                String res = "";

                for (Object o:aux) {

                    res += o.toString() + " ";
                }

                Log.v("Test","res = "+res);
            }
        }
    }
}

Parcelable table

This is a simple one, that we will use in the upcoming implementation of the state machine framework.

Tables are useful data structures; however if you look around Android there’s no explicit data structure for them. Lots of lists, sets and one-to-one key/value maps, but now tables. It would be even better if the table could be shared across components and processes.

The definition of a table we present in this section is this:

A data structure mapping two indexes to one and only one entry in the table. The indexes can be of any type.

In order to accomplish this we used a HashMap like this:

public HashMap<String,V2> where K, V1 and V2 can be of any type

where the String used as a key to the HashMap is the concatenation of the String value for the objects used as indexes to the the table.

The reason this works is that a unique hash will be created for the pair used as the hash index based on the pair contents.

The HashMap is a Serializable class and so as long as V2 is also Serializable or Parcelable the HashMap can be shared between processes/components using both Intents via public Intent putExtra (String name, Serializable value)

and Bundles, via public void putSerializable (String key, Serializable value)

State machines

State machines are useful implementation of the State design pattern. One of the advantages of writing software as state machines is predictability and the ability to avoid race conditions.

The Android framework code implements state machines in many internal components; the AndroidX framework exposes some specialized state machines (e.g. LIfecycle for UI state management).

The implementation we present here has 5 main components:

1. The State parent class, that must be implemented by each state associated with the state machine
2. A QueueService, responsible for queueing Events received from other parts of the application/system according to their priority; by ordering the events based on priority and not based on the order of arrival we can guarantee the app will behave consistently. Our implementation will use Android’s class PriorityQueue.
3. A TransitionTable, which define the events that trigger a state change. The TransitionTable can be hardcoded in software or provided as a resource (e.g. an XML or JSON file with the transition definition)
4. Events, to be delivered to the current state. Each Event must have a priority; the content of the Event itself will depend of the source (e.g. Intents from BroadcastReceivers, data received over the network by a Service, etc.)
5. EventHandler, responsible for delivering events from the queue to the current state and for state transitions.

What are the source of events? That will depend on the plication design and purpose. User actions in the UI, network data received by a network service in the app, BroadcastReceivers handling Intents received from the system, all these are possible sources of Events.

The transition tables will normally only contain Events that cause an state transition. In general it will have 3 elements per row: the Event ID, the present state and the next state.

The logic for handling events is implemented like this:

1. If the Event is not in the transition table then it’s delivered to the current state
2. If the Event is in the transition table, but the resent state does not match the current state then the Event is delivered to the current state
3. If the Event is in the transition table and the current state is the present state then the current state is exited, the next state is entered and the transition event is delivered to the next state (now set as the current state)
4. If the present state is the wildcard state. then one of 2 things can happen: 1) if the next states matches the current state the event is delivered to the current state
   2) otherwise the state transition is executed as described in step 3

The only important rule when building the transition table is that the pair (event, present state) can only occur once in the table. In other words (state A is the present state, B and C are valid next states):

1. Different Events can cause a transition between state A and state B but
2. The same Event cannot trigger a transition between state A and B and between state A and C

One more note before we go into the code. The implementation we present here will only allow state transitions if the state is idle.

But what does idle state mean? Again it’s up to the application to decide. For example the state may be designed to spawn multiple threads to handle separate events and consider itself idle after the threads are launched, even if the threads are still running.

PriorityQueue Service flowchart

EventHandler flowchart

State flowchart

Source code can be found here:

https://github.com/mauricioandrada2018/state_machine.git

Some pros of a state machine approach:

1. The code is loosely coupled, as long as each state is self-contained and does not depend on another state running simultaneously
2. Each state can be implemented and tested in parallel since they only depend on the proper events being delivered
3. Code behavior is predictable and repeatable
4. The interfaces between components are well defined and does not change so there’s no risk of a crash due to API changes
5. Architecture requires good communication in the development team regarding data structures, content, encoding, etc.