# Porting Prim’s Algorithm notebook from JavaScript to Java

**URL:** <https://discourse.processing.org/t/porting-prim-s-algorithm-notebook-from-javascript-to-java/26840>\
**Category:** Coding Questions\
**Created:** [January 6, 2021, 6:22pm UTC](https://discourse.processing.org/t/porting-prim-s-algorithm-notebook-from-javascript-to-java/26840 "2021-01-06T18:22:52Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![micycle](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/micycle/32/201_2.png) [@micycle](https://discourse.processing.org/u/micycle)\
**Post date:** [January 6, 2021, 6:22pm UTC](https://discourse.processing.org/t/porting-prim-s-algorithm-notebook-from-javascript-to-java/26840/1 "2021-01-06T18:22:52Z")

</div>

I came across [this](https://observablehq.com/@mootari/prims-algorithm-v) 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?

```auto
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);
  }
}

```

---

<div class="post-metadata">

**Author:** ![GoToLoop](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/gotoloop/32/86_2.png) [@GoToLoop](https://discourse.processing.org/u/GoToLoop)\
**Post date:** [January 6, 2021, 7:53pm UTC](https://discourse.processing.org/t/porting-prim-s-algorithm-notebook-from-javascript-to-java/26840/2 "2021-01-06T19:53:28Z")

</div>

> [@micycle](#):
>
> I came across [this](https://observablehq.com/@mootari/prims-algorithm-v) funky color-cycling Prim’s Algorithm _Observable_ notebook…

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.

> [@micycle](#):
>
> and I’m trying to port it to Processing Java.

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

Library [flatqueue](https://github.com/mourner/flatqueue) is the only from that bunch which can be easily ported to Java.

The 3 others [d3-color](https://github.com/d3/d3-color), [d3-interpolate](https://github.com/d3/d3-interpolate) and [d3-scale-chromatic](https://github.com/d3/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:

```auto
<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>

```

---

<div class="post-metadata">

**Author:** ![micycle](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/micycle/32/201_2.png) [@micycle](https://discourse.processing.org/u/micycle)\
**Post date:** [January 6, 2021, 8:39pm UTC](https://discourse.processing.org/t/porting-prim-s-algorithm-notebook-from-javascript-to-java/26840/3 "2021-01-06T20:39:47Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![micycle](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/micycle/32/201_2.png) [@micycle](https://discourse.processing.org/u/micycle)\
**Post date:** [December 22, 2022, 7:31pm UTC](https://discourse.processing.org/t/porting-prim-s-algorithm-notebook-from-javascript-to-java/26840/4 "2022-12-22T19:31:21Z")

</div>

I remembered this today and asked ChatGPT to reimplement the problematic `distance()` function in Java. It did so marvellously, so I was able to complete the port😁.

 ![image](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/3X/5/5/55b660fd58a251c2c63a89e289b115e5e29b0e52.png)

So here’s the complete working port.

```auto
import java.util.Random;
import java.util.PriorityQueue;
import java.util.ArrayDeque;

public static final int N = 1;
public static final int S = 2;
public static final int W = 4;
public static final int E = 8;

int n;
int[] cells;
int[] distance;
int[] palette = new int[360];

void setup() {
  size(1280, 720);
  n = width * height;
  cells = cells();
  distance = distance();
  loadPixels();

  for (int i = 0; i < palette.length; i++) {
    palette[i] = sinebow(i/360f);
  }
}

void draw() {
  float s = 1.1 - cos(millis() / 10000f);
  for (int i = 0; i < pixels.length; i++) {
    pixels[i] = palette[round(distance[i]*s) % 360];
  }
  updatePixels();
}

int[] cells() {
  PriorityQueue<Entry> heap = new PriorityQueue<>();
  int[] cells = new int[width * height];
  Entry entry;
  heap.add(new Entry(new Edge(0, N), random(1)));
  heap.add(new Entry(new Edge(0, E), random(1)));

  while ((entry = heap.poll()) != null) {
    Edge edge = entry.e;
    int i0 = edge.index, i1;
    int d0 = edge.direction, d1;
    int x0 = i0 % width, x1;
    int y0 = i0 / width, 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;
    }
    if (i1 >= 0 && cells[i1] == 0) {
      cells[i0] |= d0;
      cells[i1] |= d1;
      if (y1 > 0 && cells[i1 - width] == 0) {
        heap.add(new Entry(new Edge(i1, N), random(1)));
      }
      if (y1 < height - 1 && cells[i1 + width] == 0) {
        heap.add(new Entry(new Edge(i1, S), random(1)));
      }
      if (x1 > 0 && cells[i1 - 1] == 0) {
        heap.add(new Entry(new Edge(i1, W), random(1)));
      }
      if (x1 < width - 1 && cells[i1 + 1] == 0) {
        heap.add(new Entry(new Edge(i1, E), random(1)));
      }
    }
  }

  return cells;
}

int[] distance() {
  int[] distance = new int[n];
  ArrayDeque<Integer> frontier = new ArrayDeque<>();
  frontier.add((height - 1) * width);
  distance[frontier.peek()] = 0;
  while (!frontier.isEmpty()) {
    ArrayDeque<Integer> frontier1 = new ArrayDeque<>();
    int d = distance[frontier.peek()] + 1;
    while (!frontier.isEmpty()) {
      int i0 = frontier.poll(), i1;
      if ((cells[i0] & E) != 0 && distance[i1 = i0 + 1] == 0) {
        distance[i1] = d;
        frontier1.add(i1);
      }
      if ((cells[i0] & W) != 0 && distance[i1 = i0 - 1] == 0) {
        distance[i1] = d;
        frontier1.add(i1);
      }
      if ((cells[i0] & S) != 0 && distance[i1 = i0 + width] == 0) {
        distance[i1] = d;
        frontier1.add(i1);
      }
      if ((cells[i0] & N) != 0 && distance[i1 = i0 - width] == 0) {
        distance[i1] = d;
        frontier1.add(i1);
      }
    }
    frontier = frontier1;
  }
  return distance;
}

static class Edge {
  public int index;
  public int direction;

  public Edge(int index, int direction) {
    this.index = index;
    this.direction = direction;
  }
}

class Entry implements Comparable<Entry> {
  Edge e;
  float value; // location in heap

  public Entry(Edge e, float value) {
    this.e = e;
    this.value = value;
  }

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

/**
 Linear Sinebow, a better rainbow palette
 https://observablehq.com/@jobleonard/linear-sinebow
 */
int sinebow(float t) {
  t = 0.5f - t;
  return color(
    255 * lrgb_rgb(sin2(t + 0 / 3f)), // note only r linearised
    255 * (sin2(t + 1 / 3f)),
    255 * (sin2(t + 2 / 3f))
    );
}

static float sin2(float t) {
  float z = sin(PI * t);
  return z*z;
}

static float lrgb_rgb(float v) {
  // convert linear rgb space in range [0.0, 1.0] to rgb space in range [0, 255]
  return v <= 0.0031308 ? 12.92 * v : 1.055 * pow(v, (1 / 2.4)) - 0.055;
}

```

 ![image](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/3X/3/b/3b32e44931078c29f7973681cb54548931f10513.jpeg)

---

<div class="post-metadata">

**Author:** ![GoToLoop](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/gotoloop/32/86_2.png) [@GoToLoop](https://discourse.processing.org/u/GoToLoop)\
**Post date:** [December 22, 2022, 7:51pm UTC](https://discourse.processing.org/t/porting-prim-s-algorithm-notebook-from-javascript-to-java/26840/5 "2022-12-22T19:51:57Z")

</div>

Wow, very impressive!

And ChatGPT is even right that JS’ `[]` corresponds to Java’s LinkedList!

Although it’s advisable that we replace the slowest LinkedList to a more specific & faster datatype that is just enough for the task.

Now after replacing empty `<>` generics to the 1 matching the datatype the sketch worked on my old P3.

---

<div class="post-metadata">

**Author:** ![micycle](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/micycle/32/201_2.png) [@micycle](https://discourse.processing.org/u/micycle)\
**Post date:** [December 22, 2022, 7:59pm UTC](https://discourse.processing.org/t/porting-prim-s-algorithm-notebook-from-javascript-to-java/26840/6 "2022-12-22T19:59:11Z")

</div>

> Although it’s advisable that we replace the slowest LinkedList…

Indeed, I used an `ArrayDeque` myself.

---

<div class="post-metadata">

**Author:** ![Chrisir](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/chrisir/32/45_2.png) [@Chrisir](https://discourse.processing.org/u/Chrisir)\
**Post date:** [December 22, 2022, 9:04pm UTC](https://discourse.processing.org/t/porting-prim-s-algorithm-notebook-from-javascript-to-java/26840/7 "2022-12-22T21:04:06Z")

</div>

Seriously?

The long _I replaced_ list is by ChatGPT?

That is impressive…