Learn Struts（7）

Strutsで作成するアプリからlog4jを使えるようにしてみました。
せっかくなので、ApacheのCommons Loggingを通してlog4jを使ってみます。

設定

1. まずlog4j.jarをWebContent/WEB-INF/libにコピペします。（commons-logging.jarはstruts-blankをインポートすれば最初からWebContent/WEB-INF/libに入っています。）

最初$CATALINA_BASE/libに入れていたのですが、特定のアプリケーションからのみ参照できるようにしたい場合は、WEB-INF/libに入れるのが慣例のようです。
Eclipseを使ってる場合はBuild Pathからライブラリ追加しても使えないので注意してください。Tomcatが参照できる場所に置かないといけません。

2. log4j.xmlをsrcに置きます。

3. commons-logging.propertiesをsrcに置きます。中身は、

org.apache.commons.logging.Log=org.apache.commons.logging.impl.Log4JLogger

とします。

動作確認

簡単に確認できればいいので、生成したloggerのクラス名を表示するアクションクラスを作りました。
[TestAction.java]

public class TestAction extends Action {
    @Override
    public ActionForward execute(ActionMapping mapping, ActionForm form,
            HttpServletRequest request, HttpServletResponse response)
            throws Exception {
        
        Log logger = LogFactory.getLog(TestAction.class);
        System.out.println(logger.getClass());
        
        return null;
    }

}

[実行結果]

[INFO ] 2013-01-27 00:01:50 org.apache.struts.chain.ComposableRequestProcessor::init() - Initializing composable request processor for module prefix ''
[INFO ] 2013-01-27 00:01:50 org.apache.struts.chain.commands.servlet.CreateAction::createAction() - Initialize action of type: main.TestAction
class org.apache.commons.logging.impl.Log4JLogger

お、Log4JLoggerクラスのloggerインスタンスが生成できているようです。
strutsの内部のロギングもlog4jになってる。。log4j.xmlで別のlogger定義した方がよさそうですね。

仕組み

とりあえずソース読んだり、デバッグ実行したりして理解したことです。

• Jdk14Loggerはadapterの役割を果たし、log4jのロガーをcommons-loggingLogインターフェースで扱えるようにする。
• LogFactoryインターフェースを継承したlog4j専用のファクトリーを作成することで、log4jのロガーを取り出せるようにする。これは、Abstract Factory patternですかね。
• と思いきや、log4jのファクトリであるLog4jFactoryは@depricatedになっている。結局ファクトリクラスはLogFactoryImplしかなくて、ここで使用するログを切り替える処理が入っている。
• LogFactoryImpl#newInstanceFactoryでプロパティファイルから使用するロガーのクラス名を取得。このクラス名を元に使いたいロガーのクラスをクラスローダにあげて、リフレクションでコンストラクタとってきて、・・っていう処理を行う。

デザインパターン勉強してたおかげで、やりたいことはスッと入ってきた。クラスローダの仕組みがいまいち分かってないから勉強したい。

Learn log4j（2）

１つのloggerに複数のappenderを持たせて、

• loggerで設定したlevel以上の場合はコンソール表示
• errorの場合は、追加でファイルにログを出力（前提条件: logger自体のレベルがerror以上の場合）

というのをやってみました。

[src/log4j.xml]

<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE log4j:configuration SYSTEM "log4j.dtd">

<log4j:configuration xmlns:log4j="http://jakarta.apache.org/log4j/">
    <appender name="console" class="org.apache.log4j.ConsoleAppender">
        <param name="Target" value="System.out" />
        <layout class="org.apache.log4j.PatternLayout">
            <param name="ConversionPattern" value="[%-5p] %d{yyyy-MM-dd HH:mm:ss} %c::%M() - %m%n" />
        </layout>
    </appender>
    <appender name="file" class="org.apache.log4j.FileAppender">
        <param name="File" value="tmp/error.log" />
        <param name="Append" value="true" />
        <layout class="org.apache.log4j.PatternLayout">
            <param name="ConversionPattern" value="[%-5p] %d{yyyy-MM-dd HH:mm:ss} %c::%M() - %m%n" />
        </layout>
        <filter class="org.apache.log4j.varia.LevelRangeFilter">
            <param name="levelMin" value="error" />
            <param name="levelMax" value="error" />
        </filter>
    </appender>
    <root>
        <level value="info" />
        <appender-ref ref="console" />
        <appender-ref ref="file" />
    </root>
