11
\$\begingroup\$

Here's something I wrote a while ago. I needed a collection that was ordered, but also guaranteed duplicates did not occur. So I made a class with both Set and List interfaces. It seems to work well.

I'm interested if there are better ways of doing this, maybe in the standard API or some library. I'd also be interested in general comments, if anyone cares to offer them.

This is a fairly simple implementation, designed to meet my immediate needs. There's probably lots of ways it could be made more fancy.

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Set;

/**
 * Unholy spawn of set and list!
 * 
 * <p>@code HashSetList} is similar to {@code LinkedHashSet}.  Objects
 * inserted can be retrieved in a predicable order.  Unlike
 * {@code LinkedHashSet}, this class implements more of the {@code List}
 * API, including a reverse iterator and a subList() method.
 * </p>
 * 
 * <p><b>Very lightly tested!</b>  Caveat emptor.</p>
 * 
 * @author Brenden Towey
 * @param <T> The type parameter of the {@code HashSetList}.
 */
public class HashSetList<T> implements Set<T>, List<T>
{
   private final HashSet<T> set = new HashSet<>();
   private final ArrayList<T> list = new ArrayList<>();

   @Override
   public boolean containsAll(
           Collection<?> c )
   {
      return set.containsAll( c );
   }

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

   @Override
   public boolean isEmpty()
   {
      return list.isEmpty();
   }

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

   @Override
   public int indexOf( Object o )
   {
      return list.indexOf( o );
   }

   @Override
   public int lastIndexOf( Object o )
   {
      return list.lastIndexOf( o );
   }

//   @Override
//   public Object clone()
//   {
//      try {
//         HashSetList copy = (HashSetList) super.clone();
//         return copy;
//      } catch( CloneNotSupportedException ex ) {
//         throw new AssertionError( "This should NOT happen.", ex );
//      }
//   }

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

   @Override
   public <T> T[] toArray( T[] a )
   {
      return list.toArray( a );
   }

   @Override
   public T get( int index )
   {
      return list.get( index );
   }

   /**
    * Throws {@code UnsupportedOperationException}.
    * 
    * @param index
    * @param element 
    */
   @Override
   public T set( int index, T element )
   {
      throw new UnsupportedOperationException();
//      return list.set( index, element );
   }

   @Override
   public boolean add( T e )
   {
      if( set.add( e ) ) {
         return list.add( e ); // always returns true
      }
      return false;
   }

   /**
    * Throws {@code UnsupportedOperationException}.
    * 
    * @param index
    * @param element 
    */
   @Override
   public void add( int index, T element )
   {
      throw new UnsupportedOperationException();
//      list.add( index, element );
   }

   /**
    * Throws {@code UnsupportedOperationException}.
    * 
    * @param index
    */
   @Override
   public T remove( int index )
   {
      throw new UnsupportedOperationException();
//      return list.remove( index );
   }

   @Override
   public boolean remove( Object o )
   {
      if( set.remove( o ) )
         return list.remove( o );
      else
         return false;
   }

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

   /**
    * Adds all elements in the {@code Collection c} to this
    * {@code HashSetList}.  This method is implemented very simply
    * and likely to be quite slow.  Caveat emptor.
    * 
    * @param c {@code Collection} of elements to remove.
    * @return @{code true} if changed.
    */
   @Override
   public boolean addAll(
           Collection<? extends T> c )
   {
      boolean change = false;
      for( T x : c )
         change |= this.add( x );
      return change;
   }

   /**
    * Throws {@code UnsupportedOperationException}.
    * 
    * @param index
    * @param element 
    */
   @Override
   public boolean addAll( int index,
           Collection<? extends T> c )
   {
      throw new UnsupportedOperationException();
//      return list.addAll( index, c );
   }

   /**
    * Removes all elements in the {@code Collection c} from this
    * {@code HashSetList}.  This method is implemented very simply
    * and likely to be quite slow.  Caveat emptor.
    * 
    * @param c {@code Collection} of elements to remove.
    * @return @{code true} if changed.
    */
   @Override
   public boolean removeAll(
           Collection<?> c )
   {
      boolean change = false;
      for( Object o : c )
         change |= this.remove( o );
      return change;
   }

   /**
    * Retains all elements in the {@code Collection c} which also in this
    * {@code HashSetList}.  (In other words it computes the intersection
    * of {@code c} and this {@code HashSetList}.
    * This method is implemented very simply
    * and likely to be quite slow.  Caveat emptor.
    * 
    * @param c {@code Collection} of elements to remove.
    * @return @{code true} if changed.
    */
   @Override
   public boolean retainAll(
           Collection<?> c )
   {
      boolean change = set.retainAll( c );
      change |= list.retainAll( c );
      return change;
   }

