1#!/usr/bin/python
2#
3# Copyright 2012 The Native Client Authors. All rights reserved.
4# Use of this source code is governed by a BSD-style license that can be
5# found in the LICENSE file.
6# Copyright 2012, Google Inc.
7#
8
9"""
10Table minimization algorithm.
11"""
12
13def optimize_rows(rows):
14    """Breaks rows up into batches, and attempts to minimize each batch,
15    using _optimize_rows_for_single_action.
16    """
17    rows_by_action = dict()
18    for row in rows:
19        if (row.action, row.arch) in rows_by_action:
20            rows_by_action[(row.action, row.arch)].append(row)
21        else:
22            rows_by_action[(row.action, row.arch)] = [row]
23
24    optimized_rows = []
25    for row_group in rows_by_action.itervalues():
26        optimized_rows.extend(_optimize_rows_for_single_action(row_group))
27
28    _remove_unused_columns(optimized_rows)
29    return optimized_rows
30
31def _optimize_rows_for_single_action(rows):
32    """Performs basic automatic minimization on the given rows.
33
34    Repeatedly selects a pair of rows to merge.  Recurses until no suitable pair
35    can be found.  It's not real smart, and is O(n^2).
36
37    A pair of rows is compatible if all columns are equal, or if exactly one
38    row differs but is_strictly_compatible.
39    """
40    for (i, j) in each_index_pair(rows):
41        row_i, row_j = rows[i], rows[j]
42
43        if row_i.can_merge(row_j):
44            new_rows = list(rows)
45            del new_rows[j]
46            del new_rows[i]
47            new_rows.append(row_i + row_j)
48            return _optimize_rows_for_single_action(new_rows)
49
50    # No changes made:
51    return rows
52
53def _remove_unused_columns(rows):
54    num_cols = len(rows[0].patterns)
55    used = [False] * num_cols
56
57    for r in rows:
58        for i in range(0, num_cols):
59            if r.patterns[i].mask != 0:
60                used[i] = True
61
62    if not True in used:
63        # Always preserve at least one column
64        used[0] = True
65
66    for col in range(num_cols - 1, 0 - 1, -1):
67        for r in rows:
68            if not used[col]:
69                del r.patterns[col]
70
71
72def each_index_pair(sequence):
73    """Utility function: Generates each unique index pair in sequence."""
74    for i in range(0, len(sequence)):
75        for j in range(i + 1, len(sequence)):
76            yield (i, j)
77