</log4j:configuration>

上のように、appenderのfilter機能を使うとうまくいきます。これを使えば、レベル毎に

• DBに書き込む
• メールを飛ばす
• ファイルに書き込む

などの設定が行えます。

logger単位のレベルの制御しか知らなかったけど、appender毎にも制御できるんですねー。便利ですねー。

Learn log4j（1）

自宅マシンにlog4jを入れてみました。

ダウンロード・設定

まず以下のサイトからダウンロード。
http://logging.apache.org/log4j/1.2/download.html

Eclipseのプロジェクトから、「Build Path」 - 「Configure Build Path」 - 「Add External JARs」でlog4j-x.x.xx.jarを追加。これだけ。簡単です。

動かしてみる

Hello, World的なものを書いてみました。

[src/log4j.xml]

<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE log4j:configuration SYSTEM "log4j.dtd">

<log4j:configuration xmlns:log4j="http://jakarta.apache.org/log4j/">
    <appender name="console" class="org.apache.log4j.ConsoleAppender">
        <param name="Target" value="System.out" />
        <layout class="org.apache.log4j.PatternLayout">
            <param name="ConversionPattern" value="[%-5p] %d{yyyy-MM-dd HH:mm:ss} %c::%M() - %m%n" />
        </layout>
    </appender>
    <root>
        <priority value="info" />
        <appender-ref ref="console" />
    </root>
</log4j:configuration>

[src/com/kenjih/sample/Log4jTest.java]

package com.kenjih.sample;
import org.apache.log4j.Logger;

public class Log4jTest {
    public static void main(String[] args) {
        Logger logger = Logger.getLogger(Log4jTest.class);
        
        System.out.println("Hello, log4j!");

        logger.fatal("fatal message.");
        logger.error("error message.");
        logger.warn("warn message.");
        logger.info("info message.");
        logger.debug("debug message.");
        logger.trace("trace message");
        
    }    
}

[ログ表示結果]

Hello, log4j!
[FATAL] 2013-01-26 19:02:09 com.kenjih.sample.Log4jTest::main() - fatal message.
[ERROR] 2013-01-26 19:02:09 com.kenjih.sample.Log4jTest::main() - error message.
[WARN ] 2013-01-26 19:02:09 com.kenjih.sample.Log4jTest::main() - warn message.
[INFO ] 2013-01-26 19:02:09 com.kenjih.sample.Log4jTest::main() - info message.

Learn Struts（6）

前回のbean:writeタグでintを表示させるという話の続き。

formatを指定してあげればうまく表示できるってことだったけど、デフォルトのフォーマットをリソースファイルで定義した方がよいのではということでやってみました。

1. src/resources/message.propertiesというファイルを作成。その中で以下のようにデフォルトのフォーマットを定義しました。

org.apache.struts.taglib.bean.format.int=###,###

2. struts-config.xmlの設定追加。

<message-resources parameter="resources.message" />

これで、bean:writenにformat指定していなくても、メッセージリソースファイルからデフォルトのformatを取得できます。

あと今回いろいろいじくっていて、メッセージファイルを用意しておけば、
たとえその中で「org.apache.struts.taglib.bean.format.int」を定義しなくてもbean:writeは仕様どおり動くことに気付きました。

前回エラーで苦しんだのは、そもそもメッセージファイル自体が存在しなかったのが原因でした。「仕様とちがうやんかー。toStringした値出せよ」という人は、メッセージファイルを用意すると解決すると思います。

