Примеры Структур Данных Android Kotlin

// Android Kotlin Array Operations Examples
// Using Lists, Arrays, and MutableList

// 1. Basic Array Operations
class BasicArrayOperations {

    // Create and initialize arrays
    fun createArrays() {
        // Using listOf (immutable)
        val immutableList = listOf(1, 2, 3, 4, 5)
        println("Immutable list: $immutableList")

        // Using mutableListOf (mutable)
        val mutableList = mutableListOf(1, 2, 3, 4, 5)
        println("Mutable list: $mutableList")

        // Using arrayOf
        val array = arrayOf(1, 2, 3, 4, 5)
        println("Array: ${array.contentToString()}")

        // Using IntArray (primitive)
        val intArray = intArrayOf(1, 2, 3, 4, 5)
        println("Int array: ${intArray.contentToString()}")
    }

    // Access elements
    fun accessElements(list: List<Int>) {
        println("First element: ${list.first()}")
        println("Last element: ${list.last()}")
        println("Element at index 2: ${list[2]}")
        println("Element at index 10 (safe): ${list.getOrElse(10) { -1 }}")

        // Safe access with null
        println("Element at index 10: ${list.getOrNull(10)}")
    }

    // Check element existence
    fun checkElement(list: List<Int>, element: Int) {
        println("Contains $element: ${list.contains(element)}")
        println("Index of $element: ${list.indexOf(element)}")
        println("Last index of $element: ${list.lastIndexOf(element)}")
    }

    // Get array size
    fun getSize(list: List<Int>) {
        println("Size: ${list.size}")
        println("Is empty: ${list.isEmpty()}")
        println("Is not empty: ${list.isNotEmpty()}")
    }
}

// 2. Mutable Array Operations
class MutableArrayOperations {

    // Add elements
    fun addElements() {
        val list = mutableListOf<Int>()

        // Add single element
        list.add(1)
        list.add(2)
        println("After adding: $list")

        // Add at specific index
        list.add(1, 10)
        println("After insert at index 1: $list")

        // Add all from another collection
        list.addAll(listOf(20, 30, 40))
        println("After addAll: $list")

        // Add at index from another collection
        list.addAll(2, listOf(100, 200))
        println("After addAll at index: $list")
    }

    // Remove elements
    fun removeElements() {
        val list = mutableListOf(1, 2, 3, 4, 5, 3, 6)

        // Remove by value
        list.remove(3)
        println("After remove(3): $list")

        // Remove by index
        list.removeAt(2)
        println("After removeAt(2): $list")

        // Remove first occurrence
        list.remove(3)
        println("After remove first 3: $list")

        // Remove all matching
        val numbers = mutableListOf(1, 2, 3, 4, 5)
        numbers.removeAll(listOf(2, 4))
        println("After removeAll(2,4): $numbers")

        // Remove range
        val rangeList = mutableListOf(1, 2, 3, 4, 5, 6, 7)
        rangeList.subList(2, 5).clear()
        println("After remove range 2-5: $rangeList")

        // Clear all
        rangeList.clear()
        println("After clear: $rangeList")
    }

    // Update elements
    fun updateElements() {
        val list = mutableListOf(1, 2, 3, 4, 5)

        // Update by index
        list[2] = 30
        println("After update index 2: $list")

        // Update using set
        list.set(3, 40)
        println("After set index 3: $list")

        // Replace all
        val newList = list.map { it * 2 }
        println("After map * 2: $newList")

        // Update in place
        for (i in list.indices) {
            list[i] = list[i] * 10
        }
        println("After in-place update: $list")
    }
}

// 3. Array Searching
class ArraySearching {

    // Linear search
    fun linearSearch(list: List<Int>, target: Int): Int? {
        for (i in list.indices) {
            if (list[i] == target) {
                return i
            }
        }
        return null
    }

    // Binary search (requires sorted list)
    fun binarySearch(list: List<Int>, target: Int): Int? {
        var left = 0
        var right = list.size - 1

        while (left <= right) {
            val mid = left + (right - left) / 2

            when {
                list[mid] == target -> return mid
                list[mid] < target -> left = mid + 1
                else -> right = mid - 1
            }
        }

        return null
    }

    // Find max and min
    fun findMaxMin(list: List<Int>): Pair<Int, Int>? {
        if (list.isEmpty()) return null

        var max = list[0]
        var min = list[0]

        for (element in list) {
            if (element > max) max = element
            if (element < min) min = element
        }

        return Pair(max, min)
    }

    // Find duplicates
    fun findDuplicates(list: List<Int>): List<Int> {
        val seen = mutableSetOf<Int>()
        val duplicates = mutableSetOf<Int>()

        for (element in list) {
            if (!seen.add(element)) {
                duplicates.add(element)
            }
        }

        return duplicates.toList()
    }

    // Count occurrences
    fun countOccurrences(list: List<Int>, target: Int): Int {
        return list.count { it == target }
    }
}

// 4. Array Sorting
class ArraySorting {

