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
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
23 assert(benchmark.status['number of dimensions'] == 3)
24 DataStructure.__init__(self, benchmark)
25
26 from dsc_suite.tools.math import fak
27
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'
32
33
34
35
54
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
103
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
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
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
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
141 test += P_list[i][1:]
142
143 i += 1
144 if test[-1] == i:
145 del test[-1]
146 else:
147 return False
148 return True
149
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
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
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