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
*/
参考:
