001: /*
002: * (c) Copyright 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
003: * All rights reserved.
004: *
005: * Redistribution and use in source and binary forms, with or without
006: * modification, are permitted provided that the following conditions
007: * are met:
008: * 1. Redistributions of source code must retain the above copyright
009: * notice, this list of conditions and the following disclaimer.
010: * 2. Redistributions in binary form must reproduce the above copyright
011: * notice, this list of conditions and the following disclaimer in the
012: * documentation and/or other materials provided with the distribution.
013: * 3. The name of the author may not be used to endorse or promote products
014: * derived from this software without specific prior written permission.
015:
016: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
017: * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
018: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
019: * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
020: * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
021: * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
022: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
023: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
024: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
025: * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
026: *
027: * $Id: Relation.java,v 1.9 2008/01/02 12:09:33 andy_seaborne Exp $
028: *
029: */
030:
031: package com.hp.hpl.jena.xmloutput.impl;
032:
033: import java.util.HashMap;
034: import java.util.HashSet;
035: import java.util.Iterator;
036: import java.util.Map;
037: import java.util.Set;
038:
039: import com.hp.hpl.jena.util.iterator.IteratorIterator;
040: import com.hp.hpl.jena.util.iterator.Map1;
041: import com.hp.hpl.jena.util.iterator.Map1Iterator;
042:
043: /**
044: * A sparse 2 dimensional array of boolean indexed by Object.
045: *
046: * Complete with transitive closure algorithm.
047: * @author jjc
048: * @version Release='$Name: $' Revision='$Revision: 1.9 $' Date='$Date: 2008/01/02 12:09:33 $'
049: */
050: class Relation {
051: final private Map rows;
052: final private Map cols;
053: final private Set index;
054:
055: /** The empty Relation.
056: */
057: public Relation() {
058: rows = new HashMap();
059: cols = new HashMap();
060: index = new HashSet();
061: }
062:
063: /** <code>a</code> is now related to <code>b</code>
064: *
065: */
066: synchronized public void set(Object a, Object b) {
067: index.add(a);
068: index.add(b);
069: innerAdd(rows, a, b);
070: innerAdd(cols, b, a);
071: }
072:
073: /** Uniquely <code>a</code> is now related to uniquely <code>b</code>.
074: *
075: * When this is called any other <code>a</code> related to this <code>b</code> is removed.
076: * When this is called any other <code>b</code> related to this <code>a</code> is removed.
077: *
078: */
079: synchronized public void set11(Object a, Object b) {
080: clearX(a, forward(a));
081: clearX(backward(b), b);
082: set(a, b);
083: }
084:
085: /** Uniquely <code>a</code> is now related to <code>b</code>.
086: * Many <code>b</code>'s can be related to each <code>a</code>.
087: * When this is called any other <code>a</code> related to this <code>b</code> is removed.
088: */
089: synchronized public void set1N(Object a, Object b) {
090: clearX(backward(b), b);
091: set(a, b);
092: }
093:
094: /** <code>a</code> is now related to uniquely <code>b</code>.
095: * Many <code>a</code>'s can be related to each <code>b</code>.
096: * When this is called any other <code>b</code> related to this <code>a</code> is removed.
097: */
098: synchronized public void setN1(Object a, Object b) {
099: clearX(a, forward(a));
100: set(a, b);
101: }
102:
103: /** <code>a</code> is now related to <code>b</code>
104: *
105: */
106: synchronized public void setNN(Object a, Object b) {
107: set(a, b);
108: }
109:
110: /** <code>a</code> is now <em>not</em> related to <code>b</code>
111: *
112: */
113: synchronized public void clear(Object a, Object b) {
114: innerClear(rows, a, b);
115: innerClear(cols, b, a);
116: }
117:
118: private void clearX(Set s, Object b) {
119: if (s == null)
120: return;
121: Iterator it = s.iterator();
122: while (it.hasNext())
123: clear(it.next(), b);
124: }
125:
126: private void clearX(Object a, Set s) {
127: if (s == null)
128: return;
129: Iterator it = s.iterator();
130: while (it.hasNext())
131: clear(a, it.next());
132: }
133:
134: static private void innerAdd(Map s, Object a, Object b) {
135: Set vals = (Set) s.get(a);
136: if (vals == null) {
137: vals = new HashSet();
138: s.put(a, vals);
139: }
140: vals.add(b);
141: }
142:
143: static private void innerClear(Map s, Object a, Object b) {
144: Set vals = (Set) s.get(a);
145: if (vals != null) {
146: vals.remove(b);
147: }
148: }
149:
150: /** Is <code>a</code> related to <code>b</code>?
151: *
152: */
153: public boolean get(Object a, Object b) {
154: Set vals = (Set) rows.get(a);
155: return vals != null && vals.contains(b);
156: }
157:
158: /**
159: * Takes this to its transitive closure.
160: See B. Roy. <b>Transitivité et connexité.</b> <i>C.R. Acad. Sci.</i> Paris <b>249</b>, 1959 pp 216-218.
161: or
162: S. Warshall, <b>A theorem on Boolean matrices</b>, <i>Journal of the ACM</i>, <b>9</b>(1), 1962, pp11-12
163:
164:
165: */
166: synchronized public void transitiveClosure() {
167: Iterator j = index.iterator();
168: while (j.hasNext()) {
169: Object oj = j.next();
170: Set si = (Set) cols.get(oj);
171: Set sk = (Set) rows.get(oj);
172: if (si != null && sk != null) {
173: Iterator i = si.iterator();
174: while (i.hasNext()) {
175: Object oi = i.next();
176: if (oi != oj) {
177: Iterator k = sk.iterator();
178: while (k.hasNext()) {
179: Object ok = k.next();
180: if (ok != oj)
181: set(oi, ok);
182: }
183: }
184: }
185: }
186: }
187: }
188:
189: /**
190: * The set of <code>a</code> such that <code>a</code> is related to <code>a</code>.
191: *
192: */
193: synchronized public Set getDiagonal() {
194: Set rslt = new HashSet();
195: Iterator it = index.iterator();
196: while (it.hasNext()) {
197: Object o = it.next();
198: if (get(o, o))
199: rslt.add(o);
200: }
201: return rslt;
202: }
203:
204: /**
205: * The set of <code>b</code> such that <code>a</code> is related to <code>b</code>.
206: *
207: */
208: public Set forward(Object a) {
209: return (Set) rows.get(a);
210: }
211:
212: /**
213: * The set of <code>a</code> such that <code>a</code> is related to <code>b</code>.
214: *
215: */
216: public Set backward(Object b) {
217: return (Set) cols.get(b);
218: }
219:
220: /**
221: * An Iterator over the pairs of the Relation.
222: * Each pair is returned as a java.util.Map.Entry.
223: * The first element is accessed through <code>getKey()</code>,
224: * the second through <code>getValue()</code>.
225: *@see java.util.Map.Entry
226: */
227: public Iterator iterator() {
228: return new IteratorIterator(new Map1Iterator(new Map1() {
229: // Convert a Map.Entry into an iterator over Map.Entry
230: public Object map1(Object o) {
231: Map.Entry pair = (Map.Entry) o;
232: final Object a = pair.getKey();
233: Set bs = (Set) pair.getValue();
234: return new Map1Iterator(
235: // Converts a b into a Map.Entry pair.
236: new Map1() {
237: public Object map1(Object b) {
238: return new PairEntry(a, b);
239: }
240: }, bs.iterator());
241: }
242: }, rows.entrySet().iterator()));
243: }
244:
245: synchronized public Relation copy() {
246: Relation rslt = new Relation();
247: Iterator it = iterator();
248: while (it.hasNext()) {
249: Map.Entry e = (Map.Entry) it.next();
250: rslt.set(e.getKey(), e.getValue());
251: }
252: return rslt;
253: }
254: }
|