| 103 | } |
| 104 | |
| 105 | size_t Get(size_t key) const { |
| 106 | if (Data.empty()) |
| 107 | return key; // difference is zero; |
| 108 | |
| 109 | if (key < Data.front().first) |
| 110 | return key; |
| 111 | |
| 112 | // Binary search for the highest entry in the list that does not exceed the key |
| 113 | size_t from = 0; |
| 114 | size_t to = Data.size() - 1; |
| 115 | |
| 116 | while (from < to) { |
| 117 | size_t midpoint = (from + to + 1) / 2; |
| 118 | |
| 119 | if (key < Data[midpoint].first) |
| 120 | to = midpoint - 1; |
| 121 | else |
| 122 | from = midpoint; |
| 123 | } |
| 124 | |
| 125 | TSizePair entry = Data[from]; |
| 126 | |
| 127 | return key - entry.first + entry.second; |
| 128 | } |
| 129 | }; |
| 130 | |
| 131 | class TPieceComparer { |