| 403 | } |
| 404 | |
| 405 | public Path<T> find(T value) { |
| 406 | Node<T> newRoot = new Node(root); |
| 407 | Cell<Node<T>> ancestors = null; |
| 408 | |
| 409 | Node<T> old = root; |
| 410 | Node<T> new_ = newRoot; |
| 411 | while (old != NullNode) { |
| 412 | ancestors = new Cell(new_, ancestors); |
| 413 | |
| 414 | int difference = comparator.compare(value, old.value); |
| 415 | if (difference < 0) { |
| 416 | old = old.left; |
| 417 | new_ = new_.left = new Node(old); |
| 418 | } else if (difference > 0) { |
| 419 | old = old.right; |
| 420 | new_ = new_.right = new Node(old); |
| 421 | } else { |
| 422 | return new Path(false, new_, |
| 423 | new PersistentSet(newRoot, comparator, size), |
| 424 | ancestors.next); |
| 425 | } |
| 426 | } |
| 427 | |
| 428 | new_.value = value; |
| 429 | return new Path(true, new_, |
| 430 | new PersistentSet(newRoot, comparator, size), |
| 431 | ancestors); |
| 432 | } |
| 433 | |
| 434 | public Path<T> first() { |
| 435 | if (root == NullNode) return null; |