SimpleBoxes

今日の進捗 2009.04.14

問題
与えられた配列の n 番目の要素 (先頭の要素は 0 番目とする) に対して、同じ値を持つ要素が、配列のその要素の前にいくつあるかを返す関数を作成して下さい。

例えば、以下のような配列

A,B,B,B,C,D,E,F,G,G,G,G,H,I,J,J,J,J,J,J,J,J,J,J,K,L

があった場合、

  • n = 0 の時は 0 (値が A である要素はひとつしかない)
  • n = 1 の時は 0 (値が B である最初の要素)
  • n = 2 の時は 1 (値が B である二番目の要素なので 1 を返す)
  • n = 3 の時は 2 (値が B である三番目の要素なので 2 を返す)
  • n = 4 の時は 0 (値が C である要素はひとつしかない)
  • ……以下、続く

のようになります。

とりあえずの解答 (perl のコード) は「続き」に。

続きを読む
このエントリーをはてなブックマークに追加

スポンサーリンク

Serene Bach 多言語への対応

Serene Bach では、多言語対応を行なうライブラリとして sb::Language というモジュールが用意されています。

sb::Language の主な役割は二つ。

  • 定型文字列の多言語対応
  • 文字コードの変換

Serene Bach 3 になって仕組みは若干変わりましたが、基本的な内容はほぼ一緒です。

定型文字列の取得

例えば、

my $error = sb::Language->get->string('No article.');

のようにすると $error に「No article.」に対応した文字列がセットされます。

比較的よく利用されるインタフェースなので、Serene Bach 3 では

my $error = sb->string('No article.');

という形式のショートカットも用意されています。

言語リソースは特定ディレクトリ内にテキストファイルとして置かれています。

  • リソースディレクトリ (例 : /lib/resource/)
    • ja.txt : 日本語リソース
    • en.txt : 英語リソース

Serene Bach 2 では、基本的な言語リソースはモジュール内に記述されていましたが、Serene Bach 3 では上述のリソースファイルに移っています。

文字コード変換

文字コードの変換処理は sb::Language モジュールにあるインタフェースを利用します。

my $output = sb::Language->get->convert($input,'sjis');

現在のところ、あまり高度で複雑な処理などは想定されてなく、単に Jcode.pm のラッパーとして機能しています。

将来的には標準モジュールである Encode を利用するように変更したいところです。

Serene Bach のコンストラクタ

sb::Language は Singleton オブジェクトなので、どこで取得しても同一なオブジェクトが取得できることが保証されています。

Serene Bach では、new 以外に get がコンストラクタとして利用できます。

sb::Language->get->string('No article.');

のように、より自然な形で利用できるようにしています。

get コンストラクタは、sb::Object を継承した全てのクラスで利用できます。

関連記事
このエントリーをはてなブックマークに追加

スポンサーリンク

mixi アプリを開発するのに携帯電話のメールアドレスが必須な件

「mixi アプリ」オープンβ版公開ということで、やはり一開発者としては気になるじゃないですか。

アプリ作成手順を見ると、まず開発者登録が必要らしいので、登録してみようと……

け、携帯電話のメールアドレスが必要なんですね、これ。……海外在住なので受け取れません。

そこで mixi 運営事務局にお問い合わせしてみました。頂いた返信メールにて

携帯電話をお持ちではない場合や、対応機種外の携帯をご利用の場合には、申し訳ございませんが、デベロッパー登録を行っていただくことはできかねます。

とのこと。

そう言えば、mixi に参加すること自体、携帯電話のメールアドレスが必須になったんでしたっけ。

携帯からの認証をおこなっていただかない限り、PCからの操作のみでは新規登録はできません。

(中略)

ユーザーの皆様にとってさらに安心感のあるコミュニティとしてmixi をご利用いただくために実施するもので、利用規約で禁止している迷惑行為等の被害を最小限にしていくための、安全性強化に関する取組みのひとつ

[mixi] ヘルプ > 登録 > 携帯がないと登録できないのですか?

ふむふむ。なるほど。

実際のところ、携帯電話のメールアドレスが必須になってから、当然ながら迷惑行為が減ったとして、どの程度の効果がこれまであったのか、一利用者としては気になるところです。

ちなみにインプレスが始めたサービス「GANREF」でもクラブメンバーになるのに mixi 同様「携帯電話のメールアドレスによる認証」が取り入れられています。