Learn Struts（5）

strutsのhtmlタグ使うと、formに入力した文字を自動で表示してくれるので便利です。

例えば「戻る」ボタンを押したときにユーザーが前回入力していた値を表示するとか、検索ボタンを押して遷移した検索結果画面の検索文字欄にユーザーが入力した値を表示するとか、使いどころはいろいろあります。

内部ではどういう動きをしているのか気になったので、ソースを読んでみました。

org.apache.struts.taglib.html.BaseFieldTagクラスの以下のメソッドでinputタグを作っています。

protected String renderInputElement()
        throws JspException {
        StringBuffer results = new StringBuffer("<input");

        prepareAttribute(results, "type", this.type);
        prepareAttribute(results, "name", prepareName());
        prepareAttribute(results, "accesskey", getAccesskey());
        prepareAttribute(results, "accept", getAccept());
        prepareAttribute(results, "maxlength", getMaxlength());
        prepareAttribute(results, "size", getCols());
        prepareAttribute(results, "tabindex", getTabindex());
        prepareValue(results);
        results.append(this.prepareEventHandlers());
        results.append(this.prepareStyles());
        if (!isXhtml()) {
            prepareAttribute(results, "autocomplete", getAutocomplete());
        }
        prepareOtherAttributes(results);
        results.append(this.getElementClose());

        return results.toString();
    }

value要素を生成しているのは、prepareValueの部分です。

protected void prepareValue(StringBuffer results)
        throws JspException {
        results.append(" value=\"");

        if (value != null) {
            results.append(this.formatValue(value));
        } else if (redisplay || !"password".equals(type)) {
            Object value =
                TagUtils.getInstance().lookup(pageContext, name, property, null);

            results.append(this.formatValue(value));
        }

        results.append('"');
    }

TagUtils#lookup()を使って指定された名前のBeanの指定されたプロパティ値を取り出しています。なるほど。
いやそれにしても、フレームワークのソース読むのはなかなか楽しいですね。競技プログラミングとはまた違った楽しみがあります。

Learn Struts（4）

昨日の続き。とりあえずDispatchActionを継承したアクションを使って簡単なwebアプリを書いてみた。

https://github.com/Kenji-H/calculator/tree/v1.0

微妙にはまったのが、int型プロパティの<bean:write>。なぜかエラーになる。Integer型にすればうまくいくと思ったけどうまくいかない。

「キー org.apache.struts.action.MESSAGE に対するメッセージリソースが見つかりません」という謎のメッセージが出てエラーページに遷移してしまう。

公式リファレンス（http://struts.apache.org/1.3.10/struts-taglib/tagreference.html#bean:write）にはtoString()した値が出力されるって書いてるけど何故かエラー。

とりあえず、taglibのソースを読んでみる。

org.apache.struts.taglib.bean.WriteTag#formatValueの

formatString = retrieveFormatString(INT_FORMAT_KEY);

で落ちてる。リソースファイルからデフォルトメッセージ取ろうとするときに落ちるみたい。formatStringが設定されていればリソースファイルを読みに行かないようになっていたので、以下のように<bean:write>タグ内でformat属性を設定した。
動いた！

<body>
Ans=<bean:write name="numberForm" property="ans" format="######"/>
</body>

プロパティファイルに定義する方法の方がスマートなので、次回やってみよう。

Learn Struts（3）

org.apache.struts.action.ActionだとStrutsから呼ばれるのはexecuteメソッド。関連する処理を一つのクラスにまとめたい場合はDispatchActioinを使うといい。DispatchActionを使うと、リクエストに応じて適切なメソッドを呼べるようになる。

で、DispatchActionを継承したクラスを作ろうとしたんだけど、無い。
DispatchActionクラスが無い。
探してみるとstruts-extras-1.3.10.jarの中にあった。