    // Built-in sort
    fun sortAscending(list: MutableList<Int>): MutableList<Int> {
        list.sort()
        return list
    }

    fun sortDescending(list: MutableList<Int>): MutableList<Int> {
        list.sortDescending()
        return list
    }

    // Sort by custom comparator
    fun sortCustom(list: MutableList<String>): MutableList<String> {
        // Sort by length
        list.sortBy { it.length }
        return list
    }

    // Sort with comparator
    fun sortWithComparator(list: MutableList<Int>): MutableList<Int> {
        // Sort by absolute value
        list.sortWith(compareBy { Math.abs(it) })
        return list
    }

    // Bubble sort (manual implementation)
    fun bubbleSort(arr: MutableList<Int>): MutableList<Int> {
        val n = arr.size
        for (i in 0 until n - 1) {
            for (j in 0 until n - i - 1) {
                if (arr[j] > arr[j + 1]) {
                    // Swap
                    val temp = arr[j]
                    arr[j] = arr[j + 1]
                    arr[j + 1] = temp
                }
            }
        }
        return arr
    }

    // Quick sort (manual implementation)
    fun quickSort(arr: MutableList<Int>, low: Int, high: Int) {
        if (low < high) {
            val pivotIndex = partition(arr, low, high)
            quickSort(arr, low, pivotIndex - 1)
            quickSort(arr, pivotIndex + 1, high)
        }
    }

    private fun partition(arr: MutableList<Int>, low: Int, high: Int): Int {
        val pivot = arr[high]
        var i = low - 1

        for (j in low until high) {
            if (arr[j] <= pivot) {
                i++
                // Swap arr[i] and arr[j]
                val temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
            }
        }

        // Swap arr[i+1] and arr[high]
        val temp = arr[i + 1]
        arr[i + 1] = arr[high]
        arr[high] = temp

        return i + 1
    }
}

// 5. Array Filtering and Mapping
class ArrayTransformations {

    // Filter elements
    fun filterEven(list: List<Int>): List<Int> {
        return list.filter { it % 2 == 0 }
    }

    fun filterGreaterThan(list: List<Int>, threshold: Int): List<Int> {
        return list.filter { it > threshold }
    }

    // Map elements
    fun doubleElements(list: List<Int>): List<Int> {
        return list.map { it * 2 }
    }

    fun toStringList(list: List<Int>): List<String> {
        return list.map { "Number: $it" }
    }

    // FlatMap
    fun flatten(lists: List<List<Int>>): List<Int> {
        return lists.flatten()
    }

    fun flatMapExample(list: List<Int>): List<Int> {
        return list.flatMap { listOf(it, it * 2) }
    }

    // Reduce/Fold
    fun sum(list: List<Int>): Int {
        return list.reduce { acc, num -> acc + num }
    }

    fun product(list: List<Int>): Int {
        return list.reduce { acc, num -> acc * num }
    }

    fun joinToString(list: List<Int>): String {
        return list.joinToString(separator = ", ", prefix = "[", postfix = "]")
    }

    // Partition
    fun partitionEvenOdd(list: List<Int>): Pair<List<Int>, List<Int>> {
        return list.partition { it % 2 == 0 }
    }

    // Group by
    fun groupByLength(list: List<String>): Map<Int, List<String>> {
        return list.groupBy { it.length }
    }

    // Chunk
    fun chunkList(list: List<Int>, size: Int): List<List<Int>> {
        return list.chunked(size)
    }

    // Window
    fun slidingWindow(list: List<Int>, size: Int): List<List<Int>> {
        return list.windowed(size)
    }
}

// 6. Advanced Array Operations
class AdvancedArrayOperations {

    // Rotate array
    fun rotateLeft(arr: MutableList<Int>, positions: Int): MutableList<Int> {
        val n = arr.size
        val effectivePositions = positions % n

        for (i in 0 until effectivePositions) {
            val first = arr[0]
            for (j in 0 until n - 1) {
                arr[j] = arr[j + 1]
            }
            arr[n - 1] = first
        }

        return arr
    }

    // Reverse array
    fun reverse(arr: MutableList<Int>): MutableList<Int> {
        arr.reverse()
        return arr
    }

    // Merge two sorted arrays
    fun mergeSortedArrays(arr1: List<Int>, arr2: List<Int>): List<Int> {
        val result = mutableListOf<Int>()
        var i = 0
        var j = 0

        while (i < arr1.size && j < arr2.size) {
            if (arr1[i] <= arr2[j]) {
                result.add(arr1[i])
                i++
            } else {
                result.add(arr2[j])
                j++
            }
        }

        while (i < arr1.size) {
            result.add(arr1[i])
            i++
        }

        while (j < arr2.size) {
            result.add(arr2[j])
            j++
        }

        return result
    }

    // Find intersection
    fun intersection(list1: List<Int>, list2: List<Int>): List<Int> {
        return list1.intersect(list2).toList()
    }

