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.db4ounit.common.btree;
022:
023: import com.db4o.internal.btree.*;
024:
025: import db4ounit.Assert;
026:
027: public class BTreeRangeTestCase extends BTreeTestCaseBase {
028:
029: public static void main(String[] args) {
030: new BTreeRangeTestCase().runSolo();
031: }
032:
033: protected void db4oSetupAfterStore() throws Exception {
034: super .db4oSetupAfterStore();
035: add(new int[] { 3, 7, 4, 9 });
036: }
037:
038: public void testLastPointer() {
039: assertLastPointer(8, 7);
040: assertLastPointer(11, 9);
041: assertLastPointer(4, 3);
042: }
043:
044: private void assertLastPointer(final int searchValue,
045: final int expectedValue) {
046: BTreeRange single = search(searchValue);
047: BTreeRange smallerRange = single.smaller();
048: BTreePointer lastPointer = smallerRange.lastPointer();
049: Assert.areEqual(new Integer(expectedValue), lastPointer.key());
050: }
051:
052: public void testSize() {
053: assertSize(4, range(3, 9));
054: assertSize(3, range(4, 9));
055: assertSize(3, range(3, 7));
056: assertSize(4, range(2, 9));
057: assertSize(4, range(3, 10));
058:
059: add(new int[] { 5, 6, 8, 10, 2, 1 });
060: assertSize(10, range(1, 10));
061: assertSize(9, range(1, 9));
062: assertSize(9, range(2, 10));
063: assertSize(9, range(2, 11));
064: assertSize(10, range(0, 10));
065: }
066:
067: private void assertSize(int size, BTreeRange range) {
068: Assert.areEqual(size, range.size());
069: }
070:
071: public void testIntersectSingleSingle() {
072: assertIntersection(new int[] { 4, 7 }, range(3, 7), range(4, 9));
073: assertIntersection(new int[] {}, range(3, 4), range(7, 9));
074: assertIntersection(new int[] { 3, 4, 7, 9 }, range(3, 9),
075: range(3, 9));
076: assertIntersection(new int[] { 3, 4, 7, 9 }, range(3, 10),
077: range(3, 9));
078: assertIntersection(new int[] {}, range(1, 2), range(3, 9));
079: }
080:
081: public void testIntersectSingleUnion() {
082: BTreeRange union = range(3, 3).union(range(7, 9));
083: BTreeRange single = range(4, 7);
084: assertIntersection(new int[] { 7 }, union, single);
085: assertIntersection(new int[] { 3, 7 }, union, range(3, 7));
086: }
087:
088: public void testIntersectUnionUnion() {
089: final BTreeRange union1 = range(3, 3).union(range(7, 9));
090: final BTreeRange union2 = range(3, 3).union(range(9, 9));
091: assertIntersection(new int[] { 3, 9 }, union1, union2);
092: }
093:
094: public void testUnion() {
095: assertUnion(new int[] { 3, 4, 7, 9 }, range(3, 4), range(7, 9));
096: assertUnion(new int[] { 3, 4, 7, 9 }, range(3, 7), range(4, 9));
097: assertUnion(new int[] { 3, 7, 9 }, range(3, 3), range(7, 9));
098: assertUnion(new int[] { 3, 9 }, range(3, 3), range(9, 9));
099: }
100:
101: public void testIsEmpty() {
102: Assert.isTrue(range(0, 0).isEmpty());
103: Assert.isFalse(range(3, 3).isEmpty());
104: Assert.isFalse(range(9, 9).isEmpty());
105: Assert.isTrue(range(10, 10).isEmpty());
106: }
107:
108: public void testUnionWithEmptyDoesNotCreateNewRange() {
109: final BTreeRange range = range(3, 4);
110: final BTreeRange empty = range(0, 0);
111: Assert.areSame(range, range.union(empty));
112: Assert.areSame(range, empty.union(range));
113:
114: final BTreeRange union = range.union(range(8, 9));
115: Assert.areSame(union, union.union(empty));
116: Assert.areSame(union, empty.union(union));
117: }
118:
119: public void testUnionsMerge() {
120: final BTreeRange range = range(3, 3).union(range(7, 7)).union(
121: range(4, 4));
122: assertIsRangeSingle(range);
123: BTreeAssert.assertRange(new int[] { 3, 4, 7 }, range);
124: }
125:
126: private void assertIsRangeSingle(final BTreeRange range) {
127: Assert.isInstanceOf(BTreeRangeSingle.class, range);
128: }
129:
130: public void testUnionsOfUnions() {
131: final BTreeRange union1 = range(3, 4).union(range(8, 9));
132:
133: BTreeAssert.assertRange(new int[] { 3, 4, 9 }, union1);
134: BTreeAssert.assertRange(new int[] { 3, 4, 7, 9 }, union1
135: .union(range(7, 7)));
136:
137: final BTreeRange union2 = range(3, 3).union(range(7, 7));
138: assertUnion(new int[] { 3, 4, 7, 9 }, union1, union2);
139:
140: assertIsRangeSingle(union1.union(union2));
141: assertIsRangeSingle(union2.union(union1));
142:
143: final BTreeRange union3 = range(3, 3).union(range(9, 9));
144: assertUnion(new int[] { 3, 7, 9 }, union2, union3);
145: }
146:
147: public void testExtendToLastOf() {
148: BTreeAssert.assertRange(new int[] { 3, 4, 7 }, range(3, 7));
149: BTreeAssert.assertRange(new int[] { 4, 7, 9 }, range(4, 9));
150: }
151:
152: public void testUnionOfOverlappingSingleRangesYieldSingleRange() {
153: Assert.isInstanceOf(BTreeRangeSingle.class, range(3, 4).union(
154: range(4, 9)));
155: }
156:
157: private void assertUnion(int[] expectedKeys, BTreeRange range1,
158: BTreeRange range2) {
159: BTreeAssert.assertRange(expectedKeys, range1.union(range2));
160: BTreeAssert.assertRange(expectedKeys, range2.union(range1));
161: }
162:
163: private void assertIntersection(int[] expectedKeys,
164: BTreeRange range1, BTreeRange range2) {
165: BTreeAssert.assertRange(expectedKeys, range1.intersect(range2));
166: BTreeAssert.assertRange(expectedKeys, range2.intersect(range1));
167: }
168: }
|