Source code: org/objectstyle/ashwood/util/IntPartition.java
1 /* ====================================================================
2 *
3 * Copyright(c) 2003, Andriy Shapochka
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above
11 * copyright notice, this list of conditions and the following
12 * disclaimer.
13 *
14 * 2. Redistributions in binary form must reproduce the above
15 * copyright notice, this list of conditions and the following
16 * disclaimer in the documentation and/or other materials
17 * provided with the distribution.
18 *
19 * 3. Neither the name of the ASHWOOD nor the
20 * names of its contributors may be used to endorse or
21 * promote products derived from this software without
22 * specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
26 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
27 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
30 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
31 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
32 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
33 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 *
35 * ====================================================================
36 *
37 * This software consists of voluntary contributions made by
38 * individuals on behalf of the ASHWOOD Project and was originally
39 * created by Andriy Shapochka.
40 *
41 */
42
43 package org.objectstyle.ashwood.util;
44
45 public final class IntPartition {
46 private int[] partition;
47 private int setCount;
48
49 public IntPartition(int elementCount) {
50 partition = new int[elementCount];
51 reset();
52 }
53
54 public final int joinSets(int setId1, int setId2) {
55 if (setId1 < 0 || setId2 < 0)
56 throw new IndexOutOfBoundsException("setId1=" + setId1 + ", setId2=" + setId2);
57 if (setId1 == setId2) return setId1;
58 int rank1 = partition[setId1];
59 int rank2 = partition[setId2];
60 setCount--;
61 if (rank2 < rank1) {
62 partition[setId1] = setId2;
63 return setId2;
64 } else {
65 if (rank2 == rank1) partition[setId1]--;
66 partition[setId2] = setId1;
67 return setId1;
68 }
69 }
70
71 public final int findSetId(int element) {
72 if (partition[element] < 0)
73 return element;
74 else {
75 partition[element] = findSetId(partition[element]);
76 return partition[element];
77 }
78 }
79
80 public final int size() {
81 return partition.length;
82 }
83
84 public final int getSetCount() {
85 return setCount;
86 }
87
88 public final void reset() {
89 for (int i = 0; i < partition.length; i++) {
90 partition[i] = -1;
91 }
92 setCount = size();
93 }
94
95 public final boolean isSetId(int element) {
96 return partition[element] < 0;
97 }
98 }