1 """
2 crossutil
3 =========
4 Contains all sort of utilities to search and manipulate nested lists in the
5 context of strongly-typed crossover.
6
7 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
8 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
9 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
10 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
11 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
12 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
13 THE SOFTWARE.
14
15 @author: by Mehdi Khoury
16 @version: 1.20
17 @copyright: (c) 2009 Mehdi Khoury under the mit license
18 http://www.opensource.org/licenses/mit-license.html
19
20
21 """
22
23 from collections import deque
24 import psyco
25 from copy import copy
26 import string
27
28
29 psyco.profile()
30
31
33 """
34 BillSubtreeIndices
35 ==================
36 gives the indexes of nested lists by depth
37 original idea from bill at
38 python-forum.org
39
40 @param tree_rep: a nested list representing a tree
41
42 @return: a list representing the indexes of the nested lists by depth
43
44 """
45 q = deque([ ([],tree_rep) ])
46 list_of_index_lists = []
47 while q:
48 (indices, sub_tree) = q.popleft()
49 list_of_index_lists.append(indices)
50 for (ordinal, sst) in enumerate( sub_tree[1:] ):
51 if isinstance( sst, list ):
52 idxs = indices[:]
53 idxs.append(ordinal+1)
54 q.append( (idxs, sst) )
55 return list_of_index_lists
56
57
59 """
60 BillSubtreeIndices2
61 ===================
62 gives the indexes of nested lists by depth
63 original idea from bill at
64 python-forum.org
65
66 @param tree_rep: a nested list representing a tree
67
68 @return: a dictionary representing the indexes of the nested lists by depth
69
70 """
71 q = [ ([],tree_rep) ]
72 dict_of_index_lists = {}
73 while q != []:
74 (indices, sub_tree) = q.pop(0)
75 dict_of_index_lists.setdefault(len(indices), []).append(indices)
76 for (ordinal, sst) in enumerate( sub_tree[1:] ):
77 if isinstance( sst, list ):
78 q.append( (indices[:] + [ordinal+1], sst) )
79 return dict_of_index_lists
80
81
82
84 """
85 GetIndicesMappingFromTree
86 =========================
87 reuse bill's idea to gives the indexes of all nodes (may they be
88 a sub tree or a single leaf) gives a list of indices of every sublist.
89 To do that, I add one thing: the last element of an index is the length
90 of the present list. e.g.
91 - get_indices_mapping_from_tree([1,2,3,4,5,6,7,8,9])
92 gives: [([0], 9)]
93 - get_indices_mapping_from_tree([1,[2,3],4,5,6,7,8,9])
94 gives: [([0], 8), ([1], 2)]
95 - get_indices_mapping_from_tree([1,[2,3,7],4,5,6,7,8,9])
96 gives: [([0], 8), ([1], 3)]
97 - get_indices_mapping_from_tree([1,[2,3,7],4,[5,[6,[7,8,9]]]])
98 gives: [([0], 4), ([1], 3), ([3], 2), ([3, 1], 2), ([3, 1, 1], 3)]
99
100
101 @param tree: a nested list representing a tree
102
103 @return: a nested list representing the indexes of the nested lists by depth
104
105 """
106 q = deque([ ([],tree) ])
107 list_of_index_lists = [([0],len(tree))]
108 while q:
109 (indices, sub_tree) = q.popleft()
110 list_of_index_lists.append((indices,len(sub_tree)))
111 for (ordinal, sst) in enumerate( sub_tree[1:] ):
112 if isinstance( sst, list ):
113 idxs = indices[:]
114 idxs.append(ordinal+1)
115 q.append( (idxs, sst) )
116 list_of_index_lists.pop(1)
117 return list_of_index_lists
118
119
120
122 """
123 GetDepthFromIndicesMapping
124 ==========================
125 Gives the depth of the nested list from the index mapping
126
127 @param list_indices: a nested list representing the indexes of the nested lists by depth
128
129 @return: depth
130
131 """
132 return max([len(x[0]) for x in list_indices])+1
133
134
136 """
137 GetPackedListIndicesAtDepth
138 ===========================
139 gives the indexes of nested lists at a specific depth.
140 Only works if the map of indices has been done
141
142 @param list_indices: a nested list representing the indexes of the nested lists by depth
143 @param depth: depth at which we wnat the indexes
144
145 @return: a nested list representing the indexes of the nested lists
146 at a specific depth
147
148 """
149 if depth==0:
150 return [(list_indices[0][0],1)]
151 elif depth==1:
152 result=[]
153 temp=copy(list_indices)
154 temp.pop(0)
155 temp1=[x for x in temp if len(x[0])==1]
156 if list_indices[0][1]>1:
157 for x in range(1,list_indices[0][1]):
158 if [x] not in [elem[0] for elem in temp1]:
159 result.append(([x],1) )
160 result.extend(temp1)
161 return result
162 else :
163 list_indices.pop(0)
164 return [x for x in list_indices if len(x[0])==depth]
165
166
168 """
169 UnpackIndicesFromList
170 =====================
171 unpack_indices_from_list. e.g. ([([1], 6), ([2], 4)])
172 gives: [[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [2, 2], [2, 3]]
173
174 @param map_indices: a nested list representing the indexes of the nested lists by depth
175
176 @return: the indexes of different nodes in the tree as a flat list
177
178 """
179 result=[]
180 for elem in map_indices:
181 if elem[0][0]==[0]:
182 result.append(range(1,elem[1]))
183 else:
184 if elem[1]==1:
185 temp=copy(elem[0])
186 result.append(temp)
187 else:
188 for x in range(1,elem[1]):
189 temp=copy(elem[0])
190 temp.append(x)
191 result.append(temp)
192 return result
193
194
195
197 """
198 GetDepth
199 ========
200 Gives the depth of the nested list. Slow recursive way.
201
202 @param tree_rep: a nested list representing a tree
203
204 @return: depth
205
206 """
207 return max([len(x[0]) for x in bill_subtree_indices3( tree_rep )])+1
208
209
210
212 """
213 IndexLstToIndexStr
214 ==================
215 transform a list into an index element
216 e.g. list named 'a' and index ref is [1,1,2], result is
217 '[1][1][2]'
218
219 @param index: a flat list of indexes
220
221 @return: a string
222
223 """
224 return str(index).replace(',','][')
225
226
227
228
229
231 """
232 IndexLstToIndexStr2
233 ===================
234 transform a list into an index element
235 this version is 15% faster
236 transform a list into an index element
237 e.g. list named 'a' and index ref is [1,1,2], result is
238 '[1][1][2]'
239
240 @param index: a flat list of indexes
241
242 @return: a string
243
244 """
245 ls= "[%s]"%string.join(map(str, index), "][")
246 return ls
247