HW02 송기원 20180637.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# HW02\n",
    "* 이름: 송기원\n",
    "* 학번: 20180637\n",
    "\n",
    "위에 이름과 학번을 자신의 것으로 기입하고 또 맨 위에 노트북의 제목도 `HW02 이름 학번`으로 바꾸어 HiClass를 통해 마감시간까지 제출하면 됩니다.\n",
    "마감시간은 HiClass 제출하는 항목에 설정해 놓겠습니다.\n",
    "\n",
    "주의사항: 이번에는 반드시 테스트 코드가 있어야 합니다.\n",
    " * 메소드 내용이 완전히 맞게 구현되었다 하더라도 테스트 코드가 없으면 0점입니다.\n",
    " * 리스트에는 기본적으로 두 가지 경우가 항상 있으므로 (null인 경우와 아닌 경우) 각각의 테스트마다 최소한 2개 이상의 값으로 테스트해 보아야 합니다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 우선 제너릭이 아닌 정수 리스트와 \"정수 리스트\"의 리스트를 따로 정의\n",
    "\n",
    " * `equals` (1점)\n",
    " * `append` (1점)\n",
    " * `reverse` (1점)\n",
    " * `tails` (1점)\n",
    " * `palindrome` (1점)\n",
    " * `flat` (1점)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "com.twosigma.beaker.javash.bkra694f056.NodeInt"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class NodeInt {\n",
    "    private int value;\n",
    "    private NodeInt next;\n",
    "    // 생성자\n",
    "    NodeInt(int v, NodeInt n) { value=v; next=n; } \n",
    "    // 기본적인 값을 가져오기 위한 메소드\n",
    "    int head() { return value; }\n",
    "    NodeInt tail() { return next; }\n",
    "\n",
    "    @Override // 리스트의 내용을 알아보기 편하게 출력되게\n",
    "    public String toString() {\n",
    "        return head() + \", \" + tail();\n",
    "    }\n",
    "    \n",
    "    ////////////////////////////////////////////////////////////////\n",
    "\n",
    "    // 빈 리스트를 나타내는 null인 경우를 포함해 처리하기 위한 정적 메소드\n",
    "    static int length(NodeInt xs) {\n",
    "        return (xs==null)? 0: xs.length(); // null이 아니면 인스턴스 메소드 호출\n",
    "    }\n",
    "    static boolean equals(NodeInt xs, NodeInt ys) {\n",
    "        return (xs==null)? ys==null: xs.equals(ys); // null이 아니면 인스턴스 메소드 호출\n",
    "    }\n",
    "    static NodeInt append(NodeInt xs, NodeInt ys) { // xs와 ys를 이어붙인 새로운 리스트\n",
    "        return (xs==null)? ys: xs.append(ys);\n",
    "    }\n",
    "    static NodeInt reverse(NodeInt xs) { // xs를 뒤집은 새로운 리스트\n",
    "        return (xs==null)? null: xs.reverse();\n",
    "    }\n",
    "    static boolean palindrome(NodeInt xs) { // xs의 순서를 뒤집어도 같은 내용의 리스트인지 검사\n",
    "        return (xs == null) ? true : xs.palindrome(); // 이걸 완성해보자\n",
    "    } \n",
    "    static NodeNodeInt tails(NodeInt xs) { // xs의 tail, xs의 tail의 tail, xs의 tail의 tail의 tail, ... , null\n",
    "        return (xs==null)? null: xs.tails(); // null이 아니면 인스턴스 메소드 호출\n",
    "    }\n",
    "    \n",
    "    // 위의 정적 메소드에 대응되는 인스턴스 메소드\n",
    "    int length() {\n",
    "        return 1 + length( tail() ); // tail()이 null일수도 있으므로 클래스 메소드 호출\n",
    "    }\n",
    "    boolean equals(NodeInt ys) { // 같은 원소가 정확히 같은 순서로 나타나는 리스트인지 검사\n",
    "        return (this.head() != ys.head()) ? false : equals(this.tail(), ys.tail());\n",
    "    }\n",
    "    NodeInt append(NodeInt ys) { // 끝에다 주어진 리스트를 이어붙인 새로운 리스트\n",
    "        return (ys == null) ? this : new NodeInt (this.head(), append(this.tail(), ys));\n",
    "    }\n",
    "    NodeInt reverse() { // 리스트를 원소가 나열된 순서를 뒤집은 새로운 리스트\n",
    "        return append(reverse(this.tail()), new NodeInt(this.head(), null));\n",
    "    }\n",
    "    boolean palindrome() { // 순서를 뒤집어도 같은 내용의 리스트인지 검사\n",
    "        return (equals(this, reverse(this))) ? true : false; // 작성해보기\n",
    "    }\n",
    "    NodeNodeInt tails() {\n",
    "        // 1,2,3,null 의 tails는\n",
    "        // [2,3,null],[3,null],[null],null\n",
    "        return new NodeNodeInt(this.tail() ,tails(this.tail())); // 작성해보기\n",
    "    }\n",
    "}\n",
    "\n",
    "class NodeNodeInt { // 정수 리스트를 원소로 하는 리스트, 즉 \"정수 리스트\"의 리스트이다\n",
    "    private NodeInt value;\n",
    "    private NodeNodeInt next;\n",
    "    // 생성자\n",
    "    NodeNodeInt(NodeInt v, NodeNodeInt n) { value=v; next=n; } \n",
    "    // 기본적인 값을 가져오기 위한 메소드\n",
    "    NodeInt head() { return value; }\n",
    "    NodeNodeInt tail() { return next; }\n",
    "\n",
    "    @Override // 리스트의 내용을 알아보기 편하게 출력되게\n",
    "    public String toString() {\n",
    "        return \"[\" + head() + \"], \" + tail();\n",
    "    }\n",
    "    \n",
    "    static NodeInt flat(NodeNodeInt xss) { return (xss==null)? null: xss.flat(); }\n",
    "    \n",
    "    NodeInt flat() { \n",
    "        return NodeInt.append(this.head(), flat(this.tail()));\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "l3: 1, 2, 3, null\n",
      "2, 3, null\n",
      "ll3: [3, null], [2, 3, null], [1, 2, 3, null], null\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "null"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "NodeInt l0 = null;\n",
    "NodeInt l1 = new NodeInt(3, l0);\n",
    "NodeInt l2 = new NodeInt(2, l1);\n",
    "NodeInt l3 = new NodeInt(1, l2);\n",
    "\n",
    "System.out.println(\"l3: \" + l3);\n",
    "System.out.println(l2);// a, b, c, null\n",
    "\n",
    "NodeNodeInt ll0 = null;\n",
    "NodeNodeInt ll1 = new NodeNodeInt(l3, ll0);\n",
    "NodeNodeInt ll2 = new NodeNodeInt(l2, ll1);\n",
    "NodeNodeInt ll3 = new NodeNodeInt(l1, ll2);\n",
    "\n",
    "System.out.println(\"ll3: \" + ll3); // [3, null], [2, 3, null], [1, 2, 3, null], null\n",
    "\n",
    "// // flat을 제대로 정의하고 나면 이런 게 동작할 것이다.\n",
    "// System.out.println(\"NodeNodeInt.flat(ll3) = \" + NodeNodeInt.flat(ll3)); // 3, 2, 3, 1, 2, 3, null"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "=================================================\n",
      "equals(l3, l2) = false\n",
      "equals(l3, l3) = true\n",
      "=================================================\n",
      "append(l3, l1) = 1, 2, 3, 3, null\n",
      "append(l2, l1) = 2, 3, 3, null\n",
      "append(l1, null) = 3, null\n",
      "=================================================\n",
      "reverse(l2) =3, 2, null\n",
      "reverse(l3) = 3, 2, 1, null\n",
      "reverse(null) = null\n",
      "=================================================\n",
      "palindrome(null) = true\n",
      "palindrome(l1) = true\n",
      "palindrome(append(l2, reverse(l2))) = true\n",
      "=================================================\n",
      "tails(l3) = [2, 3, null], [3, null], [null], null\n",
      "tails(l2) = [3, null], [null], null\n",
      "tails(l1) = [null], null\n",
      "=================================================\n",
      "flat(ll1) = 1, 2, 3, null\n",
      "flat(ll2) = 2, 3, 1, 2, 3, null\n",
      "flat(ll3) = 3, 2, 3, 1, 2, 3, null\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "null"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "NodeInt l0 = null;\n",
    "NodeInt l1 = new NodeInt(3, l0);\n",
    "NodeInt l2 = new NodeInt(2, l1);\n",
    "NodeInt l3 = new NodeInt(1, l2);\n",
    "\n",
    "NodeNodeInt ll0 = null;\n",
    "NodeNodeInt ll1 = new NodeNodeInt(l3, ll0);\n",
    "NodeNodeInt ll2 = new NodeNodeInt(l2, ll1);\n",
    "NodeNodeInt ll3 = new NodeNodeInt(l1, ll2);\n",
    "\n",
    "System.out.println(\"=================================================\");\n",
    "\n",
    "System.out.println(\"equals(l3, l2) = \" + NodeInt.equals(l3, l2));\n",
    "System.out.println(\"equals(l3, l3) = \" + NodeInt.equals(l3, l3));\n",
    "\n",
    "System.out.println(\"=================================================\");\n",
    "\n",
    "System.out.println(\"append(l3, l1) = \" + NodeInt.append(l3, l1));\n",
    "System.out.println(\"append(l2, l1) = \" + NodeInt.append(l2, l1));\n",
    "System.out.println(\"append(l1, null) = \" + NodeInt.append(l1, null));\n",
    "\n",
    "System.out.println(\"=================================================\");\n",
    "\n",
    "System.out.println(\"reverse(l2) =\" + NodeInt.reverse(l2));\n",
    "System.out.println(\"reverse(l3) = \" + NodeInt.reverse(l3));\n",
    "System.out.println(\"reverse(null) = \" + NodeInt.reverse(null));\n",
    "\n",
    "System.out.println(\"=================================================\");\n",
    "\n",
    "System.out.println(\"palindrome(null) = \" + NodeInt.palindrome(null));\n",
    "System.out.println(\"palindrome(l1) = \" + NodeInt.palindrome(l1));\n",
    "System.out.println(\"palindrome(append(l2, reverse(l2))) = \" + NodeInt.palindrome(NodeInt.append(l2, NodeInt.reverse(l2))));\n",
    "\n",
    "System.out.println(\"=================================================\");\n",
    "\n",
    "System.out.println(\"tails(l3) = \" + NodeInt.tails(l3));\n",
    "System.out.println(\"tails(l2) = \" + NodeInt.tails(l2));\n",
    "System.out.println(\"tails(l1) = \" + NodeInt.tails(l1));\n",
    "\n",
    "System.out.println(\"=================================================\");\n",
    "\n",
    "System.out.println(\"flat(ll1) = \" + NodeNodeInt.flat(ll1));\n",
    "System.out.println(\"flat(ll2) = \" + NodeNodeInt.flat(ll2));\n",
    "System.out.println(\"flat(ll3) = \" + NodeNodeInt.flat(ll3));\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 제너릭 클래스 정의\n",
    "\n",
    "* 생성자 (1점)\n",
    "* length (1점)\n",
    "* equals (1점)\n",
    "* append (1점)\n",
    "* reverse (1점)\n",
    "* tails (1점)\n",
    "* palindrome (1점)\n",
    "* flat (4점) - 이것은 클래스 메소드로만 정의하도록. 그게 아마 더 쉬울 것이다. 인스턴스 메소드와 함께 정의하기는 좀 까다로움."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "com.twosigma.beaker.javash.bkra694f056.Nd"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Nd { }\n",
    "\n",
    "class Node<T> extends Nd {\n",
    "    T value;\n",
    "    Node<T> next;\n",
    "    \n",
    "    // 생성자를 적절하게 정의하라\n",
    "    public Node(T _value, Node<T> _next ){\n",
    "        this.value = _value;\n",
    "        this.next = _next;\n",
    "    }\n",
    "    \n",
    "    T head() { return value; }\n",
    "    Node<T> tail() { return next; }\n",
    "    \n",
    "    @Override // 리스트의 내용을 알아보기 편하게 출력되게\n",
    "    public String toString() {\n",
    "        return\n",
    "            ( (head() instanceof Nd)\n",
    "             ? \"[\"+ head() + \"]\"\n",
    "             :      head() )\n",
    "            + \", \" + tail();\n",
    "    }\n",
    "    \n",
    "    ///////////////////////////////////////////////////////////////\n",
    "    static int length(Node xs) {\n",
    "        return (xs==null)? 0: xs.length(); // null이 아니면 인스턴스 메소드 호출\n",
    "    }\n",
    "    static boolean equals(Node xs, Node ys) {\n",
    "        return (xs==null)? ys==null: xs.equals(ys); // null이 아니면 인스턴스 메소드 호출\n",
    "    }\n",
    "    static Node append(Node xs, Node ys) { // xs와 ys를 이어붙인 새로운 리스트\n",
    "        return (xs==null)? ys: xs.append(ys);\n",
    "    }\n",
    "    static Node reverse(Node xs) { // xs를 뒤집은 새로운 리스트\n",
    "        return (xs==null)? null: xs.reverse();\n",
    "    }\n",
    "    static boolean palindrome(Node xs) { // xs의 순서를 뒤집어도 같은 내용의 리스트인지 검사\n",
    "        return false; // 이걸 완성해보자\n",
    "    } \n",
    "    static Node tails(Node xs) {\n",
    "        return (xs==null)? null: xs.tails(); // null이 아니면 인스턴스 메소드 호출\n",
    "    }\n",
    "    \n",
    "    static <S> Node<S> flat(Node< Node<S> > xss) { \n",
    "        return (xss==null)?null:append(xss.head(),flat(xss.tail()));\n",
    "    }\n",
    "    //////////////////////////////////////////////////////////////\n",
    "    \n",
    "    int length() {\n",
    "        return 1 + length( tail() ); // tail()이 null일수도 있으므로 클래스 메소드 호출\n",
    "    }\n",
    "    boolean equals(Node ys) { // 같은 원소가 정확히 같은 순서로 나타나는 리스트인지 검사\n",
    "        return (this.head() != ys.head()) ? false : equals(this.tail(), ys.tail());\n",
    "    }\n",
    "    Node append(Node ys) { // 끝에다 주어진 리스트를 이어붙인 새로운 리스트\n",
    "        return (ys == null) ? this : new Node<T>(this.head(), append(this.tail(), ys));\n",
    "    }\n",
    "    Node reverse() { // 리스트를 원소가 나열된 순서를 뒤집은 새로운 리스트\n",
    "        return append(reverse(this.tail()), new Node<T>(this.head(), null));\n",
    "    }\n",
    "    boolean palindrome() { // 순서를 뒤집어도 같은 내용의 리스트인지 검사\n",
    "        return (equals(this, reverse(this))) ? true : false;\n",
    "    }\n",
    "     Node tails() {\n",
    "        return new Node(tail(),tails(tail()));\n",
    "    }\n",
    "\n",
    "    // 제너릭 클래스에 맞게 나머지 메소드들도 정의해 보라\n",
    "    // length, equals, apppend, reverse, palindrome, tails, flat\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "l3: a, b, c, null\n",
      "ll3: [c, null], [b, c, null], [a, b, c, null], null\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "null"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// 위에서 생성자만 제대로 정의하면 아래 코드가 에러없이 실행되어 정상적으로 출력될 것이다\n",
    "\n",
    "Node<String> l0 = null;\n",
    "Node<String> l1 = new Node<String>(\"c\", l0);\n",
    "Node<String> l2 = new Node<>(\"b\", l1); // 생략가능\n",
    "Node<String> l3 = new Node(\"a\", l2); // 이렇게도 생략가능\n",
    "\n",
    "System.out.println(\"l3: \" + l3); // a, b, c, null\n",
    "\n",
    "Node< Node<String> > ll0 = null;\n",
    "Node< Node<String> > ll1 = new Node< Node<String> >(l3, ll0);\n",
    "Node< Node<String> > ll2 = new Node<>(l2, ll1); // 생략가능\n",
    "Node< Node<String> > ll3 = new Node(l1, ll2); // 이렇게도 생략가능\n",
    "\n",
    "System.out.println(\"ll3: \" + ll3); // [c, null], [b, c, null], [a, b, c, null], null\n",
    "\n",
    "// // flat을 제대로 정의하고 나면 이런 게 동작할 것이다.\n",
    "// System.out.println(\"Node.flat(ll3) = \" + Node.flat(ll3)); // c, b, c, a, b, c, null\n",
    "\n",
    "// 마찬가지로 다른 메소드에 대해서도 테스트 코드 작성"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "=================================================\n",
      "equals(l3, l2) = false\n",
      "equals(l3, l3) = true\n",
      "=================================================\n",
      "append(l3, l1) = a, b, c, c, null\n",
      "append(l2, l1) = b, c, c, null\n",
      "append(l1, null) = c, null\n",
      "=================================================\n",
      "reverse(l2) =c, b, null\n",
      "reverse(l3) = c, b, a, null\n",
      "reverse(null) = null\n",
      "=================================================\n",
      "palindrome(null) = false\n",
      "palindrome(l1) = false\n",
      "palindrome(append(l2, reverse(l2))) = false\n",
      "=================================================\n",
      "tails(l3) = [b, c, null], [c, null], null, null\n",
      "tails(l2) = [c, null], null, null\n",
      "tails(l1) = null, null\n",
      "=================================================\n",
      "flat(ll1) = a, b, c, null\n",
      "flat(ll2) = b, c, a, b, c, null\n",
      "flat(ll3) = c, b, c, a, b, c, null\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "null"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Node<String> l0 = null;\n",
    "Node<String> l1 = new Node<String>(\"c\", l0);\n",
    "Node<String> l2 = new Node<>(\"b\", l1); // 생략가능\n",
    "Node<String> l3 = new Node(\"a\", l2); // 이렇게도 생략가능\n",
    "\n",
    "Node< Node<String> > ll0 = null;\n",
    "Node< Node<String> > ll1 = new Node< Node<String> >(l3, ll0);\n",
    "Node< Node<String> > ll2 = new Node<>(l2, ll1); // 생략가능\n",
    "Node< Node<String> > ll3 = new Node(l1, ll2); // 이렇게도 생략가능\n",
    "\n",
    "System.out.println(\"=================================================\");\n",
    "\n",
    "System.out.println(\"equals(l3, l2) = \" + Node.equals(l3, l2));\n",
    "System.out.println(\"equals(l3, l3) = \" + Node.equals(l3, l3));\n",
    "\n",
    "System.out.println(\"=================================================\");\n",
    "\n",
    "System.out.println(\"append(l3, l1) = \" + Node.append(l3, l1));\n",
    "System.out.println(\"append(l2, l1) = \" + Node.append(l2, l1));\n",
    "System.out.println(\"append(l1, null) = \" + Node.append(l1, null));\n",
    "\n",
    "System.out.println(\"=================================================\");\n",
    "\n",
    "System.out.println(\"reverse(l2) =\" + Node.reverse(l2));\n",
    "System.out.println(\"reverse(l3) = \" + Node.reverse(l3));\n",
    "System.out.println(\"reverse(null) = \" + Node.reverse(null));\n",
    "\n",
    "System.out.println(\"=================================================\");\n",
    "\n",
    "System.out.println(\"palindrome(null) = \" + Node.palindrome(null));\n",
    "System.out.println(\"palindrome(l1) = \" + Node.palindrome(l1));\n",
    "System.out.println(\"palindrome(append(l2, reverse(l2))) = \" + Node.palindrome(Node.append(l2, Node.reverse(l2))));\n",
    "\n",
    "System.out.println(\"=================================================\");\n",
    "\n",
    "System.out.println(\"tails(l3) = \" + Node.tails(l3));\n",
    "System.out.println(\"tails(l2) = \" + Node.tails(l2));\n",
    "System.out.println(\"tails(l1) = \" + Node.tails(l1));\n",
    "\n",
    "System.out.println(\"=================================================\");\n",
    "\n",
    "System.out.println(\"flat(ll1) = \" + Node.flat(ll1));\n",
    "System.out.println(\"flat(ll2) = \" + Node.flat(ll2));\n",
    "System.out.println(\"flat(ll3) = \" + Node.flat(ll3));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java",
   "language": "java",
   "name": "java"
  },
  "language_info": {
   "codemirror_mode": "text/x-java",
   "file_extension": ".java",
   "mimetype": "",
   "name": "Java",
   "nbconverter_exporter": "",
   "version": "1.8.0_121"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": false,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": false,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}