{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 集合库继承层次\n",
    "- 集合继承层次从TraversableOnce特质开始。这个特质代表至少能遍历一次的集合。这个特质对Traversable和Iterator进行了抽象。\n",
    "- Iterator代表了一个数据流，前进到下一个数据项意味着“消费”了当前数据项（也就是只能遍历一次）。\n",
    "- Traversable代表提供了遍历全部数据的机制的集合，而且能够反复地遍历。\n",
    "- 最后继承层次分裂为三个分支：sequence、map和set。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](./images/collections_hierarchy.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Gen\\*特质\n",
    "集合库中有一种generic变种，如GenTraversableOnce、GenIterator和GenSeq。该特质不确保线性执行或并行执行，在并行集合的遍历顺序是不确保的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1 Traversable\n",
    "Traversable特质定义了一个foreach方法。foreach方法是一个内部迭代器，其接受一个函数作为参数，对集合的每个元素应用该函数。\n",
    "\n",
    "Traversable特质没有提供任何在foreach里停止遍历的方法。为了使某些操作更高效，库使用预初始化的异常来提前跳出迭代。\n",
    "\n",
    "> 内部迭代&外部迭代\n",
    "- 内部迭代器是由集合或迭代器自己负责遍历集合；外部迭代器是由外部迭代器确定何时和如何迭代\n",
    "- Traversable特质提供了foreach方法，客户代码可以传入函数给它用于遍历处理；Iterable特质提供了iterator方法，客户代码可以获取迭代器，自行遍历"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[32mimport \u001b[36mjava.io.FileReader\u001b[0m\n",
       "\u001b[32mimport \u001b[36mjava.io.BufferedReader\u001b[0m\n",
       "\u001b[32mimport \u001b[36mjava.io.File\u001b[0m\n",
       "defined \u001b[32mclass \u001b[36mFileLineTraversable\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import java.io.FileReader\n",
    "import java.io.BufferedReader\n",
    "import java.io.File\n",
    "\n",
    "class FileLineTraversable(file: File) extends Traversable[String] {\n",
    "    override def foreach[U](f: String => U): Unit = {\n",
    "        println(\"Opening file\")\n",
    "        val input = new BufferedReader(new FileReader(file))\n",
    "        try {\n",
    "            var line = input.readLine\n",
    "            while (line != null) {\n",
    "                f(line)\n",
    "                line = input.readLine\n",
    "            }\n",
    "            println(\"Done iterating file\")\n",
    "        } finally {\n",
    "            println(\"Closing file\")\n",
    "            input.close()\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面定义了一个Traversable，它打开一个文件，遍历文件的每一行。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Opening file\n",
      "Done iterating file\n",
      "Closing file\n",
      "Opening file\n",
      "Done iterating file\n",
      "Closing file\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mx\u001b[0m: \u001b[32mFileLineTraversable\u001b[0m = \u001b[33mcmd0\u001b[0m(\n",
       "  \u001b[32m\"Line 1\"\u001b[0m,\n",
       "  \u001b[32m\"Line 2\"\u001b[0m,\n",
       "  \u001b[32m\"Line 3\"\u001b[0m,\n",
       "  \u001b[32m\"Line 4\"\u001b[0m,\n",
       "  \u001b[32m\"Line 5\"\u001b[0m,\n",
       "  \u001b[32m\"Line 6\"\u001b[0m\n",
       ")"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val x = new FileLineTraversable(new File(\"test.txt\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Opening file\n",
      "Done iterating file\n",
      "Closing file\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mres2\u001b[0m: \u001b[32mTraversable\u001b[0m[\u001b[32mString\u001b[0m] = \u001b[33mList\u001b[0m(\n",
       "  \u001b[32m\"Line\"\u001b[0m,\n",
       "  \u001b[32m\"1\"\u001b[0m,\n",
       "  \u001b[32m\"Line\"\u001b[0m,\n",
       "  \u001b[32m\"2\"\u001b[0m,\n",
       "  \u001b[32m\"Line\"\u001b[0m,\n",
       "  \u001b[32m\"3\"\u001b[0m,\n",
       "  \u001b[32m\"Line\"\u001b[0m,\n",
       "  \u001b[32m\"4\"\u001b[0m,\n",
       "  \u001b[32m\"Line\"\u001b[0m,\n",
       "  \u001b[32m\"5\"\u001b[0m,\n",
       "  \u001b[32m\"Line\"\u001b[0m,\n",
       "  \u001b[32m\"6\"\u001b[0m\n",
       ")"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "// 遍历文件，并且遍历每一行，把行拆分成词，最后构造一个词的列表，结果是一个Traversable[String]\n",
    "for {\n",
    "    line <- x\n",
    "    word <- line.split(\"\\\\s+\")\n",
    "} yield word"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Opening file\n",
      "Closing file\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mres3\u001b[0m: \u001b[32mTraversable\u001b[0m[\u001b[32mString\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m\"Line\"\u001b[0m, \u001b[32m\"1\"\u001b[0m, \u001b[32m\"Line\"\u001b[0m, \u001b[32m\"2\"\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "for {\n",
    "    line <- x.take(2)\n",
    "    word <- line.split(\"\\\\s+\")\n",
    "} yield word"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "FileLineTraversable调用了take方法抽取集合的前n个元素，这里“Done iterating file”没有打印。\n",
    "\n",
    "这是因为**Traversable类有一个在必要时高效停止foreach的手段，就是抛出scala.util.control.ControlThrowable**。这是一种预分配的异常，JVM能够高效地抛出和捕获它。这样做法的缺点是take方法实际上会多取一个元素才抛出异常终止迭代。\n",
    "\n",
    "由于foreach方法不支持高效的随机访问，所以其对很多算法都是次优的选择，我们可以通过Iterable的外部迭代器来解决。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 Iterable\n",
    "Iterable特质提供了iterator方法，iterator方法返回一个能用来遍历集合元素的外部迭代器。这个类允许只是用集合部分元素的方法比Traversable更早提前停止迭代，从而在性能上比Traversable稍有提高。**Iterable特质应该用在明确需要外部迭代器，但不需要随机访问的应用场景。**\n",
    "\n",
    "迭代器支持hasNext和next方法。\n",
    "\n",
    "Iterable特质的主要优点之一是有能力高效地合作迭代两个集合。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mnames\u001b[0m: \u001b[32mIterable\u001b[0m[\u001b[32mString\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m\"Josh\"\u001b[0m, \u001b[32m\"Jim\"\u001b[0m)\n",
       "\u001b[36maddress\u001b[0m: \u001b[32mIterable\u001b[0m[\u001b[32mString\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m\"123 Anyroad\"\u001b[0m, \u001b[32m\"125 Anyroad\"\u001b[0m)\n",
       "\u001b[36mn\u001b[0m: \u001b[32mIterator\u001b[0m[\u001b[32mString\u001b[0m] = non-empty iterator\n",
       "\u001b[36ma\u001b[0m: \u001b[32mIterator\u001b[0m[\u001b[32mString\u001b[0m] = non-empty iterator"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val names = Iterable(\"Josh\", \"Jim\")\n",
    "val address = Iterable(\"123 Anyroad\", \"125 Anyroad\")\n",
    "\n",
    "val n = names.iterator\n",
    "val a = address.iterator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Josh lives at 123 Anyroad\n",
      "Jim lives at 125 Anyroad\n"
     ]
    },
    {
     "data": {
      "text/plain": []
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "while(n.hasNext && a.hasNext) {\n",
    "    println(n.next + \" lives at \" + a.next)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Scala提供了zip方法，用来把两个集合压缩成一个pair的集合"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Josh lives at 123 Anyroad\n",
      "Jim lives at 125 Anyroad\n"
     ]
    },
    {
     "data": {
      "text/plain": []
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "names.iterator zip address.iterator map {\n",
    "    case (n, a) => n+ \" lives at \" + a\n",
    "} foreach println"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**当在可变集合上使用外部迭代器时候，可能迭代器不知道集合发生了变化**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mx\u001b[0m: \u001b[32mcollection\u001b[0m.\u001b[32mmutable\u001b[0m.\u001b[32mArrayBuffer\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mArrayBuffer\u001b[0m(\u001b[32m1\u001b[0m, \u001b[32m2\u001b[0m, \u001b[32m3\u001b[0m)\n",
       "\u001b[36mi\u001b[0m: \u001b[32mIterator\u001b[0m[\u001b[32mInt\u001b[0m] = non-empty iterator"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val x = collection.mutable.ArrayBuffer(1, 2, 3)\n",
    "val i = x.iterator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres8_1\u001b[0m: \u001b[32mBoolean\u001b[0m = true"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "x.remove(0, 3)\n",
    "i.hasNext"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "java.lang.IndexOutOfBoundsException: 0",
      "\tscala.collection.mutable.ResizableArray$class.apply(ResizableArray.scala:43)",
      "\tscala.collection.mutable.ArrayBuffer.apply(ArrayBuffer.scala:48)",
      "\tscala.collection.IndexedSeqLike$Elements.next(IndexedSeqLike.scala:65)",
      "\tcmd9$$user$$anonfun$1.apply$mcI$sp(Main.scala:81)"
     ]
    }
   ],
   "source": [
    "i.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面remove移除了集合中的全部元素，由于迭代器是外部的，它不知道背后集合已经变化，hasNext方法返回了true，调用next方法时却抛出了异常。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3 Seq\n",
    "Seq特质是用过length和apply方法定义的。apply方法用来根据序号进行索引操作，length返回集合的大小。Seq特质不对索引或length的性能做任何保证。\n",
    "\n",
    "**如果元素插入集合的顺序是很重要的，而且允许重复元素，那么应该使用Seq。**\n",
    "\n",
    "Seq经常被用在抽象方法里，因为算法经常以其两个子类之一作为目标数据结果：LinearSeq和IndexedSeq。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mx\u001b[0m: \u001b[32mSeq\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\n",
       "  \u001b[32m2\u001b[0m,\n",
       "  \u001b[32m1\u001b[0m,\n",
       "  \u001b[32m30\u001b[0m,\n",
       "  \u001b[32m-2\u001b[0m,\n",
       "  \u001b[32m20\u001b[0m,\n",
       "  \u001b[32m1\u001b[0m,\n",
       "  \u001b[32m2\u001b[0m,\n",
       "  \u001b[32m0\u001b[0m\n",
       ")\n",
       "\u001b[36mres10_1\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m3\u001b[0m, \u001b[32m31\u001b[0m, \u001b[32m28\u001b[0m, \u001b[32m18\u001b[0m, \u001b[32m21\u001b[0m, \u001b[32m3\u001b[0m, \u001b[32m2\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "// 该示例是通过滑动窗口计算元素和\n",
    "val x = Seq(2, 1, 30, -2, 20, 1, 2, 0)\n",
    "\n",
    "x.tails map(_.take(2)) filter(_.length > 1) map (_.sum) toList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "滑动窗口是通过使用tails方法创建的，tails方法返回一个集合的tail迭代器。也就是说，tails产生的迭代器组的每个迭代器都比前一个迭代器少一个元素。此外，还可以使用Scala提供的sliding方法来代替tails："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres12\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m3\u001b[0m, \u001b[32m31\u001b[0m, \u001b[32m28\u001b[0m, \u001b[32m18\u001b[0m, \u001b[32m21\u001b[0m, \u001b[32m3\u001b[0m, \u001b[32m2\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "x.sliding(2) map (_.sum) toList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 LinearSeq\n",
    "LinearSeq特质代表能够分割为头元素+尾集合的集合。该特质是通过三个“假定高效”的抽象方法来定义的，分别是isEmpty、head和tail。\n",
    "\n",
    "Stack是LinearSeq的典型代表，下面的例子是在一个遍历树算法里如何把LinearSeq用作堆栈。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait \u001b[36mBinaryTree\u001b[0m\n",
       "defined \u001b[32mobject \u001b[36mNilTree\u001b[0m\n",
       "defined \u001b[32mclass \u001b[36mBranch\u001b[0m\n",
       "defined \u001b[32mclass \u001b[36mLeaf\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "// define a binary tree structure\n",
    "sealed trait BinaryTree[+A]\n",
    "case object NilTree extends BinaryTree[Nothing]\n",
    "case class Branch[+A](value: A,\n",
    "                     lhs: BinaryTree[A],\n",
    "                     rhs: BinaryTree[A]) extends BinaryTree[A]\n",
    "case class Leaf[+A] (value: A) extends BinaryTree[A]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[32mimport \u001b[36mscala.collection.LinearSeq\u001b[0m\n",
       "\u001b[32mimport \u001b[36mscala.annotation.tailrec\u001b[0m\n",
       "defined \u001b[32mfunction \u001b[36mtraverse\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "// define algorithm to traverse the binary tree\n",
    "import scala.collection.LinearSeq\n",
    "import scala.annotation.tailrec\n",
    "\n",
    "def traverse[A, U](t: BinaryTree[A])(f: A => U): Unit = {\n",
    "    @tailrec\n",
    "    def traverseHelper(current: BinaryTree[A],\n",
    "                      next: LinearSeq[BinaryTree[A]]): Unit = \n",
    "        current match {\n",
    "            case Branch(value, lhs, rhs) =>\n",
    "                f(value)\n",
    "                traverseHelper(lhs, rhs +: next)\n",
    "            case Leaf(value) if !next.isEmpty =>\n",
    "                f(value)\n",
    "                traverseHelper(next.head, next.tail)\n",
    "            case Leaf(value) => f(value)\n",
    "            case NilTree if !next.isEmpty =>\n",
    "                traverseHelper(next.head, next.tail)\n",
    "            case NilTree => ()\n",
    "        }\n",
    "    traverseHelper(t, LinearSeq())\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "traverseHelper实现了遍历树的核心功能，该方法接受当前要遍历的树和下一个LinearSeq，其中包含之后要迭代的二叉树元素。模式匹配的规则是：\n",
    "- 当前树是分支时，把分支的值传给f函数，然后递归调用自身，传入左树作为下个要迭代的节点，并用+:方法把右树加到待处理的LinearSeq前面，该方法是O(1)的效率\n",
    "- 当碰到Leaf，如果next不是空，那么用head和tail分解之，head作为当前树，tail作为next\n",
    "- 当碰到NilTree时，处理逻辑和Leaf一样"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36matree\u001b[0m: \u001b[32mBranch\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mBranch\u001b[0m(\u001b[32m1\u001b[0m, Leaf(2), Branch(3,Leaf(4),NilTree))"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val atree = Branch(1, Leaf(2), Branch(3, Leaf(4), NilTree))\n",
    "traverse(atree)(println)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "当需要把一个普通递归的算法转化成尾递归或循环算法时，在堆（heap）上手工创建个栈（stack），然后用这个栈来完成实际功能是一种常见的做法。在使用函数式风格的尾递归算法时，LinearSeq是个恰当的选择。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 IndexedSeq \n",
    "IndexedSeq在随机访问时更为高效，也就是说，其访问元素的开销应该是常量或接近常量。这种集合类型适用于大多数一般的、不涉及头尾分解的算法。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mx\u001b[0m: \u001b[32mIndexedSeq\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mVector\u001b[0m(\u001b[32m1\u001b[0m, \u001b[32m2\u001b[0m, \u001b[32m3\u001b[0m)\n",
       "\u001b[36mres4_1\u001b[0m: \u001b[32mIndexedSeq\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mVector\u001b[0m(\u001b[32m1\u001b[0m, \u001b[32m5\u001b[0m, \u001b[32m3\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val x = IndexedSeq(1, 2, 3)\n",
    "\n",
    "x.updated(1, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面使用IndexedSeq对象定义的工厂方法创建IndexedSeq实例，默认情况下，这会创建一个不可变的Vector。IndexedSeq有个update方法，该方法接受一个下标和新值，返回用新值修改了下标位置上的值的新集合。\n",
    "\n",
    "IndexedSeq用apply方法来根据下标取值，在Scala里，apply方法调用可以省略。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres5\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m3\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "x.apply(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres6\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m3\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "x(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4 Set\n",
    "Set集合类型代表一种其每个元素都是唯一的结合，至少对==方法来说是唯一。当需要测试一个集合是否包含某个元素或者要确保集合里没有重复元素的时候，Set是很好用的集合类型。\n",
    "\n",
    "Scala支持三种类型的不可变和可变Set：TreeSet、HashSet和BitSet：\n",
    "> - TreeSet用红黑树实现，具有O(logn)的随机访问复杂度。要创建一个TreeSet，必须提供隐式的Ordering类型类，以便能执行小于和大于比较（因为查找元素时需要比较期望值大小）\n",
    "- HashSet也是用树结构实现的集合。最大的区别是HashSet用元素的hash值决定把元素放在树的哪个节点上，这意味着hash值相同的元素会被放在相同的节点上。如果hash算法的碰撞几率很小，那么HashSet在查找时的性能一般优于TreeSet\n",
    "- BitSet是用Long型值的序列实现的。BitSet只能保存整数。BitSet通过把其底层的Long值与欲保存的整数值对应的位置为true来保存整数。BitSet经常用来高效地在内存里跟踪和保存一大批标志位"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5 Map\n",
    "Map特质代表键值对的集合，只有有键的值才能存在。\n",
    "\n",
    "Scala的Map有两种实现：HashMap和TreeMap，类似HashSet和TreeSet实现。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36merrorcodes\u001b[0m: \u001b[32mMap\u001b[0m[\u001b[32mInt\u001b[0m, \u001b[32mString\u001b[0m] = \u001b[33mMap\u001b[0m(\n",
       "  \u001b[32m1\u001b[0m -> \u001b[32m\"O NOES\"\u001b[0m,\n",
       "  \u001b[32m2\u001b[0m -> \u001b[32m\"KTHXBAI\"\u001b[0m,\n",
       "  \u001b[32m3\u001b[0m -> \u001b[32m\"ZOMG\"\u001b[0m\n",
       ")"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val errorcodes = Map(1 -> \"O NOES\", 2 -> \"KTHXBAI\", 3 -> \"ZOMG\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres8\u001b[0m: \u001b[32mString\u001b[0m = \u001b[32m\"O NOES\"\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "errorcodes(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres9\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mString\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m\"O NOES\"\u001b[0m, \u001b[32m\"ZOMG\"\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "// Map能用做从键类型到值类型的偏函数\n",
    "List(1, 3) map errorcodes "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Scala还提供了当键不存在时返回默认值的能力"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36merrorcodes\u001b[0m: \u001b[32mMap\u001b[0m[\u001b[32mInt\u001b[0m, \u001b[32mString\u001b[0m] = \u001b[33mMap\u001b[0m(\n",
       "  \u001b[32m1\u001b[0m -> \u001b[32m\"O NOES\"\u001b[0m,\n",
       "  \u001b[32m2\u001b[0m -> \u001b[32m\"KTHXBAI\"\u001b[0m,\n",
       "  \u001b[32m3\u001b[0m -> \u001b[32m\"ZOMG\"\u001b[0m\n",
       ")"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val errorcodes = Map(1 -> \"O NOES\", 2 -> \"KTHXBAI\", 3 -> \"ZOMG\").withDefaultValue(\"Error key\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres11\u001b[0m: \u001b[32mString\u001b[0m = \u001b[32m\"Error key\"\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "errorcodes(4)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Scala 2.11",
   "language": "scala211",
   "name": "scala211"
  },
  "language_info": {
   "codemirror_mode": "text/x-scala",
   "file_extension": ".scala",
   "mimetype": "text/x-scala",
   "name": "scala211",
   "pygments_lexer": "scala",
   "version": "2.11.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}