struts-blank-1.3.10.warに入っていないので、struts-blank-1.3.10.warをインポートして開発を進める場合は、自分でstruts-extras-1.3.10.jarをパスの通った場所に置かないといけない。
Eclipse使ってる場合は、他のjarがあるlib配下にコピペすればよい。

Learn Struts（2）

Strutsの勉強２日目。ActionForm Beanのscopeについて。

<action path="/sample1" type="sample1.Action1" name="form1"
            scope="request">
    <forward name="success" path="/sample1.jsp" />
</action>

struts-config.xmlで上のような定義をすれば、

bean:write=<bean:write name="form1" scope="request"/>

のようにsample1.jspからbeanを参照できる。

気になったのはscopeのところ。これでbeanのライフサイクルを指定できるのは分かるけど、内部ではどのようにデータを管理しているのだろう。

RequestProcessor#processActionFormに書いてた。

if ("request".equals(mapping.getScope())) {
    request.setAttribute(mapping.getAttribute(), instance);
} else {
    HttpSession session = request.getSession();

    session.setAttribute(mapping.getAttribute(), instance);
}

そういうことか。まあ普通に考えるとそうか。。ってことは、JSPから

request scope bean = <%=request.getAttribute("form1") %>
session scope bean = <%=session.getAttribute("form1") %>

とすれば"form1"という名前のActoinForm Beanを参照できるってことか。
出来た、出来た。

Learn Struts（１）

For some reason, I decided to learn a popular Java MVC framework "Struts." Maybe it's because I'm now engaged in a project concerning the framework, or maybe I just think that I should be familiar with at least one famous framework...

Anyway let's get started. This is the first day, so I'll start it with an easy task.

Question

How does the focus property in html:tag work?

Answer

I just created a simple jsp and checked it.

<%@ page contentType="text/html; charset=UTF-8"%>
<%@ taglib uri="http://struts.apache.org/tags-html" prefix="html"%>
<html:html>
<head>
<title>HTML Tags Test</title>
</head>
<body>
<html:form action="/auth" focus="id">
    ID: <html:text property="id" size="16" /><br/>
    PASS: <html:text property="pass" size="16" /><br/>
    <html:submit property="submit" value="submit" />
    <html:reset value="reset" />
</html:form>
</body>
</html:html>

The above JSP yields the following HTML:

<html>
<head>
<title>HTML Tags Test</title>
</head>
<body>
<form name="testForm" method="post" action="/struts/auth.do">
    ID: <input type="text" name="id" size="16" value=""><br/>
    PASS: <input type="text" name="pass" size="16" value=""><br/>
    <input type="submit" name="submit" value="submit">
    <input type="reset" value="reset">
</form>
<script type="text/javascript" language="JavaScript">
  <!--
  var focusControl = document.forms["testForm"].elements["id"];

  if (focusControl != null && focusControl.type != "hidden" && !focusControl.disabled && focusControl.style.display != "none") {
     focusControl.focus();
  }
  // -->
</script>

</body>
</html>

It added some javascript code. So this is how it works.

Server-side Java(5) Strutsをインストール

ついに我が家のローカルマシンにもStrutsが入りました。意外と簡単に入りました。
設定手順をメモっておきます。

1. Struts 1.3.10をApacheのサイトからダウンロード
2. 適当な場所に解凍
3. Eclipseを起動
4. warファイルのインポートで、struts-1.3.10/apps/struts-blank-1.3.10.warをインポート
5. Serversビューから新しいサーバーを定義
6. インポートしたプロジェクトをサーバーに追加

setTimeoutでクロージャ使うときのメモ

毎回悩んでるような気がするので、メモしておく。

やりたいこと

以下のような処理をタイマーを使って実行したい。

for (i = 0; i < 5; i++)
    alert(i);

ダメな例

「0, 1, 2, 3, 4」と1秒間隔でアラートが出ると期待してしまいそうですが、「5, 5, 5, 5, 5」と出ます。「へ〜せいポリスメン!!」じゃありませんよ。

