A ring is much like a sequence: It holds N values associated with the integer indices zero through N-1 when N is positive. An empty ring holds no values. Values are pointers. Like the values in a sequence, values in a ring may be accessed by indexing.Unlike a sequence, however, values can be added to a ring anywhere, and any value in a ring can be removed. In addition, the values can be renumbered: ” rotating” a ring left decrements the index of each value by one modulo the length. —-《C interfaces and implementations》
Ring 和常用的桟、队列一样,是一种抽象数据类型,中文可以译成环。和桟和队列不同的是,一般的教课书上没有它的介绍,也很少有人谈论到它。 实际上环很常见,像在出名的淘宝网,首页中间切换图片的幻灯片,其实就是一个环。当图片切换到最后一张又会从头开始切换,这样一直循环。 环的特征就是这样,首尾相接,甚至可以没有首和尾。
环看上去很直观,也很简单,一旦把和环有相似的特征的对象抽象成环,那么就会使代码更加清晰简洁,和环一样直观了。
简单的实现
文章中的例子都是基于下面 JavaScript 的简单实现,注意到它只提供了两个接口:
var Ring = (function() {
function Ring(list) {
this._list = [].slice.call(list, 0);
this._length = this._list.length;
this._curr = -1;
};
Ring.prototype = {
rollTo: function(idx) {
this._curr = idx % this._length;
if (this._curr < 0) this._curr += this._length;
return this._list[this._curr];
},
next: function() {
return this.rollTo(this._curr + 1);
}
};
return function(list) {
return new Ring(list);
};
}());
格子
有一个非常有趣的题目,大概是这样描述的:
用程序实现九个格子和一个按钮。当点击一次按钮,第一个格子就显示 1;点击第二次,第二个格子就显示 2 … 点击第十次,因为一共只有九个格子,所以就回到第一个格子,第一个格子就显示 10;这样一直循环。
很显然,那九个格子就构成了一个环。第一个格子和第九个格子是相连的,每点击一次按钮,就在下一个相邻的格子里显示总共点击的次数。 不过,一年前我并没有这样的概念,从这个 gist 可以看出那时是通过模运算,和在格子上标识出id找到下一个格子的。
使用环重新实现之后更容易看懂了,: (打开 demo )
var numClicked = 0
, cells = Ring(
document.getElementsByTagName('td')
);
document.getElementById('button').onclick = function() {
cells.next().innerHTML = (++numClicked);
}
帧动画
在游戏中,通常会使用连续变换背景图的偏移位置,来模拟一个人物的奔跑动画。奔跑动画分解成许多静态的动作,每一个动作即一帧。整个背景图也是相邻的,实现的时候把每一帧的偏移坐标放在一个数组里面,从数组依次取出坐标值,然后改变背景偏移位置。当取到了数组最后一个值的时候,又从头开始取值。
同样很明显,背景图的每一个动作构成一个环。在有很多这种动画的时候,抽象成环能避免重复,使得代码可读性更好。(打开 demo )
var role = (function() {
var elem = document.getElementById('role')
, offsets = Ring(
range(14).map(function(i) {
return (-106) * i + 'px 0';
})
);
return {
run: function() {
elem.style['backgroundPosition'] = offsets.next();
}
};
}());
幻灯片切换
UCDChina书友会网站上有个切换图片的幻灯片,仔细观察会发现往回切换图片的时候有一点点问题。 但是它的实方式很复杂(源代码链接在这里),想去修复那个问题却很难把其中的逻辑理清楚,这也是因为缺乏很好的抽象。
这种图片切换和淘宝首页的图片切换是一样的,也可以使用环来进行抽象。(打开 demo )
var slider = (function() {
var slideRing = Ring(
range(links.length).map(function(i) {
return {
link: links[i], offset: (-1)*w*i + 'px'
};
})
);
function switchSlide(slide) {
var curr = document.getElementById('on');
curr && (curr.id = '');
slide.link.id = 'on';
//using css3 animation
slides.style.left = slide.offset;
};
return {
next: function() {
switchSlide( slideRing.next() );
return this;
},
rollTo: function(i) {
switchSlide( slideRing.rollTo(i) );
return this;
}
};
}());
可以和原来的程序做一下比较,使用环来实现确实简单多了 :D
结论
我用 JavaScript 实现的 Ring 还不完整,仅仅是为了表达一个概念,根据不同的情景会进行调整。希望通过这几个例子能说明好的抽象给程序带来的好处。