でも、mixi と決定的に違うのは、携帯電話がなくても登録する方法が用意されていることです (2009.04.11 現在)。

GANREF では、携帯電話がない場合、住所を記述して認証コードを郵送してもらうことで本人確認を行なっています。

[写真] GANREF から届いた認証メール

実際、私は海外から登録して、携帯電話のメールアドレスなしで GANREF のクラブメンバーになることができました。

ただし、私の場合認証コードの送付先は日本の住所を指定しました (海外の住所を受け付けているかどうかまでは確認していません)。

このエントリーをはてなブックマークに追加

スポンサーリンク

Serene Bach 管理画面の構成

管理画面を処理する Admin アプリケーションは、Serene Bach 3 でも中核と言えるアプリケーションです。

その核となるモジュール sb::App::Admin は Serene Bach 3 のアプリケーションモジュール群の中で最も複雑な構造になっています。

[図] Admin アプリケーションの基本フロー

メニュー構築

メニュー構築は主に初期化処理にあたります。有効な管理用プラグインをロードして、メニューを構築する処理が含まれます。

ログイン処理

ログイン処理は基本的に sb::Session というセッション管理用モジュールを使って行なっています。

ページ処理

管理画面はそれぞれのメニューを「ページ」として処理するページドリブン的なアプローチを取っています。

基本的には各メニューごとにモジュールがあり、それぞれのモジュールがページ処理を行ないます。sb::App::Admin では、状況に合わせて適切なモジュールを起動します。

管理画面モジュールの基本コード

管理画面の各モジュールは、処理する内容・出力する内容について、ページ内容のみを考慮すればよい構成になっています。

そのため、プラグインも含め管理画面の個々のモジュールは、それほど複雑な構成にはなっていません。

sub callback
{
  my $self = shift;
  return ( $self->regi() )
    ? $self->_update(@_)
    : $self->_display(@_);
}
sub _update
{
  my $self = shift;
  my $msg = undef;
  # 
  # クライアント (ブラウザ) からの入力を処理する
  # 
  return $self->_display('message'=>$msg);
}
sub _display
{
  my $self = shift;
  my %param = (
    'message' => undef,
    @_
  );
  my $temp = sb::Template->new($self->load_template('file'=>TEMPLATE));
  # 
  # 出力内容を処理する
  # 
  $self->common_parts($temp);
  $self->set_message($temp,$param{'message'});
  return $self->set_main($temp->output);
}

ほとんどの管理画面モジュールは、上述のようなコードを踏襲しています。管理用プラグインも同様です。

関連記事
このエントリーをはてなブックマークに追加

スポンサーリンク

Serene Bach フレームワーク

Serene Bach 3 は sb モジュールを起点としたフレームワークで構成されています。

このモジュール群は「Spica」という形で汎用化して公開しています (ただし、現在はバージョンが若干古めです)。

アプリケーションは sb モジュール内の run メソッド (sb::run) を通して起動します。

[図] CGI スクリプトの基本フロー

クライアントからアクセスされる CGI スクリプト自体はとてもシンプルな構成になっています。

use strict;
use lib qw(. ./lib ./ext);
eval {
  require sb;
  sb->run('app' => 'Main');
};

実際のスクリプトには、もう少し装飾がありますが、基本的なコードはこれだけです。

sb::run はアプリケーションを発動する起点になります。条件に応じて、起動するアプリケーションを変更する場合もあります。

上記のコードの場合、基本的には「Main」というアプリケーションを起動するように動作しますが、場合によって Main ではないアプリケーションが起動する場合もあります。

Serene Bach 3 では、主なアプリケーションとして以下のものがあります。

Admin
ウェブログの管理画面を処理します。
Main
ウェブログを動的に出力します。プレビューなどにも利用されます。
Counter
カウンターの表示、アクセスログの取得を行ないます。
Install
インストール・アップグレード処理を行ないます。
Xmlrpc
XMLRPC の処理を行ないます。

他にもありますが、とりあえず主だったものをここでは挙げました。

管理画面を処理する Admin アプリケーションは、Serene Bach 3 のアプリケーションモジュール群の中で最も複雑な構造になっています。これについては後日、改めて触れたいと思います。

関連記事
このエントリーをはてなブックマークに追加

スポンサーリンク

Unknown error

データベースに正しくアクセスできませんでした。Serene Bach が正しくインストールされているかご確認ください。

