1 package org.thegalactic.util;
2
3 /*
4 * ComparableSet.java
5 *
6 * Copyright: 2010-2015 Karell Bertet, France
7 * Copyright: 2015-2016 The Galactic Organization, France
8 *
9 * License: http://www.cecill.info/licences/Licence_CeCILL-B_V1-en.html CeCILL-B license
10 *
11 * This file is part of java-lattices.
12 * You can redistribute it and/or modify it under the terms of the CeCILL-B license.
13 */
14 import java.util.SortedSet;
15 import java.util.TreeSet;
16
17 /**
18 * This class gives a minimal representation of a comparable set where sets are
19 * compared using the lectic order.
20 *
21 * This class extends class `TreeSet`, implements class `Comparable` and
22 * provides a {@link #compareTo} method that implements the lectic order between
23 * two sets.
24 *
25 * Therefore, a comparable set can be stored in a sorted collection, and in
26 * particular in a sorted set where set operations are provided.
27 *
28 * The lectic order extends the inclusion, and is defined only for comparable
29 * elements, i.e. elements that can be sorted, as follows:
30 *
31 * "a set `A` is smaller than a set `B` iff there exists an element in `B\A`
32 * such that any smaller element belonging to `A` also belongs to `B`."
33 *
34 * @param <E> Element type
35 *
36 * @todo Check if this class is correctly used (performance). Overload
37 * modification method to compute the hashCode only once.
38 *
39 * 
40 *
41 * @uml ComparableSet.png
42 * !include resources/org/thegalactic/util/ComparableSet.iuml
43 *
44 * hide members
45 * show ComparableSet members
46 * class ComparableSet #LightCyan
47 * title ComparableSet UML graph
48 */
49 public class ComparableSet<E extends Comparable> extends TreeSet<E> implements Comparable<ComparableSet>, Cloneable {
50
51 /*
52 * ------------- CONSTRUCTORS ------------------
53 */
54 /**
55 * Constructs a new and empty ComparableSet.
56 */
57 public ComparableSet() {
58 super();
59 }
60
61 /**
62 * Constructs a new ComparableSet with the set from the specified set.
63 *
64 * @param set a comparable set
65 */
66 public ComparableSet(final SortedSet<E> set) {
67 super(set);
68 }
69
70 /*
71 * --------------- OVERLAPPING METHODS ------------
72 */
73 /**
74 * Returns a clone of this component.
75 *
76 * @return a clone of this component.
77 */
78 @Override
79 public ComparableSet clone() {
80 return (ComparableSet) super.clone();
81 }
82
83 /**
84 * Compares this component with those in parameter according to the lectic
85 * order.
86 *
87 * The lectic order defines a sort on sets of elements extending the
88 * inclusion order as follows:
89 *
90 * A set `A` is smaller than a set `B` iff there exists an element in `B\A`
91 * such that any smaller element belonging to A also belongs to B. The
92 * result is
93 *
94 * - zero if the identifiers are equal;
95 * - 1 if this component's identifier is greater;
96 * - -1 otherwise.
97 *
98 * This comparison method is needed to define a natural and total sort on a
99 * sets.
100 *
101 * It allows to use sets of this class in a sorted collection
102 *
103 * @param set the specified element to be compared with this component
104 *
105 * @return a negative integer, zero, or a positive integer as this component
106 * is less than, equal to, or greater than the specified object according to
107 * the lectic order.
108 *
109 * @todo Is this correct? (see test)
110 */
111 public int compareTo(final ComparableSet set) {
112
113 int cmp;
114
115 // case of equality between this component and object
116 if (this.equals(set)) {
117 cmp = 0;
118 } else {
119 // computes index i of the first element in set minus this
120 // if i doesn't exist, then this component is not smaller than the set by lectic order
121 final TreeSet<Comparable> setMinusThis = new TreeSet(set);
122 setMinusThis.removeAll(this);
123 if (setMinusThis.isEmpty()) {
124 cmp = 1;
125 } else {
126 final Comparable i = setMinusThis.first();
127 // compute this inter {1, ..., i-1}
128 final TreeSet setAiMinus1 = new TreeSet();
129 for (final Object c : this) {
130 if (i.compareTo(c) > 0) {
131 setAiMinus1.add(c);
132 }
133 }
134 // compute set inter {1, ..., i-1}
135 final TreeSet setBiMinus1 = new TreeSet();
136 for (final Object c : set) {
137 if (i.compareTo(c) > 0) {
138 setBiMinus1.add(c);
139 }
140 }
141 // if setAiminus1 and setBiminus1 are equal then this component is smaller than B by lectic order
142 if (setAiMinus1.equals(setBiMinus1)) {
143 cmp = -1;
144 } else {
145 cmp = 1;
146 }
147 }
148 }
149 return cmp;
150 }
151 }