java.util.Set extension/implementation

Question

Lately, I was working on some experimental java.util.Set extension, IdSet:

package idSet;
import java.util.Collection;
import java.util.Set;
public interface IdSet<E extends Identifiable> extends Set<E> {
 boolean containsId(Object o);
 E getByElem(E e);
 E get(Object id);
 E removeId(Object o);
 boolean containsAllIds(Collection<?> c);
 boolean removeAllIds(Collection<?> c);
 boolean retainAllIds(Collection<?> c);
 Set<Object> idSet();
 Set<E> entrySet();
}

Implemented by FlexSet, source code can be found in this repo.

Apart from standard Set interface, by using IdSet we are able to find/remove elements by their properties, called ids. Example usage:

Let's say we persist objects in DB. Each object needs to have defined id (primary-key) in its respective table. Usually (for ORM) this id is a field in object definition. We can then use this id, as a key in such an IdSet and easily perform access/find operations without explicitly defining a key for each relation.

Instead of Map<Integer, SomeObject> we have IdSet<SomeObject>, where SomeObject implements Identifiable with overridden method getId(), such as in the following case:

private static class IntegerIdentifiable implements Identifiable {
 private final int integer;
 private IntegerIdentifiable(int integer) {
 this.integer = integer;
 }
 @Override
 public Object getId() {
 return integer;
 }
 @Override
 public boolean equals(Object o) {
 return o != null && integer == ((IntegerIdentifiable) o).integer;
 }
 @Override
 public int hashCode() {
 return integer;
 }
}

The repo contains about 60 unit tests concerning FlexSet and one benchmark test covering combinations of:

1. 3 containers: HashSet, HashMap, FlexSet
2. 3 operations: add, contains, remove
3. 1-131072 number of elements for each operation
4. 4 types of id calculation
5. 2 types of objects added

Results of these tests are attached in jmh-result.xlsx. For the aforementioned params, FlexSet wins at 86% against HashMap + HashSet performance-wise.

I would greatly appreciate any comments/hints/questions on performance, usability and code quality of the package.

Regarding code quality/performance I'm particularly interested in code review for the following areas:

1. rebuild mechanizm - rebuild(),
2. treeifying algorithm - treeifyIfNeeded(IdRef<E> idRef, int modHashCode, IdRef<E>[] elements),
3. tree balancing algorithm - rebuildTreeIdRef()

Below is the code I would like to have reviewed.

