OrderedCollection

OrderedCollection.java

package com.sun.javafx.binding;

import java.util.AbstractCollection;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;

public class OrderedCollection<T> extends AbstractCollection<T> {
  private static final int EMPTY = -1;

  private T[] items;
  private int[] links;  // maintains singly linked list and hash buckets in one array

  private int bucketCount;
  private int nextAvailableSlot;
  private int occupiedSlots;

  public OrderedCollection(Collection<T> items) {
    compact(items, items.size());
  }

  public OrderedCollection(T[] items) {
    compact(Arrays.asList(items), items.length);
  }

  boolean addAtEnd = true;  // determines if removal will remove the first match, or last match (ArrayList removes first match)

  @Override
  public boolean add(T item) {
    Objects.requireNonNull(item, "item");

    if(nextAvailableSlot == items.length) {
      compact();
    }

    if(addAtEnd) {
      int tailIndex = determineBucket(item);

      while(links[tailIndex] != EMPTY) {
        tailIndex = links[tailIndex];
      }

      links[tailIndex] = nextAvailableSlot;
      links[nextAvailableSlot] = EMPTY;
    }
    else {
      int index = determineBucket(item);

      links[nextAvailableSlot] = links[index];
      links[index] = nextAvailableSlot;
    }

    items[nextAvailableSlot++] = item;
    occupiedSlots++;

    return true;
  }

  @Override
  public boolean remove(Object item) {
    int index = findIndexOf(item);

    if(index == EMPTY) {
      return false;
    }

    items[index] = null;
    occupiedSlots--;

    if(occupiedSlots < items.length / 2) {
      compact();
    }

    return true;
  }

  @Override
  public int size() {
    return occupiedSlots;
  }

  @Override
  public boolean isEmpty() {
    return occupiedSlots == 0;
  }

  @Override
  public boolean contains(Object item) {
    return findIndexOf(item) != EMPTY;
  }

  @Override
  public Iterator<T> iterator() {
    return new Iterator<>() {
      int next = -1;

      {
        findNext();
      }

      private void findNext() {
        next++;

        while(next < items.length && items[next] == null) {
          next++;
        }
      }

      @Override
      public boolean hasNext() {
        return next != items.length;
      }

      @Override
      public T next() {
        if(!hasNext()) {
          throw new NoSuchElementException();
        }

        T item = items[next];
        findNext();

        return item;
      }
    };
  }

  @Override
  public void clear() {
    compact(Collections.emptyList(), 4);
  }

  private void compact() {

    /*
     * Capacity here is chosen to be around 150% of the minimum required.
     * It is rounded to a multiple of 4, with a minimum of 4.
     */

    int capacity = (Math.max(4, occupiedSlots * 3 / 2) + 3) / 4 * 4;

    compact(Arrays.asList(this.items), capacity);
  }

  private void compact(Collection<T> oldItems, int capacity) {
    System.out.println("Compacting to " + capacity + "; occupiedSlots = " + occupiedSlots);

    @SuppressWarnings("unchecked")
    T[] castItems = (T[])new Object[capacity];

    this.bucketCount = Math.max(2, capacity / 4);  // 1 bucket for every 4 items of capacity, with a minimum of 2
    this.items = castItems;
    this.links = new int[capacity + bucketCount];
    this.occupiedSlots = 0;
    this.nextAvailableSlot = 0;

    Arrays.fill(links, items.length, items.length + bucketCount, EMPTY);

    for(T item : oldItems) {
      if(item != null) {
        add(item);
      }
    }
  }

  private int findIndexOf(Object item) {  // not to be confused with List#indexOf, this returns an internal index which may have gaps
    if(item == null) {
      return EMPTY;
    }

    int index = determineBucket(item);

    for(;;) {
      index = links[index];

      if(index == EMPTY) {
        return EMPTY;
      }

      if(item.equals(items[index])) {
        return index;
      }
    }
  }

  private int determineBucket(Object item) {
    return item.hashCode() % bucketCount + items.length;
  }
}