    // Find union
    fun union(list1: List<Int>, list2: List<Int>): List<Int> {
        return list1.union(list2).toList()
    }

    // Find difference
    fun difference(list1: List<Int>, list2: List<Int>): List<Int> {
        return list1.filter { it !in list2 }
    }

    // Remove duplicates
    fun removeDuplicates(list: List<Int>): List<Int> {
        return list.distinct()
    }

    // Zip two arrays
    fun zipArrays(list1: List<Int>, list2: List<String>): List<Pair<Int, String>> {
        return list1.zip(list2)
    }

    // Unzip
    fun unzip(pairs: List<Pair<Int, String>>): Pair<List<Int>, List<String>> {
        return pairs.unzip()
    }
}

// Main demonstration
fun demonstrateArrayOperations() {
    println("=== Kotlin Array Operations Examples ===\n")

    // 1. Basic operations
    println("--- 1. Basic Array Operations ---")
    val basicOps = BasicArrayOperations()
    basicOps.createArrays()

    val sampleList = listOf(10, 20, 30, 40, 50)
    basicOps.accessElements(sampleList)
    basicOps.checkElement(sampleList, 30)
    basicOps.getSize(sampleList)

    // 2. Mutable operations
    println("\n--- 2. Mutable Array Operations ---")
    val mutableOps = MutableArrayOperations()
    mutableOps.addElements()
    mutableOps.removeElements()
    mutableOps.updateElements()

    // 3. Searching
    println("\n--- 3. Array Searching ---")
    val searching = ArraySearching()
    val searchList = listOf(1, 5, 3, 9, 2, 8, 7)
    println("Linear search for 9: ${searching.linearSearch(searchList, 9)}")

    val sortedList = listOf(1, 2, 3, 4, 5, 6, 7, 8, 9)
    println("Binary search for 5: ${searching.binarySearch(sortedList, 5)}")
    println("Max/Min: ${searching.findMaxMin(searchList)}")
    println("Duplicates: ${searching.findDuplicates(listOf(1, 2, 2, 3, 3, 3))}")
    println("Count of 3: ${searching.countOccurrences(listOf(1, 3, 3, 2, 3), 3)}")

    // 4. Sorting
    println("\n--- 4. Array Sorting ---")
    val sorting = ArraySorting()
    val unsorted = mutableListOf(5, 2, 8, 1, 9, 3)
    println("Original: $unsorted")
    println("Sorted ascending: ${sorting.sortAscending(unsorted.toMutableList())}")

    val sortDescending = mutableListOf(5, 2, 8, 1, 9, 3)
    println("Sorted descending: ${sorting.sortDescending(sortDescending)}")

    val bubbleSortArr = mutableListOf(64, 34, 25, 12, 22, 11, 90)
    println("Bubble sort: ${sorting.bubbleSort(bubbleSortArr)}")

    // 5. Transformations
    println("\n--- 5. Array Transformations ---")
    val transformations = ArrayTransformations()
    val numbers = listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
    println("Filter even: ${transformations.filterEven(numbers)}")
    println("Filter > 5: ${transformations.filterGreaterThan(numbers, 5)}")
    println("Double elements: ${transformations.doubleElements(numbers)}")
    println("Sum: ${transformations.sum(numbers)}")
    println("Partition even/odd: ${transformations.partitionEvenOdd(numbers)}")
    println("Chunk by 3: ${transformations.chunkList(numbers, 3)}")

    // 6. Advanced operations
    println("\n--- 6. Advanced Array Operations ---")
    val advancedOps = AdvancedArrayOperations()
    val toReverse = mutableListOf(1, 2, 3, 4, 5)
    println("Reverse: ${advancedOps.reverse(toReverse)}")

    val arr1 = listOf(1, 3, 5, 7)
    val arr2 = listOf(2, 4, 6, 8)
    println("Merge sorted: ${advancedOps.mergeSortedArrays(arr1, arr2)}")
    println("Intersection: ${advancedOps.intersection(listOf(1, 2, 3), listOf(2, 3, 4))}")
    println("Union: ${advancedOps.union(listOf(1, 2, 3), listOf(3, 4, 5))}")
    println("Distinct: ${advancedOps.removeDuplicates(listOf(1, 2, 2, 3, 3, 3))}")

    println("\n=== All Array Operations Examples Completed ===")
}

// Android Kotlin Hash Table (Map) Operations Examples
// Using Map, MutableMap, HashMap, and LinkedHashMap

// 1. Basic Map Operations
class BasicMapOperations {