millisec = 0;
for (i = 0; i < 5; i++) {
    millisec += 1000;
    setTimeout(function(){alert(i);}, millisec);
}

クロージャを使ってみる

上のソースがうまくいかなかったのは、関数が実行されるときには既にforループは完了してしまっていてi=5となっているからです。iの値を"クローズド"してあげるとうまくいきます。

function genFunc(x) {
    return function() {
        alert(x);
    }
}
millisec = 0;
for (i = 0; i < 5; i++) {
    millisec += 1000;
    setTimeout(genFunc(i), millisec);
}

無名関数を使ってみる

わざわざクロージャ用の関数を定義するのは面倒くさいような気がするので、無名関数で書いてみます。

millisec = 0;
for (i = 0; i < 5; i++) {
    millisec += 1000;
    setTimeout(function(x) {
        return function() {
            alert(x);
        }
    }(i), millisec);
}

なんか分かりにくいな。。クロージャをグローバルスコープに書きたくないというのであれば、下のような書き方の方が可読性も若干高くていいかもしれない気がします。（が、どっちがいいのかは分かりません。）
一般的には書くんですかねー？javascript詳しい人教えてください。

millisec = 0;
for (i = 0; i < 5; i++) {
    millisec += 1000;
    genFunc = function(x) {
        return function() {
            alert(x);
        }
    };
    setTimeout(genFunc(i), millisec);
}

Server-side Java(4) Listner

Tomcatのリスナー機能を使ってみました。
まず例として、アクセスがある度にカウンターを増やしていくという簡単なservletを作ります。下のソースコードで使われているServletContextはアプリケーション単位でオブジェクトを格納できる入れ物のようなものです。

package com.kenjih;

import java.io.IOException;
import java.io.PrintWriter;

import javax.servlet.ServletException;
import javax.servlet.annotation.WebServlet;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

@WebServlet("/SampleServlet")
public class SampleServlet extends HttpServlet {
    private static final long serialVersionUID = -7110778233634851631L;

    protected void doGet(HttpServletRequest request,
            HttpServletResponse response) throws ServletException, IOException {
        PrintWriter out = response.getWriter();
        
        int allVisit = 0;
        
        try {
            allVisit = (Integer)this.getServletContext().getAttribute("visit");
        } catch (Exception e) {
            allVisit = 0;
        }
        
        this.getServletContext().setAttribute("visit", ++allVisit);
        
        out.println("All Visit:" + allVisit);
                
        out.close();
    }

    protected void doPost(HttpServletRequest request,
            HttpServletResponse response) throws ServletException, IOException {
    }
}

次にリスナークラスを作ってみます。アプリケーションの起動および停止時にログを出力するようなリスナーを書いてみます。

package com.kenjih;

import javax.servlet.ServletContextEvent;
import javax.servlet.ServletContextListener;
import javax.servlet.annotation.WebListener;

@WebListener
public class MyServletContextListener implements ServletContextListener {
    public void contextInitialized(ServletContextEvent sce) {
        System.out.println("servlet context is initialized.");
    }

    public void contextDestroyed(ServletContextEvent sce) {
        System.out.println("servlet context is destroyed.");
    }
}

これだけだと退屈なので、ServletContextの中のオブジェクトが追加、削除、変更されたときにもログを出すようにしてみます。

package com.kenjih;

import javax.servlet.ServletContextAttributeEvent;
import javax.servlet.ServletContextAttributeListener;
import javax.servlet.annotation.WebListener;

@WebListener
public class MyServletContextAttributeListener implements ServletContextAttributeListener {
    public void attributeAdded(ServletContextAttributeEvent scab) {
        System.out.println("A new attribute is added to the context:");
        System.out.println("Name=" + scab.getName());
        System.out.println("Value=" + scab.getValue());
        System.out.println();
    }
    public void attributeReplaced(ServletContextAttributeEvent scab) {
        System.out.println("An attribute is replaced in the context:");
        System.out.println("Name=" + scab.getName());
        System.out.println("Value=" + scab.getValue() + 
                "->" + scab.getServletContext().getAttribute(scab.getName()));
        System.out.println();
    }
    public void attributeRemoved(ServletContextAttributeEvent scab) {
        System.out.println("An attribute is repmoved in the context:");        
        System.out.println("Name=" + scab.getName());
        System.out.println("Value=" + scab.getValue());
        System.out.println();
    }
}

