Reversing a Queue

There was a question in the discussion as to how to reverse a queue without a stack.

Reversing a queue using a stack is quite easy.

 private static void reverseWithStack(Queue<Integer> queue) {
    Stack<Integer> stack = new Stack<Integer>();

    while(queue.isEmpty() == false) {
      stack.push(queue.remove());
    }

    while(stack.isEmpty() == false) {
      queue.add(stack.pop());
    }
  }

How to do it without a stack. I think, there may be convoluted ways. But here's a simple way using recursion:

  private static void reverseWithoutStack(Queue<Integer> queue) {
    if(queue.isEmpty()) {
      return;
    }
    int n = queue.remove();
    reverseWithoutStack(queue);
    queue.add(n);
  }

Well, there's no magic happening here. Actually, we are cheating a bit here. How? We have simulated the behaviour of a stack through recursion. In fact, there's still a stack -- an actual stack -- in action which enables us to solve this problem. It's the program stack! Just that it's hidden.

Many algorithms which could be implemented using a loop and a stack could be rephrased into a simpler one with recursion, simply because recursion hides the stack within itself and allows us to reap its benefits all the same! A classical example is depth first search of trees, which can be implemented using a stack, but a simpler and elegant implementation can be created using recursion.

Here's the complete code:

import java.util.Stack;
import java.util.Queue;
import java.util.LinkedList;

public class Reverse {

  public static void main(String[] args) {

    Queue<Integer> queue = new LinkedList<Integer>();
    queue.add(1);
    queue.add(2);
    queue.add(3);

    System.out.println("Before reversing ...");
    printQueue(queue);
    // reverseWithoutStack(queue);
    reverseWithoutStack(queue);
    System.out.println("After reversing ...");
    printQueue(queue);
  }

  private static void reverseWithStack(Queue<Integer> queue) {
    Stack<Integer> stack = new Stack<Integer>();

    while(queue.isEmpty() == false) {
      stack.push(queue.remove());
    }

    while(stack.isEmpty() == false) {
      queue.add(stack.pop());
    }
  }

  private static void reverseWithoutStack(Queue<Integer> queue) {
    if(queue.isEmpty()) {
      return;
    }
    int n = queue.remove();
    reverseWithoutStack(queue);
    queue.add(n);
  }

  private static void printQueue(Queue<Integer> queue) {
    String s = "[ ";
    for(int i = 0; i < queue.size(); i++) {
      int n = queue.remove();
      if(i <= queue.size() - 1) {
        s += n + ", ";
      }
      else {
        s += n + " ";
      }
      queue.add(n);
    }
    s += "]";
    System.out.println(s);
  }
}

Implementation of Lexical Analyser

Compiler texts usually provide a detailed treatment to the theoretical aspects of the design of a lexical analyser. In most cases, the issues of putting together all these concepts in a real working lexical analyser are typically never discussed. Probably, there’s good reason for this too, as very good tools exist that automatically generate lexical analysers from lexical specifications provided as regular expression patterns.
 

Yet, manually implementing a lexical anlyser that embodies all the concepts taught in a compilers text or course is an interesting engineering exercise. Doing this seems to provide some nuanced insights about how such a system can be designed. Experience thus earned is likely to be useful in solving other software design problems sharing technical properties with the lexical analyser. In this article, we show how a lexical analyser can be implemented using C++. We do so using an example discussed in the following section.

Example

Here, we design a lexical analyser that recognises the follow token classes:

Assignment. (ASSIGN) Represented by the single character ‘=’.
Regular expression: =
Automaton:

Equals. (EQ) Represented by the string ‘==’.
Regular expression: ==
Automaton:

Identifiers. (ID) Represented by any string that starts with an alphabetic character and is followed by zero or more alphanumeric characters.
Regular expression: α[α|N ]?
Automaton:

Whitespace. (WS) Represented by a non-empty string of spaces or tabs.
Regular expression: [SP ACE|T AB]+
Automaton:

A practical recogniser would try to consume as much of the input string as possible returning a token. For instance, if the input in "ab", and the input pointer has just consume ’a’, it has a choice of returning the ID token with lexeme "a". However, the lexer must hang on before hurrying to do that. It must look ahead of where it currently is and decide on its next move based on what it sees. Here, for example, it would see that the next character to be consumed is ’b’. This, if eaten, would help construct a longer lexeme, and result in further progress of the lexical analysis process before a token is returned. Hence, the lexical analyser, instead of returning rightaway will go ahead and consume ’b’. Thereafter, it will find that either the input string is over, or the next unconsumed chanracter is a non-alphanumeric one. Thus, the
lexical analyser will return ID token class "ab" being the lexeme.

Combining the Automata

There are multiple approaches possible in designing the combined recogniser. The conceptually simplest is to merge all the automata corresponding to each token class into one. This is the approach we take here. The combined automaton for the token classes is as shown in the following figure:

The Combined Automaton

Recognising the Next Token

The central function in lexical analysis is the stateful procedure that begins consuming character upon character until it can consume no other. At that point it has to make a decision as to whether it has been able to recognise a valid token. If yes, that token is returned; otherwise, an error is announced. So, at the high level, the algorithm goes like this:

Pseudocode for the procedure that gets the next token

Architecture and Implementation

Now, let’s take a look at the implementation that we have done. The system has been designed within a Scanner class, which encapsulates an instance of DFA class.

Architecture of the Lexical Analyser

Class DFA

DFA class provides the basic API for creating a deterministic finite state automaton. An instance is created by specifying the list of state IDs (which are integers), the initial state ID, and the list of final states ID. The transitions are later added to the DFA using the add transition method in a very user-friendly manner. Internally, the DFA has been designed like a directed graph using adjacency list style connections.

Class Scanner

The Scanner class implements the functionalities of the lexical analyser. It keeps account of the input string, and the progress of the lexical analysis through this string. It actuates the DFA by feeding it one character at a time, and makes the decision regarding acceptance or rejection of the input string at appropriate
times. the next token method returns the next token beginning at the current position on the input string. scan method returns all the tokens contained in the input string, by making repeated calls to next token.

Code

The code for the lexical analyser can be found in this link. In fact, as of the current date, the code contains a slight enhancement to the lexical analyser described here, in that it is also able to distinguish between identifiers and keywords. The scanner is implemented in KWScanner class which simply extends the Scanner class with the required capability.

This code is likely to keep evolving beyond what is described here. The latest version of the code can be found in this link. 

User Instructions

The executable la is created by running make. la can be run simply without provided any command line arguments.

Navigating the Code

The main function is in the file la.cpp. The above example is implemented in the test case function t3. In t3, we create an object dfa of type DFA. We construct it to resemble the DFA shown in figure above.

Simulating Higher Order Functions using Strategy Design Pattern

We wish to implement a function that takes an integer array as an input and returns an integer array of the same length but each of its elements double the corresponding element in the input array. One possibly reasonable implementation is shown below.

public class Hof {

    public static void main(String[] args) {
        int[] a = { 1, 2, 3};
        printArray(doubleArray(a));
    }

    private static int dbl(int n) {
        return n * 2;
    }

    private static int print(int n) {
        System.out.print(n + " ");
        return 0;
    }

    private static int[] doubleArray(int[] array) {
        int[] ans = new int[array.length];
        for(int i = 0; i < array.length; i++) {
            ans[i] = dbl(array[i]);
        }
        return ans;
    }

    private static int[] printArray(int[] array)  {
        int[] ans = new int[array.length];
        for(int i = 0; i < array.length; i++) {
            ans[i] = print(array[i]);
        }
        return ans;
    }
}

On running this program, we get the following output:

2 4 6

Now, we additionally wish to implement a function that squares an integer array, we may have to insert the pieces below.

public class Hof {

    public static void main(String[] args) {
        int[] a = { 1, 2, 3};
        printArray(doubleArray(a));
    }

    private static int dbl(int n) {
        return n * 2;
    }

    private static int print(int n) {
        System.out.print(n + " ");
        return 0;
    }

    private static int[] doubleArray(int[] array) {
        int[] ans = new int[array.length];
        for(int i = 0; i < array.length; i++) {
            ans[i] = dbl(array[i]);
        }
        return ans;
    }

