デザインパターン（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を使ってクラスを利用する。

疑問点

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

読書「罪と罰<下>」

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

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

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

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