1 /***
2 * Copyright 2003-2010 Terracotta, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 package net.sf.ehcache.store.disk.ods;
17
18 /***
19 * Class that represents the regions held within this set.
20 *
21 * @author Chris Dennis
22 */
23 public class Region extends AATreeSet.AbstractTreeNode<Comparable> implements Comparable<Comparable> {
24 private long start;
25 private long end;
26
27 private long contiguous;
28
29 /***
30 * Creates a region containing just the single given value
31 * @param value
32 */
33 public Region(long value) {
34 this(value, value);
35 }
36
37 /***
38 * Creates a region containing the given range of value (inclusive).
39 */
40 public Region(long start, long end) {
41 super();
42 this.start = start;
43 this.end = end;
44 updateContiguous();
45 }
46
47 /***
48 * Create a shallow copy of a region.
49 * <p>
50 * The new Region has NULL left and right children.
51 */
52 public Region(Region r) {
53 this(r.start(), r.end());
54 }
55
56 /***
57 * Return the size of the largest region linked from this node.
58 */
59 public long contiguous() {
60 if (getLeft().getPayload() == null && getRight().getPayload() == null) {
61 return size();
62 } else {
63 return contiguous;
64 }
65 }
66
67 private void updateContiguous() {
68 Region left = (Region) getLeft().getPayload();
69 Region right = (Region) getRight().getPayload();
70 long leftContiguous = left == null ? 0 : left.contiguous();
71 long rightContiguous = right == null ? 0 : right.contiguous();
72 contiguous = Math.max(size(), Math.max(leftContiguous, rightContiguous));
73 }
74
75 @Override
76 public void setLeft(AATreeSet.Node<Comparable> l) {
77 super.setLeft(l);
78 updateContiguous();
79 }
80
81 @Override
82 public void setRight(AATreeSet.Node<Comparable> r) {
83 super.setRight(r);
84 updateContiguous();
85 }
86
87 /***
88 * {@inheritDoc}
89 */
90 @Override
91 public String toString() {
92 return "Range(" + this.start + "," + this.end + ")" + " contiguous:" + this.contiguous();
93 }
94
95 /***
96 * Returns the size of this range (the number of values within its bounds).
97 */
98 public long size() {
99
100 return (isNull() ? 0 : this.end - this.start + 1);
101 }
102
103 /***
104 * Return true if this region is null, i.e. represents no valid range.
105 */
106 protected boolean isNull() {
107 return this.start > this.end;
108 }
109
110 /***
111 * Remove the supplied region from this region.
112 *
113 * @param r region to remove
114 * @return a possible extra region to be added, or null if none is required
115 * @throws IllegalArgumentException if this region does not completely enclose the supplied region
116 */
117 protected Region remove(Region r) throws IllegalArgumentException {
118 if (r.start < this.start || r.end > this.end) {
119 throw new IllegalArgumentException("Ranges : Illegal value passed to remove : " + this + " remove called for : " + r);
120 }
121 if (this.start == r.start) {
122 this.start = r.end + 1;
123 updateContiguous();
124 return null;
125 } else if (this.end == r.end) {
126 this.end = r.start - 1;
127 updateContiguous();
128 return null;
129 } else {
130 Region newRegion = new Region(r.end + 1, this.end);
131 this.end = r.start - 1;
132 updateContiguous();
133 return newRegion;
134 }
135 }
136
137 /***
138 * Merge the supplied region into this region (if they are adjoining).
139 *
140 * @param r region to merge
141 * @throws IllegalArgumentException if the regions are not adjoining
142 */
143 protected void merge(Region r) throws IllegalArgumentException {
144 if (this.start == r.end + 1) {
145 this.start = r.start;
146 } else if (this.end == r.start - 1) {
147 this.end = r.end;
148 } else {
149 throw new IllegalArgumentException("Ranges : Merge called on non contiguous values : [this]:" + this + " and " + r);
150 }
151 updateContiguous();
152 }
153
154 /***
155 * {@inheritDoc}
156 */
157 public int compareTo(Comparable other) {
158 if (other instanceof Region) {
159 return compareTo((Region) other);
160 } else if (other instanceof Long) {
161 return compareTo((Long) other);
162 } else {
163 throw new AssertionError("Unusual Type " + other.getClass());
164 }
165 }
166
167 private int compareTo(Region r) {
168 if (this.start > r.start || this.end > r.end) {
169 return 1;
170 } else if (this.start < r.start || this.end < r.end) {
171 return -1;
172 } else {
173 return 0;
174 }
175 }
176
177 private int compareTo(Long l) {
178 if (l.longValue() > end) {
179 return -1;
180 } else if (l.longValue() < start) {
181 return 1;
182 } else {
183 return 0;
184 }
185 }
186
187 /***
188 * {@inheritDoc}
189 */
190 public void swapPayload(AATreeSet.Node<Comparable> other) {
191 if (other instanceof Region) {
192 Region r = (Region) other;
193 long temp = this.start;
194 this.start = r.start;
195 r.start = temp;
196 temp = this.end;
197 this.end = r.end;
198 r.end = temp;
199 updateContiguous();
200 } else {
201 throw new AssertionError();
202 }
203 }
204
205 /***
206 * {@inheritDoc}
207 */
208 public Region getPayload() {
209 return this;
210 }
211
212 /***
213 * Returns the start of this range (inclusive).
214 */
215 public long start() {
216 return start;
217 }
218
219 /***
220 * Returns the end of this range (inclusive).
221 */
222 public long end() {
223 return end;
224 }
225
226 }