實現(xiàn)一個函數(shù)式Queue泛型類
函數(shù)式隊列是一種具有以下三種操作方式的數(shù)據(jù)結構：
head 返回隊列的第一個元素
tail 返回除第一個元素之外的隊列
append 返回尾部添加了指定元素的新隊列
如果Queue是一個不變隊列，也就是函數(shù)式隊列座硕。在添加元素的時候不會改變其內(nèi)容咐柜，而是返回包含了這個元素的新隊列。
如果Queue是可變類型的，那么append操作將改變隊列的內(nèi)容讹堤。
純函數(shù)式隊列和List具有相似性祭刚，都支持head和tail操作〈园梗可以通過List來實現(xiàn)函數(shù)式隊列赡磅。
關于時間開銷問題，append操作應該在常量時間內(nèi)完成宝与。
為了做到這一點焚廊，我們使用兩個List，分別稱為leading和trailing习劫，來表達隊列咆瘟。leading包含前段元素，而trailing包含了反向排列的后段元素诽里。隊列在任何時刻的所有內(nèi)容都可以表示為leading ::: trailing.reverse搞疗。
- 想要添加新元素，只要使用::操作符將其添加到trailing，使得append是常量時間匿乃。
- 當原始的空隊列通過后繼的append操作構建起來時桩皿，trailing將不斷增加，而leading始終是空白的幢炸。于是泄隔，在對空的leading第一次執(zhí)行head或者tail操作之前，trailing應該被反轉(zhuǎn)并復制給leading宛徊，這個操作稱為mirror佛嬉。
- mirror操作花費的時間大概與隊列的元素數(shù)量成正比，但僅在leading為空時闸天。如果leading非空暖呕，它將直接返回。
- 因為head和tail調(diào)用了mirror苞氮，所以他們的復雜度與隊列長度呈線性關系湾揽。實際上，假設leading為空時笼吟，mirror才翻轉(zhuǎn)并復制库物，那么n個元素需要進行n次tail之后才進行復制。這n次tail操作平均分擔了mirror操作的時間復雜度贷帮，也相當于常量時間了戚揭。
代碼如下：
class Queue[T] (private val leading: List[T],
private val trailing: List[T])
{
private def mirror =
if (leading.isEmpty)
new Queue(trailing.reverse, Nil)
else
this
def head = mirror.leading.head
def tail = {
val q = mirror
new Queue(q.leading.tail, q.trailing)
}
def append(element: T) =
new Queue(leading, element :: trailing)
}
信息隱藏
私有構造器和工廠方法
上面實現(xiàn)的Queue以暴露本不該暴露的實現(xiàn)細節(jié)為代價，全局可訪問Queue構造器撵枢，帶有兩個列表參數(shù)特纤，不能作為直觀表達隊列的形式落萎。
私有構造器和私有成員是隱藏類的初始化代碼和表達代碼的一種方式豌鸡。
可以通過把private修飾符添加在類參數(shù)列表的前面把主構造器隱藏起來屹培。
class Queue[T] private (private val leading: List[T],
private val trailing: List[T])
構造器是私有的，它只能被類本身及伴生對象訪問沟绪。我們可以添加可以用初始元素序列創(chuàng)建隊列的工廠方法刮便。定義與類同名的Queue對象及apply方法：
object Queue {
def apply[T](xs: T*) = new Queue[T](xs.toList, Nil)
}
私有類
使用私有類的方法可以更徹底的把類本身隱藏掉空猜，僅提供能夠暴露類公共接口的特質(zhì)绽慈。
trait Queue[T] {
def head: T
def tail: Queue[T]
def append(x: T): Queue[T]
}
object Queue {
def apply[T](xs: T*): Queue[T] =
new QueueImpl[T](xs.toList, Nil)
private class QueueImpl[T](
private val leading: List[T],
private val trailing: List[T]
) extends Queue[T]
{
def mirror =
if (leading.isEmpty)
new QueueImpl(trailing.reverse, Nil)
else
this
def head: T = mirror.leading.head
def tail: QueueImpl[T] = {
val q = mirror
new QueueImpl(q.leading.tail, q.trailing)
}
def append(x: T) =
new QueueImpl(leading, x:: trailing)
}
}
代碼中定義了特質(zhì)Queue，聲明了方法head辈毯、tail和append坝疼。
這三個方法都實現(xiàn)在子類QueueImpl中，而它本身是對象Queue的內(nèi)部類谆沃。這個方案暴露給客戶的信息與前面相同钝凶，但使用了不同的技術。代之以逐個隱藏構造器與方法唁影，這個版本隱藏全部實現(xiàn)類耕陷。
實現(xiàn)協(xié)變的泛型類
使用Queue[+T]方式對Queue實現(xiàn)協(xié)變掂名，然而在append的實現(xiàn)中，T參數(shù)出現(xiàn)在了逆變的位置哟沫。
可以通過把append變?yōu)槎鄳B(tài)以使其泛型化（即提供給append方法類型參數(shù)）并使用它的類型參數(shù)的下界饺蔑。
class Queue[+T] private (
private[this] var leading: List[T],
private[this] var trailing: List[T]
) {
def append[U >: T](x: U) =
new Queue[U](leading, x::trailing)
}
通過U >: T定義了T為U的下界。結果U必須是T的超類型嗜诀。
假設存在類Fruit和兩個子類猾警，Apple和Orange。通過Queue類的定義隆敢，可以吧Orange對象加入到Queue[Apple]发皿，結果返回Queue[Fruit]類型。
對象私有數(shù)據(jù)
到目前為止拂蝎，Queue類仍有一些問題穴墅。如果head被一遍遍的調(diào)用很多次，而leading列表為空匣屡，那么mirror操作可能會重復的把trailing復制到leading列表封救。
可以將leading和trailing指定為可以重新復制的變量，而mirror從trailing反向復制到leading的操作是在當前隊列上的副作用捣作，而不再返回新的隊列誉结。
通過將leading和trailing用private[this]修飾，聲明為對象私有變量券躁，使得這種副作用純粹是Queue操作的內(nèi)部實現(xiàn)惩坑，從而使它對于Queue的客戶不可見。
代碼如下：
class Queue[+T] private (
private[this] var leading: List[T],
private[this] var trailing: List[T]
) {
private def mirror() =
if(leading.isEmpty) {
while(!trailing.isEmpty) {
leading = trailing.head :: leading
trailing = trailing.tail
}
}
def head: T = {
mirror()
leading.head
}
def tail: Queue[T] = {
mirror()
new Queue(leading.tail, trailing)
}
def append[U >: T](x: U) =
new Queue[U](leading, x::trailing)
}
說明：
被定義在同一個對象內(nèi)訪問對象私有變量不會引起與變化型有關的問題也拜。Scala的變化型檢查規(guī)則包含了關于對象私有定義的特例以舒。當檢查到帶有+/-號的類型參數(shù)只出現(xiàn)在具有相同變化型分類的位置上時，這種定義將被忽略慢哈。
轉(zhuǎn)載請注明作者Jason Ding及其出處
jasonding.top
Github博客主頁(http://blog.jasonding.top/)
CSDN博客(http://blog.csdn.net/jasonding1354)
簡書主頁(http://www.reibang.com/users/2bd9b48f6ea8/latest_articles)
Google搜索jasonding1354進入我的博客主頁
