OptimizedSearchingAlgorithms

CachedBruteForceSearching.kt

import com.zekierciyas.cache.model.satellite_list.SatelliteListItem
import java.util.*

class CachedBruteForceSearching(private val cacheSize: Int = 5) {

    private var givenDataList: List<SatelliteListItem> = mutableListOf()

    var cache: LinkedHashMap<String, List<SatelliteListItem>> = object : LinkedHashMap<String, List<SatelliteListItem>>(5, 0.75f, true) {
        override fun removeEldestEntry(eldest: Map.Entry<String?, List<SatelliteListItem>>?): Boolean {
            return size > cacheSize
        }
    }

    fun initData(givenDataList: List<SatelliteListItem>) = apply {
        this.givenDataList = givenDataList
    }

    fun searchFilter(searchKey: String): List<SatelliteListItem> {
        if (cache.containsKey(searchKey)) {
            return cache[searchKey]!!
        }

        val filteredList = mutableListOf<SatelliteListItem>()
        for (item in givenDataList) {
            var data = item.name.toLowerCase()
            var i = 0
            while (i <= data.length - searchKey.length) {
                var j = 0
                while (j < searchKey.length && data[i + j] == searchKey[j]) {
                    j++
                }
                if (j == searchKey.length) {
                    filteredList.add(item)
                    break
                }
                i++
            }
        }

        val previousResult = cache[searchKey]
        cache[searchKey] = filteredList

        if (previousResult != null) {
            val toRemove = previousResult.subtract(filteredList.toSet()).toList()
            for (key in cache.keys) {
                cache[key] = cache[key]!!.minus(toRemove.toSet())
            }
        }

        return filteredList
    }

}

CachedRabinKarpSearching.kt

import com.zekierciyas.cache.model.satellite_list.SatelliteListItem
import kotlin.math.pow

class CachedRabinKarpSearching {

    private var givenDataList: List<SatelliteListItem> = arrayListOf()
    private val prime = 101
    private var cacheSize: Int = 5
    private val cacheMap = LinkedHashMap<String, List<SatelliteListItem>>(cacheSize, 0.75f, true)

    private fun calculateHash(str: String): Long {
        var hash = 0L
        for (i in str.indices) {
            hash += str[i].toInt() * prime.toDouble().pow(i).toLong()
        }
        return hash
    }

    private fun generateHashes(searchKey: String): Pair<Long, Long> {
        val searchKeyHash = calculateHash(searchKey)
        val x = prime.toDouble().pow(searchKey.length - 1).toLong()
        return Pair(searchKeyHash, x)
    }

    private fun recalculateHash(hash: Long, x: Long, oldChar: Char, newChar: Char): Long {
        var newHash = hash - oldChar.toInt() * x
        newHash = newHash * prime + newChar.toInt()
        return newHash
    }

    private fun searchFilter(searchKey: String): List<SatelliteListItem> {
        if (cacheMap.containsKey(searchKey)) {
            return cacheMap[searchKey]!!
        }

        val filteredList = mutableListOf<SatelliteListItem>()
        val (searchKeyHash, x) = generateHashes(searchKey)


        for (item in givenDataList) {
            val data = item.name.toLowerCase()
            var dataHash = calculateHash(data.substring(0, searchKey.length))
            var i = 0

            while (i <= data.length - searchKey.length) {
                if (searchKeyHash == dataHash) {
                    if (searchKey == data.substring(i, i + searchKey.length)) {
                        filteredList.add(item)
                        break
                    }
                }

                if (i < data.length - searchKey.length) {
                    dataHash = recalculateHash(dataHash, x, data[i], data[i + searchKey.length])
                }
                i++
            }
        }

        if (cacheMap.size >= cacheSize) {
            cacheMap.remove(cacheMap.keys.first())
        }
        cacheMap[searchKey] = filteredList

        return filteredList
    }

    fun search(searchKey: String): List<SatelliteListItem> {
        return searchFilter(searchKey)
    }

    fun init(givenDataList: List<SatelliteListItem>) = apply {
        this.givenDataList = givenDataList
    }

    fun cacheSize(cacheSize: Int = 5) = apply {
        this.cacheSize = cacheSize
    }
}