用桥梁模式实现螺旋矩阵算法

前两天写了一篇文章，分析了“内螺旋矩阵算法”的实现，讨论到了面向对象编程的可扩展性，于是今天用桥梁模式将代码做了些改造，具体如下：

package com.algo;

class Position {
	private int x;
	private int y;

	public Position(int x, int y) {
		this.x = x;
		this.y = y;
	}

	public int getX() {
		return x;
	}

	public void setX(int x) {
		this.x = x;
	}

	public int getY() {
		return y;
	}

	public void setY(int y) {
		this.y = y;
	}
}

/**
 * 螺旋走向接口
 */
abstract class Direction {
	protected StartPos startPos;
	protected Position pos;// 当期的位置
	protected Position periodPos;// 一个周期的开始位置
	protected int max;// 行列的最大值
	protected int min;// 行列的最小值
	protected int len;// 方阵的阶数

	private void init() {
		if (startPos == null || len <= 0)
			return;
		Position tempPos = startPos.getPos(len);
		pos = new Position(tempPos.getX(), tempPos.getY());
		periodPos = new Position(tempPos.getX(), tempPos.getY());
		max = len - 1;
		min = 0;
	}

	public void setStartPos(StartPos startPos) {// 设置开始位置并重新初始化
		this.startPos = startPos;
		init();
	}

	public void setLen(int len) {// 设置长度并重新初始化
		this.len = len;
		init();
	}

	public int getLen() {
		return len;
	}

	public Position getPos() {
		int currRow = pos.getX();
		int currCol = pos.getY();
		Position currPos = new Position(currRow, currCol);
		genNextPos();
		return currPos;
	}

	protected abstract void genNextPos();
}

/**
 * 顺时针螺旋实现
 */
class ClockwiseDir extends Direction {
	protected void genNextPos() {
		int row = pos.getX();
		int col = pos.getY();
		if (row == min && col < max) {
			col++;
		} else if (row < max && col == max) {
			row++;
		} else if (row == max && col > min) {
			col--;
		} else if (row > min && col == min) {
			row--;
		} else{
			return; //匹配不到任何条件，则直接跳出（指螺旋的最后一个位置）
		}
		if (row == periodPos.getX() && col == periodPos.getY()) {
			min++;
			max--;
			genNextPos();
			periodPos = new Position(pos.getX(), pos.getY());
		} else {
			pos.setX(row);
			pos.setY(col);
		}
	}
}

/**
 * 逆时针螺旋实现
 */
class AntiClockwiseDir extends Direction {
	protected void genNextPos() {
		int row = pos.getX();
		int col = pos.getY();
		if (row == min && col > min) {
			col--;
		} else if (row < max && col == min) {
			row++;
		} else if (row == max && col < max) {
			col++;
		} else if (row > min && col == max) {
			row--;
		} else{
			return; //匹配不到任何条件，则直接跳出（指螺旋的最后一个位置）
		}
		if (row == periodPos.getX() && col == periodPos.getY()) {
			min++;
			max--;
			genNextPos();
			periodPos = new Position(pos.getX(), pos.getY());
		} else {
			pos.setX(row);
			pos.setY(col);
		}
	}
}

/**
 * 螺旋起始位置接口
 */
interface StartPos {
	public Position getPos(int len);
}

/**
 * 起始位置为左上角的实现
 */
class TopLeft implements StartPos {
	public Position getPos(int len) {
		return new Position(0, 0);
	}
}

/**
 * 起始位置为右上角的实现
 */
class TopRight implements StartPos {
	public Position getPos(int len) {
		return new Position(0, len - 1);
	}
}

/**
 * 起始位置为左下角的实现
 */
class BottomLeft implements StartPos {
	public Position getPos(int len) {
		return new Position(len - 1, 0);
	}
}

/**
 * 起始位置为右下角的实现
 */
class BottomRight implements StartPos {
	public Position getPos(int len) {
		return new Position(len - 1, len - 1);
	}
}

public class HelixAlgo {
	public void print(Direction dir,int initVal,int step) {
		int len = dir.getLen();
		if (len <= 0) {
			System.out.println("请输入大于0的整数！");
			return;
		}
		int[][] helix = calculate(dir, len,initVal,step);
		for (int i = 0; i < helix.length; i++) {
			for (int j = 0; j < helix[i].length; j++) {
				System.out.print(helix[i][j] + "\t");
			}
			System.out.println("");
		}
	}

	private int[][] calculate(Direction dir, int len,int val,int step) {
		int[][] helix = new int[len][len];
		for (int i = 0; i < len * len; i++) {
			Position pos = dir.getPos();
			int row = pos.getX();
			int col = pos.getY();
			helix[row][col] = val;
			val+=step;
		}
		return helix;
	}

	public static void main(String[] args) {
		HelixAlgo algo = new HelixAlgo();
		int len = 5;
		Direction dir_clockwise = new ClockwiseDir();
		dir_clockwise.setLen(len); //用set方法动态地插入长度

		Direction dir_antiClockwise = new AntiClockwiseDir();
		dir_antiClockwise.setLen(len);

		System.out.println("\n左上角开始顺时针内旋(长度" + len + ")：");
		dir_clockwise.setStartPos(new TopLeft()); //用set方法动态地插入开始位置
		algo.print(dir_clockwise,1,1);
		System.out.println("\n右上角开始顺时针内旋(长度" + len + ")：");
		dir_clockwise.setStartPos(new TopRight());
		algo.print(dir_clockwise,1,1);
		System.out.println("\n右下角开始顺时针内旋(长度" + len + ")：");
		dir_clockwise.setStartPos(new BottomRight());
		algo.print(dir_clockwise,1,1);
		System.out.println("\n左下角开始顺时针内旋(长度" + len + ")：");
		dir_clockwise.setStartPos(new BottomLeft());
		algo.print(dir_clockwise,1,1);
		
		System.out.println("\n左上角开始逆时针内旋(长度" + len + ")：");
		dir_antiClockwise.setStartPos(new TopLeft());
		algo.print(dir_antiClockwise,1,1);
		System.out.println("\n右上角开始逆时针内旋(长度" + len + ")：");
		dir_antiClockwise.setStartPos(new TopRight());
		algo.print(dir_antiClockwise,1,1);
		System.out.println("\n右下角开始逆时针内旋(长度" + len + ")：");
		dir_antiClockwise.setStartPos(new BottomRight());
		algo.print(dir_antiClockwise,1,1);
		System.out.println("\n左下角开始逆时针内旋(长度" + len + ")：");
		dir_antiClockwise.setStartPos(new BottomLeft());
		algo.print(dir_antiClockwise,1,1);
		
		System.out.println("\n中心点开始顺时针外旋(长度" + len + ")：");
		dir_antiClockwise.setStartPos(new TopLeft());
		algo.print(dir_antiClockwise,len*len,-1);
		System.out.println("\n中心点开始逆时针外旋(长度" + len + ")：");
		dir_clockwise.setStartPos(new TopLeft());
		algo.print(dir_clockwise,len*len,-1);
	}
}

 

螺旋矩阵的解题思路就不多说了，不了解的可以看下我前面的文章“内螺旋矩阵算法分析”,这里主要说下为什么要用桥梁模式：

首先看看螺旋矩阵有哪些变化点：矩阵阶数（即边长），初始位置，和螺旋方向（顺时针，逆时针）

初始位置前面的文章在回复中已经提及，合法的初始位置只有四个既矩阵的四个角，否则会出现死胡同（可参考前面文章在10楼的回复）。

