D3 Examples - String-Word Inversion

String-Word Inversion

This one is a classic : reverse a string, and reverse the word of the strings, in place, and in linear time.

Cost comparison is caracter exchange. The heart of the algorithm is the reverseWord function, which reverses a word.

The first passe uses N/2 characters exchange, where N is the number of character

The second passe uses W*(w/2) characters exchange, where w is the average length of a word, and W the number of word. This falls back around N/2

Overall Cost is N exchange

xxxxxxxxxx
 
<!DOCTYPE html>
<meta charset="utf-8">
<style>
​
text {
  font: bold 38px monospace;
}
​
.enter {
  fill: green;
}
​
.update {
  fill: #333;
}
​
</style>
<body>
<script src="https://d3js.org/d3.v2.min.js?2.10.1"></script>
​
<script>
​
​
var string = "I AM LEARNING SOME ALGORITHMS";
var chars=[];
var initialPos = [];
for (var i=0;i<string.length;i++) {
  chars.push({c:string[i],p:i});
​
}
var width = 960,
    height = 500;
var transition = null;
var step = 0;
var done = 0;
var animations = [];
var svg = d3.select("body").append("svg")
    .attr("width", width)
    .attr("height", height)
    .append("g")
    .attr("transform", "translate(32," + (height / 2) + ")");
​
var text = svg.selectAll("text")
      .data(chars,function(d,i) { return  });
text.enter().append("text")
      .attr("class", "enter")
      .attr("x",0)
      .attr("transform",function(d, i) { return "translate("+(i * 32)+",0)"; })
      .attr("dy", ".35em").text(function(d) { return d.c; });
​
// ALGO REALLY STARTS HERE, WE SUPPOSE THAT WE ARE GIVEN AN ARRAY OF CHARS
reverseWord(chars,0,chars.length-1);
var lo = 0;
console.log(chars);
/// TROUP SI SI
var hi = chars.length-1;
​
for (i=chars.length-1;i>=0;i--) {
  lo = i;
  if ( chars[i].c !=" ") {
  } else {
    reverseWord(chars,lo,hi);
    hi = i;
    chars[i].c=" ";
  }
}
// reverse last word
hi = hi-1;
reverseWord(chars,lo,hi);
function swap(arr,a,b) {
  step++;
  var temp = arr[a];
​
  arr[a] = arr[b];
  arr[b] = temp;
​
  var copy = [];
  // KEEP TRACKS OF SWAPS FOR ANIMATIONS
  for (var i=0;i<arr.length;i++) {
    copy.push({c:arr[i].c,p:arr[i].p});
  }
  animations.push(copy);
  if (step == 1)
  {
      text.data(animations[done],function(d){ return d.p}).transition().duration(500)
      .attr("transform",function(d, i) {  return "translate("+(i * 32)+",0)"; });
      setTimeout(nextTransition,550);
  }
}
function reverseWord(arr,lo,hi)
{
  if (hi-lo<=1) return;
  while (lo<hi) {
    swap(arr,hi,lo);
    lo++;
    hi--;
  }
}
function nextTransition(){
    if (done< step-1) {
       done++;
       text.data(animations[done],function(d){ return d.p}).transition().duration(500)
          .attr("transform",function(d, i) { return "translate("+(i * 32)+",0)"; });
      setTimeout(nextTransition,550);
    }
}
</script>
​
​
​
​
​
​
    