phpとJavaScriptでの再帰処理

24 3月
3月 24, 2013

(1) phpでの再帰処理

　最初はphpからです。下記のようなxmlファイル(ファイル名:sample.xml)の処理をします。

<?xml version="1.0" encoding="utf-8"?>

<root>

<question>
　<answer>answer1.1</answer>
　<question>
　　<answer>answer1.2</answer>
　</question>
</question>

<question>
　<answer>answer2</answer>
</question>

</root>

questionタグのひとつが入れ子になっています。このxmlの中のAnswerタグの内容を配列に入れてみます。phpのコードは下記。

<?php

$tmptext = file_get_contents('./sample.xml');

$xml = simplexml_load_string($tmptext);


$q_ary = array();

foreach ($xml->question as $q) {

	$tmpary = array();

	$a_obj = new find_question();

	$tmpary = $a_obj->action($q,$tmpary);

	array_push($q_ary,$tmpary);

}


var_dump($q_ary);


class find_question {

function __constructor() {
}

public function action($q,$tmpary) {


array_push($tmpary, (string)$q->Answer);

if ($q->question) {

	$newq = $q->question;

	$a_obj = new find_question();

	$tmpary = $a_obj->action($newq,$tmpary);

}

return $tmpary;
}

} // end of find_question


?>

9行目の foreach は一番浅い階層の question タグのみをループします。そのため、2回のループです。入れ子になった question タグを取り扱うために、 find_question クラスを用意しました。questionタグに、さらに questionが含まれていたら、子のquestionタグを切り出します。切り出したquestionタグに対して再帰処理をします。phpだとxmlの取扱いが簡単です。javascriptだと、こんなに簡単にはいかないですね。
　この様な再帰処理は関数でもかけますが、クラスを用いて、再帰処理をしたほうが何か安心感があります（気持ちの問題だけなのですが）。
　再帰処理は何か不思議な感じがします。実際のコードでは、ほぼ始めて書いてみたのですが、いざ書いてみると、これまで書いてきたコードの中にも、再帰で書くべきものがたくさんあったような気がしてきました。

　21行目の var_dump($q_ary)の出力内容です。

array(2) {
  [0]=>
  array(2) {
    [0]=>
    string(9) "answer1.1"
    [1]=>
    string(9) "answer1.2"
  }
  [1]=>
  array(1) {
    [0]=>
    string(7) "answer2"
  }
}

(2) JavaScriptでの再帰処理

　次に、JavaScriptでも、同じような再帰処理を書いて見ました。下記のxmlファイル(sample.xml)を読み込んで、その中のAnswerタグの要素を配列に格納します。先のxmlよりも多少深く入れ子になっています。questionタグは入れ子になっていますが，配列に格納するときには入れ子にせずに，2次元配列として取り扱っています。

<?xml version="1.0" encoding="utf-8"?>

<root>

<question>
<answer>answer1.1</answer>
<question>
<answer>answer1.2</answer>
<question>
<answer>answer1.3</answer>
</question>
</question>
</question>

<question>
<answer>answer2.1</answer>
<question>
<answer>answer2.2</answer>
</question>
</question>

<question>
<answer>answer3</answer>
</question>

</root>

questionタグが入れ子になっていて、そのところが再帰処理となります。先にphpでの再帰処理を書いたのですが、phpがサーバー側で、JavaScriptがクライアント側です。サーバーとクライアントでxmlデータのやり取りをすることを想定しています。その場合、同じようなxmlをphpとJavaScriptで扱うことになります。
　下記が、全体のHTMLです。Answer タグの内容を格納する配列は、a_ary (80行)です。

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
"http://www.w3.org/TR/html4/strict.dtd">

<html><head>

<meta content="text/html; charset=UTF-8" http-equiv="content-type">

<meta http-equiv="imagetoolbar" content="false" />

    <meta charset="UTF-8">
    <meta content="chrome=1" http-equiv="X-UA-Compatible">
    <meta content="tool for simple question" name="application-name">
    <meta content="you can use expression" name="description">
    <meta content="HTML5,javaScript,Canvas" name="keywords">
    <meta content="somebody" name="Author">

