fork download 
  1. import java.util.*;
  2. class TreeeSet<E> {
  3.     class Node {
  4. 		Node(E value) {this.value = value;}
  5. 		E value;
  6. 		Node left, right;
  7. 		void add(Node n, Comparator<E> comparator) {
  8. 			if (n == null || comparator == null) return;
  9.  
  10. 			int c = comparator.compare(this.value, n.value);
  11. 			if (c < 0) { // this < n
  12. 				if (right == null) right = n; else right.add(n, comparator);
  13. 			} else if (c > 0){
  14. 				if (left == null) left = n; else left.add(n, comparator);
  15. 			} else {/* nop */}
  16. 		}
  17. 		List<E> inject(List<E> list) {
  18. 			if (left != null) left.inject(list);
  19. 			list.add(value);
  20. 			if (right != null) right.inject(list);
  21. 			return list;
  22. 		}
  23. 		private Node removedright() {Node removed = right;right = null;return removed;}
  24. 		private Node removedleft() {Node removed = left;left = null;return removed;}
  25. 		Node remove(E value, Comparator<E> comparator) {
  26. 			if (value == null || comparator == null) return null;
  27.  
  28. 			int c = comparator.compare(this.value, value);
  29. 			if (c < 0 && right != null) { // this.value < value
  30. 				return comparator.compare(right.value, value) == 0 ? removedright() : right.remove(value, comparator);
  31. 			} else if (c > 0 && left != null) {
  32. 				return comparator.compare(left.value, value) == 0 ? removedleft() : left.remove(value, comparator);
  33. 			}
  34. 			return null;
  35. 		}
  36. 	}
  37. 	public TreeeSet(Comparator<E> comparator) {
  38. 		this.comparator = comparator;
  39. 	}
  40. 	public Comparator<E> comparator() {return comparator;}
  41. 	public void add(E value) {
  42. 		if (value == null) {
  43. 			// nop
  44. 		} else if (root == null) {
  45. 			root = new Node(value);
  46. 		} else {
  47. 			root.add(new Node(value), comparator);
  48. 		}
  49. 	}
  50. 	private boolean changeroot(Node master, Node slave) {
  51. 		root = master;
  52. 		if (root != null) root.add(slave, comparator);
  53. 		return true;
  54. 	}
  55. 	private boolean removeroot() {
  56. 		return root.left != null
  57. 			? changeroot(root.left, root.right)
  58. 			: changeroot(root.right, root.left)
  59. 		;
  60. 	}
  61. 	private int cmp(E a, E b) {
  62. 		return comparator.compare(a, b);
  63. 	}
  64. 	private boolean removenode(E value) {
  65. 		Node removed = root.remove(value, comparator);
  66. 		if (removed != null) {
  67. 			root.add(removed.left, comparator);
  68. 			root.add(removed.right, comparator);
  69. 			return true;
  70. 		}
  71. 		return false;
  72. 	}
  73. 	public boolean remove(E value) {
  74. 		if (root == null || value == null) return false;
  75. 		return cmp(root.value, value) == 0 ? removeroot() : removenode(value);
  76. 	}
  77. 	public Iterator<E> iterator() {
  78. 		return root != null ? root.inject(new ArrayList<E>()).iterator() : new ArrayList<E>().iterator();
  79. 	}
  80. 	private Node root;
  81. 	private Comparator<E> comparator;
  82. }
  83. class Qz4_403 {
  84. 	public static void main(String[] args) {
  85. 		int N = 10, MAX = 1000;
  86. 		Random random = new Random();
  87. 		TreeeSet<Integer> tree = new TreeeSet<Integer>(new Comparator<Integer>() {
  88. 			public int compare(Integer o1, Integer o2) {
  89. 				return o1.compareTo(o2);
  90. 			}
  91. 		});
  92. 		for (int i = 0; i < N; i++) {
  93. 			tree.add(new Integer(random.nextInt(MAX)));
  94. 		}
  95. 		for (Iterator<Integer> it = tree.iterator(); it.hasNext();) {
  96. 			System.out.println(it.next());
  97. 		}
  98. 	}
  99. }
Success #stdin #stdout 0.03s 245632KB
comments (?)
stdin 
Standard input is empty
stdout 
299
364
413
530
567
577
615
637
761
771
https://ideone.com/lkv0Uc
language:
Java (HotSpot 12)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!