KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > xquark > extractor > algebra > Numbering


1 /*
2  * This file belongs to the XQuark distribution.
3  * Copyright (C) 2003 Universite de Versailles Saint-Quentin.
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2.1 of the License, or (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this program; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307.
18  * You can also get it at http://www.gnu.org/licenses/lgpl.html
19  *
20  * For more information on this software, see http://www.xquark.org.
21  */
22
23 package org.xquark.extractor.algebra;
24
25 import java.util.ArrayList JavaDoc;
26 import java.util.List JavaDoc;
27
28 import org.xquark.extractor.common.Debug;
29 /**
30
31 query structure
32 ---------------------
33 A
34     B
35         C
36             D
37             E
38     S
39         T
40     X
41
42 SOU table sturcture
43 1 A
44 2 A B
45 3 A B C1 C2
46 4 A B C1 C2 D
47 6 A B C1 C2 E1 E2
48 7 A S
49 8 A S T
50 9 A X
51
52 initialized matrix:
53 IdNo: 1 2 3 4 5 6 7 8 9 10
54 QUERY A B C1 C2 D E1 E2 S T X
55 1 1
56 2 1 1
57 3 1 1 1 1
58 4 1 1 1 1 1
59 5 1 1 1 1 1 1
60 6 1 1
61 7 1 1 1
62 8 1 1
63
64
65 simplified matrix:
66 IdNo: 1 2 4 5 7 8 9 10
67 QUERY A B C2 D E2 S T X
68 1 1
69 2 1 1
70 3 1 1 1
71 4 1 1 1 1
72 5 1 1 1 1
73 6 1 1
74 7 1 1 1
75 8 1 1
76
77
78
79 simplified matrix:
80 IdNo: 1 2 4 5 7 8 9 10
81 QUERY A B C2 D E2 S T X
82 1 1
83 2 2 1
84 3 2 2 1
85 4 2 2 2 1
86 5 2 2 3 1
87 6 3 1
88 7 3 2 1
89 8 4 1
90
91
92 */
93
94 public final class Numbering implements Constants{
95     private static final String JavaDoc RCSRevision = "$Revision: 1.4 $";
96     private static final String JavaDoc RCSName = "$Name: $";
97
98
99     /* a list of mapItems for id */
100     List JavaDoc _idList = null;
101
102     /* a list of mapItems for id */
103     List JavaDoc _sortSpecListList = null;
104 // List _numberAttributeList = null;
105 int _subBueryNumber;
106     int _matrix[][] ;
107     int _maxRow;
108     int _maxCol;
109
110
111     /** @todo */
112     Mapper _mapper = null;
113
114     public Numbering(List JavaDoc idList, int subBueryNumber) {
115         _idList = idList;
116         _subBueryNumber = subBueryNumber;
117     }
118
119 // public void setNumberAttributeList(List numberAttributeList)
120 // {
121 // _numberAttributeList = numberAttributeList;
122 // }
123
124     private void initializeMatrix()
125     {
126         //Trace.enter(this,"initializeMatrix()");
127 /**/
128
129         long bitMap ;
130         _maxCol = _idList.size() ;
131         _maxRow = _subBueryNumber ;
132         _matrix = new int[_maxRow+1][_maxCol+2]; /* a column added for guide */
133
134
135         long ruler ;
136         for (int col = 1; col <= _maxCol ; col++) {
137             MapItem mapItem = (MapItem)_idList.get(col-1);
138             bitMap = mapItem.getPart();
139             ruler = 1;
140             for (int row = 1; row <= _maxRow; row++) {
141
142                 _matrix[row ][col] = ((bitMap >> (row-1)) & ruler) > 0 ? 1 : 0;
143             }
144         }
145
146         for (int i = 1; i <=_maxCol; i++) {
147             _matrix[0][i] = i;
148         }
149         for (int i = 1; i <=_maxRow; i++) {
150             _matrix[i][0] = i;
151         }
152         //Trace.message(this,"initializeMatrix()", "Initialized matrix : \n" + printMatrix());
153 //Trace.exit(this,"initializeMatrix()");
154 }
155     private void simplifyMatrix()
156     {
157         //Trace.enter(this,"simplifyMatrix()");
158 /* remove duplecated*/
159         for (int col = 1; col < _maxCol ; col++) {
160             if ( colEquals(col, col + 1)) {
161                 removeCol(col);
162             }
163         }
164         //Trace.message(this,"simplifyMatrix()", "Simplified matrix : \n" + printMatrix());
165
166         //Trace.exit(this,"simplifyMatrix()");
167 }
168
169     private boolean colEquals(int col1 , int col2)
170     {
171         //Trace.enter(this, "colEquals(int col1 , int col2)", ""/*Integer.toString(col1)+ "\t"+ Integer.toString(col1)*/);
172 boolean retVal = true;
173         for (int row = 1; row <= _maxRow; row++) {
174             if (_matrix[row][col1] != _matrix[row][col2]) {
175                 retVal = false;
176                 break;
177             }
178         }
179         //Trace.exit(this, "colEquals(int col1 , int col2)", retVal ? "true":"false" );
180 return retVal;
181     }
182
183     private void removeCol(int col)
184     {
185         //Trace.enter(this, "removeCol(int col)", ""/*Integer.toString(col)*/);
186 for (int row = 0; row <= _maxRow; row++) {
187             _matrix[row][col] = 0;
188         }
189         //Trace.exit(this, "removeCol(int col)", ""/*Integer.toString(col)*/);
190 }
191
192     private int slave(int query, int variable)
193     {
194         //Trace.enter(this, "slave(int query, int variable)", ""/*Integer.toString(query)+ "\t"+ Integer.toString(variable)*/);
195 int retVal = 0;
196         for (int col = variable + 1; col <= _maxCol; col++) {
197             if (1 == _matrix[query][col] ) {
198                 retVal = col;
199                 break;
200             }
201         }
202         //Trace.exit(this, "slave(int query, int variable)", Integer.toString(retVal));
203 return retVal;
204     }
205
206     public void number()
207     {
208         //Trace.enter(this, "number()");
209
210         initializeMatrix();
211
212         eliminationGuide();
213
214         simplifyMatrix();
215
216         int curNum = 0;
217         int oldSlave;
218         int slave;
219
220         /* numbering */
221         for (int col = 1; col <= _maxCol; col++) {
222             oldSlave = 0;
223             curNum = 1;
224             for (int row = 1; row <= _maxRow; row++) {
225                 if (0 != _matrix[row][col]) {
226                     slave = slave(row, col);
227                     if (oldSlave == slave) {
228                         _matrix[row][col] = curNum;
229                     }
230                     else {
231                         oldSlave = slave;
232                         curNum ++;
233                         _matrix[row][col] = curNum;
234                     }
235                 }
236             }
237         }
238         //Trace.message(this,"number()", "numerodation : \n" + printMatrix());
239 removeEmptyColumn();
240         //Trace.message(this,"number()", "numerodation : \n" + printMatrix());
241 //Trace.exit(this, "number()");
242 }
243
244     private void removeEmptyColumn()
245     {
246         //Trace.enter(this, "removeEmptyColumn()");
247 for (int col = 1; col <= _maxCol; col++) {
248             if (isEmpty(col)) {
249                 _matrix[0][col] = 0;
250             }
251         }
252         //Trace.exit(this, "removeEmptyColumn()");
253 }
254
255     private boolean isEmpty(int col)
256     {
257         //Trace.enter(this, "isEmpty(int col)", ""/*Integer.toString(col)*/);
258 boolean retVal = true;
259         int counter = 0;
260         for (int row = 1; row <= _maxRow; row++) {
261             if (0 != _matrix[row][col]) {
262                 counter ++;
263             }
264         }
265         retVal= counter < 2;
266         //Trace.exit(this, "isEmpty(int col)", retVal ? "true":"false");
267 return retVal;
268     }
269
270     public int[] getNumbersForQuery(int query)
271     {
272         //Trace.enter(this, "getNumbersForQuery(int query)", ""/*Integer.toBinaryString(query)*/);
273 int[] retVal = new int[_maxCol+1];
274         for (int col = 0; col < _maxCol; col++) {
275             retVal[col] = _matrix[query][col];
276         }
277         //Trace.exit(this, "getNumbersForQuery(int query)", Integer.toBinaryString(query));
278 return retVal;
279     }
280
281     void setSortSpecListList(List JavaDoc sortSpecListList)
282     {
283         _sortSpecListList = sortSpecListList;
284     }
285
286     List JavaDoc getSortList()
287     {
288         //Trace.enter(this, "getSortList()");
289
290         List JavaDoc retVal = new ArrayList JavaDoc();
291
292         List JavaDoc sortSpecList = null;
293         MapItem mapItem;
294         List JavaDoc subIdList;
295         AttributeExpression numberColumn;
296
297         LitInteger pseudoNumberColomn = new LitInteger(0);
298
299         AttributeExpression sortExpr = null;
300         SortSpecification sortSpec = null;
301
302         int idCursor = 0; // a cursor on matrix column
303 int lastIdOfCurrentQuery = 0;
304         for (int query = 1; query <= _subBueryNumber; query++) {
305
306             /* Sort instruments indicated by users */
307             if (null != _sortSpecListList) {
308                 sortSpecList = (List JavaDoc)_sortSpecListList.get(query-1);
309                 if (null != sortSpecList) {
310                     retVal.addAll(sortSpecList);
311                 }
312             }
313
314             /* ids collumns of current query */
315             lastIdOfCurrentQuery = lastIdColumnIn(query);
316             for (int j = idCursor; j < lastIdOfCurrentQuery; j++) {
317 // if (0 == _matrix[0][idCursor+1]) {
318 // continue;
319 // }
320 mapItem = (MapItem)_idList.get(j);
321                 if (mapItem.isLeafPath()) {
322                     sortExpr = new AttributeExpression(null, mapItem.getItemName());
323                     sortExpr.setUnderlyingExpr(mapItem.getRelatedExpression());
324                     sortSpec = new SortSpecification(sortExpr, ASCENDING_ORDER);
325                     retVal.add(sortSpec);
326                 }
327                 else {
328                     String JavaDoc childPath = null;
329                     MapItem subItem = null;
330                     subIdList = mapItem.getChildren();
331                     for (int k = 0; k < subIdList.size(); k++) {
332
333                         childPath = (String JavaDoc)subIdList.get(k);
334                         subItem = _mapper.map(childPath);
335                         sortExpr = new AttributeExpression(null, subItem.getItemName());
336                         sortExpr.setUnderlyingExpr(subItem.getRelatedExpression());
337                         sortSpec = new SortSpecification(sortExpr,ASCENDING_ORDER);
338                         retVal.add(sortSpec);
339                     }
340                 }
341             }
342
343             idCursor = lastIdOfCurrentQuery;
344
345             /* number collumns */
346             if (0 < _matrix[0][idCursor]) {
347                 numberColumn = new AttributeExpression(null,
348                     GenAlgebraVisitor.NUMBER_COLUMN_PREFIX+Integer.toString(_matrix[0][idCursor]));
349                 /* for feeding typevisitor*/
350                 numberColumn.setUnderlyingExpr(pseudoNumberColomn);
351                 sortSpec = new SortSpecification(numberColumn, ASCENDING_ORDER);
352                 retVal.add(sortSpec);
353             }
354         }
355
356         //Trace.exit(this, "getSortList()");
357 return retVal;
358     }
359
360     private void eliminationGuide ()
361     {
362         int lastId;
363         int lastPresence;
364         for (int query = 1; query <= _maxRow; query++) {
365             lastId = lastIdColumnIn(query);
366             lastPresence = lastPresenceOf(query,lastId);
367             _matrix[query][_maxCol+1] = lastPresence;
368         }
369     }
370
371     public int[] getEliminationGuide()
372     {
373         int[] retVal = new int[_maxRow];
374         for (int query = 1; query <= _maxRow; query++) {
375             retVal[query-1] = _matrix[query][_maxCol+1];
376         }
377         return retVal;
378     }
379
380     private int lastIdColumnIn(int query)
381     {
382         int retVal = 0;
383         for (int i = 1; i <= _maxCol; i++) {
384             if (0 < _matrix[query][i]) {
385                 retVal = i;
386             }
387         }
388         Debug.assertTrue(0 != retVal,"0 != retVal");
389         return retVal;
390     }
391
392     private int lastPresenceOf(int query, int id)
393     {
394         int retVal = query;
395         for (int i = query; i <=_maxRow; i++) {
396             if (0 < _matrix[i][id]) {
397                 retVal = i;
398             }
399             else {
400                 break;
401             }
402         }
403         Debug.assertTrue(0 != retVal,"0 != retVal");
404         return retVal;
405     }
406
407
408     String JavaDoc printMatrix()
409     {
410         StringBuffer JavaDoc retVal = new StringBuffer JavaDoc();
411
412         String JavaDoc newLine = System.getProperty("line.separator");
413         for (int row = 0; row <= _maxRow; row++) {
414             for (int col = 0; col <= _maxCol +1 ; col++) {
415                 retVal.append(_matrix[row][col]);
416                 retVal.append("\t");
417             }
418             retVal.append(newLine);
419         }
420         return retVal.toString();
421     }
422 }
423
Popular Tags