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