Package dsc_suite :: Package ds :: Module o_sequence
[hide private]
[frames] | no frames]

Source Code for Module dsc_suite.ds.o_sequence

  1  """module ds.o_sequence 
  2   
  3  module implementing the o-sequence data structure 
  4  """ 
  5  from dsc_suite.ds.data_structure import DataStructure 
  6  from dsc_suite.tools.combinatorics import EnumerativeCombinatorics 
  7  from random import randrange, randint 
  8   
  9   
 10  ##### SEQUENCE TRIPLE SUBCLASS ################################################# 
11 -class OSequence(DataStructure):
12 """ class OSequence(DataStructure) - O-Sequence implementation 13 14 O-Sequence format : [module_permutation, section_variation, wall_combination, block_rotations, o_sequence] 15 16 o_sequence optional, None if not given 17 18 TODO: detailed docstring 19 """ 20 name = 'O Sequence' 21
22 - def __init__(self, benchmark):
23 assert(benchmark.status['number of dimensions'] == 3) 24 DataStructure.__init__(self, benchmark) 25 #from operator import mul 26 from dsc_suite.tools.math import fak 27 # maybe better combined in a status dictionary 28 self.num_blocks = len(benchmark.blocks) 29 self.num_parts = 3 + 1 + 1 30 self.part_lengths = [fak(self.num_blocks), 3**(self.num_blocks-1), 'unknown', 2**self.num_blocks, 'unknown'] 31 self.num_representations = 'unknown' #reduce(mul, self.part_lengths)
32 # if constructor call takes to long comment out 33 #self.update_balancing() 34 35
36 - def get_part_of_representation(self, part_index, part_number):
37 """ 38 get a single element out of a part of the abstract 39 representation, part_number between 0 and part_lengths[part_index] 40 """ 41 # parameter part_index is not used here because all three 42 # sequences are equal, but for other data structures or by adding 43 # a rotation sequence, this parameter is useful 44 if part_index == 0: 45 return EnumerativeCombinatorics.get_permutation(self.benchmark.blocks, part_number) 46 elif part_index == 1: 47 return EnumerativeCombinatorics.get_variation(['X', 'Y', 'Z'], 48 len(self.benchmark.blocks-1), part_number) 49 elif part_index == 2: 50 return 'unknown' 51 elif part_index == 3: 52 return EnumerativeCombinatorics.get_variation([self.ORIGINAL, self.ROTATED], 53 len(self.benchmark.blocks), part_number)
54
55 - def packing_to_representation(self, packing):
56 print "Not implemented and/or available!"
57
59 """ 60 still required to test if random solutions are evenly distributed! 61 """ 62 n = self.num_blocks 63 sv = [] 64 wc = [] 65 p = [] 66 contingent = {'X' : [n], 67 'Y' : [n], 68 'Z' : [n]} 69 i = n - 1 70 while i > 0: 71 sv.insert(0, ['X', 'Y', 'Z'][randrange(3)]) 72 len_cont = len(contingent[sv[0]]) 73 valid_wc_candidates = [] 74 for wc_candidate in range(1, len_cont+1): 75 good_candidate = True 76 for l in range(contingent[sv[0]][-wc_candidate]+1, n + 1): 77 a = True 78 b = False 79 for j in contingent[sv[0]][len_cont-wc_candidate+1:]: 80 if (p[j-i-1][0] != sv[0]) and (l in p[j-i-1][1:]): 81 a = False 82 for j in range(contingent[sv[0]][-wc_candidate], l): 83 if (p[j-i-1][0] == sv[0]) and (l in p[j-i-1][1:]): 84 b = True 85 if not (a or b): 86 good_candidate = False 87 if good_candidate: 88 valid_wc_candidates.append(wc_candidate) 89 wc.insert(0, valid_wc_candidates[randrange(len(valid_wc_candidates))]) 90 p.insert(0, [sv[0]] + contingent[sv[0]][-wc[0]:]) 91 del contingent[sv[0]][-wc[0]:] 92 contingent['X'].append(i) 93 contingent['Y'].append(i) 94 contingent['Z'].append(i) 95 i -= 1 96 temp = [] 97 for sd in ['X', 'Y', 'Z']: 98 temp.append([sd] + contingent[sd]) 99 p.insert(0, temp) 100 module_permutation = EnumerativeCombinatorics.get_permutation(self.benchmark.blocks, randrange(self.part_lengths[0])) 101 block_rotations = EnumerativeCombinatorics.get_variation([self.ORIGINAL, self.ROTATED], len(self.benchmark.blocks), randrange(self.part_lengths[3])) 102 # sv ... section_variation 103 # wc ... wall_combination 104 return [module_permutation, sv, wc, block_rotations, p]
105
106 - def get_P(self, slicing_variation, wall_count):
107 P_list = [] 108 sv, wc = slicing_variation, wall_count 109 i = len(sv) 110 #P_list.insert(0, i+1) 111 contingent = {'X' : [i+1], 112 'Y' : [i+1], 113 'Z' : [i+1]} 114 while i > 0: 115 if len(contingent[sv[i-1]]) < wc[i-1]: 116 return None 117 P_list.insert(0, [sv[i-1]] + contingent[sv[i-1]][-wc[i-1]:]) 118 del contingent[sv[i-1]][-wc[i-1]:] 119 #P_list.insert(0, i) 120 contingent['X'].append(i) 121 contingent['Y'].append(i) 122 contingent['Z'].append(i) 123 i -= 1 124 temp = [] 125 for sd in ['X', 'Y', 'Z']: 126 temp.append([sd] + contingent[sd]) 127 P_list.insert(0, temp) 128 return P_list
129
130 - def pair_check(self, P_list):
131 for sd in ['X', 'Y', 'Z']: 132 test = filter(lambda x:x[0]==sd, P_list[0])[0][1:] 133 i = 1 134 if test[-1] == i: 135 del test[-1] 136 else: 137 return False 138 while i < len(P_list): 139 if P_list[i][0] == sd: 140 # open new pair 141 test += P_list[i][1:] 142 # close pair 143 i += 1 144 if test[-1] == i: 145 del test[-1] 146 else: 147 return False 148 return True
149
150 - def test_no3(self, P_list):
151 p = P_list 152 n = len(p) 153 i = 1 154 while i < n: 155 for l in range(p[i][1]+1, n+1): 156 a = True 157 b = False 158 for j in p[i][2:]: 159 if (p[j][0] != p[i][0]) and (l in p[j][1:]): 160 a = False 161 for j in range(p[i][1], l): 162 if (p[j][0] == p[i][0]) and (l in p[j][1:]): 163 b = True 164 if not (a or b): 165 return False 166 i += 1 167 return True
168 169
170 - def is_valid(self, representation):
171 """ check if given o-sequence is valid. 172 173 O-Sequence format : [module_permutation, section_variation, wall_combination, block_rotations] 174 175 #1: section_variation[i] sequence of exclusively X, Y or Z, length at least 1 -> given 176 #2: parenthesis system, ordered pairing (X_k, k), (Y_k, k) and (Z_k, k) for k = 1, 2, ..., n 177 #3: previously used walls do not conflict with current ones 178 """ 179 p = self.get_P(representation[1], representation[2]) 180 return self.pair_check(p) and self.test_no3(p)
181 182
183 - def create_packing(self, representation):
184 """ Return packing in dict format. 185 packing = {'name' : [x, y, z, w, h, d], ...} 186 """ 187 p = representation[4] 188 if p == None: 189 sv, wc = representation[1:3] 190 p = self.get_P(sv, wc) 191 mn = representation[0] 192 rotations = representation[3] 193 dims = self.benchmark.dimensions 194 widths = dict(zip(dims.keys(), zip(*dims.values())[0])) 195 heights = dict(zip(dims.keys(), zip(*dims.values())[1])) 196 depths = dict(zip(dims.keys(), zip(*dims.values())[2])) 197 for i in range(len(rotations)): 198 if rotations[i] == self.ROTATED: 199 block = self.benchmark.blocks[i] 200 widths[block], heights[block] = heights[block], widths[block] 201 n = len(p) 202 packing = {} 203 packing[mn[0]] = [0, 0, 0, 204 widths[mn[0]], 205 heights[mn[0]], 206 depths[mn[0]]] 207 for k in range(n-1, 0, -1): 208 mod_k = mn[-k] 209 if p[k][0] == 'X': 210 x = max([packing[mn[-r]][0]+packing[mn[-r]][3] for r in p[k][1:]]) 211 y = min([packing[mn[-r]][1] for r in p[k][1:]]) 212 z = min([packing[mn[-r]][2] for r in p[k][1:]]) 213 packing[mod_k] = [x, y, z, 214 widths[mod_k], 215 heights[mod_k], 216 depths[mod_k]] 217 elif p[k][0] == 'Y': 218 x = min([packing[mn[-r]][0] for r in p[k][1:]]) 219 y = max([packing[mn[-r]][1]+packing[mn[-r]][4] for r in p[k][1:]]) 220 z = min([packing[mn[-r]][2] for r in p[k][1:]]) 221 packing[mod_k] = [x, y, z, 222 widths[mod_k], 223 heights[mod_k], 224 depths[mod_k]] 225 elif p[k][0] == 'Z': 226 x = min([packing[mn[-r]][0] for r in p[k][1:]]) 227 y = min([packing[mn[-r]][1] for r in p[k][1:]]) 228 z = max([packing[mn[-r]][2]+packing[mn[-r]][5] for r in p[k][1:]]) 229 packing[mod_k] = [x, y, z, 230 widths[mod_k], 231 heights[mod_k], 232 depths[mod_k]] 233 return packing
234