★☆☆
Mementoパターン
インスタンスの、あるときの状態を保存しておく
Memento とは、英語で「記念品」「形見」を意味する単語です。Memento パターンとは、 インスタンスのあるときの状態をスナップショットとして保存しておくことで、 その時のインスタンスの状態を復元することを可能にするものです。
インスタンスの状態が、プログラム実行中にどんどん変化することが考えられます。一度変化してしまったインスタンスを、「少し前の状態に戻したい」「ある時点の状態に戻したい」などの要求は時に発生するものです。このような要求にスマートに応えることができるのが、Memento パターンです。
例えば、ゴルフで空振りをしたとかOBを出してしまったというようなとき、今までのはなかったことにして、さっきのところからもう一度やり直そうというようなものです。
Memento パターンを使うと、インスタンスのある時の状態を、簡単にスナップショットとして残すことができ、さらに、そこからの復元も可能になります。インスタンス全ての状態を覚えておくために、clone を作成することもありますが、Memento パターンでは、必要な情報のみを保持しておき、必要なデータのみを復元することを考えます。
clone を作成する方法にはいくつか問題があります。このメソッドの返り値の型は Object となってしまうため、厳密な型チェックができません。また、clone() メソッドは基本的に複製を作成するためのものであるため、すべてのフィールドをコピーするように実装するのが普通です。このため、一部の情報だけを複製したオブジェクトを作成したいという用途には向いていません。
一部の情報だけを複製したオブジェクトを作成するためには、保存したい情報をパラメータとして受け取るコンストラクタを用意するのが一般的です。しかし、保存したい情報が増えるとパラメータ数も増えてしまい、使い勝手の悪いコンストラクタとなってしまいます。
また、実際にそのようなコンストラクタを用意したとしても、パラメータとして渡す情報はコピー元のオブジェクトから取得する必要があるため、コピー元となるオブジェクトのクラスは、情報を提供することになります。このことは、ある意味では内部構造を公開しているのと同じことになるため、カプセル化の破壊をしているということになります。
こういったことを考えていくと、カプセル化の破壊を防ぐための工夫をしつつ、保存したい情報を表現する特別なクラスを定義し、このクラスのオブジェクトを使うことにより、状態を保存したり、復元したり、といったことができるようにすれば良さそうだということになります。この方法を具体的に実現するデザインパターンが Mementoです。
情報を見せる、見せないの制御をするために、public、protected、private、あるいは何も書かないこと（パケージプライベート）によるアクセス制御を注意深く設計する必要がある点に注意してください。
例題
次のような木構造があります。これをたどってノード値の合計が100以上になるルートを見つけなさい。
実行結果
t01 (0)
t12 (20)
t23 (30)
t35 (10)
t44 (20)
t54 (20)
t12 (20)
t23 (30)
t35 (10)
t44 (20)
t54 (20)
共通クラス
Node.java
public class Node {
protected Node left = null;
protected Node right = null;
protected String name;
protected int number = 0;
public Node(String name, int number, Node left, Node right) {
this.name = name;
this.number = number;
this.left = left;
this.right = right;
}
public String getName() {
return name;
}
public int getNumber() {
return number;
}
}
|
Mementoパターンを使用しない例 Search.java public class Search {
public boolean exec(Node node, int total, List<Node> list) {
total += node.number;
list.add(node);
if (total >= 100)
return true;
Node left = node.left;
if (left != null) {
boolean result = exec(left, total, list);
if (result == true) {
return result;
}
}
Node right = node.right;
if (right != null) {
boolean result = exec(right, total, list);
if (result == true) {
return result;
}
}
list.remove(node);
return false;
}
}
Main.java public class Main {
public static void main(String[] args) {
List<Node> list = new ArrayList<Node>();
Node t51 = new Node("t51", 10, null, null);
Node t52 = new Node("t52", 20, null, null);
Node t53 = new Node("t53", 10, null, null);
Node t54 = new Node("t54", 20, null, null);
Node t41 = new Node("t41", 10, null, null);
Node t42 = new Node("t42", 20, t51, t52);
Node t43 = new Node("t43", 30, null, null);
Node t44 = new Node("t44", 20, t53, t54);
Node t45 = new Node("t45", 10, null, null);
Node t46 = new Node("t46", 20, null, null);
Node t31 = new Node("t31", 40, t41, null);
Node t32 = new Node("t32", 20, t42, null);
Node t33 = new Node("t33", 30, t43, null);
Node t34 = new Node("t34", 40, null, null);
Node t35 = new Node("t35", 10, t44, null);
Node t36 = new Node("t36", 30, t45, t46);
Node t21 = new Node("t21", 30, t31, null);
Node t22 = new Node("t22", 20, t32, t33);
Node t23 = new Node("t23", 30, t34, t35);
Node t24 = new Node("t24", 20, t36, null);
Node t11 = new Node("t11", 10, t21, t22);
Node t12 = new Node("t12", 20, t23, t24);
Node t01 = new Node("t01", 0, t11, t12);
Search s = new Search();
s.exec(t01, 0, list);
Iterator<Node> it = list.iterator();
while (it.hasNext()) {
Node node = (Node) it.next();
System.out.println(node.getName()
+ " (" + node.getNumber() + ")");
}
}
}
|
Mementoパターンを使用した例 Search.java public class Search {
public List<Node> exec(Node node) {
List<Node> route = new ArrayList<Node>();
int total = 0;
Memento memento = null;
Stack<Memento> mementoStack = new Stack<Memento>();
while (true) {
total += node.number;
route.add(node);
if (total >= 100)
break;
Node left = node.left;
Node right = node.right;
if (left != null && right != null) {
memento = new Memento(node, total, route);
mementoStack.push(memento);
node = left;
}
else if (left == null && right == null) {
if (mementoStack.empty())
return null;
memento = (Memento) mementoStack.pop();
node = memento.getNode().right;
route = memento.getRoute();
total = memento.getTotal();
}
else if (left != null)
node = node.left;
else
node = node.right;
}
return route;
}
}
Memento.java public class Memento {
private Node node; // ノード
private int total; // 合計値
private ArrayList<Node> route; // ルート
protected Memento(Node node, int total, List<Node> route) {
this.node = node;
this.total = total;
this.route = new ArrayList<Node>();
for (int i = 0; i < route.size(); i++)
this.route.add(route.get(i));
}
protected Node getNode() {
return node;
}
protected int getTotal() {
return total;
}
protected List<Node> getRoute() { // ルートを得る
return route;
}
}
Main.java public class Main {
public static void main(String[] args) {
Node t51 = new Node("t51", 10, null, null);
Node t52 = new Node("t52", 20, null, null);
Node t53 = new Node("t53", 10, null, null);
Node t54 = new Node("t54", 20, null, null);
Node t41 = new Node("t41", 10, null, null);
Node t42 = new Node("t42", 20, t51, t52);
Node t43 = new Node("t43", 30, null, null);
Node t44 = new Node("t44", 20, t53, t54);
Node t45 = new Node("t45", 10, null, null);
Node t46 = new Node("t46", 20, null, null);
Node t31 = new Node("t31", 40, t41, null);
Node t32 = new Node("t32", 20, t42, null);
Node t33 = new Node("t33", 30, t43, null);
Node t34 = new Node("t34", 40, null, null);
Node t35 = new Node("t35", 10, t44, null);
Node t36 = new Node("t36", 30, t45, t46);
Node t21 = new Node("t21", 30, t31, null);
Node t22 = new Node("t22", 20, t32, t33);
Node t23 = new Node("t23", 30, t34, t35);
Node t24 = new Node("t24", 20, t36, null);
Node t11 = new Node("t11", 10, t21, t22);
Node t12 = new Node("t12", 20, t23, t24);
Node t01 = new Node("t01", 0, t11, t12);
Search s = new Search();
List<Node> route = s.exec(t01);
if (route != null) {
Iterator<Node> it = route.iterator();
while (it.hasNext()) {
Node node = (Node) it.next();
System.out.println(node.getName() + " (" + node.getNumber() + ")");
}
}
}
}
|
|
この例では再起呼び出しで行っていますが、例えば t41 まで来て 100 にならなかった場合、t31、t21 というように順に戻りながら、他のルートを探すことになります。 しかし、t01 から t41 に来る間に、分岐は t11 のところにしかないと分かったのなら、一気に t11 に戻った方が効率がいいはずです。 |
Momento パターンでは、分岐に来た（left も right も null でない）ときに、その時点の情報の Memonto インスタンスを作り、スタックに保存しています。 Memento memento(node, total, route); mementostack.push(memento); そして、行き止まりになった（left も right も null）ときには、スタックから Memonto インスタンスを取り出しています。これは、直前の分岐地点の情報です。つまり、それまでのルートと合計、そして、これから行く右側ルートです。 memento = (Memento)mementoStack.pop(); node = memento.getNode().right; // 右側ルート route = memento.getRoute(); // それまでのルート total = memento.getTotal(); // それまでの合計 |
共通クラス
node.h
#include <string>
class Node
{
public:
Node* left;
Node* right;
std::string name;
int number;
Node(void);
Node(std::string, int, Node*, Node*);
virtual ~Node(void);
};
node.cpp
#include "node.h"
using namespace std;
Node::Node(void) {}
Node::Node(string name, int number, Node* left, Node* right) : name(name), number(number), left(left), right(right) {}
Node::~Node(void) {}
|
Mementoパターンを使用しない例 search.h #include <list>
#include "node.h"
class Search
{
public:
Search(void);
virtual ~Search(void);
bool exec(Node*, int, std::list<Node*>&);
}; Search.cpp #include "search.h"
using namespace std;
Search::Search(void) {}
Search::~Search(void) {}
bool Search::exec(Node* node, int total, list<Node*>& lst) {
total += node->number;
lst.push_back(node);
if (total >= 100) return true;
Node* left = node->left;
if (left != (Node *)0) {
bool result = exec(left, total, lst);
if (result == true) { return result; }
}
Node* right = node->right;
if (right != (Node *)0) {
bool result = exec(right, total, lst);
if (result == true) { return result; }
}
lst.remove(node);
return false;
}
main.cpp #include "stdafx.h"
#include <iostream>
using namespace std;
#include "node.h"
#include "search.h"
int main() {
list<Node*> lst;
Node t51("t51", 10, 0, 0);
Node t52("t52", 20, 0, 0);
Node t53("t53", 10, 0, 0);
Node t54("t54", 20, 0, 0);
Node t41("t41", 10, 0, 0);
Node t42("t42", 20, &t51, &t52);
Node t43("t43", 30, 0, 0);
Node t44("t44", 20, &t53, &t54);
Node t45("t45", 10, 0, 0);
Node t46("t46", 20, 0, 0);
Node t31("t31", 40, &t41, 0);
Node t32("t32", 20, &t42, 0);
Node t33("t33", 30, &t43, 0);
Node t34("t34", 40, 0, 0);
Node t35("t35", 10, &t44, 0);
Node t36("t36", 30, &t45, &t46);
Node t21("t21", 30, &t31, 0);
Node t22("t22", 20, &t32, &t33);
Node t23("t23", 30, &t34, &t35);
Node t24("t24", 20, &t36, 0);
Node t11("t11", 10, &t21, &t22);
Node t12("t12", 20, &t23, &t24);
Node t01("t01", 0, &t11, &t12);
Search s;
s.exec(&t01, 0, lst);
list<Node*>::iterator it = lst.begin();
while (it != lst.end()) {
Node* node = *it++;
cout << node->name << " (" << node->number << ")" << endl;
}
return 0;
}
|
Mementoパターンを使用した例 search.h #include <list>
#include "node.h"
class Search
{
public:
Search(void);
virtual ~Search(void);
std::list<Node*> exec(Node*);
}; search.cpp #include <stack>
#include "search.h"
#include "memento.h"
using namespace std;
Search::Search(void) {}
Search::~Search(void) {}
list<Node*> Search::exec(Node* node) {
list<Node*> route;
int total = 0;
total += node->number;
stack<memento> mementostack;
while(true) {
total += node->number;
route.push_back(node);
if (total >= 100) break;
Node* left = node->left;
Node* right = node->right;
if (left != (Node *)0 && right != (Node *)0) {
memento memento(node, total, route);
mementostack.push(memento);
node = left;
}
else if (left == (Node *)0 && right == (Node *)0) {
if (mementostack.empty()) return (list<Node*>)0;
memento memento = mementostack.pop();
node = memento.getNode()->right;
route = memento.getRoute();
total = memento.getTotal();
}
else if (left != (Node *)0)
node = node->left;
else
node = node->right;
}
return route;
}
memento.h #include <list>
#include "node.h"
class memento
{
private:
Node* node; // ノード
int total; // 合計値
std::list<Node*> route; // ルート
public:
memento(void);
memento(Node*, int, std::list<Node*>);
virtual ~memento(void);
Node* getNode(void);
int getTotal(void);
std::list<Node*>& getRoute(void);
}; memento.cpp #include "memento.h"
using namespace std;
memento::memento(void) {}
memento::memento(Node* node, int total, list<Node*> route)
: node(node), total(total), route(route) {}
memento::~memento(void) {}
Node* memento::getNode(void) { return node; }
int memento::getTotal(void) { return total; }
list<Node*>& memento::getRoute(void) { // ルートを得る
return route;
} main.cpp #include "stdafx.h"
#include <iostream>
using namespace std;
#include "node.h"
#include "search.h"
int main() {
Node t51("t51", 10, 0, 0);
Node t52("t52", 20, 0, 0);
Node t53("t53", 10, 0, 0);
Node t54("t54", 20, 0, 0);
Node t41("t41", 10, 0, 0);
Node t42("t42", 20, &t51, &t52);
Node t43("t43", 30, 0, 0);
Node t44("t44", 20, &t53, &t54);
Node t45("t45", 10, 0, 0);
Node t46("t46", 20, 0, 0);
Node t31("t31", 40, &t41, 0);
Node t32("t32", 20, &t42, 0);
Node t33("t33", 30, &t43, 0);
Node t34("t34", 40, 0, 0);
Node t35("t35", 10, &t44, 0);
Node t36("t36", 30, &t45, &t46);
Node t21("t21", 30, &t31, 0);
Node t22("t22", 20, &t32, &t33);
Node t23("t23", 30, &t34, &t35);
Node t24("t24", 20, &t36, 0);
Node t11("t11", 10, &t21, &t22);
Node t12("t12", 20, &t23, &t24);
Node t01("t01", 0, &t11, &t12);
Search s;
list<Node*>& route = s.exec(&t01);
list<Node*>::iterator it = route.begin();
while (it != route.end()) {
Node* node = *it++;
cout << node->name << " (" << node->number << ")" << endl;
}
return 0;
}
|
|
この例では再起呼び出しで行っていますが、例えば t41 まで来て 100 にならなかった場合、t31、t21 というように順に戻りながら、他のルートを探すことになります。 しかし、t01 から t41 に来る間に、分岐は t11 のところにしかないと分かったのなら、一気に t11 に戻った方が効率がいいはずです。 |
Momento パターンでは、分岐に来た（left も right も 0 でない）ときに、その時点の情報の Memonto インスタンスを作り、スタックに保存しています。 memento memento(node, total, route); mementostack.push(memento); そして、行き止まりになった（left も right も 0）ときには、スタックから Memonto インスタンスを取り出しています。これは、直前の分岐地点の情報です。つまり、それまでのルートと合計、そして、これから行く右側ルートです。 memento memento = mementostack.pop(); node = memento.getNode()->right; // 右側ルート route = memento.getRoute(); // それまでのルート total = memento.getTotal(); // それまでの合計 |
共通クラス
Node.cs
class Node
{
public Node left = null;
public Node right = null;
public string name;
public int number = 0;
public Node(string name, int number, Node left, Node right)
{
this.name = name;
this.number = number;
this.left = left;
this.right = right;
}
}
|
Mementoパターンを使用しない例 Search.cs class Search
{
public bool Exec(Node node, int total, ArrayList list)
{
total += node.number;
list.Add(node);
if (total >= 100) return true;
Node left = node.left;
if (left != null)
{
if (Exec(left, total, list)) return true;
}
Node right = node.right;
if (right != null)
{
if (Exec(right, total, list)) return true;
}
list.Remove(node);
return false;
}
}
Program.cs class Program
{
static void Main(string[] args)
{
ArrayList list = new ArrayList();
Node t51("t51", 10, null, null);
Node t52("t52", 20, null, null);
Node t53("t53", 10, null, null);
Node t54("t54", 20, null, null);
Node t41("t41", 10, null, null);
Node t42("t42", 20, t51, t52);
Node t43("t43", 30, null, null);
Node t44("t44", 20, t53, t54);
Node t45("t45", 10, null, null);
Node t46("t46", 20, null, null);
Node t31("t31", 40, t41, null);
Node t32("t32", 20, t42, null);
Node t33("t33", 30, t43, null);
Node t34("t34", 40, null, null);
Node t35("t35", 10, t44, null);
Node t36("t36", 30, t45, t46);
Node t21("t21", 30, t31, null);
Node t22("t22", 20, t32, t33);
Node t23("t23", 30, t34, t35);
Node t24("t24", 20, t36, null);
Node t11("t11", 10, t21, t22);
Node t12("t12", 20, t23, t24);
Node t01("t01", 0, t11, t12);
Search s = new Search();
s.Exec(t01, 0, list);
foreach(Node node in list)
{
Console.WriteLine(node.name + "(" + node.number + ")");
}
}
}
|
Mementoパターンを使用した例 Search.cs class Search
{
public ArrayList Exec(Node node)
{
ArrayList route = new ArrayList();
int total = 0;
Memento memento;
Stack<Memento> mementoStack = new Stack<Memento>();
while(true)
{
total += node.number;
route.Add(node);
if (total >= 100) break;
Node left = node.left;
Node right = node.right;
if (left != null && right != null) // 分岐あり
{
memento = new Memento(node, total, route);
mementoStack.Push(memento);
node = left;
}
else if (left == null && right == null) // 行き止まり
{
if (mementoStack.Count == 0) return null;
memento = mementoStack.Pop();
node = memento.GetNode().right;
route = memento.GetRoute();
total = memento.GetTotal();
}
else if (left != null)
{
node = node.left; // 左側のみ
}
else if (right != null)
{
node = node.right; // 右側のみ
}
}
return route;
}
} Memento.cs class Memento
{
private Node node; // ノード
private int total; // 合計値
private ArrayList route; // ルート
public Memento(Node node, int total, ArrayList route)
{
this.node = node;
this.total = total;
this.route = new ArrayList();
foreach (Node nd in route)
{
this.route.Add(nd);
}
}
public Node GetNode()
{
return node;
}
public int GetTotal()
{
return total;
}
public ArrayList GetRoute()
{
return route;
}
} Program.cs class Program
{
static void Main(string[] args)
{
Node t51("t51", 10, null, null);
Node t52("t52", 20, null, null);
Node t53("t53", 10, null, null);
Node t54("t54", 20, null, null);
Node t41("t41", 10, null, null);
Node t42("t42", 20, t51, t52);
Node t43("t43", 30, null, null);
Node t44("t44", 20, t53, t54);
Node t45("t45", 10, null, null);
Node t46("t46", 20, null, null);
Node t31("t31", 40, t41, null);
Node t32("t32", 20, t42, null);
Node t33("t33", 30, t43, null);
Node t34("t34", 40, null, null);
Node t35("t35", 10, t44, null);
Node t36("t36", 30, t45, t46);
Node t21("t21", 30, t31, null);
Node t22("t22", 20, t32, t33);
Node t23("t23", 30, t34, t35);
Node t24("t24", 20, t36, null);
Node t11("t11", 10, t21, t22);
Node t12("t12", 20, t23, t24);
Node t01("t01", 0, t11, t12);
Search s = new Search();
ArrayList route = s.Exec(t01);
if (route != null)
{
foreach(Node node in route)
{
Console.WriteLine(node.name + "(" + node.number + ")");
}
}
}
}
|
|
この例では再起呼び出しで行っていますが、例えば t41 まで来て 100 にならなかった場合、t31、t21 というように順に戻りながら、他のルートを探すことになります。 しかし、t01 から t41 に来る間に、分岐は t11 のところにしかないと分かったのなら、一気に t11 に戻った方が効率がいいはずです。 |
Momento パターンでは、分岐に来た（left も right も null でない）ときに、その時点の情報の Memonto インスタンスを作り、スタックに保存しています。 memento = new Memento(node, total, route); mementostack.Push(memento); そして、行き止まりになった（left も right も null）ときには、スタックから Memonto インスタンスを取り出しています。これは、直前の分岐地点の情報です。つまり、それまでのルートと合計、そして、これから行く右側ルートです。 memento = mementostack.Pop(); node = memento.GetNode().right; // 右側ルート route = memento.GetRoute(); // それまでのルート total = memento.GetTotal(); // それまでの合計 |
既存クラス
Node.vb
Public Class Node
Friend left As Node = Nothing
Friend right As Node = Nothing
Friend name As String
Friend number As Integer = 0
Public Sub New(ByVal name As String, ByVal number As Integer, ByVal left As Node, ByVal right As Node)
Me.name = name
Me.number = number
Me.left = left
Me.right = right
End Sub
End Class
|
Mementoパターンを使用しない例 Search.vb Public Class Search
Public Function Exec(ByVal node AsNode,
ByVal total As Integer, ByVal list As ArrayList) As Boolean
total += node.number
list.Add(node)
If total >= 100 Then Return True
Dim left As Node = node.left
If left IsNot Nothing Then
If Exec(left, total, list) Then Return True
End If
Dim right As Node = node.right
If right IsNot Nothing Then
If Exec(right, total, list) Then Return True
End If
list.Remove(node)
Return False
End Function
End Class
Program.vb Module Main
Sub Main()
Dim list As ArrayList = New ArrayList()
Dim t51 As Node = New Node("t51", 10, Nothing, Nothing)
Dim t52 As Node = New Node("t52", 20, Nothing, Nothing)
Dim t53 As Node = New Node("t53", 10, Nothing, Nothing)
Dim t54 As Node = New Node("t54", 20, Nothing, Nothing)
Dim t41 As Node = New Node("t41", 10, Nothing, Nothing)
Dim t42 As Node = New Node("t42", 20, t51, t52)
Dim t43 As Node = New Node("t43", 30, Nothing, Nothing)
Dim t44 As Node = New Node("t44", 20, t53, t54)
Dim t45 As Node = New Node("t45", 10, Nothing, Nothing)
Dim t46 As Node = New Node("t46", 20, Nothing, Nothing)
Dim t31 As Node = New Node("t31", 40, t41, Nothing)
Dim t32 As Node = New Node("t32", 20, t42, Nothing)
Dim t33 As Node = New Node("t33", 30, t43, Nothing)
Dim t34 As Node = New Node("t34", 40, Nothing, Nothing)
Dim t35 As Node = New Node("t35", 10, t44, Nothing)
Dim t36 As Node = New Node("t36", 30, t45, t46)
Dim t21 As Node = New Node("t21", 30, t31, Nothing)
Dim t22 As Node = New Node("t22", 20, t32, t33)
Dim t23 As Node = New Node("t23", 30, t34, t35)
Dim t24 As Node = New Node("t24", 20, t36, Nothing)
Dim t11 As Node = New Node("t11", 10, t21, t22)
Dim t12 As Node = New Node("t12", 20, t23, t24)
Dim t01 As Node = New Node("t01", 0, t11, t12)
Dim s As Search = New Search()
s.Exec(t01, 0, list)
For Each node As Node In list
Console.WriteLine(node.name & " (" & node.number & ")")
Next
End Sub
End Module
|
Mementoパターンを使用した例 Search.vb Public Class Search
Public Function Exec(ByVal node As Node) As ArrayList
Dim route As ArrayList = New ArrayList()
Dim total As Integer = 0
Dim memento As Memento
Dim mementoStack As Stack(Of Memento) = New Stack(Of Memento)()
While True
total += node.number
route.Add(node)
If total >= 100 Then Exit While
Dim left As Node = node.left
Dim right As Node = node.right
If left IsNot Nothing And right IsNot Nothing Then ' 分岐
memento = New Memento(node, total, route)
mementoStack.Push(memento)
node = left
ElseIf left Is Nothing And right Is Nothing Then '行き止まり
If mementoStack.Count = 0 Then Return Nothing
memento = mementoStack.Pop()
node = memento.GetNode().right
route = memento.GetRoute()
total = memento.GetTotal()
ElseIf left IsNot Nothing Then
node = node.right ' 左側のみ
Else
node = node.right ' 右側のみ
End If
End While
Return route
End Function
End Class
Memento.vb Public Class Memento
Private node As Node ' ノード
Private total As Integer ' 合計値
Private route As ArrayList ' ルート
Public Sub New(ByVal node As Node, ByVal total As Integer, route As ArrayList)
Me.node = node
Me.total = total
Me.route = New ArrayList()
For Each node In route
Me.route.Add(node)
Next
End Sub
Public Function GetNode() As Node
Return node
End Function
Public Function GetTotal() As Integer
Return total
End Function
Public Function GetRoute() As ArrayList
Return route
End Function
End Class
Program.vb Module Main
Sub Main()
Dim t51 As Node = New Node("t51", 10, Nothing, Nothing)
Dim t52 As Node = New Node("t52", 20, Nothing, Nothing)
Dim t53 As Node = New Node("t53", 10, Nothing, Nothing)
Dim t54 As Node = New Node("t54", 20, Nothing, Nothing)
Dim t41 As Node = New Node("t41", 10, Nothing, Nothing)
Dim t42 As Node = New Node("t42", 20, t51, t52)
Dim t43 As Node = New Node("t43", 30, Nothing, Nothing)
Dim t44 As Node = New Node("t44", 20, t53, t54)
Dim t45 As Node = New Node("t45", 10, Nothing, Nothing)
Dim t46 As Node = New Node("t46", 20, Nothing, Nothing)
Dim t31 As Node = New Node("t31", 40, t41, Nothing)
Dim t32 As Node = New Node("t32", 20, t42, Nothing)
Dim t33 As Node = New Node("t33", 30, t43, Nothing)
Dim t34 As Node = New Node("t34", 40, Nothing, Nothing)
Dim t35 As Node = New Node("t35", 10, t44, Nothing)
Dim t36 As Node = New Node("t36", 30, t45, t46)
Dim t21 As Node = New Node("t21", 30, t31, Nothing)
Dim t22 As Node = New Node("t22", 20, t32, t33)
Dim t23 As Node = New Node("t23", 30, t34, t35)
Dim t24 As Node = New Node("t24", 20, t36, Nothing)
Dim t11 As Node = New Node("t11", 10, t21, t22)
Dim t12 As Node = New Node("t12", 20, t23, t24)
Dim t01 As Node = New Node("t01", 0, t11, t12)
Dim s As Search = New Search()
Dim route As ArrayList = s.Exec(t01)
If route IsNot Nothing Then
For Each node As Node In route
Console.WriteLine(node.name & " (" & node.number & ")")
Next
End If
End Sub
End Module
|
|
この例では再起呼び出しで行っていますが、例えば t41 まで来て 100 にならなかった場合、t31、t21 というように順に戻りながら、他のルートを探すことになります。 しかし、t01 から t41 に来る間に、分岐は t11 のところにしかないと分かったのなら、一気に t11 に戻った方が効率がいいはずです。 |
Momento パターンでは、分岐に来た（left も right も Nothing でない）ときに、その時点の情報の Memonto インスタンスを作り、スタックに保存しています。 memento = New Memento(node, total, route) mementostack.Push(memento) そして、行き止まりになった（left も right も Nothing）ときには、スタックから Memonto インスタンスを取り出しています。これは、直前の分岐地点の情報です。つまり、それまでのルートと合計、そして、これから行く右側ルートです。 memento = mementostack.Pop() node = memento.GetNode().right ' 右側ルート route = memento.GetRoute() ' それまでのルート total = memento.GetTotal() ' それまでの合計 |
共通クラス
Nodex.js
module.exports = class Node {
constructor(name, number, left, right) {
this.name = name;
this.number = number;
this.left = left;
this.right = right;
}
getName() {
return this.name;
}
getNumber() {
return this.number;
}
}
|
Mementoパターンを使用しない例 Search.js module.exports = class Search {
exec(node, total, list) {
total += node.number;
list.push(node);
if (total >= 100)
return true;
let left = node.left;
if (left != null) {
let result = this.exec(left, total, list);
if (result == true) {
return result;
}
}
let right = node.right;
if (right != null) {
let result = this.exec(right, total, list);
if (result == true) {
return result;
}
}
list.pop();
return false;
}
}
Main.js const Node = require("./Nodex.js");
const Search = require("./Search.js");
let list = new Array();
let t51 = new Node("t51", 10, null, null);
let t52 = new Node("t52", 20, null, null);
let t53 = new Node("t53", 10, null, null);
let t54 = new Node("t54", 20, null, null);
let t41 = new Node("t41", 10, null, null);
let t42 = new Node("t42", 20, t51, t52);
let t43 = new Node("t43", 30, null, null);
let t44 = new Node("t44", 20, t53, t54);
let t45 = new Node("t45", 10, null, null);
let t46 = new Node("t46", 20, null, null);
let t31 = new Node("t31", 40, t41, null);
let t32 = new Node("t32", 20, t42, null);
let t33 = new Node("t33", 30, t43, null);
let t34 = new Node("t34", 40, null, null);
let t35 = new Node("t35", 10, t44, null);
let t36 = new Node("t36", 30, t45, t46);
let t21 = new Node("t21", 30, t31, null);
let t22 = new Node("t22", 20, t32, t33);
let t23 = new Node("t23", 30, t34, t35);
let t24 = new Node("t24", 20, t36, null);
let t11 = new Node("t11", 10, t21, t22);
let t12 = new Node("t12", 20, t23, t24);
let t01 = new Node("t01", 0, t11, t12);
let s = new Search();
s.exec(t01, 0, list);
list.forEach(print);
function print(node, index, list) {
process.stdout.write(node.getName() + " (" + node.getNumber() + ")\n");
}
|
Mementoパターンを使用した例 Search.js const Memento = require("./Memento.js");
module.exports = class Search {
exec(node) {
let route = new Array();
let total = 0;
let memento = null;
this.mementoStack = new Array();
while (true) {
total += node.number;
route.push(node);
if (total >= 100)
break;
let left = node.left;
let right = node.right;
if (left != null && right != null) {
memento = new Memento(node, total, route);
this.mementoStack.push(memento);
node = left;
}
else if (left == null && right == null) {
if (this.mementoStack.length == 0)
return null;
memento = this.mementoStack.pop();
node = memento.getNode().right;
route = memento.getRoute();
total = memento.getTotal();
}
else if (left != null)
node = node.left;
else
node = node.right;
}
return route;
}
}
Memento.js module.exports = class Memento {
constructor(node, total, route) {
this.node = node;
this.total = total;
this.route = route.slice(0); // clone
}
getNode() {
return this.node;
}
getTotal() {
return this.total;
}
getRoute() { // ルートを得る
return this.route;
}
}
Main.js const Node = require("./Nodex.js");
const Search = require("./Search.js");
let t51 = new Node("t51", 10, null, null);
let t52 = new Node("t52", 20, null, null);
let t53 = new Node("t53", 10, null, null);
let t54 = new Node("t54", 20, null, null);
let t41 = new Node("t41", 10, null, null);
let t42 = new Node("t42", 20, t51, t52);
let t43 = new Node("t43", 30, null, null);
let t44 = new Node("t44", 20, t53, t54);
let t45 = new Node("t45", 10, null, null);
let t46 = new Node("t46", 20, null, null);
let t31 = new Node("t31", 40, t41, null);
let t32 = new Node("t32", 20, t42, null);
let t33 = new Node("t33", 30, t43, null);
let t34 = new Node("t34", 40, null, null);
let t35 = new Node("t35", 10, t44, null);
let t36 = new Node("t36", 30, t45, t46);
let t21 = new Node("t21", 30, t31, null);
let t22 = new Node("t22", 20, t32, t33);
let t23 = new Node("t23", 30, t34, t35);
let t24 = new Node("t24", 20, t36, null);
let t11 = new Node("t11", 10, t21, t22);
let t12 = new Node("t12", 20, t23, t24);
let t01 = new Node("t01", 0, t11, t12);
let s = new Search();
let route = s.exec(t01);
route.forEach(print);
function print(node, index, list) {
process.stdout.write(node.getName() + " (" + node.getNumber() + ")\n");
}
|
|
この例では再起呼び出しで行っていますが、例えば t41 まで来て 100 にならなかった場合、t31、t21 というように順に戻りながら、他のルートを探すことになります。 しかし、t01 から t41 に来る間に、分岐は t11 のところにしかないと分かったのなら、一気に t11 に戻った方が効率がいいはずです。 |
Momento パターンでは、分岐に来た（left も right も null でない）ときに、その時点の情報の Memonto インスタンスを作り、スタックに保存しています。 memento = new Memento(node, total, route); this.mementostack.push(memento); そして、行き止まりになった（left も right も null）ときには、スタックから Memonto インスタンスを取り出しています。これは、直前の分岐地点の情報です。つまり、それまでのルートと合計、そして、これから行く右側ルートです。 memento = this.mementostack.pop(); node = memento.getNode().right; // 右側ルート route = memento.getRoute(); // それまでのルート total = memento.getTotal(); // それまでの合計 |
共通クラス
Node.pm
package Node {
sub new {
my ($class, $name, $number, $left, $right) = @_;
my $this = { name => $name,
number => $number,
left => $left,
right => $right
};
return bless $this, $class;
}
sub getName {
my ($this) = @_;
return $this->{name};
}
sub getNumber {
my ($this) = @_;
return $this->{number};
}
}
1;
|
Mementoパターンを使用しない例 Search.pm package Search {
sub new {
my ($class) = @_;
return bless {}, $class;
}
sub exec {
my ($this, $node, $total, $list) = @_;
$total += $node->{number};
push @{$list}, $node;
if ($total >= 100) {
return "true";
}
my $left = $node->{left};
if ($left ne undef) {
my $result = $this->exec($left, $total, $list);
if ($result eq "true") {
return $result;
}
}
my $right = $node->{right};
if ($right ne undef) {
my $result = $this->exec($right, $total, $list);
if ($result eq "true") {
return $result;
}
}
pop @{$list};
return "false";
}
}
1;
Main.pl use lib qw(./);
use Node;
use Search;
my @list = ();
my $t51 = new Node("t51", 10, null, null);
my $t52 = new Node("t52", 20, null, null);
my $t53 = new Node("t53", 10, null, null);
my $t54 = new Node("t54", 20, null, null);
my $t41 = new Node("t41", 10, null, null);
my $t42 = new Node("t42", 20, $t51, t52);
my $t43 = new Node("t43", 30, null, null);
my $t44 = new Node("t44", 20, $t53, t54);
my $t45 = new Node("t45", 10, null, null);
my $t46 = new Node("t46", 20, null, null);
my $t31 = new Node("t31", 40, $t41, null);
my $t32 = new Node("t32", 20, $t42, null);
my $t33 = new Node("t33", 30, $t43, null);
my $t34 = new Node("t34", 40, null, null);
my $t35 = new Node("t35", 10, $t44, null);
my $t36 = new Node("t36", 30, $t45, t46);
my $t21 = new Node("t21", 30, $t31, null);
my $t22 = new Node("t22", 20, $t32, t33);
my $t23 = new Node("t23", 30, $t34, t35);
my $t24 = new Node("t24", 20, $t36, null);
my $t11 = new Node("t11", 10, $t21, $t22);
my $t12 = new Node("t12", 20, $t23, $t24);
my $t01 = new Node("t01", 0, $t11, $t12);
my $s = new Search();
$s->exec($t01, 0, \@list);
foreach my $node (@list) {
print $node->getName() . " (" . $node->getNumber() . ")\n";
}
|
Mementoパターンを使用した例 Search.pm package Search {
use Memento;
use Clone qw(clone);
sub new {
my ($class) = @_;
return bless {}, $class;
}
sub exec {
my ($this, $node) = @_;
my @route = ();
my $total = 0;
my $memento = undef;
my @mementoStack = ();
while(1) {
$total += $node->{number};
push @route, $node;
last if ($total >= 100);
my $left = $node->{left};
my $right = $node->{right};
if ($left ne undef && $right ne undef) {
my $r = clone(\@route);
my @rt = @$r;
$memento = new Memento($node, $total, \@rt);
push @mementoStack, $memento;
$node = $left;
}
elsif ($left eq undef && $right eq undef) {
if (@mementoStack == 0) {
return undef;
}
$memento = pop @mementoStack;
$node = $memento->getNode()->{right};
@route = @{$memento->getRoute()};
$total = $memento->getTotal();
}
elsif ($left ne undef) {
$node = $node->{left};
}
else {
$node = $node->{right};
}
}
return \@route;
}
}
1;
Memento.pm package Memento {
sub new {
my ($class, $node, $total, $route) = @_;
my $this = { node => $node,
total => $total,
route => $route
};
bless $this, $class;
return $this;
}
sub getNode {
my ($this) = @_;
return $this->{node};
}
sub getTotal {
my ($this) = @_;
return $this->{total};
}
sub getRoute { # ルートを得る
my ($this) = @_;
return $this->{route};
}
}
1;
Main.pl use lib qw(./);
use Node;
use Search;
my $t51 = new Node("t51", 10, null, null);
my $t52 = new Node("t52", 20, null, null);
my $t53 = new Node("t53", 10, null, null);
my $t54 = new Node("t54", 20, null, null);
my $t41 = new Node("t41", 10, null, null);
my $t42 = new Node("t42", 20, $t51, t52);
my $t43 = new Node("t43", 30, null, null);
my $t44 = new Node("t44", 20, $t53, t54);
my $t45 = new Node("t45", 10, null, null);
my $t46 = new Node("t46", 20, null, null);
my $t31 = new Node("t31", 40, $t41, null);
my $t32 = new Node("t32", 20, $t42, null);
my $t33 = new Node("t33", 30, $t43, null);
my $t34 = new Node("t34", 40, null, null);
my $t35 = new Node("t35", 10, $t44, null);
my $t36 = new Node("t36", 30, $t45, t46);
my $t21 = new Node("t21", 30, $t31, null);
my $t22 = new Node("t22", 20, $t32, t33);
my $t23 = new Node("t23", 30, $t34, t35);
my $t24 = new Node("t24", 20, $t36, null);
my $t11 = new Node("t11", 10, $t21, $t22);
my $t12 = new Node("t12", 20, $t23, $t24);
my $t01 = new Node("t01", 0, $t11, $t12);
my $s = new Search();
my $route = $s->exec($t01);
foreach my $node (@$route) {
print $node->getName() . " (" . $node->getNumber() . ")\n";
}
|
|
この例では再起呼び出しで行っていますが、例えば t41 まで来て 100 にならなかった場合、t31、t21 というように順に戻りながら、他のルートを探すことになります。 しかし、t01 から t41 に来る間に、分岐は t11 のところにしかないと分かったのなら、一気に t11 に戻った方が効率がいいはずです。 |
Momento パターンでは、分岐に来た（left も right も undef でない）ときに、その時点の情報の Memonto インスタンスを作り、スタックに保存しています。 $memento = new Memento($node, $total, \@rt); push @mementoStack, $memento; そして、行き止まりになった（left も right も undef）ときには、スタックから Memonto インスタンスを取り出しています。これは、直前の分岐地点の情報です。つまり、それまでのルートと合計、そして、これから行く右側ルートです。 $memento = pop @mementoStack; $node = $memento->getNode()->{right}; // 右側ルート @route = @{$memento->getRoute()}; // それまでのルート $total = $memento->getTotal(); // それまでの合計 |
共通クラス
Node.rb
class Node
attr_reader :number
attr_reader :left
attr_reader :right
def initialize(name, number, left, right)
@name = name
@number = number
@left = left
@right = right
end
def getName()
return @name
end
def getNumber()
return @number
end
end
|
Mementoパターンを使用しない例 Search.rb class Search
def exec(node, total, list)
total += node.number
list.push(node)
if total >= 100 then
return true
end
left = node.left
if left != nil then
result = exec(left, total, list)
if result == true then
return result
end
end
right = node.right
if right != nil then
result = exec(right, total, list)
if result == true then
return result
end
end
list.pop()
return false
end
end
Main.rb require './Node'
require './Search'
list = Array.new()
t51 = Node.new("t51", 10, nil, nil)
t52 = Node.new("t52", 20, nil, nil)
t53 = Node.new("t53", 10, nil, nil)
t54 = Node.new("t54", 20, nil, nil)
t41 = Node.new("t41", 10, nil, nil)
t42 = Node.new("t42", 20, t51, t52)
t43 = Node.new("t43", 30, nil, nil)
t44 = Node.new("t44", 20, t53, t54)
t45 = Node.new("t45", 10, nil, nil)
t46 = Node.new("t46", 20, nil, nil)
t31 = Node.new("t31", 40, t41, nil)
t32 = Node.new("t32", 20, t42, nil)
t33 = Node.new("t33", 30, t43, nil)
t34 = Node.new("t34", 40, nil, nil)
t35 = Node.new("t35", 10, t44, nil)
t36 = Node.new("t36", 30, t45, t46)
t21 = Node.new("t21", 30, t31, nil)
t22 = Node.new("t22", 20, t32, t33)
t23 = Node.new("t23", 30, t34, t35)
t24 = Node.new("t24", 20, t36, nil)
t11 = Node.new("t11", 10, t21, t22)
t12 = Node.new("t12", 20, t23, t24)
t01 = Node.new("t01", 0, t11, t12)
s = Search.new()
s.exec(t01, 0, list)
list.each do |node|
puts node.getName() + " (" + node.getNumber().to_s + ")"
end
|
Mementoパターンを使用した例 Search.rb require './Memento'
class Search
def exec(node)
route = Array.new()
total = 0
memento = nil
mementoStack = []
while true do
total += node.number
route.push(node)
break if total >= 100
left = node.left
right = node.right
if left != nil && right != nil then
memento = Memento.new(node, total, route)
mementoStack.push(memento)
node = left
elsif left == nil && right == nil then
return nil if mementoStack.empty?
memento = mementoStack.pop()
node = memento.getNode().right
route = memento.getRoute()
total = memento.getTotal()
elsif left != nil then
node = node.left
else
node = node.right
end
end
return route
end
end
Memento.rb class Memento
def initialize(node, total, route)
@node = node;
@total = total;
@route = Marshal.load(Marshal.dump(route)) # clone
end
def getNode()
return @node
end
def getTotal()
return @total
end
def getRoute() # ルートを得る
return @route
end
end
Main.rb require './Node'
require './Search'
t51 = Node.new("t51", 10, nil, nil)
t52 = Node.new("t52", 20, nil, nil)
t53 = Node.new("t53", 10, nil, nil)
t54 = Node.new("t54", 20, nil, nil)
t41 = Node.new("t41", 10, nil, nil)
t42 = Node.new("t42", 20, t51, t52)
t43 = Node.new("t43", 30, nil, nil)
t44 = Node.new("t44", 20, t53, t54)
t45 = Node.new("t45", 10, nil, nil)
t46 = Node.new("t46", 20, nil, nil)
t31 = Node.new("t31", 40, t41, nil)
t32 = Node.new("t32", 20, t42, nil)
t33 = Node.new("t33", 30, t43, nil)
t34 = Node.new("t34", 40, nil, nil)
t35 = Node.new("t35", 10, t44, nil)
t36 = Node.new("t36", 30, t45, t46)
t21 = Node.new("t21", 30, t31, nil)
t22 = Node.new("t22", 20, t32, t33)
t23 = Node.new("t23", 30, t34, t35)
t24 = Node.new("t24", 20, t36, nil)
t11 = Node.new("t11", 10, t21, t22)
t12 = Node.new("t12", 20, t23, t24)
t01 = Node.new("t01", 0, t11, t12)
s = Search.new()
route = s.exec(t01)
route.each do |node|
puts node.getName() + " (" + node.getNumber().to_s + ")"
end
|
|
この例では再起呼び出しで行っていますが、例えば t41 まで来て 100 にならなかった場合、t31、t21 というように順に戻りながら、他のルートを探すことになります。 しかし、t01 から t41 に来る間に、分岐は t11 のところにしかないと分かったのなら、一気に t11 に戻った方が効率がいいはずです。 |
Momento パターンでは、分岐に来た（left も right も nil でない）ときに、その時点の情報の Memonto インスタンスを作り、スタックに保存しています。 memento = Memento.new(node, total, route) mementoStack.push(memento) そして、行き止まりになった（left も right も nil）ときには、スタックから Memonto インスタンスを取り出しています。これは、直前の分岐地点の情報です。つまり、それまでのルートと合計、そして、これから行く右側ルートです。 memento = mementoStack.pop() node = memento.getNode().right # 右側ルート route = memento.getRoute() # それまでのルート total = memento.getTotal() # それまでの合計 |
共通クラス
Node.js
class Node:
def __init__(self, name, number, left, right):
self.name = name
self.number = number
self.left = left
self.right = right
def getName(self):
return self.name
def getNumber(self):
return self.number
|
Mementoパターンを使用しない例 Search.py class Search:
def exec(self, node, total, list):
total += node.number
list.append(node)
if total >= 100:
return True
left = node.left
if left != None:
result = self.exec(left, total, list)
if result == True:
return result
right = node.right
if right != None:
result = self.exec(right, total, list)
if result == True:
return result
list.pop()
return False
Main.py from Node import Node
from Search import Search
def __print(node):
print(f"{node.getName()} ({node.getNumber()})")
list = []
t51 = Node("t51", 10, None, None)
t52 = Node("t52", 20, None, None)
t53 = Node("t53", 10, None, None)
t54 = Node("t54", 20, None, None)
t41 = Node("t41", 10, None, None)
t42 = Node("t42", 20, t51, t52)
t43 = Node("t43", 30, None, None)
t44 = Node("t44", 20, t53, t54)
t45 = Node("t45", 10, None, None)
t46 = Node("t46", 20, None, None)
t31 = Node("t31", 40, t41, None)
t32 = Node("t32", 20, t42, None)
t33 = Node("t33", 30, t43, None)
t34 = Node("t34", 40, None, None)
t35 = Node("t35", 10, t44, None)
t36 = Node("t36", 30, t45, t46)
t21 = Node("t21", 30, t31, None)
t22 = Node("t22", 20, t32, t33)
t23 = Node("t23", 30, t34, t35)
t24 = Node("t24", 20, t36, None)
t11 = Node("t11", 10, t21, t22)
t12 = Node("t12", 20, t23, t24)
t01 = Node("t01", 0, t11, t12)
s = Search()
s.exec(t01, 0, list)
for node in list:
__print(node)
|
Mementoパターンを使用した例 Search.py from Memento import Memento
class Search:
def exec(self, node):
route = []
total = 0
memento = None
self.mementoStack = []
while True:
total += node.number
route.append(node)
if total >= 100:
break
left = node.left
right = node.right
if left != None and right != None:
memento = Memento(node, total, route)
self.mementoStack.append(memento)
node = left
elif left == None and right == None:
if len(self.mementoStack) == 0:
return None
memento = self.mementoStack.pop()
node = memento.getNode().right
route = memento.getRoute()
total = memento.getTotal()
elif left != None:
node = node.left
else:
node = node.right
return route
Memento.py import copy
class Memento:
def __init__(self, node, total, route):
self.node = node
self.total = total
self.route = copy.deepcopy(route) # clone
def getNode(self):
return self.node
def getTotal(self):
return self.total
def getRoute(self): # ルートを得る
return self.route
Main.py from Node import Node
from Search import Search
def __print(node):
print(f"{node.getName()} ({node.getNumber()})")
t51 = Node("t51", 10, None, None)
t52 = Node("t52", 20, None, None)
t53 = Node("t53", 10, None, None)
t54 = Node("t54", 20, None, None)
t41 = Node("t41", 10, None, None)
t42 = Node("t42", 20, t51, t52)
t43 = Node("t43", 30, None, None)
t44 = Node("t44", 20, t53, t54)
t45 = Node("t45", 10, None, None)
t46 = Node("t46", 20, None, None)
t31 = Node("t31", 40, t41, None)
t32 = Node("t32", 20, t42, None)
t33 = Node("t33", 30, t43, None)
t34 = Node("t34", 40, None, None)
t35 = Node("t35", 10, t44, None)
t36 = Node("t36", 30, t45, t46)
t21 = Node("t21", 30, t31, None)
t22 = Node("t22", 20, t32, t33)
t23 = Node("t23", 30, t34, t35)
t24 = Node("t24", 20, t36, None)
t11 = Node("t11", 10, t21, t22)
t12 = Node("t12", 20, t23, t24)
t01 = Node("t01", 0, t11, t12)
s = Search()
route = s.exec(t01)
for node in route:
__print(node)
|
|
この例では再起呼び出しで行っていますが、例えば t41 まで来て 100 にならなかった場合、t31、t21 というように順に戻りながら、他のルートを探すことになります。 しかし、t01 から t41 に来る間に、分岐は t11 のところにしかないと分かったのなら、一気に t11 に戻った方が効率がいいはずです。 |
Momento パターンでは、分岐に来た（left も right も None でない）ときに、その時点の情報の Memonto インスタンスを作り、スタックに保存しています。 memento = Memento(node, total, route) self.mementostack.append(memento) そして、行き止まりになった（left も right も None）ときには、スタックから Memonto インスタンスを取り出しています。これは、直前の分岐地点の情報です。つまり、それまでのルートと合計、そして、これから行く右側ルートです。 memento = self.mementostack.pop() node = memento.getNode().right # 右側ルート route = memento.getRoute() # それまでのルート total = memento.getTotal() # それまでの合計 |
共通クラス
Node.php
<?php
class Node {
public $left = null;
public $right = null;
public $name;
public $number = 0;
public function __construct($name, $number, $left, $right) {
$this->name = $name;
$this->number = $number;
$this->left = $left;
$this->right = $right;
}
public function getName() {
return $this->name;
}
public function getNumber() {
return $this->number;
}
}
?>
|
Mementoパターンを使用しない例 Search.php <?php
class Search {
public function exec(node, total, &$list) {
$total += $node->number;
$list[] = $node);
if ($total >= 100)
return true;
$left = $node->left;
if ($left != null) {
$result = $this->exec($left, $total, $list);
if ($result == true) {
return $result;
}
}
$right = $node->right;
if ($right != null) {
$result = $this->exec($right, $total, $list);
if ($result == true) {
return $result;
}
}
array_splice($list, count($list)-1, 1);
return false;
}
}
?>
Main.php <?php
require_once('Node.php');
require_once('Search.php');
$list = array();
$t51 = new Node("t51", 10, null, null);
$t52 = new Node("t52", 20, null, null);
$t53 = new Node("t53", 10, null, null);
$t54 = new Node("t54", 20, null, null);
$t41 = new Node("t41", 10, null, null);
$t42 = new Node("t42", 20, $t51, $t52);
$t43 = new Node("t43", 30, null, null);
$t44 = new Node("t44", 20, $t53, $t54);
$t45 = new Node("t45", 10, null, null);
$t46 = new Node("t46", 20, null, null);
$t31 = new Node("t31", 40, $t41, null);
$t32 = new Node("t32", 20, $t42, null);
$t33 = new Node("t33", 30, $t43, null);
$t34 = new Node("t34", 40, null, null);
$t35 = new Node("t35", 10, $t44, null);
$t36 = new Node("t36", 30, $t45, $t46);
$t21 = new Node("t21", 30, $t31, null);
$t22 = new Node("t22", 20, $t32, $t33);
$t23 = new Node("t23", 30, $t34, $t35);
$t24 = new Node("t24", 20, $t36, null);
$t11 = new Node("t11", 10, $t21, $t22);
$t12 = new Node("t12", 20, $t23, $t24);
$t01 = new Node("t01", 0, $t11, $t12);
$s = new Search();
$s->exec($t01, 0, $list);
foreach($list as $node) {
print $node->getName() . " (" . $node->getNumber() . ")\n";
}
?>
|
Mementoパターンを使用した例 Search.php <?php
require_once('Memento.php');
class Search {
public function exec($node) {
$route = array();
$total = 0;
$memento = null;
$mementoStack = array();
while (true) {
$total += $node->number;
route[] = $node;
if ($total >= 100)
break;
$left = $node->$left;
$right = $node->$right;
if ($left != null && $right != null) {
$memento = new Memento($node, $total, $route);
array_push($mementoStack, $memento);
$node = $left;
}
else if ($left == null && $right == null) {
if (count(mementoStack) == 0)
return null;
$memento = array_pop($mementoStack);
$node = $memento->getNode()->right;
$route = $memento->getRoute();
$total = $memento->getTotal();
}
else if ($left != null)
$node = $node->left;
else
$node = $node->right;
}
return $route;
}
}
?>
Memento.php <?php
class Memento {
private $node; // ノード
private $total; // 合計値
private $route; // ルート
public function __construct($node, $total, $route) {
$this->node = $node;
$this->total = $total;
$this->route = array();
foreach($route as $node)
$this->route[] = $node;
}
public function getNode() {
return $this->node;
}
public function getTotal() {
return $this->total;
}
public function getRoute() { // ルートを得る
return $this->route;
}
}
?>
Main.php <?php
require_once('Node.php');
require_once('Search.php');
$t51 = new Node("t51", 10, null, null);
$t52 = new Node("t52", 20, null, null);
$t53 = new Node("t53", 10, null, null);
$t54 = new Node("t54", 20, null, null);
$t41 = new Node("t41", 10, null, null);
$t42 = new Node("t42", 20, $t51, $t52);
$t43 = new Node("t43", 30, null, null);
$t44 = new Node("t44", 20, $t53, $t54);
$t45 = new Node("t45", 10, null, null);
$t46 = new Node("t46", 20, null, null);
$t31 = new Node("t31", 40, $t41, null);
$t32 = new Node("t32", 20, $t42, null);
$t33 = new Node("t33", 30, $t43, null);
$t34 = new Node("t34", 40, null, null);
$t35 = new Node("t35", 10, $t44, null);
$t36 = new Node("t36", 30, $t45, $t46);
$t21 = new Node("t21", 30, $t31, null);
$t22 = new Node("t22", 20, $t32, $t33);
$t23 = new Node("t23", 30, $t34, $t35);
$t24 = new Node("t24", 20, $t36, null);
$t11 = new Node("t11", 10, $t21, $t22);
$t12 = new Node("t12", 20, $t23, $t24);
$t01 = new Node("t01", 0, $t11, $t12);
$s = new Search();
$route = $s->exec($t01);
foreach($route as $node) {
print $node->getName() . " (" . $node->getNumber() . ")\n";
}
?>
|
|
この例では再起呼び出しで行っていますが、例えば t41 まで来て 100 にならなかった場合、t31、t21 というように順に戻りながら、他のルートを探すことになります。 しかし、t01 から t41 に来る間に、分岐は t11 のところにしかないと分かったのなら、一気に t11 に戻った方が効率がいいはずです。 |
Momento パターンでは、分岐に来た（left も right も null でない）ときに、その時点の情報の Memonto インスタンスを作り、スタックに保存しています。 $memento = new Memento($node, $total, $route); array_push($mementoStack, $memento); そして、行き止まりになった（left も right も null）ときには、スタックから Memonto インスタンスを取り出しています。これは、直前の分岐地点の情報です。つまり、それまでのルートと合計、そして、これから行く右側ルートです。 array_push($mementoStack, $memento); $node = $memento->getNode()->right; // 右側ルート $route = $memento->getRoute(); // それまでのルート $total = $memento->getTotal(); // それまでの合計 |
共通クラス
Nodex.ts
export
class Node {
public name:string;
public number:number;
public left:Node;
public right:Node;
public constructor(name:string, number:number, left:Node, right:Node) {
this.name = name;
this.number = number;
this.left = left;
this.right = right;
}
public getName():string {
return name;
}
public getNumber():number {
return number;
}
}
|
Mementoパターンを使用しない例 Search.ts import {Node} from "./Nodex";
export
class Search {
public exec(node:Node, total:number, list:Array<Node> ):boolean {
total += node.number;
list.push(node);
if (total >= 100)
return true;
let left:Node = node.left;
if (left != null) {
let result:boolean = this.exec(left, total, list);
if (result == true) {
return result;
}
}
let right:Node = node.right;
if (right != null) {
let result:boolean = this.exec(right, total, list);
if (result == true) {
return result;
}
}
list.pop();
return false;
}
}
Main.ts import {Node} from "./Nodex";
import {Search} from "./Search";
let list:List<Node> = new Array<Node>();
let t51:Node = new Node("t51", 10, null, null);
let t52:Node = new Node("t52", 20, null, null);
let t53:Node = new Node("t53", 10, null, null);
let t54:Node = new Node("t54", 20, null, null);
let t41:Node = new Node("t41", 10, null, null);
let t42:Node = new Node("t42", 20, t51, t52);
let t43:Node = new Node("t43", 30, null, null);
let t44:Node = new Node("t44", 20, t53, t54);
let t45:Node = new Node("t45", 10, null, null);
let t46:Node = new Node("t46", 20, null, null);
let t31:Node = new Node("t31", 40, t41, null);
let t32:Node = new Node("t32", 20, t42, null);
let t33:Node = new Node("t33", 30, t43, null);
let t34:Node = new Node("t34", 40, null, null);
let t35:Node = new Node("t35", 10, t44, null);
let t36:Node = new Node("t36", 30, t45, t46);
let t21:Node = new Node("t21", 30, t31, null);
let t22:Node = new Node("t22", 20, t32, t33);
let t23:Node = new Node("t23", 30, t34, t35);
let t24:Node = new Node("t24", 20, t36, null);
let t11:Node = new Node("t11", 10, t21, t22);
let t12:Node = new Node("t12", 20, t23, t24);
let t01:Node = new Node("t01", 0, t11, t12);
let s:Search = new Search();
s.exec(t01, 0, list);
list.forEach(function(node:Node) {
process.stdout.write(node.getName() + " (" + node.getNumber() + ")\n");
});
|
Mementoパターンを使用した例 Search.ts import {Memento} from "./Memento";
import {Node} from "./Nodex";
export
class Search {
private mementoStack:Array<Memento>;
public exec(node:Node):Array<Node> {
let route:List<Node>= new Array<Node>();
let total:number = 0;
let memento:Memento = null;
this.mementoStack = new Array<Memento>();
while (true) {
total += node.number;
route.push(node);
if (total >= 100)
break;
let left:Node = node.left;
let right:Node = node.right;
if (left != null && right != null) {
memento = new Memento(node, total, route);
this.mementoStack.push(memento);
node = left;
}
else if (left == null && right == null) {
if (this.mementoStack.length == 0)
return null;
memento = this.mementoStack.pop();
node = memento.getNode().right;
route = memento.getRoute();
total = memento.getTotal();
}
else if (left != null)
node = node.left;
else
node = node.right;
}
return route;
}
}
Memento.ts import {Node} from "./Nodex";
export
class Memento {
private node:Node; // ノード
private total:number; // 合計値
private route:Array<Node>; // ルート
public constructor(node:Node, total:number, route:Array<Node> ) {
this.node = node;
this.total = total;
this.route = route.slice(0); // clone
}
public getNode():Node {
return this.node;
}
public getTotal():number {
return this.total;
}
public getRoute():Array<Node> { // ルートを得る
return this.route;
}
}
Main.ts import {Node} from "./Nodex";
import {Search} from "./Search";
let t51:Node = new Node("t51", 10, null, null);
let t52:Node = new Node("t52", 20, null, null);
let t53:Node = new Node("t53", 10, null, null);
let t54:Node = new Node("t54", 20, null, null);
let t41:Node = new Node("t41", 10, null, null);
let t42:Node = new Node("t42", 20, t51, t52);
let t43:Node = new Node("t43", 30, null, null);
let t44:Node = new Node("t44", 20, t53, t54);
let t45:Node = new Node("t45", 10, null, null);
let t46:Node = new Node("t46", 20, null, null);
let t31:Node = new Node("t31", 40, t41, null);
let t32:Node = new Node("t32", 20, t42, null);
let t33:Node = new Node("t33", 30, t43, null);
let t34:Node = new Node("t34", 40, null, null);
let t35:Node = new Node("t35", 10, t44, null);
let t36:Node = new Node("t36", 30, t45, t46);
let t21:Node = new Node("t21", 30, t31, null);
let t22:Node = new Node("t22", 20, t32, t33);
let t23:Node = new Node("t23", 30, t34, t35);
let t24:Node = new Node("t24", 20, t36, null);
let t11:Node = new Node("t11", 10, t21, t22);
let t12:Node = new Node("t12", 20, t23, t24);
let t01:Node = new Node("t01", 0, t11, t12);
let s:Search = new Search();
let route:List<Node> = s.exec(t01);
route.forEach(function(node:Node) {
process.stdout.write(node.getName() + " (" + node.getNumber() + ")\n");
});
|
|
この例では再起呼び出しで行っていますが、例えば t41 まで来て 100 にならなかった場合、t31、t21 というように順に戻りながら、他のルートを探すことになります。 しかし、t01 から t41 に来る間に、分岐は t11 のところにしかないと分かったのなら、一気に t11 に戻った方が効率がいいはずです。 |
Momento パターンでは、分岐に来た（left も right も null でない）ときに、その時点の情報の Memonto インスタンスを作り、スタックに保存しています。 memento = new Memento(node, total, route); this.mementostack.push(memento); そして、行き止まりになった（left も right も null）ときには、スタックから Memonto インスタンスを取り出しています。これは、直前の分岐地点の情報です。つまり、それまでのルートと合計、そして、これから行く右側ルートです。 memento = this.mementoStack.pop(); node = memento.getNode().right; // 右側ルート route = memento.getRoute(); // それまでのルート total = memento.getTotal(); // それまでの合計 |
共通クラス
Node.swift
public class Node {
internal var left:Node!
internal var right:Node!
internal var name:String = ""
internal var number:Int = 0
public init(_ name:String, _ number:Int, _ left:Node!, _ right:Node!) {
self.name = name
self.number = number
self.left = left
self.right = right
}
public func getName() -> String {
return name
}
public func getNumber() -> Int {
return number
}
}
|
Mementoパターンを使用しない例 Search.swift public class Search {
public func exec(_ node:Node, _ total:Int, _ list:[Node] ) -> Bool {
let t:Int = total + node.number
list.append(node)
if total >= 100 {
return true
}
let left:Node! = node.left
if left != nil {
let result:Bool = exec(left, t, &list)
if result == true {
return result
}
}
let right:Node! = node.right
if (right != nil) {
let result:Bool = exec(right, t, &list)
if result == true {
return result
}
}
list.removeLast()
return false
}
}
Main.swift let list:List[Node] = []
let t51:Node = Node("t51", 10, nil, nil)
let t52:Node = Node("t52", 20, nil, nil)
let t53:Node = Node("t53", 10, nil, nil)
let t54:Node = Node("t54", 20, nil, nil)
let t41:Node = Node("t41", 10, nil, nil)
let t42:Node = Node("t42", 20, t51, t52)
let t43:Node = Node("t43", 30, nil, nil)
let t44:Node = Node("t44", 20, t53, t54)
let t45:Node = Node("t45", 10, nil, nil)
let t46:Node = Node("t46", 20, nil, nil)
let t31:Node = Node("t31", 40, t41, nil)
let t32:Node = Node("t32", 20, t42, nil)
let t33:Node = Node("t33", 30, t43, nil)
let t34:Node = Node("t34", 40, nil, nil)
let t35:Node = Node("t35", 10, t44, nil)
let t36:Node = Node("t36", 30, t45, t46)
let t21:Node = Node("t21", 30, t31, nil)
let t22:Node = Node("t22", 20, t32, t33)
let t23:Node = Node("t23", 30, t34, t35)
let t24:Node = Node("t24", 20, t36, nil)
let t11:Node = Node("t11", 10, t21, t22)
let t12:Node = Node("t12", 20, t23, t24)
let t01:Node = Node("t01", 0, t11, t12)
let s:Search = Search()
_ = s.exec(t01, 0, &list)
list.forEach {
print($0.getName() + " (" + String($0.getNumber()) + ")")
})
|
Mementoパターンを使用した例 Search.swift public class Search {
public func exec(_ node:Node!) -> [Node] {
var node:Node! = node
var route:[Node] = []
var total:Int = 0
var memento:Memento
var mementoStack:[Memento] = []
while true {
total += node.number
route.append(node)
if total >= 100 {
break
}
let left:Node! = node.left
let right:Node! = node.right
if left != nil && right != nil {
memento = Memento(node, total, route)
mementoStack.append(memento)
node = left
}
else if left == nil && right == nil {
if mementoStack.isEmpty {
return nil
}
memento = mementoStack.removeLast()
node = memento.getNode().right
route = memento.getRoute()
total = memento.getTotal()
}
else if left != nil {
node = node.left
}
else {
node = node.right
}
}
return route
}
}
Memento.swift public class Memento {
private var node:Node // ノード
private var total:Int // 合計値
private var route:[Node] = [] // ルート
public init(_ node:Node, _ total:Int, _ route:[Node]) {
self.node = node
self.total = total
for i in (0..<route.count) {
self.route.append(route[i])
}
}
public func getNode() -> Node {
return node
}
public func getTotal() -> Int {
return total
}
public func getRoute() -> [Node] { // ルートを得る
return route
}
}
Main.swift var list:[Node] = []
let t51:Node = Node("t51", 10, nil, nil)
let t52:Node = Node("t52", 20, nil, nil)
let t53:Node = Node("t53", 10, nil, nil)
let t54:Node = Node("t54", 20, nil, nil)
let t41:Node = Node("t41", 10, nil, nil)
let t42:Node = Node("t42", 20, t51, t52)
let t43:Node = Node("t43", 30, nil, nil)
let t44:Node = Node("t44", 20, t53, t54)
let t45:Node = Node("t45", 10, nil, nil)
let t46:Node = Node("t46", 20, nil, nil)
let t31:Node = Node("t31", 40, t41, nil)
let t32:Node = Node("t32", 20, t42, nil)
let t33:Node = Node("t33", 30, t43, nil)
let t34:Node = Node("t34", 40, nil, nil)
let t35:Node = Node("t35", 10, t44, nil)
let t36:Node = Node("t36", 30, t45, t46)
let t21:Node = Node("t21", 30, t31, nil)
let t22:Node = Node("t22", 20, t32, t33)
let t23:Node = Node("t23", 30, t34, t35)
let t24:Node = Node("t24", 20, t36, nil)
let t11:Node = Node("t11", 10, t21, t22)
let t12:Node = Node("t12", 20, t23, t24)
let t01:Node = Node("t01", 0, t11, t12)
let s:Search = Search()
let route:[Node] = s.exec(t01)
route.forEach {
print($0.getName() + " (" + String($0.getNumber()) + ")")
}
|
|
この例では再起呼び出しで行っていますが、例えば t41 まで来て 100 にならなかった場合、t31、t21 というように順に戻りながら、他のルートを探すことになります。 しかし、t01 から t41 に来る間に、分岐は t11 のところにしかないと分かったのなら、一気に t11 に戻った方が効率がいいはずです。 |
Momento パターンでは、分岐に来た（left も right も nil でない）ときに、その時点の情報の Memonto インスタンスを作り、スタックに保存しています。 memento = Memento(node, total, route) mementostack.append(memento) そして、行き止まりになった（left も right も nil）ときには、スタックから Memonto インスタンスを取り出しています。これは、直前の分岐地点の情報です。つまり、それまでのルートと合計、そして、これから行く右側ルートです。 memento = mementoStack.removeLast() node = memento.getNode().right // 右側ルート route = memento.getRoute() // それまでのルート total = memento.getTotal() // それまでの合計 |
共通クラス
Nodex.kt
class Node(internal val name: String, internal val number: Int, val left: Node?, val right:Node?) {}
|
Mementoパターンを使用しない例 Search.kt class Search {
fun exec(node: Node, total: Int, list: ArrayList<Node> ): Boolean {
var total = total
total += node.number
list.add(node)
if (total >= 100) return true
var left = node.left
if (left != null) {
val result = exec(left, total, list)
if (result) {
return result
}
}
var right = node.right
if (right != null) {
val result = exec(right, total, list)
if (result) {
return result
}
}
list.remove(node)
return false
}
}
Main.kt fun main() {
var list:ArrayList<Node> = ArrayList()
var t51 = Node("t51", 10, null, null)
var t52 = Node("t52", 20, null, null)
var t53 = Node("t53", 10, null, null)
var t54 = Node("t54", 20, null, null)
var t41 = Node("t41", 10, null, null)
var t42 = Node("t42", 20, t51, t52)
var t43 = Node("t43", 30, null, null)
var t44 = Node("t44", 20, t53, t54)
var t45 = Node("t45", 10, null, null)
var t46 = Node("t46", 20, null, null)
var t31 = Node("t31", 40, t41, null)
var t32 = Node("t32", 20, t42, null)
var t33 = Node("t33", 30, t43, null)
var t34 = Node("t34", 40, null, null)
var t35 = Node("t35", 10, t44, null)
var t36 = Node("t36", 30, t45, t46)
var t21 = Node("t21", 30, t31, null)
var t22 = Node("t22", 20, t32, t33)
var t23 = Node("t23", 30, t34, t35)
var t24 = Node("t24", 20, t36, null)
var t11 = Node("t11", 10, t21, t22)
var t12 = Node("t12", 20, t23, t24)
var t01 = Node("t01", 0, t11, t12)
var s = Search()
s.exec(t01, 0, list)
val it = list.iterator()
while (it.hasNext()) {
val node = it.next()
println(node.name + " (" + node.number + ")")
}
|
Mementoパターンを使用した例 Search.kt import java.util.*
class Search {
public exec(node: Node):List<Node>? {
var node = node
var route: ArrayList<Node>= ArrayList()
var total: Int = 0
var memento:Memento
val mementoStack = Stack<Memento>()
while (true) {
total += node.number
route.add(node)
if (total >= 100) break
var left = node.left
var right = node.right
if (left != null && right != null) {
memento = Memento(node, total, route)
mementoStack.push(memento)
node = left
}
else if (left == null && right == null) {
if (mementoStack.empty()) return null
memento = mementoStack.pop() as Memento
node = memento.node.right!!
route = memento.route
total = memento.total
}
else if (left != null)
node = node.left!!
else
node = node.right!!
}
return route
}
}
Memento.kt class Memento(internal val node: Node, internal val total: Int, route: ArrayList<Node>) {
internal var route = ArrayList<Node>() // ルート
init {
for (node: Node in route) this.route.add(node)
}
}
Main.kt fun main() {
var t51 = Node("t51", 10, null, null)
var t52 = Node("t52", 20, null, null)
var t53 = Node("t53", 10, null, null)
var t54 = Node("t54", 20, null, null)
var t41 = Node("t41", 10, null, null)
var t42 = Node("t42", 20, t51, t52)
var t43 = Node("t43", 30, null, null)
var t44 = Node("t44", 20, t53, t54)
var t45 = Node("t45", 10, null, null)
var t46 = Node("t46", 20, null, null)
var t31 = Node("t31", 40, t41, null)
var t32 = Node("t32", 20, t42, null)
var t33 = Node("t33", 30, t43, null)
var t34 = Node("t34", 40, null, null)
var t35 = Node("t35", 10, t44, null)
var t36 = Node("t36", 30, t45, t46)
var t21 = Node("t21", 30, t31, null)
var t22 = Node("t22", 20, t32, t33)
var t23 = Node("t23", 30, t34, t35)
var t24 = Node("t24", 20, t36, null)
var t11 = Node("t11", 10, t21, t22)
var t12 = Node("t12", 20, t23, t24)
var t01 = Node("t01", 0, t11, t12)
var s = Search()
val route = s.exec(t01)
if (route != null) {
val it = route.iterator()
while (it.hasNext()) {
val node = it.next()
println(node.name + " (" + node.number + ")")
}
}
}
|
|
この例では再起呼び出しで行っていますが、例えば t41 まで来て 100 にならなかった場合、t31、t21 というように順に戻りながら、他のルートを探すことになります。 しかし、t01 から t41 に来る間に、分岐は t11 のところにしかないと分かったのなら、一気に t11 に戻った方が効率がいいはずです。 |
Momento パターンでは、分岐に来た（left も right も null でない）ときに、その時点の情報の Memonto インスタンスを作り、スタックに保存しています。 memento = new Memento(node, total, route) this.mementostack.push(memento) そして、行き止まりになった（left も right も null）ときには、スタックから Memonto インスタンスを取り出しています。これは、直前の分岐地点の情報です。つまり、それまでのルートと合計、そして、これから行く右側ルートです。 memento = this.mementoStack.pop() node = memento.getNode().right // 右側ルート route = memento.getRoute() // それまでのルート total = memento.getTotal() // それまでの合計 |
共通クラス
Node.scala
class Node(val name: String, val number: Int, val left: Node, val right:Node) {}
|
Mementoパターンを使用しない例 Search.scala import java.util.ArrayList
class Search {
def exec(node: Node, ttl: Int, list: ArrayList[Node]): Boolean = {
var total: Int = ttl + node.number
list.add(node)
if (total >= 100) return true
var left = node.left
if (left != null) {
val result = exec(left, total, list)
if (result == true) {
return result
}
}
var right = node.right
if (right != null) {
val result = exec(right, total, list)
if (result == true) {
return result
}
}
list.remove(node)
false
}
}
Main.scala import java.util.Iterator
import java.util.ArrayList
object Main {
def main(args: Array[String]) {
var list = new ArrayList[Node]()
var t51 = new Node("t51", 10, null, null)
var t52 = new Node("t52", 20, null, null)
var t53 = new Node("t53", 10, null, null)
var t54 = new Node("t54", 20, null, null)
var t41 = new Node("t41", 10, null, null)
var t42 = new Node("t42", 20, t51, t52)
var t43 = new Node("t43", 30, null, null)
var t44 = new Node("t44", 20, t53, t54)
var t45 = new Node("t45", 10, null, null)
var t46 = new Node("t46", 20, null, null)
var t31 = new Node("t31", 40, t41, null)
var t32 = new Node("t32", 20, t42, null)
var t33 = new Node("t33", 30, t43, null)
var t34 = new Node("t34", 40, null, null)
var t35 = new Node("t35", 10, t44, null)
var t36 = new Node("t36", 30, t45, t46)
var t21 = new Node("t21", 30, t31, null)
var t22 = new Node("t22", 20, t32, t33)
var t23 = new Node("t23", 30, t34, t35)
var t24 = new Node("t24", 20, t36, null)
var t11 = new Node("t11", 10, t21, t22)
var t12 = new Node("t12", 20, t23, t24)
var t01 = new Node("t01", 0, t11, t12)
var s = new Search()
s.exec(t01, 0, list)
val it = list.iterator()
while (it.hasNext()) {
val node = it.next()
System.out.println(node.name + " (" + node.number + ")")
}
}
}
|
Mementoパターンを使用した例 Search.scala import java.util.ArrayList
import java.util.Stack
import scala.util.control.Breaks
class Search {
def exec(nd: Node): ArrayList[Node] {
var node: Node = nd
var route = new ArrayList[Node]()
var total: Int = 0;
var memento:Memento = null
val mementoStack = new Stack[Memento]()
val b = new Breaks
b.breakable {
while (true) {
total += node.number
route.add(node)
if (total >= 100) b.break
var left: Node = node.left
var right = node.right
if (left != null && right != null) {
memento = new Memento(node, total, route)
mementoStack.push(memento)
node = left
}
else if (left == null && right == null) {
if (mementoStack.empty) return null
memento = mementoStack.pop()
node = memento.node.right
route = memento.route
total = memento.total
}
else if (left != null)
node = node.left
else
node = node.right
}
}
route
}
}
Memento.scala import java.util.ArrayList
class Memento(val node: Node, val total: Int, val rt: ArrayList[Node]) {
val route_ = new ArrayList[Node]() // ルート
rt.forEach(r => route_.add(r))
def route : ArrayList[Node] = route_
}
Main.scala import java.util.ArrayList
object Main {
def main(args: Array[String]) {
var list = new ArrayList[Node]()
var t51 = new Node("t51", 10, null, null)
var t52 = new Node("t52", 20, null, null)
var t53 = new Node("t53", 10, null, null)
var t54 = new Node("t54", 20, null, null)
var t41 = new Node("t41", 10, null, null)
var t42 = new Node("t42", 20, t51, t52)
var t43 = new Node("t43", 30, null, null)
var t44 = new Node("t44", 20, t53, t54)
var t45 = new Node("t45", 10, null, null)
var t46 = new Node("t46", 20, null, null)
var t31 = new Node("t31", 40, t41, null)
var t32 = new Node("t32", 20, t42, null)
var t33 = new Node("t33", 30, t43, null)
var t34 = new Node("t34", 40, null, null)
var t35 = new Node("t35", 10, t44, null)
var t36 = new Node("t36", 30, t45, t46)
var t21 = new Node("t21", 30, t31, null)
var t22 = new Node("t22", 20, t32, t33)
var t23 = new Node("t23", 30, t34, t35)
var t24 = new Node("t24", 20, t36, null)
var t11 = new Node("t11", 10, t21, t22)
var t12 = new Node("t12", 20, t23, t24)
var t01 = new Node("t01", 0, t11, t12)
var s = new Search()
val route = s.exec(t01)
if (route != null) {
val it = list.iterator()
while (it.hasNext()) {
val node: Node = it.next()
System.out.println(node.name + " (" + node.number + ")")
}
}
}
}
|
|
この例では再起呼び出しで行っていますが、例えば t41 まで来て 100 にならなかった場合、t31、t21 というように順に戻りながら、他のルートを探すことになります。 しかし、t01 から t41 に来る間に、分岐は t11 のところにしかないと分かったのなら、一気に t11 に戻った方が効率がいいはずです。 |
Momento パターンでは、分岐に来た（left も right も null でない）ときに、その時点の情報の Memonto インスタンスを作り、スタックに保存しています。 memento = new Memento(node, total, route) mementostack.push(memento) そして、行き止まりになった（left も right も null）ときには、スタックから Memonto インスタンスを取り出しています。これは、直前の分岐地点の情報です。つまり、それまでのルートと合計、そして、これから行く右側ルートです。 memento = mementoStack.pop() node = memento.getNode().right // 右側ルート route = memento.getRoute() // それまでのルート total = memento.getTotal() // それまでの合計 |
共通クラス
Node.groovy
class Node {
Node left = null
Node right = null
String name
int number = 0
Node(String name, int number, Node left, Node right) {
this.name = name
this.number = number
this.left = left
this.right = right
}
}
|
Mementoパターンを使用しない例 Search.groovy class Search {
boolean exec(Node node, int total, List<Node> list) {
total += node.number
list.add(node)
if (total >= 100)
return true
Node left = node.left
if (left != null) {
boolean result = exec(left, total, list)
if (result == true) {
return result
}
}
Node right = node.right
if (right != null) {
boolean result = exec(right, total, list)
if (result == true) {
return result
}
}
list.remove(node)
return false
}
}
Main.groovy class Main {
static void main(String[] args) {
List<Node> list = new ArrayList<Node>()
Node t51 = new Node("t51", 10, null, null)
Node t52 = new Node("t52", 20, null, null)
Node t53 = new Node("t53", 10, null, null)
Node t54 = new Node("t54", 20, null, null)
Node t41 = new Node("t41", 10, null, null)
Node t42 = new Node("t42", 20, t51, t52)
Node t43 = new Node("t43", 30, null, null)
Node t44 = new Node("t44", 20, t53, t54)
Node t45 = new Node("t45", 10, null, null)
Node t46 = new Node("t46", 20, null, null)
Node t31 = new Node("t31", 40, t41, null)
Node t32 = new Node("t32", 20, t42, null)
Node t33 = new Node("t33", 30, t43, null)
Node t34 = new Node("t34", 40, null, null)
Node t35 = new Node("t35", 10, t44, null)
Node t36 = new Node("t36", 30, t45, t46)
Node t21 = new Node("t21", 30, t31, null)
Node t22 = new Node("t22", 20, t32, t33)
Node t23 = new Node("t23", 30, t34, t35)
Node t24 = new Node("t24", 20, t36, null)
Node t11 = new Node("t11", 10, t21, t22)
Node t12 = new Node("t12", 20, t23, t24)
Node t01 = new Node("t01", 0, t11, t12)
Search s = new Search()
s.exec(t01, 0, list)
Iterator<Node> it = list.iterator()
while (it.hasNext()) {
Node node = (Node) it.next()
System.out.println(node.name + " (" + node.number + ")")
}
}
}
|
Mementoパターンを使用した例 Search.groovy class Search {
List<Node> exec(Node node) {
List<Node> route = new ArrayList<Node>()
int total = 0
Memento memento = null
Stack<Memento> mementoStack = new Stack<Memento>()
while (true) {
total += node.number
route.add(node)
if (total >= 100)
break
Node left = node.left
Node right = node.right
if (left != null && right != null) {
memento = new Memento(node, total, route)
mementoStack.push(memento)
node = left
}
else if (left == null && right == null) {
if (mementoStack.empty())
return null
memento = (Memento) mementoStack.pop()
node = memento.node.right
route = memento.route
total = memento.total
}
else if (left != null)
node = node.left
else
node = node.right
}
return route
}
}
Memento.groovy class Memento {
private Node node // ノード
private int total // 合計値
private ArrayList<Node> route // ルート
Memento(Node node, int total, List<Node> route) {
this.node = node
this.total = total
this.route = new ArrayList<Node>()
for (int i in 0..<route.size())
this.route.add(route.get(i))
}
}
Main.groovy class Main {
static void main(String[] args) {
Node t51 = new Node("t51", 10, null, null)
Node t52 = new Node("t52", 20, null, null)
Node t53 = new Node("t53", 10, null, null)
Node t54 = new Node("t54", 20, null, null)
Node t41 = new Node("t41", 10, null, null)
Node t42 = new Node("t42", 20, t51, t52)
Node t43 = new Node("t43", 30, null, null)
Node t44 = new Node("t44", 20, t53, t54)
Node t45 = new Node("t45", 10, null, null)
Node t46 = new Node("t46", 20, null, null)
Node t31 = new Node("t31", 40, t41, null)
Node t32 = new Node("t32", 20, t42, null)
Node t33 = new Node("t33", 30, t43, null)
Node t34 = new Node("t34", 40, null, null)
Node t35 = new Node("t35", 10, t44, null)
Node t36 = new Node("t36", 30, t45, t46)
Node t21 = new Node("t21", 30, t31, null)
Node t22 = new Node("t22", 20, t32, t33)
Node t23 = new Node("t23", 30, t34, t35)
Node t24 = new Node("t24", 20, t36, null)
Node t11 = new Node("t11", 10, t21, t22)
Node t12 = new Node("t12", 20, t23, t24)
Node t01 = new Node("t01", 0, t11, t12)
Search s = new Search()
List<Node> route = s.exec(t01)
if (route != null) {
Iterator<Node> it = route.iterator()
while (it.hasNext()) {
Node node = (Node) it.next()
System.out.println(node.name + " (" + node.number + ")")
}
}
}
}
|
|
この例では再起呼び出しで行っていますが、例えば t41 まで来て 100 にならなかった場合、t31、t21 というように順に戻りながら、他のルートを探すことになります。 しかし、t01 から t41 に来る間に、分岐は t11 のところにしかないと分かったのなら、一気に t11 に戻った方が効率がいいはずです。 |
Momento パターンでは、分岐に来た（left も right も null でない）ときに、その時点の情報の Memonto インスタンスを作り、スタックに保存しています。 Memento memento(node, total, route); mementostack.push(memento); そして、行き止まりになった（left も right も null）ときには、スタックから Memonto インスタンスを取り出しています。これは、直前の分岐地点の情報です。つまり、それまでのルートと合計、そして、これから行く右側ルートです。 memento = (Memento)mementoStack.pop(); node = memento.getNode().right; // 右側ルート route = memento.getRoute(); // それまでのルート total = memento.getTotal(); // それまでの合計 |
共通クラス
Node.go
type Node struct {
left *Node
right *Node
Name string
Number int
}
func NewNode(name string, number int, left *Node, right *Node) *Node {
return &Node {
Name: name,
Number: number,
left: left,
right: right,
}
}
|
Mementoパターンを使用しない例 Search.go type Search struct {}
func (self *Search) Exec(node *Node, total int, list []*Node) ([]*Node, bool) {
total += node.number
list = append(list, node)
if total >= 100 {
return list, true
}
var left = node.left
if left != nil {
var list, result = self.Exec(left, total, list)
if result == true {
return list, true
}
}
var right = node.right
if right != nil {
var list, result = self.Exec(right, total, list)
if result == true {
return list, true
}
}
list = list[:len(list)-1]
return false
}
func NewSearch() *Search {
return &Search{}
}
Main.go import "fmt"
func main() {
var List []*Node
var t51 = NewNode("t51", 10, nil, nil)
var t52 = NewNode("t52", 20, nil, nil)
var t53 = NewNode("t53", 10, nil, nil)
var t54 = NewNode("t54", 20, nil, nil)
var t41 = NewNode("t41", 10, nil, nil)
var t42 = NewNode("t42", 20, t51, t52)
var t43 = NewNode("t43", 30, nil, nil)
var t44 = NewNode("t44", 20, t53, t54)
var t45 = NewNode("t45", 10, nil, nil)
var t46 = NewNode("t46", 20, nil, nil)
var t31 = NewNode("t31", 40, t41, nil)
var t32 = NewNode("t32", 20, t42, nil)
var t33 = NewNode("t33", 30, t43, nil)
var t34 = NewNode("t34", 40, nil, nil)
var t35 = NewNode("t35", 10, t44, nil)
var t36 = NewNode("t36", 30, t45, t46)
var t21 = NewNode("t21", 30, t31, nil)
var t22 = NewNode("t22", 20, t32, t33)
var t23 = NewNode("t23", 30, t34, t35)
var t24 = NewNode("t24", 20, t36, nil)
var t11 = NewNode("t11", 10, t21, t22)
var t12 = NewNode("t12", 20, t23, t24)
var t01 = NewNode("t01", 0, t11, t12)
var s = NewSearch()
list, _ = s.Exec(t01, 0, list)
for _, node := range list {
fmt.Printf("%s(%d)\n", node.Name, node.Number)
}
}
|
Mementoパターンを使用した例 Search.go type Search struct {}
func (self *Search) Exec(node *Node) []*Node {
var route []*Node
var total = 0
var memento = *Memento
var mementoStack []*Memento
for true {
total += node.Number
route = append(route, node)
if total >= 100 {
return route
}
var left = node.left
var right = node.right
if left != nil && right != nil {
memento = NewMemento(node, total, route)
mementoStack = append(mementoStack. memento) // push
node = left
} else if left == nil && right == nil {
if len(mementoStack) == 0 {
return nil
}
var last = len(mementoStack) - 1
memento = mementoStack[last]; mementoStack = mementoStack[0 : last] // pop
node = memento.node.right
route = memento.route
total = memento.total
} else if left != nil {
node = node.left
} else {
node = node.right
}
}
return route
}
func NewSearch() *Search {
return &Search{}
}
Memento.go type Memento struct {
node *Node // ノード
total int // 合計値
route []*Node // ルート
}
func NewMemento(node *Node, total int, route []*Node) *Memento {
return &Memento {
node: node
total: total
route: route
}
}
Main.go import "fmt"
func main() {
var t51 = NewNode("t51", 10, nil, nil)
var t52 = NewNode("t52", 20, nil, nil)
var t53 = NewNode("t53", 10, nil, nil)
var t54 = NewNode("t54", 20, nil, nil)
var t41 = NewNode("t41", 10, nil, nil)
var t42 = NewNode("t42", 20, t51, t52)
var t43 = NewNode("t43", 30, nil, nil)
var t44 = NewNode("t44", 20, t53, t54)
var t45 = NewNode("t45", 10, nil, nil)
var t46 = NewNode("t46", 20, nil, nil)
var t31 = NewNode("t31", 40, t41, nil)
var t32 = NewNode("t32", 20, t42, nil)
var t33 = NewNode("t33", 30, t43, nil)
var t34 = NewNode("t34", 40, nil, nil)
var t35 = NewNode("t35", 10, t44, nil)
var t36 = NewNode("t36", 30, t45, t46)
var t21 = NewNode("t21", 30, t31, nil)
var t22 = NewNode("t22", 20, t32, t33)
var t23 = NewNode("t23", 30, t34, t35)
var t24 = NewNode("t24", 20, t36, nil)
var t11 = NewNode("t11", 10, t21, t22)
var t12 = NewNode("t12", 20, t23, t24)
var t01 = NewNode("t01", 0, t11, t12)
var s = NewSearch()
var route = s.Exec(t01)
for _, node := range route {
fmt.Printf("%s(%d)\n", node.Name, node.Number)
}
}
|
|
この例では再起呼び出しで行っていますが、例えば t41 まで来て 100 にならなかった場合、t31、t21 というように順に戻りながら、他のルートを探すことになります。 しかし、t01 から t41 に来る間に、分岐は t11 のところにしかないと分かったのなら、一気に t11 に戻った方が効率がいいはずです。 |
Momento パターンでは、分岐に来た（left も right も null でない）ときに、その時点の情報の Memonto インスタンスを作り、スタックに保存しています。 Memento memento(node, total, route); mementostack.push(memento); そして、行き止まりになった（left も right も null）ときには、スタックから Memonto インスタンスを取り出しています。これは、直前の分岐地点の情報です。つまり、それまでのルートと合計、そして、これから行く右側ルートです。 memento = (Memento)mementoStack.pop(); node = memento.getNode().right; // 右側ルート route = memento.getRoute(); // それまでのルート total = memento.getTotal(); // それまでの合計 |
共通クラス
node.d
public class Node {
public Node left = null;
public Node right = null;
public string name;
public int number = 0;
public this(in string name, in int number, Node left, Node right) {
this.name = name;
this.number = number;
this.left = left;
this.right = right;
}
}
|
Mementoパターンを使用しない例 search.d import node;
public class Search {
public bool exec(Node node, in int total, ref Node[] list) {
total += node.number;
list ~= node;
if (total >= 100)
return true;
Node left = node.left;
if (left !is null) {
bool result = exec(left, total, list);
if (result == true) {
return result;
}
}
Node right = node.right;
if (right !is null) {
bool result = exec(right, total, list);
if (result == true) {
return result;
}
}
list = list[0..$-1];
return false;
}
}
main.d import std.stdio;
import node;
import search;
int main() {
Node[] list;
Node t51 = new Node("t51", 10, null, null);
Node t52 = new Node("t52", 20, null, null);
Node t53 = new Node("t53", 10, null, null);
Node t54 = new Node("t54", 20, null, null);
Node t41 = new Node("t41", 10, null, null);
Node t42 = new Node("t42", 20, t51, t52);
Node t43 = new Node("t43", 30, null, null);
Node t44 = new Node("t44", 20, t53, t54);
Node t45 = new Node("t45", 10, null, null);
Node t46 = new Node("t46", 20, null, null);
Node t31 = new Node("t31", 40, t41, null);
Node t32 = new Node("t32", 20, t42, null);
Node t33 = new Node("t33", 30, t43, null);
Node t34 = new Node("t34", 40, null, null);
Node t35 = new Node("t35", 10, t44, null);
Node t36 = new Node("t36", 30, t45, t46);
Node t21 = new Node("t21", 30, t31, null);
Node t22 = new Node("t22", 20, t32, t33);
Node t23 = new Node("t23", 30, t34, t35);
Node t24 = new Node("t24", 20, t36, null);
Node t11 = new Node("t11", 10, t21, t22);
Node t12 = new Node("t12", 20, t23, t24);
Node t01 = new Node("t01", 0, t11, t12);
Search s = new Search();
s.exec(t01, 0, list);
foreach (Node node; list) {
writefln("%s (%d)", node.name, node.number);
}
return 0;
}
|
Mementoパターンを使用した例 search.d import node;
import memento;
public class Search {
public Node[] exec(Node node) {
Node[] route;
int total = 0;
Memento memento = null;
Memento[] mementoStack;
while (true) {
total += node.number;
route ~= node;
if (total >= 100)
break;
Node left = node.left;
Node right = node.right;
if (left !is null && right !is null) {
memento = new Memento(node, total, route);
mementoStack ~= memento;
node = left;
}
else if (left is null && right is null) {
if (mementoStack.length == 0)
return null;
memento = mementoStack[mementoStack.length-1];
mementoStack = mementoStack[0..$-1]; // pop
node = memento.getNode().right;
route = memento.getRoute();
total = memento.getTotal();
}
else if (left !is null)
node = node.left;
else
node = node.right;
}
return route;
}
}
memento.d import node;
public class Memento {
private Node node; // ノード
private int total; // 合計値
private Node[] route; // ルート
protected this(Node node, in int total, Node[] route) {
this.node = node;
this.total = total;
this.route = [];
foreach (int i; 0..route.length)
this.route ~= route[i];
}
protected Node getNode() {
return node;
}
protected int getTotal() {
return total;
}
protected Node[] getRoute() { // ルートを得る
return route;
}
}
main.d import std.stdio;
import node;
import search;
int main() {
Node t51 = new Node("t51", 10, null, null);
Node t52 = new Node("t52", 20, null, null);
Node t53 = new Node("t53", 10, null, null);
Node t54 = new Node("t54", 20, null, null);
Node t41 = new Node("t41", 10, null, null);
Node t42 = new Node("t42", 20, t51, t52);
Node t43 = new Node("t43", 30, null, null);
Node t44 = new Node("t44", 20, t53, t54);
Node t45 = new Node("t45", 10, null, null);
Node t46 = new Node("t46", 20, null, null);
Node t31 = new Node("t31", 40, t41, null);
Node t32 = new Node("t32", 20, t42, null);
Node t33 = new Node("t33", 30, t43, null);
Node t34 = new Node("t34", 40, null, null);
Node t35 = new Node("t35", 10, t44, null);
Node t36 = new Node("t36", 30, t45, t46);
Node t21 = new Node("t21", 30, t31, null);
Node t22 = new Node("t22", 20, t32, t33);
Node t23 = new Node("t23", 30, t34, t35);
Node t24 = new Node("t24", 20, t36, null);
Node t11 = new Node("t11", 10, t21, t22);
Node t12 = new Node("t12", 20, t23, t24);
Node t01 = new Node("t01", 0, t11, t12);
Search s = new Search();
Node[] route = s.exec(t01);
if (route !is null) {
foreach (Node node; list) {
writefln("%s (%d)", node.name, node.number);
}
}
return 0;
}
|
|
この例では再起呼び出しで行っていますが、例えば t41 まで来て 100 にならなかった場合、t31、t21 というように順に戻りながら、他のルートを探すことになります。 しかし、t01 から t41 に来る間に、分岐は t11 のところにしかないと分かったのなら、一気に t11 に戻った方が効率がいいはずです。 |
Momento パターンでは、分岐に来た（left も right も null でない）ときに、その時点の情報の Memonto インスタンスを作り、スタックに保存しています。 Memento memento(node, total, route); mementostack.push(memento); そして、行き止まりになった（left も right も null）ときには、スタックから Memonto インスタンスを取り出しています。これは、直前の分岐地点の情報です。つまり、それまでのルートと合計、そして、これから行く右側ルートです。 memento = (Memento)mementoStack.pop(); node = memento.getNode().right; // 右側ルート route = memento.getRoute(); // それまでのルート total = memento.getTotal(); // それまでの合計 |
共通クラス
Node.pas
unit UnitNode;
interface
type
Node = class
private
var name:string;
var number:integer;
public
var left:Node;
var right:Node;
constructor Create(name:string; number:integer; left:Node; right:Node);
destructor Destroy(); override;
function getName():string;
function getNumber():integer;
end;
implementation
constructor Node.Create(name:string; number:integer; left:Node; right:Node);
begin
self.name := name;
self.number := number;
self.left := left;
self.right := right;
end;
destructor Node.Destroy();
begin
if left <> nil then
left.Free;
if right <> nil then
right.Free;
inherited Destroy();
end;
function Node.getName():string;
begin
Result := name;
end;
function Node.getNumber():integer;
begin
Result := number;
end;
end.
|
Mementoパターンを使用しない例 Search.pas unit UnitSearch;
interface
uses
System.SysUtils,
System.Generics.Collections,
UnitNode;
type
Search = class
var left, right:Node;
public
function exec(node:Node; total:integer; list:TList<Node>):boolean;
end;
implementation
function Search.exec(node:Node; total:integer; list:TList<Node>):boolean;
begin
total := total + node.getNumber();
list.Add(node);
if total >= 100 then begin
Result := true;
exit;
end;
left := node.left;
if left <> nil then begin
Result := exec(left, total, list);
if Result = true then
exit;
end;
right := node.right;
if right <> nil then begin
Result := exec(right, total, list);
if Result = true then
exit;
end;
list.Remove(node);
Result := false;
end;
end.
Main.dpr program MementoNon;
uses
System.SysUtils,
System.Generics.Collections,
UnitNode,
UnitSearch;
var list:TList<Node>;
var t01:Node;
var t11, t12:Node;
var t21, t22, t23, t24:Node;
var t31, t32, t33, t34, t35, t36:Node;
var t41, t42, t43, t44, t45, t46:Node;
var t51, t52, t53, t54:Node;
var s:Search;
var _node:Node;
begin
list := TList<Node>.Create();
t51 := Node.Create('t51', 10, nil, nil);
t52 := Node.Create('t52', 20, nil, nil);
t53 := Node.Create('t53', 10, nil, nil);
t54 := Node.Create('t54', 20, nil, nil);
t41 := Node.Create('t41', 10, nil, nil);
t42 := Node.Create('t42', 20, t51, t52);
t43 := Node.Create('t43', 30, nil, nil);
t44 := Node.Create('t44', 20, t53, t54);
t45 := Node.Create('t45', 10, nil, nil);
t46 := Node.Create('t46', 20, nil, nil);
t31 := Node.Create('t31', 40, t41, nil);
t32 := Node.Create('t32', 20, t42, nil);
t33 := Node.Create('t33', 30, t43, nil);
t34 := Node.Create('t34', 40, nil, nil);
t35 := Node.Create('t35', 10, t44, nil);
t36 := Node.Create('t36', 30, t45, t46);
t21 := Node.Create('t21', 30, t31, nil);
t22 := Node.Create('t22', 20, t32, t33);
t23 := Node.Create('t23', 30, t34, t35);
t24 := Node.Create('t24', 20, t36, nil);
t11 := Node.Create('t11', 10, t21, t22);
t12 := Node.Create('t12', 20, t23, t24);
t01 := Node.Create('t01', 0, t11, t12);
s = Search.Create();
s.exec(t01, 0, list);
for _node in list do begin
Writeln(Format('%s(%d)', [_node.getName(), _node.getNumber()]));
end;
list.Free;
s.Free;
t01.Free;
end.
|
Mementoパターンを使用した例 Search.pas unit UnitSearch;
interface
uses
System.Generics.Collections,
UnitNode,
UnitMemento;
type
Search = class
public
function exec(_node:Node):TList<Node>;
end;
implementation
function Search.exec(_node:Node):TList<Node>;
var left, right:Node;
var total:integer;
var mementoStack:TStack<Memento>;
var route:TList<Node>;
var _memento:Memento;
begin
mementoStack := TStack<Memento>.Create();
route := TList<Node>.Create();
total := 0;
while(true) do begin
total := total + _node.getNumber();
route.Add(_node);
if total >= 100 then
break;
left := _node.left;
right := _node.right;
if (left <> nil) and (right <> nil) then begin
_memento := Memento.Create(_node, total, route);
mementoStack.Push(_memento);
_node := left;
end
else if (left = nil) and (right = nil) then begin
if mementoStack.Count = 0 then begin
Result := nil;
exit;
end;
_memento := mementoStack.Pop();
_node := _memento.getNode().right;
route := _memento.getRoute();
total := _memento.getTotal();
end
else if left <> nil then begin
_node := _node.left;
end
else begin
_node := _node.right;
end;
end;
Result := route;
end;
end.
Memento.pas unit UnitMemento;
interface
uses
System.Generics.Collections,
UnitNode;
type
Memento = class
private
var _node:Node;
var total:integer;
var route:TList<Node>;
public
constructor Create(_node:Node; total:integer; route:TList<Node>);
function getNode():Node;
function getTotal:integer;
function getRoute():TList<Node>;
end;
implementation
constructor Memento.Create(_node:Node; total:integer; route:TList<Node>);
var nd:Node;
begin
self._node := _node;
self.total := total;
self.route := TList<Node>.Create();
for nd in route do
self.route.Add(nd);
end;
function Memento.getNode():Node;
begin
Result := _node;
end;
function Memento.getTotal:integer;
begin
Result := total;
end;
function Memento.getRoute():TList<Node>;
begin
Result := route;
end;
end.
Main.dpr program MementoNon;
uses
System.SysUtils,
System.Generics.Collections,
UnitNode,
UnitSearch;
var t01:Node;
var t11, t12:Node;
var t21, t22, t23, t24:Node;
var t31, t32, t33, t34, t35, t36:Node;
var t41, t42, t43, t44, t45, t46:Node;
var t51, t52, t53, t54:Node;
var s:Search;
var route:TList<Node>;
var _node:Node;
begin
t51 := Node.Create('t51', 10, nil, nil);
t52 := Node.Create('t52', 20, nil, nil);
t53 := Node.Create('t53', 10, nil, nil);
t54 := Node.Create('t54', 20, nil, nil);
t41 := Node.Create('t41', 10, nil, nil);
t42 := Node.Create('t42', 20, t51, t52);
t43 := Node.Create('t43', 30, nil, nil);
t44 := Node.Create('t44', 20, t53, t54);
t45 := Node.Create('t45', 10, nil, nil);
t46 := Node.Create('t46', 20, nil, nil);
t31 := Node.Create('t31', 40, t41, nil);
t32 := Node.Create('t32', 20, t42, nil);
t33 := Node.Create('t33', 30, t43, nil);
t34 := Node.Create('t34', 40, nil, nil);
t35 := Node.Create('t35', 10, t44, nil);
t36 := Node.Create('t36', 30, t45, t46);
t21 := Node.Create('t21', 30, t31, nil);
t22 := Node.Create('t22', 20, t32, t33);
t23 := Node.Create('t23', 30, t34, t35);
t24 := Node.Create('t24', 20, t36, nil);
t11 := Node.Create('t11', 10, t21, t22);
t12 := Node.Create('t12', 20, t23, t24);
t01 := Node.Create('t01', 0, t11, t12);
s = Search.Create();
route := s.exec(t01);
if route <> nil then begin
for _node in route do begin
Writeln(Format('%s(%d)', [_node.getName(), _node.getNumber()]));
end;
end;
route.Free;
s.Free;
t01.Free;
end.
|
|
この例では再起呼び出しで行っていますが、例えば t41 まで来て 100 にならなかった場合、t31、t21 というように順に戻りながら、他のルートを探すことになります。 しかし、t01 から t41 に来る間に、分岐は t11 のところにしかないと分かったのなら、一気に t11 に戻った方が効率がいいはずです。 |
Momento パターンでは、分岐に来た（left も right も null でない）ときに、その時点の情報の Memonto インスタンスを作り、スタックに保存しています。 Memento memento(node, total, route); mementostack.push(memento); そして、行き止まりになった（left も right も null）ときには、スタックから Memonto インスタンスを取り出しています。これは、直前の分岐地点の情報です。つまり、それまでのルートと合計、そして、これから行く右側ルートです。 memento = (Memento)mementoStack.pop(); node = memento.getNode().right; // 右側ルート route = memento.getRoute(); // それまでのルート total = memento.getTotal(); // それまでの合計 |