<title>test for simple question</title>

    <link rel="stylesheet" href="jquery/jquery-ui.css" type="text/css">
    <script src="jquery/jquery.js" type="text/javascript"></script>
    <script src="jquery/jquery-ui.js" type="text/javascript"></script>

<script type="text/javascript">
//<![CDTA[

var sample_xml;

function read_xml() {

var tmp = new Date().getTime();
    $.ajax({
        url:'./sample.xml?' + tmp,
        type:'get',
        dataType:'text',
        timeout:5000,
	async:false,
        success:function(xmltext,status){

if(status!='success')return;

//alert(xmltext);

sample_xml = text2xml(xmltext);


// firefoxのみ。xmlを表示する。
/*
if (typeof XMLSerializer != "undefined") {
var tmpserial = new XMLSerializer();
alert(tmpserial.serializeToString(sample_xml));
}
*/

find_node(sample_xml);

//alert(a_ary);

var divbox = document.getElementById("divbox");

var ary2text = 'array (<br /><br />';

for (i = 0; i < a_ary.length; i++) {

	ary2text = ary2text + ' [ ' + a_ary[i] + ' ]';

	if (i == a_ary.length - 1) {
		ary2text = ary2text + '<br />';
	} else {
		ary2text = ary2text + ',<br /><br />'
	}

}

ary2text = ary2text + '<br />)';
divbox.innerHTML = ary2text;

}
});
}


var a_ary = new Array();

function find_node(xml) {

// 直接の子要素である question のみを選択したい。

$(xml).find('root').find('> question').each(function(){

	var tmpary = new Array();

	var answer = $("> Answer",this).text();
	tmpary.push(answer);

	// 入れ子のquestion の処理

	if ($(this).find('> question').length) {

		var newq = $(this).find('> question')[0];
		tmpary = find_q(newq,tmpary);

	}
	a_ary.push(tmpary);
});
}


function find_q(q,tmpary) {

var answer = $("> Answer",q).text();

//alert(answer);

tmpary.push(answer);

if ($(q).find('> question').length) {

var newq = $(q).find('> question')[0];
tmpary = find_q(newq,tmpary);

}
return tmpary;
}


// テキストをxmlに変換。もともと xml ならばそのまま。

function text2xml(xmltext) {

if (!($.isXMLDoc(xmltext))) {

if (find_msie.use == 'no') {

var dbObj = new DOMParser();
var xml = dbObj.parseFromString(xmltext,"text/xml");

} else {

xml = new ActiveXObject("Microsoft.XMLDOM");
xml.async = "false";
xml.loadXML(xmltext);

}

} else {
var xml = xmltext;
}

return xml;
}

// IEかどうか判定
find_msie.use = "no";

function find_msie() {
find_msie.use = 'yes';
}

function startup() {
read_xml();
}

//]]>
</script>


</head>

<body onload="startup();">

<!--[if IE]>
<script language="JavaScript" type="text/javascript">
find_msie();
alert('you use IE!');
</script>
<![endif]-->

<div id='divbox' style="color:#000000; position: absolute; left:10px; top: 10px; background-color: #f0f0f0; height:400px; width:400px; border:solid 1px; padding: 10px;"></div>

</body></html>

　166行目に、IEであるかどうか判断するところがあります。xmlを取り扱う時に、IEの場合は書き分けないといけません。124行目にtextデータをxmlオブジェクトに変換する関数があります。この時に、IEであるかないかで場合分けをしています。
　82行目の関数 find_node が Answer タグを探すものです。JavaScriptでxmlを扱う場合には、find().each でタグを処理していくときに、入れ子になったタグをすべて対象として、処理をしてしまいます。直下のタグのみを取り扱う場合には find(‘> question’) のように、不等号を入れて指示をします。105行目の find_q が再帰的な処理をするための関数です。　97行にあるように、インデックスを指定して子要素をとりだすなど、多少込み入ったやり方になっています。q としたり $(q) としたりして、JavaScript と jQueryを行き来しています。もっとスマートな方法があるのかもしれません。
　57行以降が、配列 a_ary の内容を画面に書き出すところです。何か配列をそれらしく表示する関数が欲しい所です。

最終の画面表示は下記のようになります。入れ子になったquestionタグですが，配列では入れ子にしていません。横に並べています。