01: /*
02: * Copyright 2004-2006 the original author or authors.
03: *
04: * Licensed under the Apache License, Version 2.0 (the "License");
05: * you may not use this file except in compliance with the License.
06: * You may obtain a copy of the License at
07: *
08: * http://www.apache.org/licenses/LICENSE-2.0
09: *
10: * Unless required by applicable law or agreed to in writing, software
11: * distributed under the License is distributed on an "AS IS" BASIS,
12: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13: * See the License for the specific language governing permissions and
14: * limitations under the License.
15: */
16:
17: package org.compass.gps.device.support.parallel;
18:
19: import java.util.HashSet;
20: import java.util.LinkedList;
21: import java.util.Set;
22:
23: import org.compass.gps.CompassGpsException;
24:
25: /**
26: * Partitions a list of {@link org.compass.gps.device.support.parallel.IndexEntity} into
27: * several groups of lists of index entities based on their sub indexes. Index entities
28: * that share the same sub index will be grouped into the same group since parallel indexing
29: * is best performed based on the sub index as Compass perfoms sub index level locking during
30: * indexing.
31: *
32: * @author kimchy
33: */
34: public class SubIndexIndexEntitiesPartitioner implements
35: IndexEntitiesPartitioner {
36:
37: public IndexEntity[][] partition(IndexEntity[] entities)
38: throws CompassGpsException {
39: LinkedList<Holder> list = new LinkedList<Holder>();
40: for (IndexEntity entity : entities) {
41: Holder holder = new Holder();
42: holder.indexEntities.add(entity);
43: for (int j = 0; j < entity.getSubIndexes().length; j++) {
44: holder.subIndexes.add(entity.getSubIndexes()[j]);
45: }
46: list.add(holder);
47: }
48: boolean merged;
49: do {
50: merged = false;
51: for (int i = 0; i < list.size(); i++) {
52: Holder holder = list.get(i);
53: for (int j = i + 1; j < list.size(); j++) {
54: Holder tempHolder = list.get(j);
55: if (holder.containsSubIndex(tempHolder.subIndexes)) {
56: list.remove(j);
57: holder.subIndexes.addAll(tempHolder.subIndexes);
58: holder.indexEntities
59: .addAll(tempHolder.indexEntities);
60: merged = true;
61: }
62: }
63: }
64: } while (merged);
65: IndexEntity[][] returnEntities = new IndexEntity[list.size()][];
66: for (int i = 0; i < returnEntities.length; i++) {
67: Holder holder = list.get(i);
68: returnEntities[i] = holder.indexEntities
69: .toArray(new IndexEntity[holder.indexEntities
70: .size()]);
71: }
72: return returnEntities;
73: }
74:
75: private class Holder {
76: Set<String> subIndexes = new HashSet<String>();
77: Set<IndexEntity> indexEntities = new HashSet<IndexEntity>();
78:
79: public boolean containsSubIndex(Set<String> checkSubIndexes) {
80: for (String checkSubIndex : checkSubIndexes) {
81: if (subIndexes.contains(checkSubIndex)) {
82: return true;
83: }
84: }
85: return false;
86: }
87: }
88: }
|