1 /**
2  *  Copyright 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         // since it is all inclusive
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 }
227