他にもセッションに関するリスナー、HTTPリクエストに関するリスナーなどがあります。
Javaおもしろいな。。

デザインパターン（12） Decorator

ようやく半分まで来ました！Decoratorパターンです。
このパターンはすごいです。今まで見てきたパターンの中で一番すごいと思います。

まとめ

• 基本的な機能を提供するオブジェクトと装飾的な機能を提供するオブジェクトを同一視するためのパターン。
• 動的に機能を追加できる。
• 任意の組み合わせで機能を追加できる。
• Decoratorは透過的インターフェースを使用。

疑問点

結城さんの本では、java.ioパッケージのライブラリでDecoratorパターンが使われていることが紹介されています。他にはどういう場面で使われるのか調べてみました[1]。

よく使われるのはwindowシステムのwindow。単純なwindowにスクロールバーをつけたり、枠線をつけたりといった場合にDecoratorを使うと便利。これをクラス階層でやろうとすると、装飾機能のべき乗個のクラスが必要になる(Window, ScrollingWindow, WindowWithBorder, ScrollingWindowWithBorder, ....)ので、Decorator必須です。

あとは、アクセス制御にも使えるようです。「この条件の場合は、このメソッドは呼び出せない。あの条件の場合は、あのメソッドは呼び出せない。」というような要件が必要な場合、もともとのオブジェクトでアクセス制御をごちゃごちゃと書くのではなく、オブジェクトを制御用のDecoratorで包むようにしてあげると綺麗な設計になります。

ソースコード

「実行時にキーボード入力された値に従って動的に機能を追加する。」という例を実装してみました。

import java.util.Scanner;

interface Cake {
    public void display();
}

class PlainCake implements Cake {
    @Override
    public void display() {
        System.out.println("普通のケーキ");
    }
}

abstract class Decorator implements Cake {
    protected Cake cake;
    
    public Decorator(Cake cake) {
        this.cake = cake;
    }
}

class ChocolateDecorator extends Decorator {
    public ChocolateDecorator(Cake cake) {
        super(cake);
    }

    @Override
    public void display() {
        System.out.println("チョコレートつき");
        cake.display();
    }
}

class StrawberryDecorator extends Decorator {
    public StrawberryDecorator(Cake cake) {
        super(cake);
    }

    @Override
    public void display() {
        System.out.println("苺つき");
        cake.display();    
    }    
}

class CreamDecorator extends Decorator {
    public CreamDecorator(Cake cake) {
        super(cake);
    }

    @Override
    public void display() {
        System.out.println("クリームつき");
        cake.display();            
    }
}

public class Main {
    public static void main(String[] args) {    
        Cake cake = new PlainCake();
        Scanner in = new Scanner(System.in);
        
        System.out.println("チョコレートいる？ (Y/N)");
        if ("Y".equals(in.next()))
            cake = new ChocolateDecorator(cake);
        
        System.out.println("苺いる？ (Y/N)");
        if ("Y".equals(in.next()))
            cake = new StrawberryDecorator(cake);

        System.out.println("クリームいる？ (Y/N)");        
        if ("Y".equals(in.next()))
            cake = new CreamDecorator(cake);
        
        in.close();

        System.out.println("ケーキ完成！");
        cake.display();
    }
}

参考URL

[1] http://en.wikipedia.org/wiki/Decorator_pattern

デザインパターン（11） Composite

結城さんの本でCompositeパターンを勉強しました。

まとめ

