View Javadoc
1   /*
2    * Copyright (c) 2000, 2003, Oracle and/or its affiliates. All rights reserved.
3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4    *
5    * This code is free software; you can redistribute it and/or modify it
6    * under the terms of the GNU General Public License version 2 only, as
7    * published by the Free Software Foundation.
8    *
9    * This code is distributed in the hope that it will be useful, but WITHOUT
10   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12   * version 2 for more details (a copy is included in the LICENSE file that
13   * accompanied this code).
14   *
15   * You should have received a copy of the GNU General Public License version
16   * 2 along with this work; if not, write to the Free Software Foundation,
17   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18   *
19   * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20   * or visit www.oracle.com if you need additional information or have any
21   * questions.
22   *
23   */
24  
25  package sun.jvm.hotspot.utilities;
26  
27  /** Derived from the example in Section 15.3 of CLR. */
28  
29  import java.util.Comparator;
30  
31  public class IntervalNode extends RBNode {
32    private Interval   interval;
33    private Comparator endpointComparator;
34    private Object     minEndpoint;
35    private Object     maxEndpoint;
36  
37    public IntervalNode(Interval interval, Comparator endpointComparator, Object data) {
38      super(data);
39      this.interval = interval;
40      this.endpointComparator = endpointComparator;
41    }
42  
43    public void copyFrom(RBNode arg) {
44      IntervalNode argNode = (IntervalNode) arg;
45      this.interval = argNode.interval;
46    }
47  
48    public Interval getInterval() {
49      return interval;
50    }
51  
52    public Object getMinEndpoint() {
53      return minEndpoint;
54    }
55  
56    public Object getMaxEndpoint() {
57      return maxEndpoint;
58    }
59  
60    public boolean update() {
61      Object newMaxEndpoint = computeMaxEndpoint();
62      Object newMinEndpoint = computeMinEndpoint();
63  
64      if ((maxEndpoint != newMaxEndpoint) || (minEndpoint != newMinEndpoint)) {
65        maxEndpoint = newMaxEndpoint;
66        minEndpoint = newMinEndpoint;
67        return true;
68      }
69  
70      return false;
71    }
72  
73    // Computes maximum endpoint without setting it in this node
74    public Object computeMinEndpoint() {
75      IntervalNode left = (IntervalNode) getLeft();
76      if (left != null) {
77        return left.getMinEndpoint();
78      }
79      return interval.getLowEndpoint();
80    }
81  
82    // Computes maximum endpoint without setting it in this node
83    public Object computeMaxEndpoint() {
84      Object curMax = interval.getHighEndpoint();
85      if (getLeft() != null) {
86        IntervalNode left = (IntervalNode) getLeft();
87        if (endpointComparator.compare(left.getMaxEndpoint(), curMax) > 0) {
88          curMax = left.getMaxEndpoint();
89        }
90      }
91  
92      if (getRight() != null) {
93        IntervalNode right = (IntervalNode) getRight();
94        if (endpointComparator.compare(right.getMaxEndpoint(), curMax) > 0) {
95          curMax = right.getMaxEndpoint();
96        }
97      }
98      return curMax;
99    }
100 
101   public String toString() {
102     String res = interval.toString();
103     Object d = getData();
104     if (d != null) {
105       res += " " + d;
106     }
107     return res;
108   }
109 }