package idSet;
import java.lang.reflect.Array;
import java.util.*;
public class FlexSet<E extends Identifiable> implements IdSet<E>, Identifiable {
 private static final int MAX_CAPACITY = Integer.MAX_VALUE >> 1;
 private static final int DEFAULT_INITIAL_CAPACITY = 16; // must be greater than or equal 16
 // package private access for test purposes
 static final int ID_REF_TREEIFY_THRESHOLD = 7;
 // package private access for test purposes
 static final int ID_REF_UNTREEIFY_THRESHOLD = 5;
 // package private access for test purposes
 IdRef<E>[] elements;
 private int size;
 // package private access for test purposes
 int capacity;
 // package private access for test purposes
 int modCapacity;
 // package private access for test purposes
 int expansionThreshold;
 // package private access for test purposes
 int shrinkThreshold;
 private FlexSet(int initialCapacity) {
 if (initialCapacity <= 0) {
 throw new IllegalArgumentException("Parameter initialCapacity should be greater than 0.");
 }
 size = 0;
 int highestOneBit = Integer.highestOneBit(initialCapacity);
 capacity = initialCapacity == highestOneBit ? initialCapacity : highestOneBit << 1;
 calculateModCapacity();
 calculateResizeThresholds();
 elements = initElements();
 }
 public static <T extends Identifiable> FlexSet<T> instance() {
 return instance(DEFAULT_INITIAL_CAPACITY);
 }
 public static <T extends Identifiable> FlexSet<T> instance(int initialCapacity) {
 return new FlexSet<>(initialCapacity);
 }
 @SafeVarargs
 public static <T extends Identifiable> FlexSet fromArray(T... a) {
 FlexSet<T> flexSet = instance(a.length);
 Collections.addAll(flexSet, a);
 return flexSet;
 }
 public static <K, V> FlexSet<IdWrapper<K, V>> fromMap(Map<K, V> map) {
 Objects.requireNonNull(map);
 FlexSet<IdWrapper<K, V>> flexSet = instance(map.size());
 for (Map.Entry<K, V> entry : map.entrySet()) {
 flexSet.add(new IdWrapper<>(entry.getKey(), entry.getValue()));
 }
 return flexSet;
 }
 private IdRef<E>[] initElements() {
 @SuppressWarnings("unchecked")
 IdRef<E>[] elements = (IdRef<E>[]) Array.newInstance(IdRef.class, capacity);
 for (int i = 0; i < elements.length; i++) {
 elements[i] = new IdRef<>();
 }
 return elements;
 }
 @Override
 public int size() {
 return size;
 }
 @Override
 public boolean isEmpty() {
 return size == 0;
 }
 @Override
 public boolean contains(Object o) {
 return containsId(ensureTypeValid(o).getId());
 }
 @Override
 public boolean containsId(Object o) {
 return get(o) != null;
 }
 @Override
 public E getByElem(E e) {
 Objects.requireNonNull(e);
 return get(e.getId());
 }
 @Override
 public E get(Object id) {
 int hashCode = id.hashCode();
 return elements[modHashCode(hashCode)].get(id, hashCode);
 }
 @Override
 public Object[] toArray() {
 Object[] a = new Object[size];
 return copyToArray(a);
 }
 @SuppressWarnings("unchecked")
 @Override
 public <T> T[] toArray(T[] a) {
 Objects.requireNonNull(a);
 ensureCapacityOfGivenArray(a);
 a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
 return copyToArray(a);
 }
 @SuppressWarnings("unchecked")
 public <K> Map<K, E> toHashMap() {
 Map<K, E> map = new HashMap<>();
 for (E e : this) {
 map.put((K) e.getId(), e);
 }
 return map;
 }
 private <T> void ensureCapacityOfGivenArray(T[] a) {
 if (a.length < size) {
 throw new IllegalArgumentException(String.format("Cannot fit idSet.FlexSet elements into array of length %s.", a.length));
 }
 }
 @SuppressWarnings("unchecked")
 private <T> T[] copyToArray(T[] a) {
 int i = 0;
 for (E e : this) {
 a[i] = (T) e;
 i++;
 }
 return a;
 }
 @Override
 public boolean add(E e) {
 Objects.requireNonNull(e);
 int hashCode = e.getId().hashCode();
 int modHashCode = modHashCode(hashCode);
 IdRef<E> idRef = elements[modHashCode];
 if (idRef.add(e, hashCode)) {
 if (expandOnAdditionIfNeeded()) {
 treeifyIfNeeded(idRef, modHashCode, elements);
 }
 return true;
 }
 return false;
 }
 private boolean expandOnAdditionIfNeeded() {
 size++;
 if ((capacity < MAX_CAPACITY) && (size > expansionThreshold)) {
 capacity <<= 1;
 rebuild();
 return false;
 }
 return true;
 }
 private void treeifyIfNeeded(IdRef<E> idRef, int modHashCode, IdRef<E>[] elements) {
 if (idRef.size == ID_REF_TREEIFY_THRESHOLD && idRef.getClass() == IdRef.class) {
 elements[modHashCode] = TreeIdRef.fromIdRef(idRef);
 }
 }
 private void rebuild() {
 calculateModCapacity();
 calculateResizeThresholds();
 this.elements = rebuildElements();
 }
 private IdRef<E>[] rebuildElements() {
 IdRef<E>[] elements = initElements();
 for (IdRef<E> element : this.elements) {
 rebuildElement(elements, element);
 }
 return elements;
 }
 private void rebuildElement(IdRef<E>[] elements, IdRef<E> idRef) {
 while (idRef != null) {
 if (idRef.e != null) {
 doRebuildElement(elements, idRef);
 }
 idRef = idRef.next;
 }
 }
 private void doRebuildElement(IdRef<E>[] elements, IdRef<E> idRef) {
 int hashCode = idRef.hashCode;
 int modHashCode = modHashCode(hashCode);
 IdRef<E> idRefToRebuild = elements[modHashCode];
 idRefToRebuild.add(idRef.e, hashCode);
 treeifyIfNeeded(idRefToRebuild, modHashCode, elements);
 }
 @Override
 public boolean remove(Object o) {
 Objects.requireNonNull(o);
 return removeId(ensureTypeValid(o).getId()) != null;
 }
 @Override
 public E removeId(Object id) {
 int hashCode = id.hashCode();
 int modHashCode = modHashCode(hashCode);
 IdRef<E> idRef = elements[modHashCode];
 E e = idRef.removeId(id, hashCode);
 if (e != null) {
 if (shrinkOnRemovalIfNeeded()) {
 untreeifyIfNeeded(idRef, modHashCode, elements);
 }
 }
 return e;
 }
 private boolean shrinkOnRemovalIfNeeded() {
 size--;
 if ((capacity > 63) && (size < shrinkThreshold)) {
 capacity >>= 2;
 rebuild();
 return false;
 }
 return true;
 }
 private void untreeifyIfNeeded(IdRef<E> idRef, int modHashCode, IdRef<E>[] elements) {
 if (idRef.size == ID_REF_UNTREEIFY_THRESHOLD && idRef.getClass() == TreeIdRef.class) {
 elements[modHashCode] = TreeIdRef.toIdRef(idRef);
 }
 }
 @Override
 public boolean containsAll(Collection<?> c) {
 if (checkNecessaryConditionsForContainsAll(c)) {
 return false;
 }
 for (Object o : c) {
 if (!(o instanceof Identifiable) || !containsId(((Identifiable) o).getId())) {
 return false;
 }
 }
 return true;
 }
 @Override
 public boolean containsAllIds(Collection<?> c) {
 if (checkNecessaryConditionsForContainsAll(c)) {
 return false;
 }
 for (Object o : c) {
 if (!containsId(o)) {
 return false;
 }
 }
 return true;
 }
 private boolean checkNecessaryConditionsForContainsAll(Collection<?> c) {
 Objects.requireNonNull(c);
 return c instanceof Set && size < c.size();
 }
 @Override
 public boolean addAll(Collection<? extends E> c) {
 Objects.requireNonNull(c);
 boolean result = false;
 for (E e : c) {
 if (add(e)) {
 result = true;
 }
 }
 return result;
 }
 @Override
 public boolean removeAll(Collection<?> c) {
 Objects.requireNonNull(c);
 boolean result = false;
 for (Object o : c) {
 if (o instanceof Identifiable && removeId(((Identifiable) o).getId()) != null) {
 result = true;
 }
 }
 return result;
 }
 @Override
 public boolean removeAllIds(Collection<?> c) {
 Objects.requireNonNull(c);
 boolean result = false;
 for (Object o : c) {
 if (removeId(o) != null) {
 result = true;
 }
 }
 return result;
 }
 @Override
 public boolean retainAll(Collection<?> c) {
 Objects.requireNonNull(c);
 boolean result = false;
 for (E e : this) {
 if (!c.contains(e)) {
 if (remove(e)) {
 result = true;
 }
 }
 }
 return result;
 }
 @Override
 public boolean retainAllIds(Collection<?> c) {
 Objects.requireNonNull(c);
 boolean result = false;
 for (E e : this) {
 Object id = e.getId();
 if (!c.contains(id)) {
 if (removeId(id) != null) {
 result = true;
 }
 }
 }
 return result;
 }
 @Override
 public void clear() {
 size = 0;
 elements = initElements();
 }
 @Override
 public Iterator<E> iterator() {
 return new Iterator<E>() {
 private IdRef<E> current;
 private int index;
 @Override
 public boolean hasNext() {
 while (index < elements.length) {
 if (hasNextForCurrent()) {
 return true;
 }
 prepareForNext();
 }
 return false;
 }
 private boolean hasNextForCurrent() {
 if (current == null) {
 current = elements[index];
 }
 return current.next != null;
 }
 private void prepareForNext() {
 current = null;
 index++;
 }
 @Override
 public E next() {
 E result = current.e;
 current = current.next;
 return result;
 }
 };
 }
 @Override
 public Set<Object> idSet() {
 Set<Object> idSet = new HashSet<>();
 for (E e : this) {
 idSet.add(e.getId());
 }
 return idSet;
 }
 @Override
 public Set<E> entrySet() {
 return new HashSet<>(this);
 }
 private int modHashCode(int hashCode) {
 return (hashCode ^ (hashCode >>> 16)) & modCapacity;
 }
 private void calculateModCapacity() {
 modCapacity = capacity - 1;
 }
 private void calculateResizeThresholds() {
 expansionThreshold = capacity;
 shrinkThreshold = capacity >> 2;
 }
 private Identifiable ensureTypeValid(Object o) {
 if (o instanceof Identifiable) {
 return (Identifiable) o;
 }
 throw new IllegalArgumentException(String.format("Object %s has to be of type idSet.Identifiable.", o));
 }
 @Override
 public boolean equals(Object o) {
 if (this == o) return true;
 if (o == null || getClass() != o.getClass()) return false;
 FlexSet<?> flexSet = (FlexSet<?>) o;
 return size == flexSet.size &&
 containsAll(flexSet);
 }
 @Override
 public int hashCode() {
 int result = Objects.hash(capacity, size);
 result = 31 * result + Arrays.hashCode(elements);
 return result;
 }
 @Override
 public Object getId() {
 return hashCode();
 }
 @Override
 public String toString() {
 return "idSet.FlexSet{" +
 "elements=" + Arrays.toString(elements) +
 '}';
 }
 // package private access for test purposes
 static class IdRef<E extends Identifiable> {
 int size;
 E e;
 IdRef<E> next;
 int hashCode;
 private IdRef() {
 }
 boolean add(E e, int hashCode) {
 if (checkFirst(e) && (setUpIfEmpty(e, hashCode) || setUpAtTheBegginingIfNeeded(e, hashCode) || skipLowerHashCodesAndProceedWithAdding(e, hashCode))) {
 size++;
 return true;
 }
 return false;
 }
 private boolean checkFirst(E e) {
 return !e.equals(this.e);
 }
 private boolean setUpIfEmpty(E e, int hashCode) {
 if (this.e == null) {
 setUpAtTheEnd(this, e, hashCode);
 return true;
 }
 return false;
 }
 private boolean setUpAtTheBegginingIfNeeded(E e, int hashCode) {
 if (isHashCodeInRange(hashCode)) {
 setUpAtTheBeggining(e, hashCode);
 return true;
 }
 return false;
 }
 private void setUpAtTheBeggining(E e, int hashCode) {
 IdRef<E> thisTemp = new IdRef<>();
 thisTemp.e = this.e;
 thisTemp.next = next;
 thisTemp.hashCode = this.hashCode;
 this.e = e;
 next = thisTemp;
 this.hashCode = hashCode;
 }
 private boolean skipLowerHashCodesAndProceedWithAdding(E e, int hashCode) {
 IdRef<E> current = this;
 while (current.hashCode < hashCode) {
 if (setUpAtTheEndIfNeeded(e, hashCode, current)) return true;
 current = current.next;
 }
 while (current.e != null) {
 Boolean x = setUpInTheMiddleIfNeeded(current, e, hashCode);
 if (x != null) return x;
 current = current.next;
 }
 setUpAtTheEnd(current, e, hashCode);
 return true;
 }
 private boolean setUpAtTheEndIfNeeded(E e, int hashCode, IdRef<E> current) {
 if (current.next == null) {
 setUpAtTheEnd(current, e, hashCode);
 return true;
 }
 return false;
 }
 private void setUpAtTheEnd(IdRef<E> current, E e, int hashCode) {
 current.e = e;
 current.next = new IdRef<>();
 current.hashCode = hashCode;
 }
 private Boolean setUpInTheMiddleIfNeeded(IdRef<E> current, E e, int hashCode) {
 if (current.hashCode != hashCode) {
 setUpInTheMiddle(current, e, hashCode);
 return true;
 }
 if (current.e.equals(e)) {
 return false;
 }
 return null;
 }
 private void setUpInTheMiddle(IdRef<E> current, E e, int hashCode) {
 IdRef<E> idRef = new IdRef<>();
 idRef.e = e;
 idRef.next = current.next;
 idRef.hashCode = hashCode;
 current.next = idRef;
 }
 E get(Object id, int hashCode) {
 if (checkFirst(id)) {
 return e;
 }
 if (isHashCodeInRange(hashCode)) {
 return null;
 }
 return skipLowerHashCodesAndProceedWithGetting(id, hashCode);
 }
 private boolean checkFirst(Object id) {
 return e == null || e.getId().equals(id);
 }
 private boolean isHashCodeInRange(int hashCode) {
 return this.hashCode > hashCode;
 }
 private E skipLowerHashCodesAndProceedWithGetting(Object id, int hashCode) {
 IdRef<E> current = skipLowerHashCodes(hashCode);
 if (current == null) return null;
 while (current.e != null && current.hashCode == hashCode) {
 if (isFound(current, id)) {
 return current.e;
 }
 current = current.next;
 }
 return null;
 }
 E removeId(Object id, int hashCode) {
 if (e == null) return null;
 if (e.getId().equals(id)) {
 return getRemovedAndAdjust(this);
 }
 return skipLowerHashCodesAndProceedWithRemoving(id, hashCode);
 }
 private E skipLowerHashCodesAndProceedWithRemoving(Object id, int hashCode) {
 IdRef<E> current = skipLowerHashCodes(hashCode);
 if (current == null) return null;
 while (current.e != null && current.hashCode == hashCode) {
 if (isFound(current, id)) {
 return getRemovedAndAdjust(current);
 }
 current = current.next;
 }
 return null;
 }
 private void adjustOnRemoval(IdRef<E> current, IdRef<E> next) {
 current.e = next.e;
 current.next = next.next;
 current.hashCode = next.hashCode;
 }
 private IdRef<E> skipLowerHashCodes(int hashCode) {
 IdRef<E> current = next;
 while (current.hashCode < hashCode) {
 if (current.e == null) return null;
 current = current.next;
 }
 return current;
 }
 private E getRemovedAndAdjust(IdRef<E> current) {
 IdRef<E> next = current.next;
 E e = current.e;
 adjustOnRemoval(current, next);
 size--;
 return e;
 }
 private boolean isFound(IdRef<E> current, Object id) {
 return current.e.getId().equals(id);
 }
 @Override
 public String toString() {
 return "IdRef{" +
 ", hashCode=" + hashCode +
 '}';
 }
 @Override
 public boolean equals(Object o) {
 if (this == o) return true;
 if (o == null || getClass() != o.getClass()) return false;
 IdRef<?> idRef = (IdRef<?>) o;
 return hashCode == idRef.hashCode &&
 Objects.equals(e, idRef.e);
 }
 @Override
 public int hashCode() {
 return Objects.hash(e, hashCode);
 }
 }
 // package private access for test purposes
 static final class TreeIdRef<E extends Identifiable> extends IdRef<E> {
 private TreeIdRef<E> left;
 private TreeIdRef<E> right;
 private IdRef<E> block = new IdRef<>();
 private int nodesCount;
 private TreeIdRef() {
 }
 @Override
 boolean add(E e, int hashCode) {
 if (addByHashCode(this, null, e, hashCode, 0)) {
 size++;
 return true;
 }
 return false;
 }
 private boolean addByHashCode(TreeIdRef<E> current, TreeIdRef<E> parent, E e, int hashCode, int consecutiveNodesCount) {
 if (hashCode == current.hashCode) {
 return handleEqualHashCodes(current, parent, e, hashCode, consecutiveNodesCount);
 } else if (hashCode < current.hashCode) {
 return checkLeft(current, e, hashCode, consecutiveNodesCount) || addByHashCode(current.left, current, e, hashCode, consecutiveNodesCount + 1);
 } else {
 return checkRight(current, e, hashCode, consecutiveNodesCount) || addByHashCode(current.right, current, e, hashCode, consecutiveNodesCount + 1);
 }
 }
 private boolean handleEqualHashCodes(TreeIdRef<E> current, TreeIdRef<E> parent, E e, int hashCode, int consecutiveNodesCount) {
 return !checkFirst(current, e) && (handleNull(current, parent, e, consecutiveNodesCount) || handleBlock(current, e, hashCode));
 }
 private boolean checkFirst(TreeIdRef<E> current, E e) {
 return e.equals(current.e);
 }
 private boolean handleNull(TreeIdRef<E> current, TreeIdRef<E> parent, E e, int consecutiveNodesCount) {
 if (current.e == null) {
 current.e = e;
 parent.next = current;
 rebuildTreeIdRefIfNeeded(consecutiveNodesCount);
 return true;
 }
 return false;
 }
 private boolean handleBlock(TreeIdRef<E> current, E e, int hashCode) {
 current.next = current.block;
 return current.block.add(e, hashCode);
 }
 private boolean checkLeft(TreeIdRef<E> current, E e, int hashCode, int consecutiveNodesCount) {
 if (current.left == null) {
 current.left = createLinkedTreeIdRef(current);
 current.left.e = e;
 current.left.hashCode = hashCode;
 rebuildTreeIdRefIfNeeded(consecutiveNodesCount);
 return true;
 }
 return false;
 }
 private boolean checkRight(TreeIdRef<E> current, E e, int hashCode, int consecutiveNodesCount) {
 if (current.right == null) {
 current.right = createLinkedTreeIdRef(current);
 current.right.e = e;
 current.right.hashCode = hashCode;
 rebuildTreeIdRefIfNeeded(consecutiveNodesCount);
 return true;
 }
 return false;
 }
 private TreeIdRef<E> createLinkedTreeIdRef(TreeIdRef<E> parent) {
 TreeIdRef<E> treeIdRef = new TreeIdRef<>();
 IdRef<E> parentNext = parent.next;
 parent.next = treeIdRef;
 treeIdRef.next = parentNext;
 return treeIdRef;
 }
 @Override
 E get(Object id, int hashCode) {
 TreeIdRef<E> treeIdRef = findByHashCode(this, hashCode);
 if (treeIdRef == null) {
 return null;
 }
 E e = treeIdRef.e;
 if (e == null || e.getId().equals(id)) {
 return e;
 }
 return treeIdRef.block.get(id, hashCode);
 }
 private TreeIdRef<E> findByHashCode(TreeIdRef<E> current, int hashCode) {
 if (hashCode == current.hashCode) {
 return current;
 } else {
 if (hashCode < current.hashCode) {
 current = current.left;
 } else {
 current = current.right;
 }
 if (current == null) {
 return null;
 }
 }
 return findByHashCode(current, hashCode);
 }
 @Override
 E removeId(Object id, int hashCode) {
 TreeIdRef<E> treeIdRef = findByHashCode(this, hashCode);
 if (treeIdRef == null) {
 return null;
 }
 E e = treeIdRef.e;
 if (e == null) {
 return null;
 }
 IdRef<E> block = treeIdRef.block;
 if (e.getId().equals(id)) {
 if (block.size == 0) {
 treeIdRef.e = null;
 } else {
 treeIdRef.e = block.removeId(block.e.getId(), hashCode);
 }
 size--;
 return e;
 }
 return null;
 }
 private void rebuildTreeIdRefIfNeeded(int consecutiveNodesCount) {
 nodesCount++;
 if ((28 - Integer.numberOfLeadingZeros(nodesCount) + ID_REF_TREEIFY_THRESHOLD < consecutiveNodesCount)) {
 rebuildTreeIdRef();
 }
 }
 private void rebuildTreeIdRef() {
 TreeIdRef<E>[] temporarySortedTreeIdRefs = createTemporarySortedTreeIdRefs();
 TreeIdRef<E> rebuilt = rebuildFromSorted(temporarySortedTreeIdRefs);
 e = rebuilt.e;
 hashCode = rebuilt.hashCode;
 block = rebuilt.block;
 next = rebuilt.next;
 left = rebuilt.left;
 right = rebuilt.right;
 }
 @SuppressWarnings("unchecked")
 private TreeIdRef<E>[] createTemporarySortedTreeIdRefs() {
 TreeIdRef<E>[] temporarySortedTreeIdRefs = new TreeIdRef[nodesCount];
 sortStartingFromLeftmost(temporarySortedTreeIdRefs, this.left, this, 0);
 return temporarySortedTreeIdRefs;
 }
 private int sortStartingFromLeftmost(TreeIdRef<E>[] temporarySortedTreeIdRefs, TreeIdRef<E> current, TreeIdRef<E> parent, int i) {
 i = sortForCurrent(temporarySortedTreeIdRefs, current, i);
 i = sortForParent(temporarySortedTreeIdRefs, current, parent, i);
 return i;
 }
 private int sortForParent(TreeIdRef<E>[] temporarySortedTreeIdRefs, TreeIdRef<E> current, TreeIdRef<E> parent, int i) {
 if (parent.right != current) {
 if (parent.e != null) {
 temporarySortedTreeIdRefs[i++] = parent;
 }
 if (parent.right != null) {
 i = sortForCurrent(temporarySortedTreeIdRefs, parent.right, i);
 }
 }
 return i;
 }
 private int sortForCurrent(TreeIdRef<E>[] temporarySortedTreeIdRefs, TreeIdRef<E> current, int i) {
 if (current.left != null) {
 i = sortStartingFromLeftmost(temporarySortedTreeIdRefs, current.left, current, i);
 } else {
 if (current.e != null) {
 temporarySortedTreeIdRefs[i++] = current;
 }
 if (current.right != null) {
 i = sortStartingFromLeftmost(temporarySortedTreeIdRefs, current.right, current, i);
 }
 }
 return i;
 }
 private TreeIdRef<E> rebuildFromSorted(TreeIdRef<E>[] temporarySortedTreeIdRefs) {
 int index = temporarySortedTreeIdRefs.length >> 1;
 TreeIdRef<E> midTreeIdRef = temporarySortedTreeIdRefs[index].createStandaloneCopy();
 FlexSet<IntegerIdentifiable> usedIndices = new FlexSet<>(nodesCount << 1);
 usedIndices.add(new IntegerIdentifiable(index));
 midTreeIdRef.nodesCount = rebuildForBoth(temporarySortedTreeIdRefs, midTreeIdRef, 0, index, temporarySortedTreeIdRefs.length, usedIndices);
 return midTreeIdRef;
 }
 private int rebuildForBoth(TreeIdRef<E>[] temporarySortedTreeIdRefs, TreeIdRef<E> midTreeIdRef, int from, int index, int to, FlexSet<IntegerIdentifiable> usedIndices) {
 int nodesCount = rebuildForLeft(temporarySortedTreeIdRefs, midTreeIdRef, from, index, usedIndices);
 nodesCount += rebuildForRight(temporarySortedTreeIdRefs, midTreeIdRef, index, to, usedIndices);
 return nodesCount;
 }
 private int rebuildForLeft(TreeIdRef<E>[] temporarySortedTreeIdRefs, TreeIdRef<E> midTreeIdRef, int from, int to, FlexSet<IntegerIdentifiable> usedIndices) {
 midTreeIdRef.next = null;
 int diff = to - from;
 if (diff != 0) {
 int index = (diff >> 1) + from;
 if (usedIndices.add(new IntegerIdentifiable(index))) {
 TreeIdRef<E> treeIdRef = temporarySortedTreeIdRefs[index].createStandaloneCopy();
 midTreeIdRef.left = treeIdRef;
 midTreeIdRef.next = treeIdRef;
 return rebuildForBoth(temporarySortedTreeIdRefs, midTreeIdRef.left, from, index, to, usedIndices);
 }
 }
 midTreeIdRef.left = null;
 return 0;
 }
 private int rebuildForRight(TreeIdRef<E>[] temporarySortedTreeIdRefs, TreeIdRef<E> midTreeIdRef, int from, int to, FlexSet<IntegerIdentifiable> usedIndices) {
 int diff = to - from;
 if (diff != 1) {
 int index = (diff >> 1) + from;
 if (usedIndices.add(new IntegerIdentifiable(index))) {
 TreeIdRef<E> treeIdRef = temporarySortedTreeIdRefs[index].createStandaloneCopy();
 midTreeIdRef.right = treeIdRef;
 getLast(midTreeIdRef).next = treeIdRef;
 return rebuildForBoth(temporarySortedTreeIdRefs, midTreeIdRef.right, from, index, to, usedIndices);
 }
 }
 midTreeIdRef.right = null;
 return 0;
 }
 private IdRef<E> getLast(IdRef<E> midTreeIdRef) {
 while (midTreeIdRef.next != null) {
 midTreeIdRef = midTreeIdRef.next;
 }
 return midTreeIdRef;
 }
 private TreeIdRef<E> createStandaloneCopy() {
 TreeIdRef<E> treeIdRef = new TreeIdRef<>();
 treeIdRef.e = e;
 treeIdRef.hashCode = hashCode;
 treeIdRef.block = block;
 return treeIdRef;
 }
 private static <E extends Identifiable> TreeIdRef<E> fromIdRef(IdRef<E> idRef) {
 TreeIdRef<E> treeIdRef = new TreeIdRef<>();
 treeIdRef.e = idRef.next.next.next.e;
 treeIdRef.hashCode = idRef.next.next.next.hashCode;
 treeIdRef.size = 1;
 treeIdRef.nodesCount = 1;
 fromIdRefHelp(treeIdRef, idRef.next);
 fromIdRefHelp(treeIdRef, idRef.next.next.next.next.next);
 fromIdRefHelp(treeIdRef, idRef);
 fromIdRefHelp(treeIdRef, idRef.next.next);
 fromIdRefHelp(treeIdRef, idRef.next.next.next.next);
 fromIdRefHelp(treeIdRef, idRef.next.next.next.next.next.next);
 return treeIdRef;
 }
 private static <E extends Identifiable> void fromIdRefHelp(TreeIdRef<E> treeIdRef, IdRef<E> idRef) {
 treeIdRef.add(idRef.e, idRef.hashCode);
 }
 private static <E extends Identifiable> IdRef<E> toIdRef(IdRef<E> treeIdRef) {
 IdRef<E> idRef = new IdRef<>();
 while (treeIdRef != null) {
 if (treeIdRef.e != null) {
 idRef.add(treeIdRef.e, treeIdRef.hashCode);
 }
 treeIdRef = treeIdRef.next;
 }
 return idRef;
 }
 }
 private static class IntegerIdentifiable implements Identifiable {
 private final int integer;
 private IntegerIdentifiable(int integer) {
 this.integer = integer;
 }
 @Override
 public Object getId() {
 return integer;
 }
 @Override
 public boolean equals(Object o) {
 return o != null && integer == ((IntegerIdentifiable) o).integer;
 }
 @Override
 public int hashCode() {
 return integer;
 }
 }
}

