日期: 2020 年 8 月 19 日

package com.datacrafts.digitalevers.generic

import util.control.Breaks._
import scala.reflect.runtime.universe._


/**
 * 比较粗略实现了泛型版本的单向链表的增删改查操作，代码在scala 2.12.10上编译通过，测试运行通过。有几个点需要注意
 * 1.上下边界 <: >:都没有隐式转换 只有视图边界 % 才有隐式转换
 * 2.在按顺序往链表添加节点时 应将比较器的实例化对象提取到 链表类的属性层 而不应放在方法中  此举是为了解决内存使用
 * 3.编译过程中，实例化比较器需要得知泛型参数的具体类型，之前在这个地方纠结了很久，最终无法通过隐式转换实行自动比较，故只能显式将其转换为Int 或者 Double类型
 * 4.但是由于 scala 在运行过程中会擦除泛型类型，故使用了一个小技巧——加入一个隐式参数TypeTag[T]来保存运行时泛型类型，然后通过模式匹配来决定改转换成哪种对象（Int或者Double)，然后会自动通过隐式转换为 Comparable 子类来进行比较操作
 * 5.感觉还有更好的实现方式，以便可以支持更多的数据类型
 * @param in
 * @tparam T
 */
class genericClass[T,U](in:T,v:U) {
  private var size = 0
  var head:node[T,U] = new node[T,U](in,v)

  //比较器
  val cc = new commonCompare
  /**
   * 链表尾部添加节点
   * @param newNode
   */
  def addNode(newNode:node[T,U]): Unit = {
    var temp = head
    while(temp.next != null){
      temp = temp.next
    }
    temp.next = newNode
    size += 1
  }

  /**
   * 按顺序插入节点
   */
  def addNodeOrder(newNode:node[T,U])(implicit t:TypeTag[T]): Unit = {
    var curr = head
    var prev = head

    t.tpe match {
      case tpe if tpe == typeOf[Int]=>{
        breakable {
          while (curr != null) {
            prev = curr
            curr = curr.next
            if (curr != null && cc.greater(curr.id.asInstanceOf[Int], newNode.id.asInstanceOf[Int]) == false) {
              //如果找到了这个比新节点数据更小或相等的节点 跳出循环
              break()
            }
          }
        }
      }
      case tpe if tpe == typeOf[Double] =>{
        breakable {
          while (curr != null) {
            prev = curr
            curr = curr.next
            if (curr != null && cc.greater(curr.id.asInstanceOf[Double], newNode.id.asInstanceOf[Double]) == false) {
              //如果找到了这个比新节点数据更小或相等的节点 跳出循环
              break()
            }
          }
        }
      }
    }
    /////match

    if(curr == null){
      //没有找到该节点则在链表尾部插入新节点
      prev.next = newNode
    } else {
      //没有则在该节点前置插入新节点
      newNode.next = curr
      prev.next = newNode
    }
    size += 1
  }

  /**
   * 更新节点数据域
   */
  def updateNode(id:T,data:U){
    var curr = head
    while (curr != null && curr.id != id) {
      curr = curr.next
    }
    if(curr != null){
      curr.data = data
    }
  }

  /**
   * 删除节点
   */
  def delete(id:T): Unit = {
    var curr = head
    var prev = head
    while (curr != null && curr.id != id){
      prev = curr
      curr = curr.next
    }
    if(curr != null){
      prev.next = curr.next
    }
  }

  /**
   * 展示链表的所有数据
   */
  def show(): Unit ={
    var temp = head
    while(temp.next != null){
      temp = temp.next
      println(temp)
    }
  }

  def length = {
    size
  }
}

class node[T,U](in:T,v:U){
  var id:T = in
  var data:U = v
  var next:node[T,U] = null

  override def toString: String = {
    id + " "+data.toString
  }
}

/**
 * 泛型的通用比较类
 */
class commonCompare{
  def greater[T<% Comparable[T]](t1:T,t2:T) =
    if(t1.compareTo(t2) > 0) true else false
}



object test{
  def main(args: Array[String]): Unit = {
    val linkTest = new genericClass(0,"")
    val newNode = new node(13,"hello")
    linkTest.addNodeOrder(newNode)
    val newNode2 = new node(15,"scala")
    linkTest.addNodeOrder(newNode2)
    linkTest.updateNode(13,"php")
    //linkTest.delete(15)
    linkTest.show()
    //print(linkTest.length)
  }
}