ArrayHashSet, a Set in Java with random access and list iterators

Java offers a very useful Set implementation called LinkedHashSet, which keeps a parallel list to a HashSet that keeps the original insertion order available for iteration. This leads to more predictable outcomes with minimum overhead.

I've already wondered why they have not provided an analogous ArrayHashSet implementation in which an ArrayList fills the role of the parallel list, which would make middle-insertion slower, but on the other hand would offer random access.

Also, I don't know why they don't let LinkedHashSet provide a list iterator for more flexible iteration.

Anyway, given all that, I have implemented ArrayHashSet, which provides random access and list iterator. Here's the code:

/*
 * Copyright (c) 2013, SRI International
 * All rights reserved.
 * Licensed under the The BSD 3-Clause License;
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 * 
 * http://opensource.org/licenses/BSD-3-Clause
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * Redistributions of source code must retain the above copyright
 * notice, this arrayList of conditions and the following disclaimer.
 * 
 * Redistributions in binary form must reproduce the above copyright
 * notice, this arrayList of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 * 
 * Neither the name of the aic-expresso nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package com.sri.ai.util.collect;

import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.ListIterator;

/**
 * Analogous to {@link LinkedHashSet}, but with an {@link ArrayList} instead of a {@link LinkedList},
 * offering the same advantages (random access) and disadvantages (slower addition and removal of elements),
 * but with the extra advantage of offering an iterator that is actually a {@link ListIterator}.
 * @author braz
 *
 * @param
 */
public class ArrayHashSet extends AbstractSet {

private HashSet   set;
private ArrayList arrayList;

public ArrayHashSet() {
this.set  = new HashSet();
this.arrayList = new ArrayList();
}

// additional random access methods

public ArrayHashSetIterator listIterator() {
return new ArrayHashSetIterator(arrayList.listIterator());
}

public ArrayHashSetIterator listIterator(int index) {
return new ArrayHashSetIterator(arrayList.listIterator(index));
}

public E get(int index) {
return listIterator(index).next();
}

public void set(int index, E element) {
ArrayHashSet.ArrayHashSetIterator listIterator = listIterator(index);
listIterator.next();
listIterator.set(element);
}

// end of additional random access methods

// required implementations

public ArrayHashSet(Collection collection) {
this();
addAll(collection);
}

@Override
public boolean add(E element) {
boolean modified = set.add(element);
if (modified) {
arrayList.add(element);
}
return modified;
}

@Override
public ArrayHashSetIterator iterator() {
return new ArrayHashSetIterator(arrayList.listIterator());
}

@Override
public int size() {
return set.size();
}

// end of required implementations

// methods not required to be implemented, but more efficient

@Override
public boolean contains(Object o) {
return set.contains(o);
}

@Override
public Object[] toArray() {
return arrayList.toArray();
}

@Override
public T[] toArray(T[] a) {
return arrayList.toArray(a);
}

@Override
public boolean remove(Object o) {
boolean removed = set.remove(o);
if (removed) {
arrayList.remove(o);
}
return removed;
}

@Override
public void clear() {
set.clear();
arrayList.clear();
}

// end of methods not required to be implemented, but more efficient

private class ArrayHashSetIterator implements ListIterator {

private ListIterator arrayListIterator;
private E lastElementProvided;

public ArrayHashSetIterator(ListIterator arrayListIterator) {
this.arrayListIterator = arrayListIterator;
}

@Override
public boolean hasNext() {
return arrayListIterator.hasNext();
}

@Override
public E next() {
return lastElementProvided = arrayListIterator.next();
}

@Override
public void add(E element) {
if (set.add(element)) {
arrayListIterator.add(element);
}
}

@Override
public boolean hasPrevious() {
return arrayListIterator.hasPrevious();
}

@Override
public int nextIndex() {
return arrayListIterator.nextIndex();
}

@Override
public E previous() {
return lastElementProvided = arrayListIterator.previous();
}

@Override
public int previousIndex() {
return arrayListIterator.previousIndex();
}

@Override
public void remove() {
arrayListIterator.remove();
set.remove(lastElementProvided);
}

@Override
public void set(E element) {
if (element.equals(lastElementProvided)) {
// no need to do anything
}
else {
if (set.contains(element)) {
// cannot add because element would appear more than once
throw new IllegalArgumentException("Cannot set already-present element in a different position in ArrayHashSet.");
}
else {
arrayListIterator.set(element);
set.remove(lastElementProvided);
set.add(element);
}
}
}
}
}


and here is a unit testing class:

/*
 * Copyright (c) 2013, SRI International
 * All rights reserved.
 * Licensed under the The BSD 3-Clause License;
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 * 
 * http://opensource.org/licenses/BSD-3-Clause
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 * 
 * Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 * 
 * Neither the name of the aic-util nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package com.sri.ai.test.util.collect;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;

import java.util.NoSuchElementException;

import org.junit.Before;
import org.junit.Test;

import com.sri.ai.util.Util;
import com.sri.ai.util.collect.ArrayHashSet;

public class ArrayHashSetTest {

@Before
public void setUp() throws Exception {
}

@Test
public void test() {

ArrayHashSet set;

set = new ArrayHashSet();
assertTrue(set.isEmpty());
assertEquals(set.size(), 0);

assertEquals(Util.list(), Util.listFrom(set.iterator())); // tests iteration order

set.add("tree");
assertFalse(set.isEmpty());
assertEquals(set.size(), 1);
assertEquals("tree", set.get(0));

set.add("almond");
assertFalse(set.isEmpty());
assertEquals(set.size(), 2);
assertEquals("tree", set.get(0));
assertEquals("almond", set.get(1));

assertEquals(Util.list("tree", "almond"), Util.listFrom(set.iterator())); // tests iteration order

set.clear();
assertTrue(set.isEmpty());
assertEquals(set.size(), 0);

set.add("almond");
assertFalse(set.isEmpty());
assertEquals(set.size(), 1);
assertEquals("almond", set.get(0));

set.add("tree");
assertFalse(set.isEmpty());
assertEquals(set.size(), 2);
assertEquals("almond", set.get(0));
assertEquals("tree", set.get(1));

set.add("leaf");
assertFalse(set.isEmpty());
assertEquals(set.size(), 3);
assertEquals("almond", set.get(0));
assertEquals("tree", set.get(1));
assertEquals("leaf", set.get(2));

assertEquals(Util.list("almond", "tree", "leaf"), Util.listFrom(set.iterator())); // tests iteration order

set.remove("tree");
assertFalse(set.isEmpty());
assertEquals(set.size(), 2);
assertEquals("almond", set.get(0));
assertEquals("leaf", set.get(1));

assertEquals(Util.list("almond", "leaf"), Util.listFrom(set.iterator())); // tests iteration order

set.remove("leaf");
assertFalse(set.isEmpty());
assertEquals(set.size(), 1);
assertEquals("almond", set.get(0));

assertEquals(Util.list("almond"), Util.listFrom(set.iterator())); // tests iteration order

set.remove("almond");
assertTrue(set.isEmpty());
assertEquals(set.size(), 0);

assertEquals(Util.list(), Util.listFrom(set.iterator())); // tests iteration order

set.add("almond");
set.add("tree");
set.add("tree");
set.add("almond");
set.add("leaf");
set.add("tree");

assertEquals("almond", set.get(0));
assertEquals("tree", set.get(1));
assertEquals("leaf", set.get(2));
assertEquals(Util.list("almond", "tree", "leaf"), Util.listFrom(set.iterator())); // tests iteration order

set.set(2, "trunk");
assertEquals("almond", set.get(0));
assertEquals("tree", set.get(1));
assertEquals("trunk", set.get(2));
assertEquals(Util.list("almond", "tree", "trunk"), Util.listFrom(set.iterator())); // tests iteration order

set.set(2, "leaf");

assertEquals("almond", set.get(0));
assertEquals("tree", set.get(1));
assertEquals("leaf", set.get(2));
assertEquals(Util.list("almond", "tree", "leaf"), Util.listFrom(set.iterator())); // tests iteration order

set.set(2, "leaf");

assertEquals("almond", set.get(0));
assertEquals("tree", set.get(1));
assertEquals("leaf", set.get(2));
assertEquals(Util.list("almond", "tree", "leaf"), Util.listFrom(set.iterator())); // tests iteration order

try {
set.set(2, "almond"); // cannot add an already-present element in a different position
fail("Should have thrown an exception");
}
catch (IllegalArgumentException e) {
// good, did what it had to do
}
catch (Exception e) {
fail("Should have thrown an IllegalArgumentException but threw " + e);
}

try {
set.set(3, "almond"); // cannot set a non-existing position
fail("Should have thrown an exception");
}
catch (NoSuchElementException e) {
// good, did what it had to do
}
catch (Exception e) {
fail("Should have thrown an NoSuchElementException but threw " + e);
}

// should remain the same after failed operations
assertEquals("almond", set.get(0));
assertEquals("tree", set.get(1));
assertEquals("leaf", set.get(2));
assertEquals(Util.list("almond", "tree", "leaf"), Util.listFrom(set.iterator())); // tests iteration order
}
}