• Joe C: Welcome to Code Review! Please be sure to include all code that you want reviewed, rather than linking to repositories on third-party sites.
• Wojciech Karwacki: Hey Joe, the code i'd like to have reviewed is 1k lines long, should i really post it here? I would like to listen to comments about whole library FlexSet, not only some particular parts of it.
• Joe C: There's a discussion on meta on this, which is probably good guidance here.
• Wojciech Karwacki: Thank you Joe, i have edited my question with regard to the discussion you have provided. Please let me know if the question is properly asked now.
• Joe C: Yes, this looks better to me.

Answer 1

Possible Use of Delegation

I look at this code and see a lot that reminds me of code in the HashMap class. You may be able to simplify this considerably by delegating your methods to a HashMap.

public class FlexSet<E extends Identifiable> implements IdSet<E> {
 private Map<Object, E> backingMap = new HashMap<>();
 //example
 @Override
 boolean containsId(Object o) {
 return backingMap.containsKey(o);
 }
 //and so on
}

Use Generic Type for Identifier

It is highly likely that the ID of your Identifiable will have a type that can be known at compile time. You can use generics to improve the prospects of bugs being found at compile time rather than runtime.

public interface Identifiable<ID> {
 ID getId();
}

API methods unclear

The signature of containsAllIds(Collection<?> c) (and other methods along those lines) do not tell me clearly what they accept (IDs? Elements? Mix of both?). Making the Identifiable generic will probably help here.