001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
002:
003: This file is part of the db4o open source object database.
004:
005: db4o is free software; you can redistribute it and/or modify it under
006: the terms of version 2 of the GNU General Public License as published
007: by the Free Software Foundation and as clarified by db4objects' GPL
008: interpretation policy, available at
009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
011: Suite 350, San Mateo, CA 94403, USA.
012:
013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: for more details.
017:
018: You should have received a copy of the GNU General Public License along
019: with this program; if not, write to the Free Software Foundation, Inc.,
020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
021: package com.db4o.internal.btree.algebra;
022:
023: import com.db4o.foundation.*;
024: import com.db4o.internal.btree.*;
025:
026: /**
027: * @exclude
028: */
029: class BTreeAlgebra {
030:
031: public static BTreeRange intersect(BTreeRangeUnion union,
032: BTreeRangeSingle single) {
033: final SortedCollection4 collection = newBTreeRangeSingleCollection();
034: collectIntersections(collection, union, single);
035: return toRange(collection);
036: }
037:
038: public static BTreeRange intersect(BTreeRangeUnion union1,
039: BTreeRangeUnion union2) {
040: final SortedCollection4 collection = newBTreeRangeSingleCollection();
041: final Iterator4 ranges = union1.ranges();
042: while (ranges.moveNext()) {
043: final BTreeRangeSingle current = (BTreeRangeSingle) ranges
044: .current();
045: collectIntersections(collection, union2, current);
046: }
047: return toRange(collection);
048: }
049:
050: private static void collectIntersections(
051: final SortedCollection4 collection, BTreeRangeUnion union,
052: BTreeRangeSingle single) {
053: final Iterator4 ranges = union.ranges();
054: while (ranges.moveNext()) {
055: final BTreeRangeSingle current = (BTreeRangeSingle) ranges
056: .current();
057: if (single.overlaps(current)) {
058: collection.add(single.intersect(current));
059: }
060: }
061: }
062:
063: public static BTreeRange intersect(BTreeRangeSingle single1,
064: BTreeRangeSingle single2) {
065: BTreePointer first = BTreePointer.max(single1.first(), single2
066: .first());
067: BTreePointer end = BTreePointer.min(single1.end(), single2
068: .end());
069: return single1.newBTreeRangeSingle(first, end);
070: }
071:
072: public static BTreeRange union(final BTreeRangeUnion union1,
073: final BTreeRangeUnion union2) {
074: final Iterator4 ranges = union1.ranges();
075: BTreeRange merged = union2;
076: while (ranges.moveNext()) {
077: merged = merged.union((BTreeRange) ranges.current());
078: }
079: return merged;
080: }
081:
082: public static BTreeRange union(final BTreeRangeUnion union,
083: final BTreeRangeSingle single) {
084: if (single.isEmpty()) {
085: return union;
086: }
087:
088: SortedCollection4 sorted = newBTreeRangeSingleCollection();
089: sorted.add(single);
090:
091: BTreeRangeSingle range = single;
092: Iterator4 ranges = union.ranges();
093: while (ranges.moveNext()) {
094: BTreeRangeSingle current = (BTreeRangeSingle) ranges
095: .current();
096: if (canBeMerged(current, range)) {
097: sorted.remove(range);
098: range = merge(current, range);
099: sorted.add(range);
100: } else {
101: sorted.add(current);
102: }
103: }
104:
105: return toRange(sorted);
106: }
107:
108: private static BTreeRange toRange(SortedCollection4 sorted) {
109: if (1 == sorted.size()) {
110: return (BTreeRange) sorted.singleElement();
111: }
112: return new BTreeRangeUnion(sorted);
113: }
114:
115: private static SortedCollection4 newBTreeRangeSingleCollection() {
116: return new SortedCollection4(BTreeRangeSingle.COMPARISON);
117: }
118:
119: public static BTreeRange union(final BTreeRangeSingle single1,
120: final BTreeRangeSingle single2) {
121: if (single1.isEmpty()) {
122: return single2;
123: }
124: if (single2.isEmpty()) {
125: return single1;
126: }
127: if (canBeMerged(single1, single2)) {
128: return merge(single1, single2);
129: }
130: return new BTreeRangeUnion(new BTreeRangeSingle[] { single1,
131: single2 });
132: }
133:
134: private static BTreeRangeSingle merge(BTreeRangeSingle range1,
135: BTreeRangeSingle range2) {
136: return range1.newBTreeRangeSingle(BTreePointer.min(range1
137: .first(), range2.first()), BTreePointer.max(range1
138: .end(), range2.end()));
139: }
140:
141: private static boolean canBeMerged(BTreeRangeSingle range1,
142: BTreeRangeSingle range2) {
143: return range1.overlaps(range2) || range1.adjacent(range2);
144: }
145: }
|