src/jalview/util/LinkedIdentityHashSet.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
   3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
   4  *
   5  * This file is part of Jalview.
   6  *
   7  * Jalview is free software: you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation, either version 3
  10  * of the License, or (at your option) any later version.
  11  *
  12  * Jalview is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty
  14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE.  See the GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
  19  * The Jalview Authors are detailed in the 'AUTHORS' file.
  20  */
  21 package jalview.util;
  22
  23 import java.util.AbstractSet;
  24 import java.util.Iterator;
  25 import java.util.LinkedHashMap;
  26
  27 /**
  28  * Order preserving Set based on System.identityHashCode() for an object, which
  29  * also supports Object->index lookup.
  30  *
  31  * @author Jim Procter (2016) based on Evgeniy Dorofeev's response: via
  32  *         https://stackoverflow.com/questions/17276658/linkedidentityhashset
  33  *
  34  */
  35 public class LinkedIdentityHashSet<E> extends AbstractSet<E>
  36 {
  37   LinkedHashMap<IdentityWrapper, IdentityWrapper> set = new LinkedHashMap<IdentityWrapper, IdentityWrapper>();
  38
  39   static class IdentityWrapper
  40   {
  41     Object obj;
  42
  43     public int p;
  44
  45     IdentityWrapper(Object obj, int p)
  46     {
  47       this.obj = obj;
  48       this.p = p;
  49     }
  50
  51     @Override
  52     public boolean equals(Object obj)
  53     {
  54       return this.obj == obj;
  55     }
  56
  57     @Override
  58     public int hashCode()
  59     {
  60       return System.identityHashCode(obj);
  61     }
  62   }
  63
  64   @Override
  65   public boolean add(E e)
  66   {
  67     IdentityWrapper el = (new IdentityWrapper(e, set.size()));
  68     // Map.putIfAbsent() from Java 8
  69     // return set.putIfAbsent(el, el) == null;
  70     return putIfAbsent(el, el) == null;
  71   }
  72
  73   /**
  74    * If the specified key is not already associated with a value (or is mapped
  75    * to null) associates it with the given value and returns null, else returns
  76    * the current value.
  77    *
  78    * Method added for Java 7 (can remove for Java 8)
  79    *
  80    * @param key
  81    * @param value
  82    * @return
  83    * @see https
  84    *      ://docs.oracle.com/javase/8/docs/api/java/util/Map.html#putIfAbsent
  85    *      -K-V-
  86    */
  87   private IdentityWrapper putIfAbsent(IdentityWrapper key,
  88           IdentityWrapper value)
  89   {
  90     IdentityWrapper v = set.get(key);
  91     if (v == null)
  92     {
  93       v = set.put(key, value);
  94     }
  95     return v;
  96   }
  97
  98   @Override
  99   public Iterator<E> iterator()
 100   {
 101     return new Iterator<E>()
 102     {
 103       final Iterator<IdentityWrapper> se = set.keySet().iterator();
 104
 105       @Override
 106       public boolean hasNext()
 107       {
 108         return se.hasNext();
 109       }
 110
 111       @SuppressWarnings("unchecked")
 112       @Override
 113       public E next()
 114       {
 115         return (E) se.next().obj;
 116       }
 117
 118       @Override
 119       public void remove()
 120       {
 121         // Java 8 default behaviour
 122         throw new UnsupportedOperationException();
 123       }
 124     };
 125   }
 126
 127   @Override
 128   public int size()
 129   {
 130     return set.size();
 131   }
 132
 133   /**
 134    * Lookup the index for e in the set
 135    *
 136    * @param e
 137    * @return position of e in the set when it was added.
 138    */
 139   public int indexOf(E e)
 140   {
 141     return set.get(e).p;
 142   }
 143 }