    private static int[] printArray(int[] array)  {
        int[] ans = new int[array.length];
        for(int i = 0; i < array.length; i++) {
            ans[i] = print(array[i]);
        }
        return ans;
    }
}

2 4 6
1 4 9 

However, Java does badly when it comes to economy of expression.

Let's just look at how the same code would look in another programming language, Python, shown below.

print map(lambda x: 2 * x, [1, 2, 3])
print map(lambda x: x * x, [1, 2, 3])

On running this program, we get the following output:

[2, 4, 6]
[1, 4, 9]

One of the reasons for this enormous of economy of syntax is a higher order function called map. A higher order function is a function that takes other functions as inputs (and possibly computes functions as output). map is one such function that takes a function, say \lstinline$f$, and a list, say l, and returns a list each of whose elements is f applied to the corresponding element in l. HOFs are a common feature of functional programming. In fact, what inheritance and polymorphism is to object-oriented programming, HOFs are the same to functional programming: the main abstraction mechanism for code reuse and modularisation.

Unfortunately, Java (until Java 8) doesn't have higher order functions. But the case for higher order functions is strong enough that we wish to implement something similar in Java. How do we do it?

With our knowledge of object-oriented programming, we can come out with a fairly close approximation to the idea of higher order functions. The central idea is: in OOP, we can't pass functions to functions, but we can pass objects which have functions in them. Thus, all we need to do is pack the function that we want to pass to a HOF in a class, and pass an object of that class to the HOF.

The solution for the problem is presented below.

public class Hof {
  public static void main(String[] a) {
    int[] ar = {1, 2, 3};

    int[] newarray = Hof.map(new Dbl(), ar);
    for(int n : newarray) {
      System.out.println(n);
    }

 
    newarray = Hof.map(new Dbl(), ar);
    for(int n : newarray) {
      System.out.println(n);
    }
  }

  public static int [] map(Function f, int [] a) {
    int[] newarray = new int[a.length];
    for(int i = 0; i < a.length; i++) {
      newarray[i] = f.execute(a[i]);
    }
    return newarray;
  }
}

interface Function {
  int execute(int n);
}

class Dbl implements Function {
  public int execute(int n) {
    return 2 * n;
  }
}

class Sqr implements Function {
  public int execute(int n) {
    return n * n;
  }
}

which gives us the following output:

2
4
6
1
4
9

Just in case it's not clear already, let me help you walk through the code.

1. The first thing to notice is the interface Function. It has a method declaration execute that takes an integer and returns an integer. This represents the function that would be passed to the higher order function map and would be applied to each element of the integer array.
2. The next thing to observe is the map method which takes two parameters: the first is f, an instance of Function; and the other is the array of ints a. It returns the resultant array after applying f on each element of a as shown.
3. Finally, an instance of Dbl and Sqr are passed in turn to Hof.map in the \lstinline@main@ method to be applied to array.

This application is to demonstrate how object-oriented principles can be used to create highly reusable code. The map method here is a boiler-plate code that can be used wherever there's a need to apply a function on all elements of an integer array to create a new one. What that function to applied should be is a parameter to the method, and hence is flexible.

Anonymous Classes

The next question we ask is: In Java, is there something equivalent to lambda expressions as seen in Python. Lambda expressions are like anonymous functions which are typically created for a one time use as a parameter to a higher order function. This avoids creation of extra named functions and saves the namespace (variable environment) from unnecessary clutter. Here, the classes Dbl and Sqr are similar classes: to be instantiated once to be passed to Hof.map, and then to be forgotten. Why do we need to create a named class which will ever be implemented only once? Like anonymous functions (lambda) in Python, do we have something like anonymous classes? Indeed, yes!

We replace the earlier Hof.main method with the lines shown below.

  public static void main(String[] a) {

    int[] ar = {1, 2, 3};

    Function triple = new Function() {
        public int execute(int n) {
          return 3 * n;
        }
      };

    newarray = Hof.map(triple, ar);
    for(int n : newarray) {
      System.out.println(n);
    }
  }

Here's the output:

3
6
9

Here, we used the map method to triple the array. The Function interface is implemented through an anonymous class (a class with no name) set to Function triple. All we need to do to make it a concrete class is to provide its own implementation of the execute method. We do so. And it just works smoothly. No need to create another class named Triple or something. No too many unused class names. No namespace clutter!