• 単体のオブジェクトとその集合を同一視するためのパターン。
• 木構造のような再帰的なデータ構造に適用できる。

疑問点

いわゆる葉になるようなデータと、そうでないデータを統一的に扱えるようにするというのが利点だというのは分かったけど、わざわざ共通のインターフェースを用意する必要があるのか。葉かそうじゃないかの判定は子を管理しているコンテナがnullか否かでできそうだし、それやればクラス一つでいいからクライアントからは統一的に扱えるような・・・。
Wikipediaを見てみよう[1]。。

When dealing with Tree-structured data, programmers often have to discriminate between a leaf-node and a branch.

そうそう。Compositeパターン使わなくても葉かどうかは見分けられる。

This makes code more complex, and therefore, error prone. The solution is an interface that allows treating complex and primitive objects uniformly. In object-oriented programming, a composite is an object designed as a composition of one-or-more similar objects, all exhibiting similar functionality. This is known as a "has-a" relationship between objects.The key concept is that you can manipulate a single instance of the object just as you would manipulate a group of them.

うーむ、確かに。もし葉の場合はごにょごにょごにょ、そうでない場合はごにょごにょごにょみたいなコードを書くよりは、Composite使った方が綺麗にまとまるし、バグも減るってことか。

参考URL

[1] http://en.wikipedia.org/wiki/Composite_pattern

デザインパターン（10） Strategy

--上海の夜--

Strategyパターンを勉強しました。継承ではなく、委譲を用いることでクラス間の結びつきを弱くするのがポイント。

まとめ

• 使用するアルゴリズムの切り替えを簡単にするためのパターン。
• 実行中にアルゴリズムを切り替えることも可能。

疑問点

多態性を使えば、委譲じゃなく継承でもいけるけど、どうなんだろう。使いどころを調べてみると、

For instance, a class that performs validation on incoming data may use a strategy pattern to select a validation algorithm based on the type of data, the source of the data, user choice, and/or other discriminating factors. These factors are not known for each case until run-time, and may require radically different validation to be performed. The validation strategies, encapsulated separately from the validating object, may be used by other validating objects in different areas of the system (or even different systems) without code duplication.[1]

とあった。んー、うまく理解できてなかったところが分かった気がする。Strategyのユーザは、いろいろなStrategyを自由に選ぶようにしたい。プラス、個々のアルゴリズムは他にもいろいろなところで使われることがある。ってことか。

Formally speaking, the strategy pattern defines a family of algorithms, encapsulates each one, and makes them interchangeable. Strategy lets the algorithm vary independently from clients that use it.[1]

ってあるから、クライアントの部品性とアルゴリズムの部品性を高めるために、それぞれえを独立したものにしたいってことか。確かにこれなら委譲じゃないとダメか。

参考URL

[1]http://en.wikipedia.org/wiki/Strategy_pattern

SCCでなぜpostorderを使うか

強連結成分分解（SCC）でDFSを2回するとき、なぜ1回目のDFSでpostorderを使ってその逆順をとるのかが今までしっくりきてなかった。

わざわざ逆順とかしなくても、素直にpreorderでトラバースすればいいんじゃない？と思っていた。

しかし、preorderだと上のようなグラフのときに困る。DFSをDから始めれば、(D, A, B, C)という列になるが、AからDFSを始めてしまうと、(A, B, C, D)となってしまう。こうなってしまうと、2度目の逆辺を用いたDFSでAからDに逆辺があるので、AとDが強連結だとみなされてしまう。

「トポロジカル順序でx < yならば、xの方がyよりpreorderで小さな番号が付けられるはず」と思っていたが、上のように必ずしもそうはならないようだ。

なら、postorderならどうか。postorderの場合は、
「トポロジカル順序でx < yならば、xの方が大きな番号が付けられる。」これはDFSを始める順序によらず正しそう。本当にそうか考えてみる。

