package breadthfirstsearch

import java.util.*
import kotlin.collections.HashMap
import kotlin.collections.HashSet

/**
 * @Author: zhangQi
 * @Date: 2020-09-19 21:57
 */
//泛型别名
typealias Graph<V> = MutableMap<V, List<V>>

//kotlin泛型,boolean值 lambda方式
/**
 * this对象调用,传入一个要搜索的key 和 是否是销售员的boolean值
 * 默认boolean值false,传入什么改为什么
 * 首先方法中声明了linkedList为Deque类型
 */
fun <V> Graph<V>.breadthFirstSearch(key: V, isSearched: (V) -> Boolean): Boolean {
    println("key : "+key)
    println("this[key] : "+this[key])
    //kotlin创建对象总是用对象() 不用加new
    val queue: Deque<V> = LinkedList()

    //let key 递加 this[key]返回数据
    this[key]?.let {
        //拼接了这个key的value , 即关键人的关联人列表
        queue += it 
    }
    //新创建一个HashSet,不会重复
    val searched = HashSet<V>()
    while (queue.isNotEmpty()) {
        //return the element at the front of this deque (which is the top
        //of the stack represented by this deque)
        val value = queue.pop()
        /**
         * pop()取得并销毁, Sergey为key时,没有联系人
         */
        if (!searched.contains(value)) {
            //判定那个boolean值,这个也可以判定如该用户手机号为欠费的业务,判定后单独对该用户发送提示短信
            if (isSearched(value)) {
                println("value : $value is here~~~~~~~")
                return true
            } else {
                println("this[value] : "+this[value])
                this[value]?.let { queue += it }
                searched.add(value)
            }
        }
    }
    return false
}

//对象类
data class Person(
        //var val的区别就是var是变量(可变) val是常量
        val name: String,
        //boolean 默认false值
        val isSellerMango: Boolean = false
) {
    //重写了equals方法
    override fun equals(other: Any?): Boolean =
            if (other is Person) other.name == name
            else false

    //重写了hashCode为名字长度 这样好像不严谨啊..应该直接调用name的hashCode
    override fun hashCode(): Int {
        return name.length
    }
}

fun main(args: Array<String>) {
    //graph是kotlin的自定义集合 图
    val graph: Graph<Person> = HashMap()

    (graph as HashMap<Person,List<Person>>).apply {
        put(Person("John"), listOf(Person("Sergey"),Person("Viktoria")))
        //放入其他集合,其中有个person的isSellerMango为true
        put(Person("Viktoria"), listOf(Person("Sergey"), Person("Phara")))
        put(Person("Phara"), listOf(Person("Sergey"), Person("Thrall"), Person("Xul"), Person("Juncart", true)))
    }

    println(graph.breadthFirstSearch(Person("John"),Person::isSellerMango))
}

/**
key : Person(name=John, isSellerMango=false)
this[key] : [Person(name=Sergey, isSellerMango=false), Person(name=Viktoria, isSellerMango=false)]
//Sergey为key时没有联系人
this[value] : null 
//Viktoria为key时的联系人列表
this[value] : [Person(name=Sergey, isSellerMango=false), Person(name=Phara, isSellerMango=false)]
//Phara为key时的联系人列表
this[value] : [Person(name=Sergey, isSellerMango=false), Person(name=Thrall, isSellerMango=false), Person(name=Xul, isSellerMango=false), Person(name=Juncart, isSellerMango=true)]
//Xul时
this[value] : null
//Juncart时
this[value] : null
value : Person(name=Juncart, isSellerMango=true) is here~~~~~~~
true
*/

广度优先搜索参考