[図] Serene Bach 3 エラー画面

現在、Serene Bach 3 のインストーラを作り込んでいる最中です。

これまで Serene Bach 3 のバージョンアップで、データベーステーブルの更新が必要な場合、install.cgi に再度アクセスする必要がありました。

この部分の仕様を見直して、バージョンアップ後、データベーステーブルの更新が必要な場合は、管理画面から自動的にデータベース更新画面に移行できるように変更しています。

そのついでにインストールチェックを行なうようにして、インストール前に管理画面などにアクセスすると上述したようなエラーが出るようにしてみました。

このエントリーをはてなブックマークに追加

スポンサーリンク

Serene Bach のクラス構造

Serene Bach は CPAN への依存性が比較的薄い構造になっています。

標準モジュールもあまり利用していなくて、例えば、CGI.pm も使っていません。

これはポリシーというより惰性に近いものがあります。「CGI.pm ぐらいは使えばいいのに」と私自身も思います。ちなみに Serene Bach で CGI.pm に相当するものは sb::Interface というクラスですが、独自に開発したものではなく、cgi-lib.pl をリファクタリングしたような形になっています。

Serene Bach 2.* (以下、SB2) からオブジェクト指向的なアプローチを取り入れて、Serene Bach 3 (以下、SB3) ではクラス構造を若干見直しました。

Serene Bach 2 のクラス構造