考虑到弹性，这三个变化点都应该是可以独立变化的，其中矩阵阶数只是个整数，它的变化比较方便，而另外两个可以用不同的接口封装，即上面代码的"StartPos"接口和"Direction"抽象类，这样两个变化点便可以独立的变化，因此想到了使用桥梁模式，把这两个变化点的耦合彻底移到对象层面，于是便有了mian函数中“dir_clockwise ”和“dir_antiClockwise”两个对象封装的多种输出。

其他就不多说了，代码可以运行，直接拷贝到机器上跑一下应该就明白了，有什么不足或者疑问欢迎大家一起讨论。

评论

4 楼 shuishou119800 2009-12-20  

re:3 楼 ilove2009

不可否认Direction接口下的确存在着“Bad Smell”（即genNextPos()方法中的分支结构），可如果将这些分支用多态的方式实现，则将产生很多的细粒度对象。无论什么样的设计思想，其目的都是为了在高效完成任务的基础上提高代码的弹性。一般来说，封装的粒度越小，代码的弹性越高，但生产效率也将随之下降。笔者认为系统设计的关键应该是在效率与弹性之间寻找一个平衡点，既不偏向于高效的过程化设计，也不要太偏向于纯粹的面向对象设计。而所谓的平衡点就是具体业务变化点。
此处以顺时针循环为例，ClockwiseDir类完全可以分解成（ClockwiseDir_Top,ClockwiseDir_Right,ClockwiseDir_Bottom,ClockwiseDir_Left），从而去除掉genNextPos()方法中“Bad Smell”。但这样的话，每增加一种新的流转类型（比如S形流转）就必须同时创建四个类。分析下这个业务的变化点，流转的类型可以一直扩展下去（平躺式S形流转，古文排版式流转。。。），矩阵的长度可以一直扩展下去（6阶，7阶，8阶。。。），这两者是独立的变化点，因此需要分离。可就流转类型而言，无论是那种流转都有着他们自己独有的规则（如顺时针螺旋的顶边对应的下一个方向一定是右边），换句话说，这些规则的生命周期局限于他们所属的流转类型，没有了ClockwiseDir的流转类型，ClockwiseDir_Top,ClockwiseDir_Right,ClockwiseDir_Bottom,ClockwiseDir_Left这些细粒度规则对象也就失去了他们存在的意义。因此笔者认为此处为了提高面向对象的纯度而将流转类型对象细分，是没有必要的，毕竟变化的点是在流转类型上。
再以人为例，每个特定的人身上都存在着很多对象（眼、耳、口、鼻。。。），对于一个以器官为研究对象的业务系统来说，将人分解成各种器官对象是必须的；可对于一个以人为研究对象的业务系统，将人分解成各种器官对象不仅意义不大且反倒会增加系统的复杂度。
设计的目的是为了解决问题，而不能为了设计而设计。

3 楼 ilove2009 2009-12-18  

面向对象的代码很少有if  else这样的语句，一般都是用多态来替代。感觉就是过程化的代码套上对象的外壳。

面向对象应该是用我们普通人的思维描述系统，数学化的方法描述不是。

比如你的代码是不是很自然地表达出生活中的场景，比如：
Snake sn = new Snake(size,new Right(size),new Point(1,1,"1"));  
这句在现实中训蛇员指定范围和方向、起点，让蛇开始游走，正常啊。而且这些属性都是随时可以变的。

再看Point类，有x、y、val属性，很自然，一个位置用xy坐标表示，这个点为啥要多个属性val呢，因为蛇走到那里点上可能拉陀屎也可能吐口水什么的，这正常啊。

再看，给定的范围、方向上，只有方向具体的子类才能知道下个点是什么、是否出界，责任很清晰啊。

只是next方法不是很清晰，因为下个方向是蛇和当前方向共同决定的。

2 楼 shuishou119800 2009-12-18  

re 1 楼 ilove2009

  能说的具体些吗？你觉得哪里需要改进？

1 楼 ilove2009 2009-12-18  

感觉面向对象不彻底，不自然。