   @Override
   public ListIterator<T> listIterator( int index )
   {
      return list.listIterator( index );
   }

   @Override
   public ListIterator<T> listIterator()
   {
      return list.listIterator();
   }

   @Override
   public Iterator<T> iterator()
   {
      return list.iterator();
   }

   @Override
   public List<T> subList( int fromIndex, int toIndex )
   {
      return list.subList( fromIndex, toIndex );
   }

}
\$\endgroup\$
  • \$\begingroup\$ How many elements do you expect to keep in this kind of list? \$\endgroup\$ – Simon Forsberg Dec 23 '14 at 0:27
  • 1
    \$\begingroup\$ Do you want "random access", such as list.get(500) or do you need this primarily for iteration or checking .contains? What exactly is the use-case here? Knowing that will make it easier to suggest exactly what you need. \$\endgroup\$ – Simon Forsberg Dec 23 '14 at 1:18
  • \$\begingroup\$ I need random access because it implements a bi-directional cursor. I use this class to implement the results of a search -- after finding a list of documents with search words, I intersect the list of documents together to find documents which contain the most words in common. Then I store the results in this HashSetList. The List part lets me go forwards and back in the results, and the Set part ensures I don't show the same document twice. Hope that makes sense. \$\endgroup\$ – markspace Dec 23 '14 at 1:32
  • \$\begingroup\$ I gotta take back the comment I made earlier: In reply to "How many elements do you expect to keep in this list?" reviewing my code, this HashSetList is part of the cursor results only, and not the actual index. So it could store as many documents (results) as the index holds, but that doesn't seem likely. It holds as many results initially as the first intersection of documents that produces a result; i.e. the first set of documents which has some of the search words in common. \$\endgroup\$ – markspace Dec 23 '14 at 1:58
  • \$\begingroup\$ What you might be needing is perhaps a LinkedList and a HashSet ? The LinkedList provides easy forward and backward iteration, while the Set makes sure that it has not been added already. If forward and backward iteration is all you need, use a ListIterator and not repeatedly call the get method. \$\endgroup\$ – Simon Forsberg Dec 23 '14 at 18:08
10
\$\begingroup\$

There is a whole bunch of throws UnsupportedOperationException in your code. More specifically, everything that has to do with specific indexes seems to be unsupported.

All this makes me wonder: Should you really implement the List interface? In my opinion, you should not. Because essentially, those List-specific methods are not supported.

I think you should consider dropping that class entirely and use LinkedHashSet or TreeSet, which I think should be sufficient for you.

I think what you are looking for is LinkedHashSet which is a Set that preserves the insertion order of elements that are added to it.

\$\endgroup\$
  • \$\begingroup\$ I think you're right about the UnsupportedOperationException. I should figure out how to actually support them. And I needed a subList() method specifically, which only List supports. It seemed best to just say this clas is-a list (it is) and go from there. \$\endgroup\$ – markspace Dec 23 '14 at 0:00
  • \$\begingroup\$ The List<T> documentation expressly provides that it is legitimate for an implementation to provide a means of reading items by index without providing useful implementations of the List<T> members which would modify the list. \$\endgroup\$ – supercat Dec 23 '14 at 0:31
  • \$\begingroup\$ If there had been from the get-go a standard ReadableList<T> interface which was similar to List<T> but without the mutating members, that might be a better choice than List<T>, but as it is I think List<T> is the standard type for code to accept when it needs a sequence of items which can be read via index. \$\endgroup\$ – supercat Dec 23 '14 at 0:33
  • \$\begingroup\$ That is a good point, @supercat. I still think thought that LinkedHashSet should be sufficient. \$\endgroup\$ – Simon Forsberg Dec 23 '14 at 1:15
  • \$\begingroup\$ @SimonAndréForsberg: If it's necessary to pass the collection to a method which expects a List<T>, then it needs to implement that interface. Even if the method only needed members that are in LinkedHashSet<T>, Java isn't duck-typed, so there would be no way for it to accept anything which didn't implement List<T>. \$\endgroup\$ – supercat Dec 23 '14 at 16:45
10
\$\begingroup\$

Note that java.util.List and java.util.Set, in addition to imposing various requirements that the compiler is capable of enforcing, also impose various requirements via Javadoc. Your class does not satisfy those requirements, and in fact it is not possible for a single class to satisfy the requirements of both interfaces.

