001: /*
002: (c) Copyright 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
003: All rights reserved - see end of file.
004: $Id: ArrayBunch.java,v 1.14 2008/01/02 12:09:51 andy_seaborne Exp $
005: */
006: package com.hp.hpl.jena.mem;
007:
008: import java.util.ConcurrentModificationException;
009:
010: import com.hp.hpl.jena.graph.Triple;
011: import com.hp.hpl.jena.graph.query.*;
012: import com.hp.hpl.jena.util.iterator.*;
013:
014: /**
015: An ArrayBunch implements TripleBunch with a linear search of a short-ish
016: array of Triples. The array can grow, but it only grows by 4 elements each time
017: (because, if it gets big enough for this linear growth to be bad, it should anyways
018: have been replaced by a more efficient set-of-triples implementation).
019:
020: @author kers
021: */
022: public class ArrayBunch implements TripleBunch {
023:
024: protected int size = 0;
025: protected Triple[] elements;
026: protected volatile int changes = 0;
027:
028: public ArrayBunch() {
029: elements = new Triple[5];
030: }
031:
032: public boolean containsBySameValueAs(Triple t) {
033: int i = size;
034: while (i > 0)
035: if (t.matches(elements[--i]))
036: return true;
037: return false;
038: }
039:
040: public boolean contains(Triple t) {
041: int i = size;
042: while (i > 0)
043: if (t.equals(elements[--i]))
044: return true;
045: return false;
046: }
047:
048: public int size() {
049: return size;
050: }
051:
052: public void add(Triple t) {
053: if (size == elements.length)
054: grow();
055: elements[size++] = t;
056: changes += 1;
057: }
058:
059: /**
060: Note: linear growth is suboptimal (order n<sup>2</sup>) normally, but
061: ArrayBunch's are meant for <i>small</i> sets and are replaced by some
062: sort of hash- or tree- set when they get big; currently "big" means more
063: than 9 elements, so that's only one growth spurt anyway.
064: */
065: protected void grow() {
066: Triple[] newElements = new Triple[size + 4];
067: System.arraycopy(elements, 0, newElements, 0, size);
068: elements = newElements;
069: }
070:
071: public void remove(Triple t) {
072: changes += 1;
073: for (int i = 0; i < size; i += 1) {
074: if (t.equals(elements[i])) {
075: elements[i] = elements[--size];
076: return;
077: }
078: }
079: }
080:
081: public void app(Domain d, StageElement next, MatchOrBind s) {
082: int i = size, initialChanges = changes;
083: while (i > 0) {
084: if (changes > initialChanges)
085: throw new ConcurrentModificationException();
086: if (s.matches(elements[--i]))
087: next.run(d);
088: }
089: }
090:
091: public ExtendedIterator iterator() {
092: return iterator(new HashCommon.NotifyEmpty() {
093: public void emptied() {
094: }
095: });
096: }
097:
098: public ExtendedIterator iterator(
099: final HashCommon.NotifyEmpty container) {
100: // System.err.println( ">> ArrayBunch::iterator: intial state" );
101: // for (int j = 0; j < size; j += 1) System.err.println( "== " + elements[j] );
102: // System.err.println( ">> (done)" );
103: return new NiceIterator() {
104: protected final int initialChanges = changes;
105:
106: protected int i = size;
107: protected final Triple[] e = elements;
108:
109: public boolean hasNext() {
110: if (changes > initialChanges)
111: throw new ConcurrentModificationException();
112: return i > 0;
113: }
114:
115: public Object next() {
116: if (changes > initialChanges)
117: throw new ConcurrentModificationException();
118: if (i == 0)
119: noElements("no elements left in ArrayBunch iteration");
120: return e[--i];
121: }
122:
123: public void remove() {
124: if (changes > initialChanges)
125: throw new ConcurrentModificationException();
126: // System.err.println( ">> ArrayBunch.iterator::remove" );
127: // System.err.println( "++ size currently " + size );
128: // System.err.println( "++ container is " + container );
129: // System.err.println( "++ selector currently " + i + " (triple " + e[i] + ")" );
130: int last = --size;
131: e[i] = e[last];
132: e[last] = null;
133: if (size == 0)
134: container.emptied();
135: // System.err.println( "++ post remove, triples are:" );
136: // for (int j = 0; j < size; j += 1) System.err.println( "== " + e[j] );
137: }
138: };
139: }
140: }
141:
142: /*
143: * (c) Copyright 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
144: * All rights reserved.
145: *
146: * Redistribution and use in source and binary forms, with or without
147: * modification, are permitted provided that the following conditions
148: * are met:
149: * 1. Redistributions of source code must retain the above copyright
150: * notice, this list of conditions and the following disclaimer.
151: * 2. Redistributions in binary form must reproduce the above copyright
152: * notice, this list of conditions and the following disclaimer in the
153: * documentation and/or other materials provided with the distribution.
154: * 3. The name of the author may not be used to endorse or promote products
155: * derived from this software without specific prior written permission.
156: *
157: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
158: * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
159: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
160: * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
161: * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
162: * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
163: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
164: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
165: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
166: * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
167: */
|