Porting Prim’s Algorithm notebook from JavaScript to Java

I came across this funky color-cycling Prim’s Algorithm Observable notebook and I’m trying to port it to Processing Java.

But surprise surprise it’s not working.

So I’ve annotated the ported code with my interpretation of the JavaScript and the Java equivalent (in case my interpretation of any part is wrong – I’m not superbly familiar with JavaScript).

The first bit (a port of cells = {...}) seems the work; the second bit distance = {...} doesn’t (it only sets a couple values of the array!)

Can anyone spot anything?

import java.util.PriorityQueue;
import java.util.Arrays;

// https://observablehq.com/@mbostock/prims-algorithm-v

static final int E = 1 << 3;
static final int W = 1 << 2;
static final int S = 1 << 1;
static final int N = 1 << 0;

void setup() {
  size(800, 800);

  int[] cells = new int[width*height];

  PriorityQueue<Entry> heap = new PriorityQueue<Entry>(); // I *think* this should be equivalent to js FlatQueue()

  heap.add(new Entry(0, N, random(1)));
  heap.add(new Entry(0, E, random(1)));

  while (!heap.isEmpty()) {
    Entry edge = heap.poll(); // pop here, not in while() check -- equivalent, right?

    int i0 = edge.index;
    int i1;
    int d0 = edge.direction;
    int d1;
    int x0 = i0 % width;
    int x1;
    int y0 = i0 / width | 0; // I think "| 0" is to get javascript integer divsion; retained here in Java for now
    int y1;

    if (d0 == N) {
      i1 = i0 - width; 
      x1 = x0; 
      y1 = y0 - 1; 
      d1 = S;
    } else if (d0 == S) {
      i1 = i0 + width; 
      x1 = x0; 
      y1 = y0 + 1; 
      d1 = N;
    } else if (d0 == W) { 
      i1 = i0 - 1; 
      x1 = x0 - 1;
      y1 = y0; 
      d1 = E;
    } else {
      i1 = i0 + 1; 
      x1 = x0 + 1; 
      y1 = y0; 
      d1 = W;
    }
    try {
      if (cells[i1] == 0) {
        cells[i0] |= d0;
        cells[i1] |= d1;
        if (y1 > 0 && cells[i1 - width] == 0) {
          heap.add(new Entry(i1, N, random(1)));
        }
        if (y1 < height - 1 && cells[i1 + width] == 0) {
          heap.add(new Entry(i1, S, random(1)));
        }
        if (x1 > 0 && cells[i1 - 1] == 0) {
          heap.add(new Entry(i1, W, random(1)));
        }
        if (x1 < width - 1 && cells[i1 + 1] == 0) {
          heap.add(new Entry(i1, E, random(1)));
        }
      }
    }
    catch (Exception e) {
      e.printStackTrace(); // catch out of bounds error -- it goes out of bounds for just 1 cell (the last one?) (for some reason)
    }
  }

  // SOMETHING IN THIS BIT ISN'T WORKING (almost everything in distance s null)

  Integer[] distance = new Integer[width*height]; // Use Integer (rather than int) array so initial values are null
  ArrayList<Integer> frontier = new ArrayList<Integer>();
  frontier.add((height - 1) * width);

  distance[frontier.get(0)] = 0;

  for (int d = 0; d < frontier.size(); ++d) {
    ArrayList<Integer> frontier1 = new ArrayList<Integer>();
    for (int i = 0, n0 = frontier.size(); i < n0; ++i) {
      int i0 = frontier.get(i);
      int i1;

      /**
       the following is my interpretation of "if (cells[i0] & E && distance[i1 = i0 + 1] === undefined)" to Java.
       
       "cells[i0] & E" is bitwise ANDing I think
       
       therefore the "&&" between each clause is casting the first clause to a boolean,
       this is only true when the answer of the AND is 1 (1 is the only numerical truthy I believe)
       **/
      //int i1 = i0 + 1; // assign here rather than inline
      if (((cells[i0] & E)==1) && distance[i1 = i0 + 1] == null) {
        distance[i1] = d; 
        frontier1.add(i1);
      }

      if (((cells[i0] & W)==1) && distance[i1 = i0-1] == null) { 
        distance[i1] = d; 
        frontier1.add(i1);
      }

      if (((cells[i0] & S)==1) && distance[i1 = i0+width] == null) { 
        distance[i1] = d; 
        frontier1.add(i1);
      }

      if (((cells[i0] & N)==1) && distance[i1 = i0-width] == null) {
        distance[i1] = d; 
        frontier1.add(i1);
      }
    }
    frontier =  new ArrayList<Integer>(frontier1);
  }

  loadPixels();
  for (int i = 0; i < pixels.length; i++) {
    if (distance[i] != null) {
      println(distance[i].intValue()); // only 2 values are not null!
    }
  }
  updatePixels();
}

void draw() {
  background(250, 0, 0); // not bothering with color mapping (the last part) yet
}

class Entry implements Comparable<Entry> {
  int index; // value
  int direction; // value
  float value; // location in heap

  public Entry(int index, int direction, float value) {
    this.index = index;
    this.direction = direction;
    this.value = value;
  }

  public int compareTo(Entry other) {
    return Float.compare(value, other.value);
  }
}

Much like Processing’s syntax isn’t exactly 100% Java, that Observable notebook code has to be converted to actual JS syntax before running it.

I don’t think it’s feasible to convert it to Java due to its complex library dependencies.

Library flatqueue is the only from that bunch which can be easily ported to Java.

The 3 others d3-color, d3-interpolate and d3-scale-chromatic would be too much work to be ported to Java I’m afraid.

You may instead attempt to port that code to a p5.js sketch though.

Here’s a very basic “index.html” template file which grabs all needed dependencies:

<script defer src=https://Unpkg.com/flatqueue></script>

<script defer src=https://Unpkg.com/d3-color></script>
<script defer src=https://Unpkg.com/d3-interpolate></script>
<script defer src=https://Unpkg.com/d3-scale-chromatic></script>

<script defer src=https://cdn.JsDelivr.net/npm/p5></script>

<script defer src=sketch.js></script>

I wasn’t actually intending to port the d3 stuff color stuff. I’ll just use Processing’s HSB mode and set pixel hue based on the value from distance.

For now it’s more the translating the algorithm / syntax faithfully.