|
1
21 package com.db4o.inside.btree.algebra;
22
23 import com.db4o.foundation.*;
24 import com.db4o.inside.btree.*;
25
26
27
30 class BTreeAlgebra {
31
32 public static BTreeRange intersect(BTreeRangeUnion union, BTreeRangeSingle single) {
33 final SortedCollection4 collection = newBTreeRangeSingleCollection();
34 collectIntersections(collection, union, single);
35 return toRange(collection);
36 }
37
38 public static BTreeRange intersect(BTreeRangeUnion union1, BTreeRangeUnion union2) {
39 final SortedCollection4 collection = newBTreeRangeSingleCollection();
40 final Iterator4 ranges = union1.ranges();
41 while (ranges.moveNext()) {
42 final BTreeRangeSingle current = (BTreeRangeSingle) ranges.current();
43 collectIntersections(collection, union2, current);
44 }
45 return toRange(collection);
46 }
47
48 private static void collectIntersections(final SortedCollection4 collection, BTreeRangeUnion union, BTreeRangeSingle single) {
49 final Iterator4 ranges = union.ranges();
50 while (ranges.moveNext()) {
51 final BTreeRangeSingle current = (BTreeRangeSingle) ranges.current();
52 if (single.overlaps(current)) {
53 collection.add(single.intersect(current));
54 }
55 }
56 }
57
58 public static BTreeRange intersect(BTreeRangeSingle single1, BTreeRangeSingle single2) {
59 BTreePointer first = BTreePointer.max(single1.first(), single2.first());
60 BTreePointer end = BTreePointer.min(single1.end(), single2.end());
61 return single1.newBTreeRangeSingle(first, end);
62 }
63
64 public static BTreeRange union(final BTreeRangeUnion union1, final BTreeRangeUnion union2) {
65 final Iterator4 ranges = union1.ranges();
66 BTreeRange merged = union2;
67 while (ranges.moveNext()) {
68 merged = merged.union((BTreeRange) ranges.current());
69 }
70 return merged;
71 }
72
73 public static BTreeRange union(final BTreeRangeUnion union, final BTreeRangeSingle single) {
74 if (single.isEmpty()) {
75 return union;
76 }
77
78 SortedCollection4 sorted = newBTreeRangeSingleCollection();
79 sorted.add(single);
80
81 BTreeRangeSingle range = single;
82 Iterator4 ranges = union.ranges();
83 while (ranges.moveNext()) {
84 BTreeRangeSingle current = (BTreeRangeSingle) ranges.current();
85 if (canBeMerged(current, range)) {
86 sorted.remove(range);
87 range = merge(current, range);
88 sorted.add(range);
89 } else {
90 sorted.add(current);
91 }
92 }
93
94 return toRange(sorted);
95 }
96
97 private static BTreeRange toRange(SortedCollection4 sorted) {
98 if (1 == sorted.size()) {
99 return (BTreeRange)sorted.singleElement();
100 }
101 return new BTreeRangeUnion(sorted);
102 }
103
104 private static SortedCollection4 newBTreeRangeSingleCollection() {
105 return new SortedCollection4(BTreeRangeSingle.COMPARISON);
106 }
107
108 public static BTreeRange union(final BTreeRangeSingle single1, final BTreeRangeSingle single2) {
109 if (single1.isEmpty()) {
110 return single2;
111 }
112 if (single2.isEmpty()) {
113 return single1;
114 }
115 if (canBeMerged(single1, single2)) {
116 return merge(single1, single2);
117 }
118 return new BTreeRangeUnion(new BTreeRangeSingle[] { single1, single2 });
119 }
120
121 private static BTreeRangeSingle merge(BTreeRangeSingle range1, BTreeRangeSingle range2) {
122 return range1.newBTreeRangeSingle(
123 BTreePointer.min(range1.first(), range2.first()),
124 BTreePointer.max(range1.end(), range2.end()));
125 }
126
127 private static boolean canBeMerged(BTreeRangeSingle range1, BTreeRangeSingle range2) {
128 return range1.overlaps(range2)
129 || range1.adjacent(range2);
130 }
131 }
132 |
Popular Tags |
Java API By Example, From Geeks To Geeks.