In particular, take a look at the definitions of equals. For Set, it is:

Compares the specified object with this set for equality. Returns true if the specified object is also a set, the two sets have the same size, and every member of the specified set is contained in this set (or equivalently, every member of this set is contained in the specified set). This definition ensures that the equals method works properly across different implementations of the set interface. [link]

For List, it is:

Compares the specified object with this list for equality. Returns true if and only if the specified object is also a list, both lists have the same size, and all corresponding pairs of elements in the two lists are equal. (Two elements e1 and e2 are equal if (e1==null ? e2==null : e1.equals(e2)).) In other words, two lists are defined to be equal if they contain the same elements in the same order. This definition ensures that the equals method works properly across different implementations of the List interface. [link]

So, for example, new HashSetList<Object>().equals(new HashSet<Object>()) must return true and must not return true.

\$\endgroup\$
  • 1
    \$\begingroup\$ Interesting point! Looking at Collection.equals() Javadoc, it states "By the same logic, it is not possible to write a class that correctly implements both the Set and List interfaces." (docs.oracle.com/javase/8/docs/api/java/util/…). In this case, I will either compromise (do I want to adhere stronger to the Set or List semantics?) or make sure I only compare with another HashSetList instance, and I will prefer the latter. Anyways, it ultimately boils down to the OP's use cases. Maybe the equals() method is not really required... \$\endgroup\$ – h.j.k. Dec 23 '14 at 6:00
  • \$\begingroup\$ Good answer. Might be helpful to the OP, though, if you explicitly list the unresolvable contradictions. \$\endgroup\$ – itsbruce Dec 23 '14 at 13:37
  • \$\begingroup\$ This is a good point (OP here). However, some Collections have their own Javadoc where they disclaim other documentation. For example, IdentityHashMap "intentionally violates Maps general contract." So I feel that as long as I document my behavior, I can reasonably wave away other class's documentation. \$\endgroup\$ – markspace Dec 23 '14 at 17:26
  • \$\begingroup\$ @markspace: Nothing is ever removed from the JDK, which means that it's accrued a number of design mistakes over the years. If IdentityHashMap<K,V> weren't in the JDK, would you consider it to be good design? (Specifically: would you agree with its implementing Map<K,V> rather than something like Map<IdentityEquivalence<K>,V>?) If not, then -- don't be led astray by its being in the JDK. \$\endgroup\$ – ruakh Dec 23 '14 at 21:07
  • \$\begingroup\$ Well, yes I consider it to be good design. In particular, inheritance as implemented in most OO languages is well known to be insufficient to cover some real life design issues. Strict adherence to a hierarchical system is a mistake, and flexibility is OK if its documented. I suspect we don't agree there, but that's my opinion. \$\endgroup\$ – markspace Dec 23 '14 at 21:47
1
\$\begingroup\$

I concur with @Simon, using LinkedHashSet or TreeSet might be a better fit if you wanted more of the Set semantics.

Since you said you needed the subList() method specifically, and if you don't mind a slight performance impact, I will suggest extending from ArrayList and overriding the add() methods to do a contains() check first so that you do not have two Collections sitting in a custom class.

Otherwise, perhaps a secondary 'light' Set<Integer> storing the hashCode() values of the List elements might be enough to act as a simpified, slightly better-performing (borrowing your words, 'caveat emptor' :p) duplicate values checker.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think you have a good idea for just using a List only, but since I do basically the same thing as a Set, it seemed appropriate to do it this way; maybe I'm wrong. Re. TreeSet: I think I tried a TreeSet at first and then had to use this to speed up the implementation. IIRC O(1) instead of O(n) was a very large speed increase during insertions. \$\endgroup\$ – markspace Dec 23 '14 at 0:51
  • \$\begingroup\$ And hence my hedge 'slight performance impact'. :p \$\endgroup\$ – h.j.k. Dec 23 '14 at 0:54
1
\$\begingroup\$

In Java, the natural interface for a class that implements both Set and List might be SortedSet, since it would presume that there is some ordering to the elements that would support element access by index.

Essentially, the Set interface mandates uniqueness of elements, and the List interface mandates some ordering. If your implementation does not satisfy those two requirements, then it is not adhering to the contracts of the interfaces.

The other critique I have of your implementation is the duplication of elements in collections within the class. This is efficient neither in memory nor computation. The source code of ArrayList and HashSet are both available, it would be instructive to study those if performance is a concern.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.