Mercurial > dive4elements > river
comparison flys-artifacts/src/main/java/de/intevation/flys/artifacts/model/QRangeTree.java @ 4797:43e69af28b3c
A naive algorithm to figure out the "Umhuellende" of a set of WQKms.
| author | Sascha L. Teichmann <teichmann@intevation.de> |
|---|---|
| date | Sun, 13 Jan 2013 14:18:04 +0100 |
| parents | 729a5edb0313 |
| children | bcf25d8c183e |
comparison
equal
deleted
inserted
replaced
| 4796:729a5edb0313 | 4797:43e69af28b3c |
|---|---|
| 99 : Double.NaN; | 99 : Double.NaN; |
| 100 } | 100 } |
| 101 return current.q; | 101 return current.q; |
| 102 } | 102 } |
| 103 } | 103 } |
| 104 | |
| 105 public Node findNode(double pos) { | |
| 106 Node current = this; | |
| 107 while (current != null) { | |
| 108 if (pos < current.a) { | |
| 109 current = current.left; | |
| 110 } | |
| 111 else if (pos > current.b) { | |
| 112 current = current.right; | |
| 113 } | |
| 114 return current; | |
| 115 } | |
| 116 return null; | |
| 117 } | |
| 118 | |
| 119 public boolean contains(double c) { | |
| 120 return c >= a && c <= b; | |
| 121 } | |
| 104 } // class Node | 122 } // class Node |
| 123 | |
| 124 /** Class to cache the last found tree leaf in a search for Q. | |
| 125 * Its likely that a neighbored pos search | |
| 126 * results in using the same leaf node. So | |
| 127 * caching this leaf will minimize expensive | |
| 128 * tree traversals. | |
| 129 * Modeled as inner class because the QRangeTree | |
| 130 * itself is a shared data structure. | |
| 131 * Using this class omits interpolation between | |
| 132 * leaves. | |
| 133 */ | |
| 134 public final class QuickQFinder { | |
| 135 | |
| 136 private Node last; | |
| 137 | |
| 138 public QuickQFinder() { | |
| 139 } | |
| 140 | |
| 141 public double findQ(double pos) { | |
| 142 if (last != null && last.contains(pos)) { | |
| 143 return last.q; | |
| 144 } | |
| 145 last = QRangeTree.this.findNode(pos); | |
| 146 return last != null ? last.q : Double.NaN; | |
| 147 } | |
| 148 } // class QuickQFinder | |
| 105 | 149 |
| 106 protected Node root; | 150 protected Node root; |
| 107 | 151 |
| 108 public QRangeTree() { | 152 public QRangeTree() { |
| 109 } | 153 } |
| 208 return parent; | 252 return parent; |
| 209 } | 253 } |
| 210 | 254 |
| 211 public double findQ(double pos) { | 255 public double findQ(double pos) { |
| 212 return root != null ? root.findQ(pos) : Double.NaN; | 256 return root != null ? root.findQ(pos) : Double.NaN; |
| 257 } | |
| 258 | |
| 259 public Node findNode(double pos) { | |
| 260 return root != null ? root.findNode(pos) : null; | |
| 213 } | 261 } |
| 214 | 262 |
| 215 protected Node head() { | 263 protected Node head() { |
| 216 Node head = root; | 264 Node head = root; |
| 217 while (head.left != null) { | 265 while (head.left != null) { |