Appearance
| 1 | namespace IR.Program is | |
| 2 | use Collections.LIST | |
| 3 | use Collections.MAP | |
| 4 | use Collections.SET | |
| 5 | ||
| 6 | /// Packs sparse rows into one table so that each row's entries keep | |
| 7 | /// their columns relative to the row's offset and no two rows claim | |
| 8 | /// the same slot. Reading `offset(row) + column` then finds exactly the | |
| 9 | /// entry `row` has at `column`. | |
| 10 | /// | |
| 11 | /// Rows are placed largest first, each at the lowest offset where all | |
| 12 | /// of its columns are free. | |
| 13 | class ROW_DISPLACEMENT[T] is | |
| 14 | _rows: LIST[(key: T, columns: LIST[int])] | |
| 15 | _offsets: MAP[T, int] | |
| 16 | _size: int | |
| 17 | ||
| 18 | init() is | |
| 19 | _rows = LIST[(key: T, columns: LIST[int])]() | |
| 20 | _offsets = MAP[T, int]() | |
| 21 | si | |
| 22 | ||
| 23 | /// Adds a row that has entries at `columns`, each zero or more. | |
| 24 | add(key: T, columns: Collections.Iterable[int]) is | |
| 25 | _rows.add((key, LIST[int](columns))) | |
| 26 | si | |
| 27 | ||
| 28 | /// Places every row added; call after the last one. | |
| 29 | pack() is | |
| 30 | _offsets.clear() | |
| 31 | _size = 0 | |
| 32 | ||
| 33 | let order = LIST[(key: T, columns: LIST[int])](_rows) | |
| 34 | ||
| 35 | order.sort((a, b) => b.columns.count - a.columns.count) | |
| 36 | ||
| 37 | let used = SET[int]() | |
| 38 | ||
| 39 | for row in order do | |
| 40 | let offset mut = 0 | |
| 41 | ||
| 42 | while !_fits(row.columns, offset, used) do | |
| 43 | offset = offset + 1 | |
| 44 | od | |
| 45 | ||
| 46 | for column in row.columns do | |
| 47 | used.add(offset + column) | |
| 48 | ||
| 49 | if offset + column + 1 > _size then | |
| 50 | _size = offset + column + 1 | |
| 51 | fi | |
| 52 | od | |
| 53 | ||
| 54 | _offsets[row.key] = offset | |
| 55 | od | |
| 56 | si | |
| 57 | ||
| 58 | _fits(columns: LIST[int], offset: int, used: SET[int]) -> bool is | |
| 59 | for column in columns do | |
| 60 | if used.contains(offset + column) then | |
| 61 | return false | |
| 62 | fi | |
| 63 | od | |
| 64 | ||
| 65 | return true | |
| 66 | si | |
| 67 | ||
| 68 | /// Where the row for `key` starts. | |
| 69 | offset(key: T) -> int => _offsets[key] | |
| 70 | ||
| 71 | /// One past the highest slot any row uses. | |
| 72 | size: int => _size | |
| 73 | si | |
| 74 | si |