Taking Interest in FIFA 2018

As a father of a growing pre-teen boy, I am supposed to take at least some interest in sports. Particularly when the whole world is afire about FIFA world cup.

So, yesterday, I sat beside my son watching the match between Japan and Senegal, picking Senegal as the team I supported (as my son supported Japan). Thank God! The match ended in a draw!

It was a nice experience. I did find the match interesting. But, it would have been too much to expect me to concentrate on the game all the while. While the match on, I fiddled with my laptop, and did a little program to calculate the importance of the remaining matches in the opening round.

I have pasted the output (with some edits to include the dates and times) at the end of the source code within comments.

The program has some simple illustration of how the library higher order functions List.map and List.sort can be used. There's also a higher order function rate_match implemented.

Hope you find it helpful in deciding which matches in the opening round you would like to watch, and in the process get a bit familiar with functional programming with OCaml.

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 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297

let teams = [ "Germany"; "Brazil"; "Belgium"; "Portugal"; "Argentina"; "Switzerland"; "France"; "Poland"; "Chile"; "Spain"; "Peru"; "Denmark"; "England"; "Uruguay"; "Mexico"; "Colombia"; "Netherlands"; "Wales"; "Italy"; "Croatia"; "Tunisia"; "Iceland"; "Costa Rica"; "Sweden"; "United States"; "Austria"; "Senegal"; "Slovakia"; "Northern Ireland"; "Romania"; "Republic of Ireland"; "Paraguay"; "Venezuela"; "Serbia"; "Ukraine"; "Australia"; "Iran"; "Turkey"; "Congo DR"; "Bosnia-Herzegovina"; "Morocco"; "Scotland"; "Montenegro"; "Greece"; "Egypt"; "Czech Republic"; "Ghana"; "Nigeria"; "Bulgaria"; "Cameroon"; "Hungary"; "Burkina Faso"; "Norway"; "Jamaica"; "Panama"; "Slovenia"; "Korea Republic"; "Albania"; "Bolivia"; "Ecuador"; "Japan"; "Honduras"; "Finland"; "Mali"; "Cape Verde Islands"; "Algeria"; "Saudi Arabia"; "Côte d'Ivoire"; "Guinea"; "Russia"; "FYR Macedonia"; "El Salvador"; "Syria"; "South Africa"; "China PR"; "Zambia"; "UAE"; "Belarus"; "Lebanon"; "Canada"; "Curaçao"; "Uganda"; "Congo"; "Oman"; "Gabon"; "Luxembourg"; "Cyprus"; "Benin"; "Iraq"; "Faroe Islands"; "Trinidad and Tobago"; "Kyrgyzstan"; "Israel"; "Estonia"; "Uzbekistan"; "Georgia"; "India"; "Qatar"; "Palestine"; "Armenia"; "Libya"; "Vietnam"; "Niger"; "Haiti"; "Azerbaijan"; "Madagascar"; "Mauritania"; "Korea DPR"; "Central African Republic"; "Jordan"; "Sierra Leone"; "Kenya"; "Bahrain"; "Mozambique"; "Philippines"; "Namibia"; "Kazakhstan"; "Zimbabwe"; "Tajikistan"; "New Zealand"; "Guinea-Bissau"; "Thailand"; "Malawi"; "Chinese Taipei"; "Togo"; "Lithuania"; "Antigua and Barbuda"; "Sudan"; "Latvia"; "Turkmenistan"; "Andorra"; "Nicaragua"; "Yemen"; "Swaziland"; "St. Kitts and Nevis"; "Rwanda"; "Angola"; "Myanmar"; "Botswana"; "Tanzania"; "Kosovo"; "Hong Kong"; "Equatorial Guinea"; "Solomon Islands"; "Afghanistan"; "Guatemala"; "Lesotho"; "Burundi"; "Comoros"; "Maldives"; "Ethiopia"; "Dominican Republic"; "Suriname"; "New Caledonia"; "Mauritius"; "South Sudan"; "Tahiti"; "Liberia"; "Kuwait"; "Barbados"; "Nepal"; "Vanuatu"; "Belize"; "Indonesia"; "Fiji"; "Cambodia"; "Papua New Guinea"; "Grenada"; "Singapore"; "St. Lucia"; "Malaysia"; "Gambia"; "St. Vincent / Grenadines"; "Puerto Rico"; "Chad"; "Moldova"; "Dominica"; "Bermuda"; "Laos"; "Liechtenstein"; "Cuba"; "Guyana"; "Bhutan"; "Malta"; "Macao"; "Mongolia"; "São Tomé e Príncipe"; "Seychelles"; "Aruba"; "Guam"; "Timor-Leste"; "American Samoa"; "Cook Islands"; "Bangladesh"; "Gibraltar"; "Brunei"; "Djibouti"; "Samoa"; "US Virgin Islands"; "Sri Lanka"; "Pakistan"; "Cayman Islands"; "San Marino"; "British Virgin Islands"; "Montserrat"; "Turks and Caicos Islands"; "Anguilla"; "Bahamas"; "Eritrea"; "Somalia"; "Tonga"; ] let matches = [ ("Japan", "Senegal"); ("Poland", "Colombia"); ("Uruguay", "Russia"); ("Saudi Arabia", "Egypt"); ("Spain", "Morocco"); ("Iran", "Portugal"); ("Australia", "Peru"); ("Denmark", "France"); ("Nigeria", "Argentina"); ("Iceland", "Croatia"); ("Korea Republic", "Germany"); ("Mexico", "Sweden"); ("Serbia", "Brazil"); ("Switzerland", "Costa Rica"); ("Japan", "Poland"); ("Senegal", "Colombia"); ("Panama", "Tunisia"); ("England", "Belgium"); ] exception My_Not_found of string let find x l = let rec iter i = function [] -> raise (My_Not_found x) | h :: t -> if h = x then i else iter (i + 1) t in iter 1 l let rate_match (t1, t2) imp = imp (find t1 teams) (find t2 teams) let rate_matches ms = let rates = List.map (fun m -> (m, rate_match m (fun x y -> x * y))) ms in List.sort (fun (_, r1) (_, r2) -> if r1 < r2 then -1 else if r1 = r2 then 0 else 1) rates (* By using 'addition' as the joining function [ (("England", "Belgium"), 14); June 28 11.30 PM (("Denmark", "France"), 17); June 26 7.30 PM (("Poland", "Colombia"), 22); June 24 11.30 PM (("Switzerland", "Costa Rica"), 27); June 27 11.30 PM (("Serbia", "Brazil"), 34); June 27 11.30 PM (("Mexico", "Sweden"), 37); June 27 7.30 PM (("Iran", "Portugal"), 39); June 25 7.30 PM (("Iceland", "Croatia"), 40); June 26 11.30 PM (("Senegal", "Colombia"), 41); June 28 7.30 PM (("Australia", "Peru"), 45); June 26 7.30 PM (("Spain", "Morocco"), 49); June 25 11.30 PM (("Nigeria", "Argentina"), 51); June 26 11.30 PM (("Korea Republic", "Germany"), 56); June 27 7.30 PM (("Japan", "Poland"), 67); June 28 7.30 PM (("Panama", "Tunisia"), 74); June 28 11.30 PM (("Uruguay", "Russia"), 82); June 25 7.30 PM (("Japan", "Senegal"), 86); June 24 8.30 PM (("Saudi Arabia", "Egypt"), 110) June 25 7.30 PM ] By using 'multiplication' as the joining function [ (("England", "Belgium"), 39); (("Korea Republic", "Germany"), 57); (("Serbia", "Brazil"), 68); (("Denmark", "France"), 84); (("Poland", "Colombia"), 128); (("Switzerland", "Costa Rica"), 138); (("Iran", "Portugal"), 148); (("Nigeria", "Argentina"), 240); (("Mexico", "Sweden"), 360); (("Australia", "Peru"), 396); (("Spain", "Morocco"), 410); (("Senegal", "Colombia"), 432); (("Iceland", "Croatia"), 440); (("Japan", "Poland"), 488); (("Uruguay", "Russia"), 980); (("Panama", "Tunisia"), 1155); (("Japan", "Senegal"), 1647); (("Saudi Arabia", "Egypt"), 3015) ] *)