0001: package org.garret.rdf;
0002:
0003: import java.util.*;
0004: import org.garret.perst.*;
0005:
0006: /**
0007: * Main class
0008: **/
0009: public class VersionedStorage {
0010: Storage db;
0011: DatabaseRoot root;
0012:
0013: private static final Iterator EmptyIterator = (new HashSet())
0014: .iterator();
0015:
0016: /**
0017: * List of separator characters used to split string into keywords
0018: **/
0019: public static char[] keywordSeparators = { ' ', ',' };
0020:
0021: /**
0022: * List of most commonly used words which should be ignored andnot included in inverse index
0023: */
0024: public static HashSet keywordStopList = new HashSet();
0025:
0026: static {
0027: keywordStopList.add("the");
0028: keywordStopList.add("at");
0029: keywordStopList.add("of");
0030: keywordStopList.add("a");
0031: keywordStopList.add("to");
0032: keywordStopList.add("at");
0033: keywordStopList.add("and");
0034: keywordStopList.add("or");
0035: keywordStopList.add("i");
0036: }
0037:
0038: /**
0039: * Open database
0040: * @param filePath path to the database file
0041: */
0042: public void open(String filePath) {
0043: db = StorageFactory.getInstance().createStorage();
0044: db.open(filePath);
0045: root = (DatabaseRoot) db.getRoot();
0046: if (root == null) {
0047: root = new DatabaseRoot();
0048: root.prefixUriIndex = db.createIndex(String.class, true);
0049: root.suffixUriIndex = db.createIndex(String.class, true);
0050: root.strPropIndex = db.createIndex(new Class[] {
0051: PropDef.class, String.class }, false);
0052: root.numPropIndex = db.createIndex(new Class[] {
0053: PropDef.class, Double.class }, false);
0054: root.refPropIndex = db.createIndex(new Class[] {
0055: PropDef.class, VersionHistory.class }, false);
0056: root.timePropIndex = db.createIndex(new Class[] {
0057: PropDef.class, Date.class }, false);
0058: root.propDefIndex = db.createFieldIndex(PropDef.class,
0059: "name", true);
0060: root.timeIndex = db.createFieldIndex(Thing.class,
0061: "timestamp", false);
0062: root.inverseIndex = db.createIndex(String.class, false);
0063: root.spatialIndex = db.createSpatialIndexR2();
0064: root.latest = db.createSet();
0065: createMetaType();
0066: db.setRoot(root);
0067: }
0068: }
0069:
0070: /**
0071: * Get verion history by URI
0072: * @param uri object URI
0073: * @return version history or null if no such object is found
0074: */
0075: public VersionHistory getObject(String uri) {
0076: return (VersionHistory) root.prefixUriIndex.get(uri);
0077: }
0078:
0079: /**
0080: * Get latest verion of object with specified URI
0081: * @param uri object URI
0082: * @return latest version of object or null if no such object is found
0083: */
0084: public Thing getLatestVersion(String uri) {
0085: VersionHistory vh = (VersionHistory) root.prefixUriIndex
0086: .get(uri);
0087: return (vh != null) ? vh.getLatest() : null;
0088: }
0089:
0090: /**
0091: * Get verion history by URI and timestamp
0092: * @param uri object URI
0093: * @param kind search kind, should be object SearchKind.LatestVersion, SearchKind.LatestBefore or
0094: * SearchKind.OldestAfter
0095: * @param timestamp timestamp used to locate version
0096: * @return version of the object or null if no such version is found
0097: */
0098: public Thing getVersion(String uri, SearchKind kind, Date timestamp) {
0099: VersionHistory vh = (VersionHistory) root.prefixUriIndex
0100: .get(uri);
0101: if (vh != null) {
0102: return vh.getVersion(kind, timestamp);
0103: }
0104: return null;
0105: }
0106:
0107: /**
0108: * Create bew object. If version history with this URI is not exists, it is created first.
0109: * Then new object version is created and appended to this version history.
0110: *
0111: * @param uri object URI
0112: * @param type URI of object type
0113: * @param props object properties
0114: * @return created object version
0115: */
0116: public Thing createObject(String uri, String type, NameVal[] props) {
0117: VersionHistory vh = (VersionHistory) root.prefixUriIndex
0118: .get(uri);
0119: if (vh == null) {
0120: VersionHistory typeVh = null;
0121: typeVh = getObject(type);
0122: if (typeVh == null) {
0123: typeVh = createVersionHistory(type, root.metatype);
0124: createObject(root.metatype.getLatest(), typeVh,
0125: new NameVal[0]);
0126: }
0127: vh = createVersionHistory(uri, typeVh);
0128: } else {
0129: root.latest.remove(vh.getLatest());
0130: }
0131: return createObject(vh.type.getLatest(), vh, props);
0132: }
0133:
0134: /**
0135: * Get iterator through object matching specified search parameters
0136: * @param type String representing type of the object (direct or indirect - IsInstanceOf
0137: * method will be used to check if object belongs to the specified type). It may be null,
0138: * in this case type criteria is skipped.
0139: * @param uri Object URI pattern. It may be null, in this case URI is not inspected.
0140: * @param patterns array of name:value pairs specifying search condition for object properties
0141: * @param kind search kind used to select inspected versions
0142: * @param timestamp timestamp used to select versions, if kind is SearchKind.LatestVersion
0143: * or SearchKind.AllVersions this parameter is ignored
0144: * @return Enumerator through object meet search criteria.
0145: */
0146: public Iterator search(String type, String uri, NameVal[] patterns,
0147: SearchKind kind, Date timestamp) {
0148: VersionHistory typeVh = null;
0149: root.sharedLock();
0150: try {
0151: if (type != null) {
0152: typeVh = getObject(type);
0153: if (typeVh == null) {
0154: return EmptyIterator;
0155: }
0156: }
0157: if (uri != null) {
0158: int wc = uri.indexOf('*');
0159: if (wc < 0) {
0160: Key key = new Key(uri);
0161: return new SearchResult(root, typeVh, null,
0162: patterns, kind, timestamp,
0163: root.prefixUriIndex.iterator(key, key,
0164: Index.ASCENT_ORDER));
0165: } else if (wc > 0) {
0166: String prefix = uri.substring(0, wc);
0167: return new SearchResult(root, typeVh, uri,
0168: patterns, kind, timestamp,
0169: root.prefixUriIndex.prefixIterator(prefix));
0170: } else if ((wc = uri.lastIndexOf('*')) < uri.length() - 1) {
0171: String suffix = reverseString(uri.substring(wc + 1,
0172: uri.length()));
0173: return new SearchResult(root, typeVh, uri,
0174: patterns, kind, timestamp,
0175: root.suffixUriIndex.prefixIterator(suffix));
0176: }
0177: }
0178: if (patterns.length > 0) {
0179: NameVal prop = patterns[0];
0180: Object val = prop.val;
0181: NameVal[] restOfPatterns = subArray(patterns);
0182:
0183: if (Symbols.Timestamp.equals(prop.name)) {
0184: if (val instanceof Range) {
0185: Range range = (Range) val;
0186: if (range.from instanceof Date) {
0187: Key fromKey = new Key((Date) range.from,
0188: range.fromInclusive);
0189: Key tillKey = new Key((Date) range.till,
0190: range.tillInclusive);
0191: return new SearchResult(root, typeVh, uri,
0192: restOfPatterns, kind, timestamp,
0193: root.timeIndex
0194: .iterator(fromKey, tillKey,
0195: Index.ASCENT_ORDER));
0196: }
0197: } else if (val instanceof Date) {
0198: Key key = new Key((Date) val);
0199: return new SearchResult(root, typeVh, uri,
0200: restOfPatterns, kind, timestamp,
0201: root.timeIndex.iterator(key, key,
0202: Index.ASCENT_ORDER));
0203: }
0204: return EmptyIterator;
0205: } else if (Symbols.Rectangle.equals(prop.name)) {
0206: if (val instanceof NameVal[]) {
0207: NameVal[] coord = (NameVal[]) val;
0208: if (coord.length == 4) {
0209: RectangleR2 r = new RectangleR2(
0210: ((Number) coord[0].val)
0211: .doubleValue(),
0212: ((Number) coord[1].val)
0213: .doubleValue(),
0214: ((Number) coord[2].val)
0215: .doubleValue(),
0216: ((Number) coord[3].val)
0217: .doubleValue());
0218: return new SearchResult(root, typeVh, uri,
0219: restOfPatterns, kind, timestamp,
0220: root.spatialIndex.iterator(r));
0221: }
0222: }
0223: } else if (Symbols.Point.equals(prop.name)) {
0224: if (val instanceof NameVal[]) {
0225: NameVal[] coord = (NameVal[]) val;
0226: if (coord.length == 2) {
0227: double x = ((Number) coord[0].val)
0228: .doubleValue();
0229: double y = ((Number) coord[1].val)
0230: .doubleValue();
0231: RectangleR2 r = new RectangleR2(x, y, x, y);
0232: return new SearchResult(root, typeVh, uri,
0233: restOfPatterns, kind, timestamp,
0234: root.spatialIndex.iterator(r));
0235: }
0236: }
0237: } else if (Symbols.Keyword.equals(prop.name)) {
0238: if (val instanceof String) {
0239: ArrayList keywords = getKeywords((String) val);
0240: Iterator[] occurences = new Iterator[keywords
0241: .size()];
0242: for (int i = 0; i < occurences.length; i++) {
0243: Key key = new Key((String) keywords.get(i));
0244: occurences[i] = root.inverseIndex.iterator(
0245: key, key, Index.ASCENT_ORDER);
0246: }
0247: return new SearchResult(root, typeVh, uri,
0248: restOfPatterns, kind, timestamp, db
0249: .merge(occurences));
0250: }
0251: }
0252:
0253: PropDef def = (PropDef) root.propDefIndex
0254: .get(prop.name);
0255: if (def == null) {
0256: return EmptyIterator;
0257: }
0258: if (val instanceof Range) {
0259: Range range = (Range) val;
0260: if (range.from instanceof Number) {
0261: Key fromKey = new Key(new Object[] { def,
0262: range.from }, range.fromInclusive);
0263: Key tillKey = new Key(new Object[] { def,
0264: range.till }, range.tillInclusive);
0265: return new SearchResult(root, typeVh, uri,
0266: restOfPatterns, kind, timestamp,
0267: root.numPropIndex.iterator(fromKey,
0268: tillKey, Index.ASCENT_ORDER));
0269: } else if (range.from instanceof Date) {
0270: Key fromKey = new Key(new Object[] { def,
0271: range.from }, range.fromInclusive);
0272: Key tillKey = new Key(new Object[] { def,
0273: range.till }, range.tillInclusive);
0274: return new SearchResult(root, typeVh, uri,
0275: restOfPatterns, kind, timestamp,
0276: root.timePropIndex.iterator(fromKey,
0277: tillKey, Index.ASCENT_ORDER));
0278: } else {
0279: Key fromKey = new Key(new Object[] { def,
0280: range.from }, range.fromInclusive);
0281: Key tillKey = new Key(new Object[] { def,
0282: range.till }, range.tillInclusive);
0283: return new SearchResult(root, typeVh, uri,
0284: restOfPatterns, kind, timestamp,
0285: root.strPropIndex.iterator(fromKey,
0286: tillKey, Index.ASCENT_ORDER));
0287: }
0288: } else if (val instanceof String) {
0289: String str = (String) val;
0290: int wc = str.indexOf('*');
0291: if (wc < 0) {
0292: Key key = new Key(new Object[] { def, str });
0293: return new SearchResult(root, typeVh, uri,
0294: restOfPatterns, kind, timestamp,
0295: root.strPropIndex.iterator(key, key,
0296: Index.ASCENT_ORDER));
0297:
0298: } else if (wc > 0) {
0299: String prefix = str.substring(0, wc);
0300: Key fromKey = new Key(new Object[] { def,
0301: prefix });
0302: Key tillKey = new Key(new Object[] { def,
0303: prefix + Character.MAX_VALUE }, false);
0304: return new SearchResult(root, typeVh, uri,
0305: wc == str.length() - 1 ? restOfPatterns
0306: : patterns, kind, timestamp,
0307: root.strPropIndex.iterator(fromKey,
0308: tillKey, Index.ASCENT_ORDER));
0309: }
0310: } else if (val instanceof Number) {
0311: Key key = new Key(new Object[] { def, val });
0312: return new SearchResult(root, typeVh, uri,
0313: restOfPatterns, kind, timestamp,
0314: root.numPropIndex.iterator(key, key,
0315: Index.ASCENT_ORDER));
0316: } else if (val instanceof Date) {
0317: Key key = new Key(new Object[] { def, val });
0318: return new SearchResult(root, typeVh, uri,
0319: restOfPatterns, kind, timestamp,
0320: root.timePropIndex.iterator(key, key,
0321: Index.ASCENT_ORDER));
0322: } else if (val instanceof NameVal) {
0323: Iterator iterator = searchReferenceProperty(typeVh,
0324: uri, patterns, kind, timestamp,
0325: (NameVal) val, false, def, new ArrayList());
0326: if (iterator != null) {
0327: return iterator;
0328: }
0329: } else if (val instanceof NameVal[]) {
0330: NameVal[] props = (NameVal[]) val;
0331: if (props.length > 0) {
0332: Iterator iterator = searchReferenceProperty(
0333: typeVh, uri, patterns, kind, timestamp,
0334: props[0], props.length > 1, def,
0335: new ArrayList());
0336: if (iterator != null) {
0337: return iterator;
0338: }
0339: }
0340: }
0341: }
0342: if (kind == SearchKind.LatestVersion) {
0343: return new SearchResult(root, typeVh, uri, patterns,
0344: kind, timestamp, root.latest.iterator());
0345: }
0346: return new SearchResult(root, typeVh, uri, patterns, kind,
0347: timestamp, root.timeIndex.iterator());
0348: } finally {
0349: root.unlock();
0350: }
0351: }
0352:
0353: class ReferenceIterator implements Iterator {
0354: PropDef[] defs;
0355: Iterator[] iterators;
0356: int pos;
0357: Thing currThing;
0358: SearchKind kind;
0359: Date timestamp;
0360: DatabaseRoot root;
0361: HashSet visited;
0362:
0363: public ReferenceIterator(DatabaseRoot root, PropDef[] defs,
0364: Iterator iterator, SearchKind kind, Date timestamp) {
0365: this .root = root;
0366: this .defs = defs;
0367: this .kind = kind;
0368: this .timestamp = timestamp;
0369: iterators = new Iterator[defs.length + 1];
0370: iterators[iterators.length - 1] = iterator;
0371: visited = new HashSet();
0372: pos = iterators.length - 1;
0373: gotoNext();
0374: }
0375:
0376: public boolean hasNext() {
0377: return currThing != null;
0378: }
0379:
0380: public Object next() {
0381: if (currThing == null) {
0382: throw new NoSuchElementException();
0383: }
0384: Thing thing = currThing;
0385: gotoNext();
0386: return thing;
0387: }
0388:
0389: public void remove() {
0390: throw new UnsupportedOperationException();
0391: }
0392:
0393: private void gotoNext() {
0394: while (true) {
0395: while (pos < iterators.length
0396: && !iterators[pos].hasNext()) {
0397: pos += 1;
0398: }
0399: if (pos == iterators.length) {
0400: currThing = null;
0401: return;
0402: }
0403: Thing thing = (Thing) iterators[pos].next();
0404: if (kind == SearchKind.LatestVersion) {
0405: if (!thing.isLatest()) {
0406: continue;
0407: }
0408: } else if (kind == SearchKind.LatestBefore) {
0409: if (thing.timestamp.compareTo(timestamp) > 0) {
0410: continue;
0411: }
0412: } else if (kind == SearchKind.OldestAfter) {
0413: if (thing.timestamp.compareTo(timestamp) < 0) {
0414: continue;
0415: }
0416: }
0417: if (pos == 0) {
0418: Integer oid = new Integer(thing.getOid());
0419: if (visited.contains(oid)) {
0420: continue;
0421: } else {
0422: visited.add(oid);
0423: }
0424: currThing = thing;
0425: return;
0426: }
0427: pos -= 1;
0428: Key key = new Key(new Object[] { defs[pos], thing.vh });
0429: iterators[pos] = root.refPropIndex.iterator(key, key,
0430: Index.ASCENT_ORDER);
0431: }
0432: }
0433: }
0434:
0435: private Iterator searchReferenceProperty(VersionHistory type,
0436: String uri, NameVal[] patterns, SearchKind kind,
0437: Date timestamp, NameVal prop, boolean compound,
0438: PropDef def, ArrayList refs) {
0439: refs.add(def);
0440:
0441: NameVal[] restOfPatterns = compound ? patterns
0442: : subArray(patterns);
0443: PropDef[] refProps = (PropDef[]) refs.toArray(new PropDef[refs
0444: .size()]);
0445:
0446: Object val = prop.val;
0447: if (Symbols.Timestamp.equals(prop.name)) {
0448: if (val instanceof Range) {
0449: Range range = (Range) val;
0450: if (range.from instanceof Date) {
0451: Key fromKey = new Key((Date) range.from,
0452: range.fromInclusive);
0453: Key tillKey = new Key((Date) range.till,
0454: range.tillInclusive);
0455: return new SearchResult(
0456: root,
0457: type,
0458: uri,
0459: restOfPatterns,
0460: kind,
0461: timestamp,
0462: new ReferenceIterator(
0463: root,
0464: refProps,
0465: root.timeIndex
0466: .iterator(fromKey, tillKey,
0467: Index.ASCENT_ORDER),
0468: kind, timestamp));
0469: }
0470: } else if (val instanceof Date) {
0471: Key key = new Key((Date) val);
0472: return new SearchResult(root, type, uri,
0473: restOfPatterns, kind, timestamp,
0474: new ReferenceIterator(root, refProps,
0475: root.timeIndex.iterator(key, key,
0476: Index.ASCENT_ORDER), kind,
0477: timestamp));
0478: }
0479: return EmptyIterator;
0480: } else if (Symbols.Rectangle.equals(prop.name)) {
0481: if (val instanceof NameVal[]) {
0482: NameVal[] coord = (NameVal[]) val;
0483: if (coord.length == 4) {
0484: RectangleR2 r = new RectangleR2(
0485: ((Number) coord[0].val).doubleValue(),
0486: ((Number) coord[1].val).doubleValue(),
0487: ((Number) coord[2].val).doubleValue(),
0488: ((Number) coord[3].val).doubleValue());
0489: return new SearchResult(root, type, uri,
0490: restOfPatterns, kind, timestamp,
0491: new ReferenceIterator(root, refProps,
0492: root.spatialIndex.iterator(r),
0493: kind, timestamp));
0494: }
0495: }
0496: } else if (Symbols.Point.equals(prop.name)) {
0497: if (val instanceof NameVal[]) {
0498: NameVal[] coord = (NameVal[]) val;
0499: if (coord.length == 2) {
0500: double x = ((Number) coord[0].val).doubleValue();
0501: double y = ((Number) coord[1].val).doubleValue();
0502: RectangleR2 r = new RectangleR2(x, y, x, y);
0503: return new SearchResult(root, type, uri,
0504: restOfPatterns, kind, timestamp,
0505: new ReferenceIterator(root, refProps,
0506: root.spatialIndex.iterator(r),
0507: kind, timestamp));
0508: }
0509: }
0510: } else if (Symbols.Keyword.equals(prop.name)) {
0511: if (val instanceof String) {
0512: ArrayList keywords = getKeywords((String) val);
0513: Iterator[] occurences = new Iterator[keywords.size()];
0514: for (int i = 0; i < occurences.length; i++) {
0515: Key key = new Key((String) keywords.get(i));
0516: occurences[i] = root.inverseIndex.iterator(key,
0517: key, Index.ASCENT_ORDER);
0518: }
0519: return new SearchResult(root, type, uri,
0520: restOfPatterns, kind, timestamp,
0521: new ReferenceIterator(root, refProps, db
0522: .merge(occurences), kind, timestamp));
0523: }
0524: }
0525:
0526: def = (PropDef) root.propDefIndex.get(prop.name);
0527: if (def == null) {
0528: return EmptyIterator;
0529: }
0530: if (val instanceof Range) {
0531: Range range = (Range) val;
0532: if (range.from instanceof Number) {
0533: Key fromKey = new Key(new Object[] { def, range.from },
0534: range.fromInclusive);
0535: Key tillKey = new Key(new Object[] { def, range.till },
0536: range.tillInclusive);
0537: return new SearchResult(root, type, uri,
0538: restOfPatterns, kind, timestamp,
0539: new ReferenceIterator(root, refProps,
0540: root.numPropIndex.iterator(fromKey,
0541: tillKey, Index.ASCENT_ORDER),
0542: kind, timestamp));
0543: } else if (range.from instanceof Date) {
0544: Key fromKey = new Key(new Object[] { def, range.from },
0545: range.fromInclusive);
0546: Key tillKey = new Key(new Object[] { def, range.till },
0547: range.tillInclusive);
0548: return new SearchResult(root, type, uri,
0549: restOfPatterns, kind, timestamp,
0550: new ReferenceIterator(root, refProps,
0551: root.timePropIndex.iterator(fromKey,
0552: tillKey, Index.ASCENT_ORDER),
0553: kind, timestamp));
0554: } else {
0555: Key fromKey = new Key(new Object[] { def, range.from },
0556: range.fromInclusive);
0557: Key tillKey = new Key(new Object[] { def, range.till },
0558: range.tillInclusive);
0559: return new SearchResult(root, type, uri,
0560: restOfPatterns, kind, timestamp,
0561: new ReferenceIterator(root, refProps,
0562: root.strPropIndex.iterator(fromKey,
0563: tillKey, Index.ASCENT_ORDER),
0564: kind, timestamp));
0565: }
0566: }
0567: if (val instanceof String) {
0568: String str = (String) prop.val;
0569: int wc = str.indexOf('*');
0570: if (wc < 0) {
0571: Key key = new Key(new Object[] { def, str });
0572: return new SearchResult(root, type, uri,
0573: restOfPatterns, kind, timestamp,
0574: new ReferenceIterator(root, refProps,
0575: root.strPropIndex.iterator(key, key,
0576: Index.ASCENT_ORDER), kind,
0577: timestamp));
0578: } else if (wc > 0) {
0579: String prefix = str.substring(0, wc);
0580: Key fromKey = new Key(new Object[] { def, prefix });
0581: Key tillKey = new Key(new Object[] { def,
0582: prefix + Character.MAX_VALUE }, false);
0583: return new SearchResult(root, type, uri, wc == str
0584: .length() - 1 ? restOfPatterns : patterns,
0585: kind, timestamp, new ReferenceIterator(root,
0586: refProps, root.strPropIndex.iterator(
0587: fromKey, tillKey,
0588: Index.ASCENT_ORDER), kind,
0589: timestamp));
0590: }
0591: } else if (val instanceof Number) {
0592: Key key = new Key(new Object[] { def, val });
0593: return new SearchResult(root, type, uri, restOfPatterns,
0594: kind, timestamp, new ReferenceIterator(root,
0595: refProps, root.numPropIndex.iterator(key,
0596: key, Index.ASCENT_ORDER), kind,
0597: timestamp));
0598: } else if (val instanceof Date) {
0599: Key key = new Key(new Object[] { def, val });
0600: return new SearchResult(root, type, uri, restOfPatterns,
0601: kind, timestamp, new ReferenceIterator(root,
0602: refProps, root.timePropIndex.iterator(key,
0603: key, Index.ASCENT_ORDER), kind,
0604: timestamp));
0605: } else if (val instanceof NameVal) {
0606: return searchReferenceProperty(type, uri, patterns, kind,
0607: timestamp, (NameVal) val, compound, def, refs);
0608: } else if (val instanceof NameVal[]) {
0609: NameVal[] props = (NameVal[]) val;
0610: if (props.length > 0) {
0611: return searchReferenceProperty(type, uri, patterns,
0612: kind, timestamp, props[0], true, def, refs);
0613: }
0614: }
0615: return null;
0616: }
0617:
0618: /**
0619: * Close database
0620: */
0621: public void close() {
0622: db.close();
0623: }
0624:
0625: /**
0626: * Commit current transaction
0627: */
0628: public void commit() {
0629: db.commit();
0630: root.unlock();
0631: }
0632:
0633: /**
0634: * Rollback current transaction
0635: */
0636: public void rollback() {
0637: db.rollback();
0638: root.unlock();
0639: }
0640:
0641: /**
0642: * Begin new write transction: set exclusive lock
0643: */
0644: public void beginTransaction() {
0645: root.exclusiveLock();
0646: }
0647:
0648: static class SearchResult implements Iterator {
0649: VersionHistory type;
0650: String uri;
0651: NameVal[] patterns;
0652: SearchKind kind;
0653: Date timestamp;
0654: Iterator iterator;
0655: Thing currThing;
0656: int currVersion;
0657: Link currHistory;
0658: DatabaseRoot root;
0659:
0660: public SearchResult(DatabaseRoot root, VersionHistory type,
0661: String uri, NameVal[] patterns, SearchKind kind,
0662: Date timestamp, Iterator iterator) {
0663: this .root = root;
0664: this .type = type;
0665: this .uri = uri;
0666: this .patterns = patterns;
0667: this .kind = kind;
0668: this .timestamp = timestamp;
0669: this .iterator = iterator;
0670: gotoNext();
0671: }
0672:
0673: public boolean hasNext() {
0674: return currThing != null;
0675: }
0676:
0677: public Object next() {
0678: if (currThing == null) {
0679: throw new NoSuchElementException();
0680: }
0681: Thing thing = currThing;
0682: gotoNext();
0683: return thing;
0684: }
0685:
0686: public void remove() {
0687: throw new UnsupportedOperationException();
0688: }
0689:
0690: private void gotoNext() {
0691: Repeat: while (true) {
0692: if (currHistory != null) {
0693: while (currVersion < currHistory.size()) {
0694: Thing thing = (Thing) currHistory
0695: .get(currVersion++);
0696: if (match(thing)) {
0697: return;
0698: }
0699: }
0700: currHistory = null;
0701: }
0702: while (iterator.hasNext()) {
0703: Object curr = iterator.next();
0704: if (curr instanceof Thing) {
0705: if (match((Thing) curr)) {
0706: return;
0707: }
0708: } else if (curr instanceof VersionHistory) {
0709: currHistory = ((VersionHistory) curr).versions;
0710: currVersion = 0;
0711: continue Repeat;
0712: }
0713: }
0714: currThing = null;
0715: return;
0716: }
0717: }
0718:
0719: private static boolean matchString(String str, String pat) {
0720: if (pat.indexOf('*') < 0) {
0721: return pat.equals(str);
0722: }
0723: int pi = 0, si = 0, pn = pat.length(), sn = str.length();
0724: int wildcard = -1, strpos = -1;
0725: while (true) {
0726: if (pi < pn && pat.charAt(pi) == '*') {
0727: wildcard = ++pi;
0728: strpos = si;
0729: } else if (si == sn) {
0730: return pi == pn;
0731: } else if (pi < pn && str.charAt(si) == pat.charAt(pi)) {
0732: si += 1;
0733: pi += 1;
0734: } else if (wildcard >= 0) {
0735: si = ++strpos;
0736: pi = wildcard;
0737: } else {
0738: return false;
0739: }
0740: }
0741: }
0742:
0743: private boolean match(Thing thing) {
0744: if (type != null
0745: && !thing.isInstanceOf(type, kind, timestamp)) {
0746: return false;
0747: }
0748: if (kind == SearchKind.LatestVersion) {
0749: if (!thing.isLatest()) {
0750: return false;
0751: }
0752: } else if (kind == SearchKind.LatestBefore) {
0753: if (thing.timestamp.compareTo(timestamp) > 0
0754: || thing.vh.getLatestBefore(timestamp) != thing) {
0755: return false;
0756: }
0757: } else if (kind == SearchKind.OldestAfter) {
0758: if (thing.timestamp.compareTo(timestamp) < 0
0759: || thing.vh.getOldestAfter(timestamp) != thing) {
0760: return false;
0761: }
0762: }
0763:
0764: if (uri != null) {
0765: if (!matchString(thing.vh.uri, uri)) {
0766: return false;
0767: }
0768: }
0769: for (int i = 0; i < patterns.length; i++) {
0770: if (!matchProperty(patterns[i], thing)) {
0771: return false;
0772: }
0773: }
0774: currThing = thing;
0775: return true;
0776: }
0777:
0778: private boolean matchProperty(NameVal prop, Thing thing) {
0779: if (Symbols.Point.equals(prop.name)) {
0780: if (prop.val instanceof NameVal[]) {
0781: NameVal[] coord = (NameVal[]) prop.val;
0782: if (coord.length == 2) {
0783: double x = ((Number) coord[0].val)
0784: .doubleValue();
0785: double y = ((Number) coord[1].val)
0786: .doubleValue();
0787: RectangleR2 r = new RectangleR2(x, y, x, y);
0788: Iterator i = root.spatialIndex.iterator(r);
0789: while (i.hasNext()) {
0790: if (i.next() == thing) {
0791: return true;
0792: }
0793: }
0794: return false;
0795: }
0796: }
0797: } else if (Symbols.Rectangle.equals(prop.name)) {
0798: if (prop.val instanceof NameVal[]) {
0799: NameVal[] coord = (NameVal[]) prop.val;
0800: if (coord.length == 4) {
0801: RectangleR2 r = new RectangleR2(
0802: ((Number) coord[0].val).doubleValue(),
0803: ((Number) coord[1].val).doubleValue(),
0804: ((Number) coord[2].val).doubleValue(),
0805: ((Number) coord[3].val).doubleValue());
0806: Iterator i = root.spatialIndex.iterator(r);
0807: while (i.hasNext()) {
0808: if (i.next() == thing) {
0809: return true;
0810: }
0811: }
0812: return false;
0813: }
0814: }
0815: } else if (Symbols.Keyword.equals(prop.name)) {
0816: if (prop.val instanceof String) {
0817: HashSet allKeywords = new HashSet();
0818: for (int i = 0; i < thing.props.length; i++) {
0819: PropVal pv = thing.props[i];
0820: Object val = pv.val;
0821: if (val instanceof String) {
0822: ArrayList keywords = getKeywords((String) val);
0823: allKeywords.addAll(keywords);
0824: }
0825: }
0826: ArrayList keywords = getKeywords((String) prop.val);
0827: return allKeywords.containsAll(keywords);
0828: }
0829: }
0830: Object[] propVal = thing.get(prop.name);
0831: NextItem: for (int i = 0; i < propVal.length; i++) {
0832: Object val = propVal[i];
0833: Object pattern = prop.val;
0834: if (val instanceof String && pattern instanceof String) {
0835: if (matchString((String) val, (String) pattern)) {
0836: return true;
0837: }
0838: } else if (pattern instanceof NameVal) {
0839: if (val instanceof VersionHistory
0840: && followReference((NameVal) pattern,
0841: (VersionHistory) val)) {
0842: return true;
0843: }
0844: } else if (pattern instanceof NameVal[]) {
0845: if (val instanceof VersionHistory) {
0846: NameVal[] arr = (NameVal[]) prop.val;
0847: for (int j = 0; j < arr.length; j++) {
0848: if (!followReference(arr[j],
0849: (VersionHistory) val)) {
0850: continue NextItem;
0851: }
0852: }
0853: return true;
0854: }
0855: } else if (pattern instanceof Range
0856: && val instanceof Comparable) {
0857: try {
0858: Range range = (Range) pattern;
0859: Comparable cmp = (Comparable) val;
0860: return cmp.compareTo(range.from) >= (range.fromInclusive ? 0
0861: : 1)
0862: && cmp.compareTo(range.till) <= (range.tillInclusive ? 0
0863: : -1);
0864: } catch (ClassCastException x) {
0865: }
0866: } else if (pattern != null && pattern.equals(val)) {
0867: return true;
0868: }
0869: }
0870: return false;
0871: }
0872:
0873: private boolean followReference(NameVal prop, VersionHistory vh) {
0874: if (vh != null) {
0875: if (kind == SearchKind.AllVersions) {
0876: for (int i = 0, n = vh.versions.size(); i < n; i++) {
0877: Thing v = (Thing) vh.versions.get(i);
0878: if (matchProperty(prop, v)) {
0879: return true;
0880: }
0881: }
0882: } else {
0883: Thing thing = vh.getVersion(kind, timestamp);
0884: return thing != null && matchProperty(prop, thing);
0885: }
0886: }
0887: return false;
0888: }
0889: }
0890:
0891: private void createMetaType() {
0892: VersionHistory vh = createVersionHistory(Symbols.Metatype, null);
0893: vh.type = vh;
0894: Thing metatype = createObject(null, vh, new NameVal[0]);
0895: metatype.type = metatype;
0896: root.metatype = vh;
0897: }
0898:
0899: private static String reverseString(String s) {
0900: int len = s.length();
0901: char[] chars = new char[len];
0902: for (int i = 0; i < len; i++) {
0903: chars[i] = s.charAt(len - i - 1);
0904: }
0905: return new String(chars);
0906: }
0907:
0908: private VersionHistory createVersionHistory(String uri,
0909: VersionHistory type) {
0910: VersionHistory vh = new VersionHistory();
0911: vh.uri = uri;
0912: vh.type = type;
0913: vh.versions = db.createLink();
0914: root.prefixUriIndex.put(uri, vh);
0915: root.suffixUriIndex.put(reverseString(uri), vh);
0916: return vh;
0917: }
0918:
0919: private static NameVal[] subArray(NameVal[] arr) {
0920: NameVal[] newArr = new NameVal[arr.length - 1];
0921: System.arraycopy(arr, 1, newArr, 0, newArr.length);
0922: return newArr;
0923: }
0924:
0925: private Thing createObject(Thing type, VersionHistory vh,
0926: NameVal[] props) {
0927: Thing thing = new Thing();
0928: thing.vh = vh;
0929: thing.type = type;
0930: thing.timestamp = new Date();
0931: thing.props = new PropVal[props.length];
0932: for (int i = 0; i < props.length; i++) {
0933: thing.props[i] = new PropVal();
0934: }
0935: for (int i = 0; i < props.length; i++) {
0936: NameVal prop = props[i];
0937: PropDef def = (PropDef) root.propDefIndex.get(prop.name);
0938: if (def == null) {
0939: def = new PropDef();
0940: def.name = prop.name;
0941: root.propDefIndex.put(def);
0942: }
0943: Object val = prop.val;
0944: PropVal pv = thing.props[i];
0945: pv.def = def;
0946: pv.val = val;
0947: Key key = new Key(new Object[] { def, val });
0948: if (val instanceof String) {
0949: root.strPropIndex.put(key, thing);
0950: ArrayList keywords = getKeywords((String) val);
0951: for (int j = keywords.size(); --j >= 0;) {
0952: root.inverseIndex.put((String) keywords.get(j),
0953: thing);
0954: }
0955: } else if (val instanceof Number) {
0956: root.numPropIndex.put(key, thing);
0957: } else if (val instanceof Date) {
0958: root.timePropIndex.put(key, thing);
0959: } else if (val instanceof VersionHistory || val == null) {
0960: root.refPropIndex.put(key, thing);
0961: if (Symbols.Rectangle.equals(prop.name)) {
0962: PropVal[] coord = ((VersionHistory) val)
0963: .getLatest().props;
0964: RectangleR2 r = new RectangleR2(
0965: ((Number) coord[0].val).doubleValue(),
0966: ((Number) coord[1].val).doubleValue(),
0967: ((Number) coord[2].val).doubleValue(),
0968: ((Number) coord[3].val).doubleValue());
0969: root.spatialIndex.put(r, thing);
0970: } else if (Symbols.Rectangle.equals(prop.name)) {
0971: PropVal[] coord = ((VersionHistory) val)
0972: .getLatest().props;
0973: double x = ((Number) coord[0].val).doubleValue();
0974: double y = ((Number) coord[1].val).doubleValue();
0975: RectangleR2 r = new RectangleR2(x, y, x, y);
0976: root.spatialIndex.put(r, thing);
0977: }
0978: } else {
0979: throw new IllegalArgumentException(
0980: "Invalid propery value type "
0981: + prop.val.getClass());
0982: }
0983: }
0984: thing.modify();
0985: vh.versions.add(thing);
0986: root.timeIndex.put(thing);
0987: root.latest.add(thing);
0988: return thing;
0989: }
0990:
0991: private static ArrayList getKeywords(String str) {
0992: ArrayList list = new ArrayList();
0993: char[] separators = keywordSeparators;
0994: str = str.toLowerCase();
0995: int len = str.length();
0996: int p = 0;
0997: do {
0998: int minNp = len;
0999: for (int i = 0; i < separators.length; i++) {
1000: int np = str.indexOf(separators[i], p);
1001: if (np >= 0 && np < minNp) {
1002: minNp = np;
1003: }
1004: }
1005: if (minNp - p > 1) {
1006: String keyword = str.substring(p, minNp);
1007: if (!keywordStopList.contains(keyword)) {
1008: list.add(keyword);
1009: }
1010: }
1011: p = minNp + 1;
1012: } while (p < len);
1013: return list;
1014: }
1015: }
|