SB2 のクラス構造をツリーとして表すと、以下のようになります。

  • sb
  • sb::App
    • sb::App::Admin
      • sb::Admin::Bookmarklet
      • sb::Admin::Help
      • sb::Admin::List
        • sb::Admin::Category
        • sb::Admin::Entry
          • sb::Admin::Amazon
          • sb::Admin::Config
          • sb::Admin::Editor
          • sb::Admin::Upload
          • sb::Admin::User
            • sb::Admin::Profile
        • sb::Admin::Link
        • sb::Admin::Message
        • sb::Admin::Status
        • sb::Admin::Template
        • sb::Admin::Trackback
      • sb::Admin::Login
      • sb::Admin::Preview
      • sb::Admin::Rebuild
      • sb::Admin::Refusal
      • sb::Ping
    • sb::App::Builder
    • sb::App::Counter
    • sb::App::Feed
    • sb::App::Install
    • sb::App::Main
    • sb::App::Mobile
    • sb::App::Rsd
    • sb::App::Trackback
    • sb::App::Xmlrpc
    • sb::Aws
    • sb::Receipt
  • sb::Build
  • sb::Config [*]
  • sb::Content
    • [#] sb::Content::Entry
    • [#] sb::Content::Message
    • [#] sb::Content::Profile
    • [#] sb::Content::Trackback
  • sb::Data
  • sb::Data::Object
    • sb::Data::Amazon
    • sb::Data::Category
    • sb::Data::Entry
    • sb::Data::Image
    • sb::Data::Link
    • sb::Data::Message
    • sb::Data::Plugin
    • sb::Data::Session
    • sb::Data::Template
    • sb::Data::Trackback
    • sb::Data::User
    • sb::Data::Weblog
  • sb::Driver [*]
    • sb::Driver::Text
  • sb::Interface [*]
  • sb::Language [*]
    • sb::Language::en
    • sb::Language::ja
  • sb::Lock
  • sb::Mailer
  • sb::Object
  • sb::Plugin [*]
  • sb::Session
  • sb::TemplateManager
  • sb::Text
  • sb::Time

[*] がついたクラスは Singleton になっています。

当初、 Singleton という概念を知らずに実装していて、パッケージ毎に定義されたスタティックな変数を使うことによって Singleton を実現しています。

この実装のため、SB2 は mod_perl などプロセスが永続するような環境では正しく動作しません。

[#] がついたクラスは、上位クラスに対して直接的に継承していません。しかしながら、強く依存しているため、ツリー上に表記しています。

Serene Bach 3 のクラス構造

SB3 のクラス構造をツリーとして表すと、以下のようになります。

  • sb::Object
    • sb::SingleObject
      • sb
      • sb::Config
      • sb::FastCGI
      • sb::Language
    • sb::RequestObject
      • sb::Content::Feed
      • sb::Content::Mobile
      • sb::Interface
      • sb::Local
        • sb::Local::jp
        • sb::Local::nz
      • sb::Plugin
    • sb::App
      • sb::Admin::Editor
        • sb::Admin::TemplateEditor
      • sb::App::Admin
        • sb::Admin::Help
        • sb::Admin::List
          • sb::Admin::CommentOption
            • sb::Admin::Message
            • sb::Admin::Trackback
          • sb::Admin::Entry
            • sb::Admin::Amazon
            • sb::Admin::Category
            • sb::Admin::Home
            • sb::Admin::Quickpost
            • sb::Admin::Upload
          • sb::Admin::EntryList
          • sb::Admin::Link
          • sb::Admin::Template
          • sb::Admin::User
            • sb::Admin::Profile
        • sb::Admin::Login
        • sb::Admin::Preview
      • sb::App::Builder
      • sb::App::Counter
      • sb::App::Feed
      • sb::App::Install
      • sb::App::Main
      • sb::App::Receipt
      • sb::App::Rsd
      • sb::App::Upgrade
      • sb::App::Xmlrpc
    • sb::Build
    • sb::Content
      • [#] sb::Content::Cetgory
      • [#] sb::Content::Common
      • [#] sb::Content::Entry
      • [#] sb::Content::List
      • [#] sb::Content::Message
      • [#] sb::Content::Profile
      • [#] sb::Content::Trackback
    • sb::Data
    • sb::Data::Object
      • sb::Data::Amazon
      • sb::Data::Category
      • sb::Data::Config
      • sb::Data::Customdata
      • sb::Data::Entry
      • sb::Data::Image
      • sb::Data::Link
      • sb::Data::Message
      • sb::Data::Plugin
      • sb::Data::Session
      • sb::Data::Template
      • sb::Data::Trackback
      • sb::Data::User
      • sb::Data::Weblog
    • sb::Driver
      • sb::Driver::SqlBasea
        • sb::Driver::Mysql
        • sb::Driver::Sqlite
      • sb::Driver::Text
      • sb::Driver::TextOld
    • sb::File
      • sb::File::Audio
        • sb::File::Object [%]
      • sb::File::Dir
        • sb::File::Object [%]
      • sb::File::Image
        • sb::File::Object [%]
      • sb::File::Uploader
    • sb::File::Audio::Info
    • sb::InitParser
    • sb::LanguageBase
      • sb::Language::en
      • sb::Language::ja
    • sb::Net
      • sb::Net::Aws
      • sb::Net::Mailer
      • sb::Net::Ping
    • sb::Session
    • sb::Test
    • sb::Text
    • sb::Time
  • sb::Template
  • sb::Utils
  • sb::File::MimeType
  • sb::Text::Base
    • sb::Text::autobreak
      • sb::Text::autolink
    • sb::Text::md5

SB3 では、ほとんどのクラスが sb::Object という基底クラスを継承するような構造になっています。

sb/Object.pm には Singleton を扱う sb::SingleObject / sb::RequestObject というクラスも含まれています。

SB3 では、これらのクラスを継承したクラスは Singleton として扱われます。これらのクラスは mod_perl / FCGI 環境下での動作も想定しています。

SingleObject と RequestObject では永続性が異なります。通常の CGI として動作させた場合には、両者の違いはありません。実は SB2 にもひっそりと sb::Object を移植しているのですが、現時点では利用されていません。

基本的に多重継承はしない構成にしていますが、例外的に [%] をつけた sb::File::Obect だけは多重継承をしています。あまり良い構成とは言えないので、今後 sb::File のクラス構成は変更するかもしれません。

関連記事
このエントリーをはてなブックマークに追加

スポンサーリンク

solipo 0.07

solipo ver 0.07 を公開しています。→ [solipo 紹介ページ]

solipo は、Windows 上で動作する polipo の GUI ラッパーアプリケーションです。

「solipo」をダウンロード

solipo 0.07 では、ver 1.0.5 のプレリリースとして公開された polipo build 20080907 を適用しています。

古いバージョンの solipo からは、 solipo.exe と polipo.exe を差し替えることでバージョンアップできます。

これまでの関連記事
このエントリーをはてなブックマークに追加

スポンサーリンク

ツリー構造の実装をリファクタリングする

ツリー構造 (多分木 : N 分木) の実装」「ツリー構造の幅優先走査」とツリー構造を表現するコードについて記述してきました。

ここでは、先の記事で使ったコードをリファクタリングして、より汎用性と移植性の高いコードを作成してみたいと思います。

ツリー構造を表現する構造体

これまでのコードでは、ルートノードからの「深さ」を示す depth という変数を構造体の中で保持していました。

ルートノードからの深さは比較的簡単に求めることができるので、あえて持つ必要はありません。

利用頻度を考慮するとあえてメンバーとして保持しなくてもよいケースがほとんどでしょう。むしろこのような特殊な変数を保持することでコードの見通しなどが悪くなってしまったりする危険性があります。

ツリー構造を表現するには、最低限子ノードと隣ノードのポインタを保持しておけばいいわけで、それにノードで保持したい情報を加えた構造体にするのがよいでしょう。

typedef struct node {
  const char* name;
  struct node* child;
  struct node* next;
} node_t;

のように depth をなくし、構造体をシンプルにします。

ノードジェネレイター

これまでのコードでは、以下のような append 関数を用意して、ノードの初期化を行なっていました。

void append(const char* name, node_t* parent, node_t* node)
{
  node->name = name;
  node->depth = 0;
  node->child = NULL;
  node->next = NULL;
  if (parent == NULL) return;
  node->depth = parent->depth + 1;
  if (parent->child == NULL)
  {
    parent->child = node;
  }
  else
  {
    node_t* last = parent->child;
    while (last->next != NULL)
    {
      last = last->next;
    }
    last->next = node;
  }
}

汎用性を高め、後からのメンテナンスを考慮すると、初期化部分は分離した方がよいでしょう。

ふうこさんからのご指摘の通り、node_t のポインタを返り値として返す create 関数を作成してみます。

node_t* create(const char* name)
{
  node_t* node; // *1
  node->name = name;
  node->child = NULL;
  node->next = NULL;
  return node;
}

このようにしたいところですが、このコードは正しく動作しません

*1 で指定している node はローカルな変数なので、create 関数のブロックを抜けると消えてしまいます。malloc 関数を使ってメモリを確保する必要があります。

node_t* create(const char* name)
{
  node_t* node = (node_t*)malloc( sizeof(node_t) );
  if ( node == NULL ) exit( EXIT_FAILURE );
  node->name = name;
  node->child = NULL;
  node->next = NULL;
  return node;
}

ノードデストラクタ

割り当てたメモリは、どこかで解放する必要があります。

今回のような短いプログラムでは、特に必要ではないかもしれませんが、念のため後始末を行なう関数も作成しておきましょう。

void destroy(node_t* node)
{
  free(node);
  node = NULL;
}

ノードを破棄する create 関数は、シンプルで単純に free 関数を呼び出しているだけです。二重に free しないようにノードのポインタに NULL をセットしています。

ついでにツリーそのものを破棄する関数も考えてみます。ルートノードを渡したら、そのツリーの全ノードを解放します。

void destroy_tree(node_t* node)
{
  if (node == NULL) return;
  destroy_tree(node->child);
  destroy_tree(node->next);
  destroy(node);
}

ここでも再帰的にノードを辿っていき、削除を実行しています。

注意して欲しいのは、自身の破棄を再帰した後に行なっているところです。こうしないと、再帰する前に自身が破棄されてしまい、正しく動作しません。

関連関数の変更

ノードの構造体から depth というパラメータを除いたので、ノードを表示する関数などはそのままでは動きません。

「深さ」を外部から引き渡すように変更します。

void append(node_t* parent, node_t* node)
{
  if (parent->child == NULL)
  {
    parent->child = node;
  }
  else
  {
    node_t* last = parent->child;
    while (last->next != NULL)
    {
      last = last->next;
    }
    last->next = node;
  }
}

void display(node_t* node, int depth)
{
  int i;
  for (i=0;i<depth;i++)
  {
    printf(" ");
  }
  printf("- %s\n",node->name);
}

void show_tree_dfs(node_t* node, int depth)
{
  if (node == NULL) return;
  display(node, depth);
  show_tree_dfs(node->child, depth + 1);
  show_tree_dfs(node->next, depth);
}

#define STACK_NUM 100
void show_tree_bfs(node_t* node)
{
  if (node == NULL) return;
  node_t* queue[STACK_NUM];
  int depth = 0;
  int num = 0;
  queue[ num++ ] = node;
  while ( 1 )
  {
    node_t* buf[STACK_NUM];
    int buf_num = 0;
    while ( num != 0 )
    {
      node = queue[ --num ];
      while (node != NULL)
      {
        display(node, depth);
        if (node->child != NULL)
        {
          buf[ buf_num++ ] = node->child;
          if (buf_num >= STACK_NUM) exit( EXIT_FAILURE );
        }
        node = node->next;
      }
    }
    if ( buf_num == 0 ) break;
    while ( buf_num != 0 )
    {
      queue[ num++ ] = buf[ --buf_num ];
      if (num >= STACK_NUM) exit( EXIT_FAILURE );
    }
    depth++;
  }
}

ツリーを深さ優先で再帰的に走査する関数 show_tree_dfs でも「深さ」のパラメータを渡すように変更しています。

子ノードを辿るときだけ、depth + 1 で引き渡しているのがポイントです。

完成

できあがったプログラムは、それなりに長くなってしまうので「続き」に記載します。

続きを読む
このエントリーをはてなブックマークに追加

スポンサーリンク

ツリー構造の幅優先走査

ツリー構造 (多分木 : N 分木) の実装では、ツリー構造を実現する構造体とツリー全体を再帰的に操作する手法について触れました。

今回はツリー構造を「幅優先で走査する」方法について考えます。

おさらい

前回に実装したコードは以下のような形になっています。

#include <stdio.h>

typedef struct node
{
  const char* name;
  int depth;
  struct node* child;
  struct node* next;
} node_t;

void append(const char* name, node_t* parent, node_t* node)
{
  node->name = name;
  node->depth = 0;
  node->child = NULL;
  node->next = NULL;
  if (parent == NULL) return;
  node->depth = parent->depth + 1;
  if (parent->child == NULL)
  {
    parent->child = node;
  }
  else
  {
    node_t* last = parent->child;
    while (last->next != NULL)
    {
      last = last->next;
    }
    last->next = node;
  }
}

void display(node_t* node)
{
  int i;
  for (i=0;i<node->depth;i++)
  {
    printf(" ");
  }
  printf("- %s\n",node->name);
}

void show_tree_dfs(node_t* node)
{
  if (node == NULL) return;
  display(node);
  show_tree_dfs(node->child);
  show_tree_dfs(node->next);
}

int main()
{
  node_t root;
  append("root",NULL,&root); // create root
  node_t n1,n2,n3;
  append("n1",&root,&n1);
  append("n2",&root,&n2);
  append("n3",&root,&n3);
  node_t n11,n12;
  append("n1-1",&n1,&n11);
  append("n2-2",&n1,&n12);
  node_t n21,n22;
  append("n2-1",&n2,&n21);
  append("n2-2",&n2,&n22);
  node_t n31;
  append("n3-1",&n3,&n31);
  node_t n111,n221;
  append("n1-1-1",&n11,&n111);
  append("n2-2-1",&n22,&n221);
  // display tree
  printf("show tree depth first\n");
  show_tree_dfs(&root);
  return 0;
}

main 関数や include 文もいれているので、コンパイルして動作させることができます。

main 関数では、以下のツリー構造を作成して、show_tree_dfs 関数を呼び出して、再帰的にツリー構成を表示しています。

  • root
    • n1
      • n1-1
        • n1-1-1
      • n1-2
    • n2
      • n2-1
      • n2-2
        • n2-2-1
    • n3
      • n3-1

幅優先の走査

さて、前回失敗した「幅優先」の走査を考えてみます。

幅優先の走査では、ルートノードから「深さ」が同じノードを全て走査してから、次の深さのノードに移っていきます。

上述したサンプルのツリー構成は

- root
 - n1
 - n2
 - n3
  - n1-1
  - n1-2
  - n2-1
  - n2-2
  - n3-1
   - n1-1-1
   - n2-2-1

のように表現されます。

前回は再帰的に走査を行なう手法を取ってみましたが、今回は再帰を利用しないアプローチで実装してみます。

サンプルのツリー構成に走査順番をつけると、次のようになります。

  • root (1)
    • n1 (2)
      • n1-1 (5)
        • n1-1-1 (10)
      • n1-2 (6)
    • n2 (3)
      • n2-1 (7)
      • n2-2 (8)
        • n2-2-1 (11)
    • n3 (4)
      • n3-1 (9)

ルートノード root を見た後は、n1 → n2 → n3 と走査しますが、そのときに、n1 の子ノード・n2 の子ノード・n3 の子ノードを記録しておき、同じ深さのノードがなくなった後で、記録しておいた子ノードを走査するようにすれば、うまくいきそうです。

子ノードの記録はキュー (待ち行列) で実装できるでしょう。ここではアルゴリズムだけを考えるので、キューのメモリ割当とか実装は気にしないようにします。

ただ、動作しないと意味はないので、待ち行列の行数を固定値にして、キューがあふれる場合はプログラムを終了するようにしちゃいます。

#define STACK_NUM 100
void show_tree_bfs(node_t* node)
{
  if (node == NULL) return;
  node_t* queue[STACK_NUM]; // *1
  int num = 0;
  queue[ num++ ] = node; // *2
  while ( 1 )
  {
    node_t* buf[STACK_NUM]; // *3
    int buf_num = 0;
    while ( num != 0 ) // *4
    {
      node = queue[ --num ]; // *5
      while (node != NULL) // *6
      {
        display(node); // *7
        if (node->child != NULL) // *8
        {
          buf[ buf_num++ ] = node->child; // *8
          if (buf_num >= STACK_NUM) exit(0); // *9
        }
        node = node->next; // *10
      }
    }
    if ( buf_num == 0 ) break; // *11
    while ( buf_num != 0 ) // *12
    {
      queue[ num++ ] = buf[ --buf_num ]; // *12
      if (num >= STACK_NUM) exit(0);
    }
  }
}
node_t* queue[STACK_NUM];
ノードを格納するキュー (作業ノード群) を宣言します。動作としては、キューになっていますが、実装自体はスタックになっています。
queue[ num++ ] = node;
まずキューに最初のノードを格納します。ルートノードが渡されたら、ルートノードがキューに格納されます。num++ となっているのに注意。num++++num は意味が異なります。前者はまず num という値を渡してから +1 され、後者はまず num の値を +1 してから値を渡します。
node_t* buf[STACK_NUM];
ループの中で、見つけた子ノードを一時的に格納するスタック (バッファ) を宣言します。
while ( num != 0 )
num はキューに格納されたノードの数です。これが 0 であれば、格納されたキューの中身を全て走査したことになります。
node = queue[ --num ];
キューの最初に格納された値を取り出しています。この行だけ見ると、後から格納された値を取り出しているようですが、動作としては最初に見つけた子ノードから取り出されます。
while (node != NULL)
キューから取り出したノードを起点として、隣ノードがなくなるまで走査します。
display(node);
ノードの表示処理はここで行ないます。
if (node->child != NULL) buf[ buf_num++ ] = node->child;
対象ノードに子ノードが存在する場合、子ノードをバッファに格納しておきます。幅優先で走査を行なうため、バッファに一時的に保管しておきます。(深さ優先の場合と異なり) この時には子ノードの走査は行ないません。
if (buf_num >= STACK_NUM) exit(0);
buf_num はバッファに格納されたノードを数を示しています。これが STACK_NUM を超えると、正しく動作しないので、プログラムを終了しています。exit 関数をコールしているので stdlib.h をインクルードする必要があります。
node = node->next;
隣ノードに移ります。こうして同じ「深さ」のノードを辿って走査します。
if ( buf_num == 0 ) break;
buf_num が 0 の場合は、それ以上の「深さ」のノードが存在しないということですから、ループを抜けて処理を終了します。
while ( buf_num != 0 ) { queue[ num++ ] = buf[ --buf_num ]; }
buf_num が 0 でない場合、バッファに一時的に格納しておいた子ノード群をキュー (作業ノード群) にコピーします。

キューとスタック

キューとスタックは似ていますが、動作がやや異なります。

キューは待ち行列とも言われていて、最初に入ったものから先に抜けていきます (First in, First out)。一方、スタックは最後に積み上げたものから先に出て行きます (Last in, First out)。

前述の例だと

queue[ num++ ] = node;

で、行列 queue の末尾に要素を追加しています。追加した要素を使うときは

node = queue[ --num ];

のようにしているので、末尾の要素から取り出しています。

最初に見つけた子ノードから順番の処理をしていきたいので、単純にこの手法を使うと、順番が逆になってしまいます。

しかしながら、ここでの実装では、ふたつのスタックを利用することにより、キューのように動作するようになっています。

このエントリーをはてなブックマークに追加

スポンサーリンク

2/6