2chのレスをアンカで並びかえる

アンカで並び替えて、例えばこのように7の次に11を表示するような処理を説明します。

さて、2chの板はこのようになっています。

アンカは、Web(網)と同様に網の目のようにリンクしています。これは有向グラフです。

有向グラフは難しい。

循環が困る。

循環は"未来へのアンカ"を無視すれば防げます。

このような未来へのアンカ>>100を無視する

これで問題が無閉路有向グラフになります。

燐隊長が困る。

燐隊長は、"一番大きなアンカ"の8をとることにしましょう。

これで問題がこのような単連結無閉路有向グラフになります。

実装

var testdata = [
  [],                // 配列のインデックスを1から始めたいので詰め物をする
  [],                // 1:
  [1],               // 2: >>1
  [1],               // 3: >>1
  [],                // 4:
  [4],               // 5: >>4
  [5],               // 6: >>5
  [5],               // 7: >>5
  [4,100],           // 8: >>4 >>100
  [1,2,3,4,5,6,7,8], // 9: 燐隊長
  [],                //10: 
  [5]];              //11: >>5

function removeFutureAnchor(aData) {
  return aData.map(function(res, i) {
    return res.filter(function(x) {
      return x < i;
    });
  });
}

function maxAnchor(aData) {
  //配列の最大の要素を求めるmax関数。
  function max(aArray) {
    var r = -1;
    for (var i = 0; i < aArray.length; i++) {
      if (aArray[i] > r) r = aArray[i];
    };
    return r;
  }
  return aData.map(function(res) {
    return res.length ? [max(res)] : [];
  });
}

//木を作る。転置インデックスに似ている。
function makeTree(aData) {
  var table = [];
  aData.forEach(function(res, i) {
    table[i] = [i];
    res.forEach(function(x) {
      table[x].push(i);
    });
  });
  return table;
}

makeTreeは[親、子、子、子]のように木を表現します。さっきのグラフと見比べてください。([0]は詰め物なので無視してください)

makeTree(maxAnchor(removeFutureAnchor(testdata))));
->
 [[0],
 [1,2,3],
 [2],    
 [3],    
 [4,5,8],
 [5,6,7,11],
 [6],
 [7],
 [8,9],
 [9],
 [10],
 [11]]

この木を順番にたどって直列にするのがserialize関数です。
木の入れ子構造に、関数fの再帰が威力を発揮します。

function serialize(aData) {
  var result = [];
  var done = aData.map(function(_) {return false;});
  function f(res) {
    if (!res.length) return;
    if (!done[res[0]]) {
      done[res[0]] = true;
      result.push(res[0]);
    }
    res.slice(1).map(function(x) {
      return aData[x];
    }).forEach(f);
  }
  aData.forEach(function(res) {
    if (!done[res[0]]) f(res);
  });
  return result;
}

serialize(makeIndex(maxAnchor(removeFutureAnchor(testdata))));

-> [0,1,2,3,4,5,6,7,11,8,9,10]

これで完成です。

発展として、木を統合する複雑なコードはこちらにあります。
木の統合(SchemeをJavaScriptに移植した) - Gemmaの日記

循環が困る。

燐隊長が困る。

実装

参考文献