    // Create and initialize maps
    fun createMaps() {
        // Using mapOf (immutable)
        val immutableMap = mapOf(
            "name" to "John",
            "age" to 30,
            "city" to "New York"
        )
        println("Immutable map: $immutableMap")

        // Using mutableMapOf (mutable)
        val mutableMap = mutableMapOf(
            "name" to "Jane",
            "age" to 25,
            "city" to "London"
        )
        println("Mutable map: $mutableMap")

        // Using HashMap
        val hashMap = HashMap<String, Int>()
        hashMap["one"] = 1
        hashMap["two"] = 2
        hashMap["three"] = 3
        println("HashMap: $hashMap")

        // Using LinkedHashMap (preserves insertion order)
        val linkedHashMap = linkedMapOf(
            "first" to 1,
            "second" to 2,
            "third" to 3
        )
        println("LinkedHashMap: $linkedHashMap")

        // Using SortedMap (TreeMap equivalent)
        val sortedMap = sortedMapOf(
            "c" to 3,
            "a" to 1,
            "b" to 2
        )
        println("SortedMap: $sortedMap")
    }

    // Access elements
    fun accessElements(map: Map<String, Int>) {
        println("Get 'a': ${map["a"]}")
        println("Get 'a' with getValue: ${map.getValue("a")}")
        println("Get 'x' with null: ${map["x"]}")

        // Safe access with default
        println("Get 'x' with default: ${map.getOrDefault("x", -1)}")

        // Safe access with lazy default
        println("Get 'x' with lazy default: ${map.getOrPut("x") { -1 }}")
    }

    // Check key/value existence
    fun checkExistence(map: Map<String, Int>) {
        println("Contains key 'a': ${"a" in map}")
        println("Contains key 'x': ${map.containsKey("x")}")
        println("Contains value 1: ${map.containsValue(1)}")

        println("Keys: ${map.keys}")
        println("Values: ${map.values}")
    }

    // Get map size
    fun getSize(map: Map<String, Int>) {
        println("Size: ${map.size}")
        println("Is empty: ${map.isEmpty()}")
    }
}

// 2. Mutable Map Operations
class MutableMapOperations {

    // Add/Update entries
    fun addEntries() {
        val map = mutableMapOf<String, Int>()

        // Add entries
        map["one"] = 1
        map["two"] = 2
        map["three"] = 3
        println("After adding: $map")

        // Update existing entry
        map["two"] = 20
        println("After updating 'two': $map")

        // Use put
        map.put("four", 4)
        println("After put 'four': $map")

        // putAll
        map.putAll(mapOf("five" to 5, "six" to 6))
        println("After putAll: $map")

        // getOrPut (get if exists, otherwise put and return)
        val value = map.getOrPut("seven") { 7 }
        println("getOrPut 'seven': $value")
        println("Map after getOrPut: $map")
    }

    // Remove entries
    fun removeEntries() {
        val map = mutableMapOf(
            "a" to 1,
            "b" to 2,
            "c" to 3,
            "d" to 4
        )

        // Remove by key
        map.remove("b")
        println("After remove 'b': $map")

        // Remove by key and value
        map.remove("c", 3)
        println("After remove 'c' with value 3: $map")

        // Remove multiple keys
        map.keys.remove("d")
        println("After remove 'd': $map")

        // Clear all
        map.clear()
        println("After clear: $map")
    }

    // Batch operations
    fun batchOperations() {
        val map1 = mutableMapOf("a" to 1, "b" to 2, "c" to 3)
        val map2 = mapOf("d" to 4, "e" to 5)

        // Put all from another map
        map1.putAll(map2)
        println("After putAll: $map1")

        // Retain only certain keys
        map1.keys.retainAll(listOf("a", "c"))
        println("After retain 'a' and 'c': $map1")

        // Remove all keys in collection
        map1.keys.removeAll(listOf("a"))
        println("After removeAll 'a': $map1")
    }
}

// 3. Map Iteration
class MapIteration {

    // Iterate over entries
    fun iterateEntries(map: Map<String, Int>) {
        println("--- Iterate Entries ---")
        for ((key, value) in map) {
            println("$key = $value")
        }
    }

    // Iterate over keys
    fun iterateKeys(map: Map<String, Int>) {
        println("\n--- Iterate Keys ---")
        for (key in map.keys) {
            println("Key: $key")
        }
    }

    // Iterate over values
    fun iterateValues(map: Map<String, Int>) {
        println("\n--- Iterate Values ---")
        for (value in map.values) {
            println("Value: $value")
        }
    }

    // forEach iteration
    fun forEachIteration(map: Map<String, Int>) {
        println("\n--- forEach ---")
        map.forEach { (key, value) ->
            println("$key -> $value")
        }
    }

    // Filter entries
    fun filterEntries(map: Map<String, Int>): Map<String, Int> {
        return map.filter { (key, value) ->
            key.startsWith("a") && value > 2
        }
    }

    // Map entries
    fun mapEntries(map: Map<String, Int>): Map<String, Int> {
        return map.mapValues { it.value * 2 }
    }
}

// 4. Advanced Map Operations
class AdvancedMapOperations {

    // Group by
    fun groupByExample(words: List<String>): Map<Int, List<String>> {
        return words.groupBy { it.length }
    }

    // Associate with
    fun associateWithExample(names: List<String>): Map<String, Int> {
        return names.associateWith { it.length }
    }

    // Associate to (custom mapping)
    fun associateExample(users: List<User>): Map<Int, String> {
        return users.associate { it.id to it.name }
    }