今、節点vをDFSで訪れて採番しようとしている。この時点でvには、それまでにつけた番号のどれよりも大きな番号がつく。さらに、vはこれまでに訪れたいずれの節点よりもトポロジカル順序が後ではない。（もし後であればこの時点でvは採番されていないとおかしいため。）
すべての節点について上記が言えるので、トポロジカル順序が先のものほど古い番号が着くと言えそう。

あれ、ていうか今までトポロジカルソートって面倒な方法で並変えしてたけど、グラフがDAGの場合はpostorderでグラフをトラバースすればトポロジカルソート完成？
wikiに「Reverse postordering produces a topological sorting of any directed acyclic graph.」ってあったので、その認識で正しいらしい。

Codeforces Round #153 Table with Letters - 2

Problem Statement

You are given a rectangular of the size (n, m), at each cell of which an English lower-letter is located. Count the number of rectangulars in the original rectangular that satisfy the both of the following conditions:
1. The number of 'a' in the rectangle is less than k.
2. All the letters located at the four corners are the same.

Approach

First I tried a stupid bruteforce solution, which failed as I expected. Then an approach that uses binary search algorithm came to my mind, and I tried it. Failed again... It was very close, but I got a TLE. I thought through a proper approach, but it didn't hit me unfortunately. So I peeked someone's solution, and it seemed like he used a technique what you call "two-poiter" -- guess it's called "しゃくとり法" in Japanese --. Good thing that I found the solution, otherwise I would sleep on it :p

Source Code

using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  

int n, m, k;
string bd[400];
int ac[400][400+1];

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    cin >> n >> m >> k;
    REP (i, n) 
        cin >> bd[i];

    REP (i, n) REP (j, m) ac[i][j+1] = ac[i][j] + (bd[i][j] == 'a');

    long long ret = 0;
    REP (q1, m) FOR (q2, q1+1, m) {
        int atot = 0;
        int cnt[26] = {0};

        for (int p1 = 0, p2 = 0; p2 < n; p2++) {
            atot += ac[p2][q2+1] - ac[p2][q1];
            if (bd[p2][q1] != bd[p2][q2])
                continue;
            int c = bd[p2][q1]-'a'; 
            ++cnt[c];    
            while(atot > k && p1 < p2) {
                atot -= ac[p1][q2+1] - ac[p1][q1];
                if (bd[p1][q1] == bd[p1][q2])
                    --cnt[bd[p1][q1]-'a'];
                ++p1;
            }

            if (atot <= k)
                ret += max(0, cnt[c]-1);
        }
    }

    cout << ret << endl;

    return 0;
}

デザインパターン（9） Bridge

結城さんの本でデザパタの勉強しました。Bridgeパターンは、今まで出てきた中で一番好きなパターンです。（ちょっと大袈裟ですが）感動すらしました。

クラスを継承する場合は、それが機能追加のための継承なのか？それとも新しい実装をするための継承なのか？を意識しなければならない。ということを学びました。

まとめ

• 機能のクラス階層と実装のクラス階層を分ける。
• 委譲により、機能のクラス階層と実装のクラス階層を結びつける。（クラス図を書くと、この委譲の部分がbridgeに見える。）
• 機能を機能のクラス階層に追加した場合は、すべての実装クラスで使用可能となる。
• クライアントは、機能のクラスのAPIを使ってクラスを利用する。

疑問点

特になし。とても分かりやすかった。

読書「罪と罰<下>」

ドストエフスキーの「罪と罰」下巻を読んだ。

ラスコーリニコフが自首を選択するまでの苦悩と、ソーニャの献身的な支えによって再び生きる意味を見出すまでの過程が描かれていた。

優れた才能を持ちながらも苦悩するラスコーリニコフ、経済的な余裕はあるが人生に意味を見出せないスヴィドリガイロフ、貧しくても前向きに強く生きようとするソーニャ。

いろいろな生き方があると思うけど、ソーニャのように一瞬一瞬を大切に生きていきたいと思った。背伸びはせずに、自分ができることをコツコツとやっていこうと思った。