木構造の幅優先探索アルゴリズムを忘れた状態から自力で考えてみた結果 gumbo-query

 gumbo-queryがHTMLからパースしてくれた木構造を、ルートノードから再帰アルゴリズム幅優先探索をしようと思ったのだが完全に忘れていたので数時間頭を捻って出した結果がこちら。
 間違ってたら恥ずかしいだけです、はい。
 ワイの脳みそ大丈夫か(´・ω・`)・・・
 使用ライブラリは、STL、boost 1.67(formatを使っている)、gumbo-parser、gumbo-query。
 ちなみに木構造を幅優先で探索するのであれば再帰アルゴリズムを使わなくても出来るし、マルチスレッド化してもっと速く実装出来る。

 実装のコツは深さ0の場合を特別扱いし、深さ0において取得した子ノード全てをstatic変数で定義してあるupper_layerに入れるところから始めること。
 そして深さ1以上の再帰処理ルーチンにおいて、先に保持しておいた1層上のノード集合(upper_layer)を参照することで、木構造においてでも各サイクルごとに各層のノードが全て簡単に取れるようになるという感じ。
 0層において子ノードを保持し、それをキーとして始める方法以外を一つの関数で再帰的に行う処理を自力で考えるのは結構きついだろう。ていうかそもそもできるんだっけ?

void output_html_tree_breath_first(
	CNode &_node, int _depth, ofstream &_ofile
)
{
	static deque<CNode> upper_layer;
	static char tab('-');
	static CNode dummy;

	if (_depth == 0)
	{
		_ofile << _node.tag() << endl;
		for (size_t c = 0; c < _node.childNum(); c++)
		        upper_layer.push_back(_node.childAt(c));
		output_html_tree_breath_first(dummy, _depth + 1, _ofile);
	}
	else if (_depth > 0)
	{
		if (upper_layer.size() == 0)
			return;

		deque<CNode> next_upper_layer;
		string tabs(_depth, tab);
		for (auto n : upper_layer)
		{
			if (!n.tag().empty())
			{
				string line = (
					format("%1%(%2%)") % (tabs + n.tag()) % _depth
					).str();
				_ofile << line << endl;
			}

			for (size_t c = 0; c < n.childNum(); c++)
				next_upper_layer.push_back(n.childAt(c));
		}
		upper_layer = next_upper_layer;
		output_html_tree_breath_first(dummy, _depth + 1, _ofile);
	}
	return;
}

 深さ優先探索はこちら。多分合ってるとは思うが・・・。

void output_html_tree_depth_first(
	CNode &_node, int _depth, ofstream &_ofile
)
{
	string tabs(_depth, '-');
	if (!_node.tag().empty())
	{
		string line = (
			format("%1%(%2%)") % (tabs + _node.tag()) % _depth
			).str();
		_ofile << line << endl;
	}

	if (0 == _node.childNum())
		return;
	for (size_t c = 0; c < _node.childNum(); c++)
	{
		CNode child = _node.childAt(c);
		output_html_tree_depth_first(child, _depth + 1, _ofile);
	}
}

 以下のように使う。

CDocument doc;
doc.parse(text);//textはstring。中身はUTF-8にすること。
CSelection c = doc.find("html");
CNode html = c.nodeAt(0);
{
	ofstream file("depth_first.txt");
	output_html_tree_depth_first(html, 0, file);
	ofstream file2("breath_first.txt");
	output_html_tree_breath_first(html, 0, file2);
}

 出力結果はまぁ大丈夫そう。