Endless loop when cutting

[hzhua]

Here is a grid style planer graph: oooooooo oooooooo oooooooo oooooooo oooooooo oooooooo oooooooo oooooooo oooooooo oooooooo

Each “o” is connected to adjacent "o". When I cutting the vertexes one by one, the program will get into endless loop occasionally. Sometimes, the program works well. But sometimes, it can not stop.

Here is my code:

var createVertex = require("dynamic-forest")
var height=8
var weight=10
var map="00000000000000000000000000000000000000000000000000000000000000000000000000000000";

vertexArray = new Array(height);
mapPos = 0;

for(var i = 0; i < height;i++){
    vertexArray[i] = new Array(weight);
    for(var j = 0; j < weight; j++){
        vertexArray[i][j] = createVertex(map[mapPos]);
        mapPos++;

        if(vertexArray[i][j].value == "0"){
            if(i>0 && vertexArray[i-1][j].value == "0"){
                vertexArray[i][j].link(vertexArray[i-1][j]);
            }
            if(j>0 && vertexArray[i][j-1].value == "0"){
                vertexArray[i][j].link(vertexArray[i][j-1]);
            }
        }
    }
}

for(var i = 0; i < height;i++){
    for(var j = 0; j < weight; j++){
        process.stdout.write(vertexArray[i][j].value); // sometimes, the program stop here.
        vertexArray[i][j].cut();
    }
    process.stdout.write("\n")
}

My debugging shows that the program loops in treap.js, line 307-309:

proto.concat = function(other) {
  if(!other) {
    return
  }
  var ra = this.root()
  var ta = ra
  while(ta.right) {
    ta = ta.right
  }
  var rb = other.root()
  var sb = rb
  while(sb.left) { //307
    sb = sb.left //308
  } //309
  ta.next = sb
  sb.prev = ta
  var r = concatRecurse(ra, rb)
  r.parent = null
  return r
} 

[mikolalysenko]

Thanks. This seems like a bug in the treap submodule. I'm not sure what is going on, but when I get a chance I can take a look at it.

[mikaelu1]

@mikolalysenko can you have a look at it now? @hzhua did you resolve it eventually?

[hzhua]

@mikaelu1 No, I didn't resolve this problem. I gave up using the dynamic forest as a workaround.

[mikaelu1]

@hzhua , wait, you mean you ended up not using this library? Or you gave up using any dynamic forest at all?

[hzhua]

@mikaelu1 I gave up using any dynamic forest at all.

[mikaelu1]

@hzhua , lol, why was that?