[Kotlin]Good problem. Let's implement the core datastruct of a matching engine.
It\'s really a good problem. It\'s the core datastruct of a matching engine. I really know it cause my job is about it.\n\nUsually we use the the LMAX Architect
It\'s really a good problem. It\'s the core datastruct of a matching engine. I really know it cause my job is about it.\n\nUsually we use the the LMAX Architecture to implement a mathing engine. If you are interested in it, you can read this article [The LMAX Architecture](https://martinfowler.com/articles/lmax.html).\n\nBut unfortunately, I got a Time Limit Exceeded. I want to sovle this problem as usual as what we do when we implement it in a real situation. But it did not work in the contest. sad.\n\nA depthLine means a set of orders with the same price.\n\n```\nclass `Number of Orders in the Backlog` {\n\n    val buy = TreeMap<Int, DepthLine> { a, b ->\n        b - a\n    }\n\n    val sell = TreeMap<Int, DepthLine> { a, b ->\n        a - b\n    }\n\n    val BUY = 0\n\n    val SELL = 1\n\n    val mod = 1000000007\n\n    fun getNumberOfBacklogOrders(orders: Array<IntArray>): Int {\n        for (order in orders) {\n            for (i in 0 until order[1]) {\n                match(Order(order[0], order[2]))\n            }\n        }\n        var res = 0\n        buy.forEach {\n            res += it.value.size()\n            res = res % mod\n        }\n        sell.forEach {\n            res += it.value.size()\n            res = res % mod\n        }\n        return res\n    }\n\n    fun match(order: Order) {\n        if (order.type == SELL) {\n            match(order, buy, sell)\n        } else {\n            match(order, sell, buy)\n        }\n    }\n\n    private fun match(order: Order, book: TreeMap<Int, DepthLine>, oppositeBook: TreeMap<Int, DepthLine>) {\n        var matched = false\n        for ((price, depthLine) in book) {\n            if (order.type == SELL) {\n                if (price > order.price && depthLine.size() > 0) {\n                    depthLine.poll()\n                    matched = true\n                    break\n                }\n            } else {\n                if (price < order.price && depthLine.size() > 0) {\n                    depthLine.poll()\n                    matched = true\n                    break\n                }\n            }\n        }\n        if (!matched) {\n            val depthLine = oppositeBook[order.price]\n            if (depthLine == null) {\n                val depthLine = DepthLine(order.price)\n                oppositeBook[order.price] = depthLine\n                depthLine.offer(Order(order.price, SELL))\n            } else {\n                depthLine.offer(Order(order.price, SELL))\n            }\n        }\n    }\n\n    class DepthLine(val price: Int) {\n        val orderList = LinkedList<Order>()\n\n        fun size(): Int {\n            return orderList.size\n        }\n\n        fun offer(order: Order) {\n            orderList.offer(order)\n        }\n\n        fun poll() {\n            orderList.poll()\n        }\n    }\n\n    class Order(val price: Int, val type: Int)\n}\n```
[]