@@ -0,0 +1,2084 @@
+//  Copyright 2022 The KeepTry Open Source Project%0A//%0A// Licensed under the Apache License, Version 2.0 (the %22License%22);%0A// you may not use this file except in compliance with the License.%0A// You may obtain a copy of the License at%0A//%0A//     http://www.apache.org/licenses/LICENSE-2.0%0A//%0A// Unless required by applicable law or agreed to in writing, software%0A// distributed under the License is distributed on an %22AS IS%22 BASIS,%0A// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.%0A// See the License for the specific language governing permissions and%0A// limitations under the License.%0A//%0A%0Apackage set;%0A%0Aimport java.util.function.Consumer;%0A%0A/*%0AA set: No duplicates, order doesn't matter%0AAssume the value range is %5B0, N-1%5D%0ARequire:%0Aclear() should not allocate new memory%0Aiterate() is O(size) runtime%0Ainsert(), remove(), lookup(), clear() is O(1) runtime%0A%0Ahttps://imgur.com/jaVze0v%0A*/%0Apublic class ValueRangeSet %7B%0A  int%5B%5D vi, iv;%0A  int i;%0A%0A  public ValueRangeSet(int N) %7B%0A    vi = new int%5BN%5D; // Value To Index%0A    iv = new int%5BN%5D; // index To Value%0A    i = 0;%0A  %7D%0A%0A  void insert(int x) %7B // Runtime O(1)%0A    if (!lookup(x)) %7B%0A      vi%5Bx%5D = i;%0A      iv%5Bi%5D = x;%0A      i++;%0A    %7D%0A  %7D%0A%0A  void remove(int x) %7B // Runtime O(1)%0A    if (lookup(x)) %7B%0A      int xi = vi%5Bx%5D;%0A%0A      i--; // swap with the last one%0A      int lastV = iv%5Bi%5D;%0A%0A      vi%5BlastV%5D = xi;%0A      iv%5Bxi%5D = lastV;%0A    %7D%0A  %7D%0A%0A  boolean lookup(int x) %7B // Runtime O(1)%0A    return vi%5Bx%5D %3C i && iv%5Bvi%5Bx%5D%5D == x;%0A  %7D%0A%0A  void clear() %7B // Runtime O(1)%0A    i = 0;%0A  %7D%0A%0A  void iterate(Consumer%3CInteger%3E f) %7B // Runtime O(count)%0A    for (int i = 0; i %3C this.i; i++) %7B%0A      f.accept(iv%5Bi%5D);%0A    %7D%0A  %7D%0A%0A  // test ----------------------------------------------------------------------%0A  public static void main(String%5B%5D args) %7B%0A    ValueRangeSet s = new ValueRangeSet(10);%0A    s.insert(5);%0A    s.insert(6);%0A    s.insert(7);%0A    s.remove(6);%0A    s.insert(9);%0A    s.iterate(v -%3E System.out.println(v));%0A    s.clear();%0A    s.insert(5);%0A    s.remove(5);%0A    s.insert(9);%0A    s.iterate(v -%3E System.out.println(v));%0A  %7D%0A%7D%0A

Set with known value range