    data class User(val id: Int, val name: String)

    // Flat map to map
    fun flattenToMap(lists: List<List<Pair<String, Int>>>): Map<String, Int> {
        return lists.flatMap { it }.toMap()
    }

    // Merge maps
    fun mergeMaps(map1: Map<String, Int>, map2: Map<String, Int>): Map<String, Int> {
        val result = mutableMapOf<String, Int>()
        result.putAll(map1)

        map2.forEach { (key, value) ->
            result[key] = (result[key] ?: 0) + value
        }

        return result
    }

    // Map with default values
    fun mapWithDefaultValues(): Map<String, Int> {
        val map = mutableMapOf<String, Int>()

        // Provide default for missing keys
        fun getValue(key: String): Int {
            return map.getOrDefault(key, 0)
        }

        map["a"] = 1
        map["b"] = 2

        println("Get 'a': ${getValue("a")}")
        println("Get 'x' with default: ${getValue("x")}")

        return map
    }

    // Multi-map (one key, multiple values)
    fun multiMapExample(): Map<String, MutableList<Int>> {
        val multiMap = mutableMapOf<String, MutableList<Int>>()

        fun addValue(key: String, value: Int) {
            multiMap.getOrPut(key) { mutableListOf() }.add(value)
        }

        addValue("numbers", 1)
        addValue("numbers", 2)
        addValue("numbers", 3)
        addValue("letters", 100)

        println("Multi-map: $multiMap")

        return multiMap
    }

    // Cache implementation using map
    class SimpleCache<K, V>(private val maxSize: Int = 100) {
        private val cache = LinkedHashMap<K, V>()

        fun get(key: K): V? {
            return cache[key]
        }

        fun put(key: K, value: V) {
            // Implement simple LRU by removing oldest if at max size
            if (cache.size >= maxSize && !cache.containsKey(key)) {
                val oldestKey = cache.keys.first()
                cache.remove(oldestKey)
            }
            cache[key] = value
        }

        fun remove(key: K) {
            cache.remove(key)
        }

        fun clear() {
            cache.clear()
        }

        fun size(): Int = cache.size

        override fun toString(): String {
            return cache.toString()
        }
    }
}

// 5. Common Use Cases
class MapUseCases {

    // Word frequency counter
    fun wordFrequency(text: String): Map<String, Int> {
        val words = text.lowercase().split(Regex("\\s+"))
        val frequency = mutableMapOf<String, Int>()

        for (word in words) {
            frequency[word] = frequency.getOrDefault(word, 0) + 1
        }

        return frequency
    }

    // Build index
    fun buildIndex(items: List<Pair<String, Int>>): Map<String, List<Int>> {
        val index = mutableMapOf<String, MutableList<Int>>()

        for ((key, value) in items) {
            index.getOrPut(key) { mutableListOf() }.add(value)
        }

        return index
    }

    // Count occurrences
    fun countOccurrences(list: List<Int>): Map<Int, Int> {
        val count = mutableMapOf<Int, Int>()

        for (item in list) {
            count[item] = count.getOrDefault(item, 0) + 1
        }

        return count
    }

    // Group and aggregate
    fun groupAndAggregate(data: List<Sale>): Map<String, Double> {
        return data.groupBy { it.category }
            .mapValues { it.value.sumOf { sale -> sale.amount } }
    }

    data class Sale(val category: String, val amount: Double)

    // Two-sum problem
    fun twoSum(nums: List<Int>, target: Int): Pair<Int, Int>? {
        val map = mutableMapOf<Int, Int>()

        for ((index, num) in nums.withIndex()) {
            val complement = target - num
            if (map.containsKey(complement)) {
                return Pair(map[complement]!!, index)
            }
            map[num] = index
        }

        return null
    }
}

// Main demonstration
fun demonstrateHashTableOperations() {
    println("=== Kotlin Hash Table (Map) Operations Examples ===\n")

    // 1. Basic operations
    println("--- 1. Basic Map Operations ---")
    val basicOps = BasicMapOperations()
    basicOps.createMaps()

    val sampleMap = mapOf("a" to 1, "b" to 2, "c" to 3)
    basicOps.accessElements(sampleMap)
    basicOps.checkExistence(sampleMap)
    basicOps.getSize(sampleMap)

    // 2. Mutable operations
    println("\n--- 2. Mutable Map Operations ---")
    val mutableOps = MutableMapOperations()
    mutableOps.addEntries()
    mutableOps.removeEntries()
    mutableOps.batchOperations()

    // 3. Iteration
    println("\n--- 3. Map Iteration ---")
    val iteration = MapIteration()
    val mapToIterate = mapOf("a" to 1, "b" to 2, "c" to 3)
    iteration.iterateEntries(mapToIterate)
    iteration.forEachIteration(mapToIterate)
    println("Filtered entries: ${iteration.filterEntries(mapToIterate)}")
    println("Mapped values: ${iteration.mapEntries(mapToIterate)}")

    // 4. Advanced operations
    println("\n--- 4. Advanced Map Operations ---")
    val advancedOps = AdvancedMapOperations()
    println("Group by length: ${advancedOps.groupByExample(listOf("apple", "pie", "banana", "kiwi"))}")
    println("Associate with: ${advancedOps.associateWithExample(listOf("apple", "pie", "banana"))}")

    val users = listOf(
        AdvancedMapOperations.User(1, "Alice"),
        AdvancedMapOperations.User(2, "Bob"),
        AdvancedMapOperations.User(3, "Charlie")
    )
    println("Associate: ${advancedOps.associateExample(users)}")

    println("Merged maps: ${advancedOps.mergeMaps(
        mapOf("a" to 1, "b" to 2),
        mapOf("b" to 3, "c" to 4)
    )}")

    println("Multi-map: ${advancedOps.multiMapExample()}")

    // 5. Cache
    println("\n--- Cache Example ---")
    val cache = AdvancedMapOperations.SimpleCache<String, String>(3)
    cache.put("key1", "value1")
    cache.put("key2", "value2")
    cache.put("key3", "value3")
    println("Cache: $cache")
    cache.put("key4", "value4") // Should evict key1
    println("Cache after adding key4: $cache")

    // 6. Use cases
    println("\n--- 5. Common Use Cases ---")
    val useCases = MapUseCases()
    val text = "hello world hello kotlin kotlin kotlin"
    println("Word frequency: ${useCases.wordFrequency(text)}")

    println("Count occurrences: ${useCases.countOccurrences(listOf(1, 2, 2, 3, 3, 3))}")

    val sales = listOf(
        MapUseCases.Sale("Food", 10.0),
        MapUseCases.Sale("Clothes", 20.0),
        MapUseCases.Sale("Food", 15.0)
    )
    println("Group and aggregate: ${useCases.groupAndAggregate(sales)}")

    println("Two sum (target=9): ${useCases.twoSum(listOf(2, 7, 11, 15), 9)}")

    println("\n=== All Hash Table Operations Examples Completed ===")
}

// Android Kotlin Linked List Operations Examples
// Using LinkedList from collections and custom implementation

import java.util.LinkedList

// 1. Using Built-in LinkedList
class BuiltInLinkedListExample {

    // Create and initialize
    fun createLinkedList() {
        // Using LinkedList class
        val list = LinkedList<Int>()
        list.add(1)
        list.add(2)
        list.add(3)
        println("LinkedList: $list")

        // Initialize from list
        val list2 = LinkedList(listOf(10, 20, 30))
        println("From list: $list2")

        // Initialize with elements
        val list3 = LinkedList(listOf(1, 2, 3, 4, 5))
        println("LinkedListOf: $list3")
    }

    // Add elements
    fun addElements() {
        val list = LinkedList<Int>()

        // Add to end
        list.add(1)
        list.add(2)
        println("Add to end: $list")

        // Add to beginning
        list.addFirst(0)
        println("Add first: $list")

        // Add to end (explicit)
        list.addLast(3)
        println("Add last: $list")

        // Add at index
        list.add(2, 99)
        println("Add at index 2: $list")

        // Add all from another collection
        list.addAll(listOf(100, 200))
        println("Add all: $list")
    }

    // Remove elements
    fun removeElements() {
        val list = LinkedList(listOf(1, 2, 3, 4, 5))

        // Remove first
        list.removeFirst()
        println("After remove first: $list")

        // Remove last
        list.removeLast()
        println("After remove last: $list")

        // Remove by value
        list.remove(3)
        println("After remove 3: $list")

        // Remove at index
        list.removeAt(0)
        println("After remove at 0: $list")

        // Clear all
        list.clear()
        println("After clear: $list")
    }

    // Access elements
    fun accessElements(list: LinkedList<Int>) {
        println("First element: ${list.first}")
        println("Last element: ${list.last}")
        println("Element at index 2: ${list[2]}")

        // Get first and last safely
        println("FirstOrNull: ${list.firstOrNull()}")
        println("LastOrNull: ${list.lastOrNull()}")
    }

    // LinkedList as Queue (FIFO)
    fun queueOperations() {
        val queue = LinkedList<String>()

        // Enqueue (add)
        queue.add("Task 1")
        queue.add("Task 2")
        queue.add("Task 3")
        println("Queue: $queue")

        // Dequeue (remove from front)
        val task = queue.removeFirst()
        println("Processed: $task")
        println("Remaining: $queue")

        // Peek at first element
        println("Next task: ${queue.first}")
    }

    // LinkedList as Stack (LIFO)
    fun stackOperations() {
        val stack = LinkedList<Int>()

        // Push (add to front)
        stack.push(1)
        stack.push(2)
        stack.push(3)
        println("Stack: $stack")

        // Pop (remove from front)
        val item = stack.pop()
        println("Popped: $item")
        println("Remaining: $stack")

        // Peek at top
        println("Top: ${stack.first}")
    }
}

// 2. Custom Singly Linked List Implementation
class SinglyLinkedList<T> {

    private class Node<T>(var data: T, var next: Node<T>? = null)

    private var head: Node<T>? = null
    private var size: Int = 0

    // Add to end
    fun add(data: T) {
        val newNode = Node(data)

        if (head == null) {
            head = newNode
        } else {
            var current = head
            while (current?.next != null) {
                current = current?.next
            }
            current?.next = newNode
        }
        size++
    }

    // Add to beginning
    fun addFirst(data: T) {
        val newNode = Node(data, head)
        head = newNode
        size++
    }

    // Add at index
    fun add(index: Int, data: T) {
        if (index < 0 || index > size) {
            throw IndexOutOfBoundsException("Index: $index, Size: $size")
        }

        if (index == 0) {
            addFirst(data)
        } else {
            val newNode = Node(data)
            var current = head
            for (i in 0 until index - 1) {
                current = current?.next
            }
            newNode.next = current?.next
            current?.next = newNode
            size++
        }
    }

    // Remove by index
    fun remove(index: Int): T? {
        if (index < 0 || index >= size) {
            throw IndexOutOfBoundsException("Index: $index, Size: $size")
        }

        if (index == 0) {
            val data = head?.data
            head = head?.next
            size--
            return data
        }

        var current = head
        for (i in 0 until index - 1) {
            current = current?.next
        }

        val data = current?.next?.data
        current?.next = current?.next?.next
        size--

        return data
    }

    // Remove by value
    fun removeByValue(data: T): Boolean {
        if (head == null) return false

        if (head?.data == data) {
            head = head?.next
            size--
            return true
        }

        var current = head
        while (current?.next != null) {
            if (current?.next?.data == data) {
                current?.next = current?.next?.next
                size--
                return true
            }
            current = current?.next
        }

        return false
    }

    // Get element at index
    fun get(index: Int): T? {
        if (index < 0 || index >= size) {
            throw IndexOutOfBoundsException("Index: $index, Size: $size")
        }

        var current = head
        for (i in 0 until index) {
            current = current?.next
        }

        return current?.data
    }

    // Find index of value
    fun indexOf(data: T): Int {
        var current = head
        var index = 0

        while (current != null) {
            if (current.data == data) {
                return index
            }
            current = current.next
            index++
        }

        return -1
    }

    // Check if contains value
    fun contains(data: T): Boolean {
        return indexOf(data) != -1
    }

    // Get size
    fun getSize(): Int = size

    // Check if empty
    fun isEmpty(): Boolean = head == null

    // Clear list
    fun clear() {
        head = null
        size = 0
    }

    // Convert to list
    fun toList(): List<T> {
        val result = mutableListOf<T>()
        var current = head

        while (current != null) {
            result.add(current.data)
            current = current.next
        }

        return result
    }

    // Reverse list
    fun reverse() {
        var prev: Node<T>? = null
        var current = head

        while (current != null) {
            val next = current.next
            current.next = prev
            prev = current
            current = next
        }

        head = prev
    }

    override fun toString(): String {
        return toList().toString()
    }
}

// 3. Custom Doubly Linked List Implementation
class DoublyLinkedList<T> {

    private class Node<T>(
        var data: T,
        var prev: Node<T>? = null,
        var next: Node<T>? = null
    )

    private var head: Node<T>? = null
    private var tail: Node<T>? = null
    private var size: Int = 0

    // Add to end
    fun add(data: T) {
        val newNode = Node(data)

        if (tail == null) {
            head = newNode
            tail = newNode
        } else {
            tail?.next = newNode
            newNode.prev = tail
            tail = newNode
        }
        size++
    }

    // Add to beginning
    fun addFirst(data: T) {
        val newNode = Node(data)

        if (head == null) {
            head = newNode
            tail = newNode
        } else {
            newNode.next = head
            head?.prev = newNode
            head = newNode
        }
        size++
    }

    // Remove from end
    fun removeLast(): T? {
        if (tail == null) return null

        val data = tail?.data
        if (head === tail) {
            head = null
            tail = null
        } else {
            tail = tail?.prev
            tail?.next = null
        }
        size--

        return data
    }

    // Remove from beginning
    fun removeFirst(): T? {
        if (head == null) return null

        val data = head?.data
        if (head === tail) {
            head = null
            tail = null
        } else {
            head = head?.next
            head?.prev = null
        }
        size--

        return data
    }

    // Traverse forward
    fun traverseForward(): List<T> {
        val result = mutableListOf<T>()
        var current = head

        while (current != null) {
            result.add(current.data)
            current = current.next
        }

        return result
    }

    // Traverse backward
    fun traverseBackward(): List<T> {
        val result = mutableListOf<T>()
        var current = tail

        while (current != null) {
            result.add(current.data)
            current = current.prev
        }

        return result
    }

    fun getSize(): Int = size

    override fun toString(): String {
        return traverseForward().toString()
    }
}

// 4. Linked List Algorithms
class LinkedListAlgorithms {

    // Detect cycle (Floyd's Cycle Detection)
    fun <T> hasCycle(list: SinglyLinkedList<T>): Boolean {
        // This is a conceptual example
        // In practice, you'd need access to internal nodes
        return false
    }

    // Find middle element
    fun <T> findMiddle(list: LinkedList<T>): T? {
        var slow = list.listIterator()
        var fast = list.listIterator()

        while (fast.hasNext() && fast.hasNext()) {
            slow.next()
            fast.next()
            if (fast.hasNext()) fast.next()
        }

        return if (slow.hasNext()) slow.next() else null
    }

    // Reverse linked list (using built-in operations)
    fun <T> reverseList(list: LinkedList<T>): LinkedList<T> {
        val reversed = LinkedList<T>()
        list.descendingIterator().forEach { reversed.add(it) }
        return reversed
    }

    // Merge two sorted lists
    fun <T : Comparable<T>> mergeSortedLists(
        list1: LinkedList<T>,
        list2: LinkedList<T>
    ): LinkedList<T> {
        val result = LinkedList<T>()
        val iter1 = list1.iterator()
        val iter2 = list2.iterator()

        var current1 = if (iter1.hasNext()) iter1.next() else null
        var current2 = if (iter2.hasNext()) iter2.next() else null

        while (current1 != null && current2 != null) {
            if (current1.compareTo(current2) <= 0) {
                result.add(current1)
                current1 = if (iter1.hasNext()) iter1.next() else null
            } else {
                result.add(current2)
                current2 = if (iter2.hasNext()) iter2.next() else null
            }
        }

        while (current1 != null) {
            result.add(current1)
            current1 = if (iter1.hasNext()) iter1.next() else null
        }

        while (current2 != null) {
            result.add(current2)
            current2 = if (iter2.hasNext()) iter2.next() else null
        }

        return result
    }

    // Remove duplicates from sorted list
    fun <T : Comparable<T>> removeDuplicates(list: LinkedList<T>): LinkedList<T> {
        if (list.size <= 1) return list

        val iterator = list.listIterator()
        var prev: T? = null

        while (iterator.hasNext()) {
            val current = iterator.next()
            if (prev != null && current == prev) {
                iterator.remove()
            }
            prev = current
        }

        return list
    }
}

// Main demonstration
fun demonstrateLinkedListOperations() {
    println("=== Kotlin Linked List Operations Examples ===\n")

    // 1. Built-in LinkedList
    println("--- 1. Built-in LinkedList ---")
    val builtIn = BuiltInLinkedListExample()
    builtIn.createLinkedList()
    builtIn.addElements()
    builtIn.removeElements()

    val sampleList = LinkedList(listOf(10, 20, 30, 40, 50))
    builtIn.accessElements(sampleList)
    builtIn.queueOperations()
    builtIn.stackOperations()

    // 2. Custom Singly Linked List
    println("\n--- 2. Custom Singly Linked List ---")
    val customList = SinglyLinkedList<Int>()

    customList.add(1)
    customList.add(2)
    customList.add(3)
    println("After adds: $customList")

    customList.addFirst(0)
    println("After addFirst: $customList")

    customList.add(2, 99)
    println("After add at index 2: $customList")

    println("Get index 2: ${customList.get(2)}")
    println("Index of 99: ${customList.indexOf(99)}")
    println("Contains 3: ${customList.contains(3)}")

    customList.remove(2)
    println("After remove index 2: $customList")

    customList.reverse()
    println("After reverse: $customList")

    println("Size: ${customList.getSize()}")

    // 3. Custom Doubly Linked List
    println("\n--- 3. Custom Doubly Linked List ---")
    val doublyList = DoublyLinkedList<String>()

    doublyList.add("First")
    doublyList.add("Second")
    doublyList.add("Third")
    println("Forward: ${doublyList.traverseForward()}")

    doublyList.addFirst("Zero")
    println("After addFirst: ${doublyList.traverseForward()}")

    println("Backward: ${doublyList.traverseBackward()}")

    println("Removed last: ${doublyList.removeLast()}")
    println("Removed first: ${doublyList.removeFirst()}")
    println("Remaining: ${doublyList.traverseForward()}")

    // 4. Linked List Algorithms
    println("\n--- 4. Linked List Algorithms ---")
    val algorithms = LinkedListAlgorithms()

    val list1 = LinkedList(listOf(1, 3, 5, 7))
    val list2 = LinkedList(listOf(2, 4, 6, 8))
    println("Merged: ${algorithms.mergeSortedLists(list1, list2)}")

    val listWithDupes = LinkedList(listOf(1, 1, 2, 2, 3, 3))
    println("Without duplicates: ${algorithms.removeDuplicates(listWithDupes)}")

    val listToReverse = LinkedList(listOf(1, 2, 3, 4, 5))
    println("Reversed: ${algorithms.reverseList(listToReverse)}")

    println("\n=== All Linked List Operations Examples Completed ===")
}