Advertisement
Guest User

Untitled

a guest
Oct 18th, 2019
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Kotlin 5.30 KB | None | 0 0
  1. var mapChar = HashMap<Char, Int>()
  2. fun main(args: Array<String>) {
  3.     val hashSet = HashSet<Int>()
  4.     val treeSet = TreeSet<Int>()
  5.  
  6.     var timeStart = 0L
  7.     var timeEnd = 0L
  8.  
  9.     val str = readLine()!!
  10.  
  11.     val map = huffmanCoding(str)
  12.     val huffStr = huffmanString(str, map)
  13.     val orig = fromHuffmanString(huffStr, map)
  14.  
  15.     mapChar.toList().sortedBy { it.second }.forEach{
  16.         println("${it.first} - ${it.second}")
  17.     }
  18.  
  19.     println("-----------------------------------------------------------------------------------")
  20.  
  21.     map.toList().sortedBy { it.second.length }.forEach{
  22.         println("${it.first} = ${it.second}")
  23.     }
  24.  
  25.     println("-----------------------------------------------------------------------------------")
  26.  
  27.     println(huffStr)
  28.  
  29.     println("-----------------------------------------------------------------------------------")
  30.  
  31.     println(orig)
  32.  
  33.     println()
  34.     println()
  35.     println("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++")
  36.  
  37.     val count = readLine()!!.toInt()
  38.  
  39.     timeStart = System.currentTimeMillis()
  40.     for (i in 0..count) {
  41.         hashSet.add(Random().nextInt(count))
  42.     }
  43.     timeEnd = System.currentTimeMillis()
  44.     println("HASH ADD ($count) : ${(timeEnd - timeStart) / 1f} milli sec.")
  45.  
  46.     timeStart = System.currentTimeMillis()
  47.     for (i in 0..count) {
  48.         hashSet.contains(Random().nextInt(count))
  49.     }
  50.     timeEnd = System.currentTimeMillis()
  51.     println("HASH FIND ($count) : ${(timeEnd - timeStart) / 1f} milli sec.")
  52.  
  53.     timeStart = System.currentTimeMillis()
  54.     for (i in (count / 1000)..(count /10))
  55.         hashSet.contains(i)
  56.     timeEnd = System.currentTimeMillis()
  57.     println("HASH FIND RANGE (${count / 1000})..(${count /10}) : ${(timeEnd - timeStart) / 1f} milli sec.")
  58.  
  59.     timeStart = System.currentTimeMillis()
  60.     for (i in 0..count) {
  61.         hashSet.remove(Random().nextInt(count))
  62.     }
  63.     timeEnd = System.currentTimeMillis()
  64.     println("HASH DELETE ($count) : ${(timeEnd - timeStart) / 1f} milli sec.")
  65.  
  66.     println("-----------------------------------------------------------------------------------")
  67.  
  68.     timeStart = System.currentTimeMillis()
  69.     for (i in 0..count) {
  70.         treeSet.add(Random().nextInt(count))
  71.     }
  72.     timeEnd = System.currentTimeMillis()
  73.     println("TREE ADD ($count) : ${(timeEnd - timeStart) / 1f} milli sec.")
  74.  
  75.     timeStart = System.currentTimeMillis()
  76.     for (i in 0..count) {
  77.         treeSet.contains(Random().nextInt(count))
  78.     }
  79.     timeEnd = System.currentTimeMillis()
  80.     println("TREE FIND ($count) : ${(timeEnd - timeStart) / 1f} milli sec.")
  81.  
  82.     timeStart = System.currentTimeMillis()
  83.     treeSet.subSet((count / 1000), (count / 10))
  84.     timeEnd = System.currentTimeMillis()
  85.     println("TREE FIND RANGE (${count / 1000})..(${count /10}) : ${(timeEnd - timeStart) / 1f} milli sec.")
  86.  
  87.     timeStart = System.currentTimeMillis()
  88.     for (i in 0..count) {
  89.         treeSet.remove(Random().nextInt(count))
  90.     }
  91.     timeEnd = System.currentTimeMillis()
  92.     println("TREE DELETE ($count) : ${(timeEnd - timeStart) / 1f} milli sec.")
  93.  
  94. }
  95.  
  96. fun huffmanCoding(phrase: String): HashMap<Char, String> {
  97.  
  98.     val chars = phrase.toCharArray()
  99.     val chapMap = HashMap<Char, Int>()
  100.  
  101.     chars.forEach {
  102.         val char = chapMap[it]
  103.         if (char == null)
  104.             chapMap[it] = 1
  105.         else
  106.             chapMap[it] = chapMap[it]!! + 1
  107.     }
  108.  
  109.     mapChar = chapMap
  110.  
  111.     val queue = PriorityQueue<HuffmanNode>(Comparator { o1, o2 -> o1.cost.compareTo(o2.cost) })
  112.     chapMap.forEach { queue.add(HuffmanNode(it.value, it.key, isChar = true)) }
  113.  
  114.     while (queue.size > 1){
  115.         val first = queue.poll()
  116.         val second = queue.poll()
  117.  
  118.         val isFirstLeft = first.cost < second.cost
  119.  
  120.         val node = HuffmanNode(first.cost + second.cost)
  121.  
  122.         if (isFirstLeft){
  123.             node.left = first
  124.             node.right = second
  125.         } else {
  126.             node.left = second
  127.             node.right = first
  128.         }
  129.  
  130.         queue.add(node)
  131.     }
  132.  
  133.     val map = HashMap<Char, String>()
  134.     val root = queue.poll()
  135.  
  136.     root.getCodes(map)
  137.  
  138.     return map
  139.  
  140. }
  141.  
  142. fun huffmanString(str: String, map: HashMap<Char, String>): String {
  143.  
  144.     var huffStr = ""
  145.     val chars = str.toCharArray()
  146.  
  147.     chars.forEach {
  148.         huffStr += map[it]
  149.     }
  150.  
  151.     return huffStr
  152. }
  153.  
  154. fun fromHuffmanString(str: String, map: HashMap<Char, String>): String {
  155.  
  156.     var s = str
  157.     val reversMap = HashMap<String, Char>()
  158.     map.forEach { reversMap[it.value] = it.key }
  159.  
  160.     var outStr = ""
  161.     var shift = 1
  162.  
  163.     while (s.isNotEmpty()){
  164.         if (reversMap[s.substring(0, shift)] == null){
  165.             shift++
  166.         } else {
  167.             outStr += reversMap[s.substring(0, shift)]
  168.             s = s.substring(shift)
  169.             shift = 1
  170.         }
  171.     }
  172.  
  173.     return outStr
  174. }
  175.  
  176. data class HuffmanNode(var cost: Int, var char: Char? = null, val isChar: Boolean = false, var left: HuffmanNode? = null, var right: HuffmanNode? = null){
  177.     fun getCodes(map: HashMap<Char, String>, str: String = "") {
  178.         if (isChar)
  179.             map[char!!] = str
  180.         else {
  181.             this.left?.getCodes(map, str + "0")
  182.             this.right?.getCodes(map, str + "1")
  183.         }
  184.     }
  185. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement