Designing a Collection

[i30817]

Designing is another word for procrastination
edit: new and better version below

This is fairly simple as you can see; just directional methods sorely lacking on the LinkedHashMap class.

Now here comes the bad part - yes, you guessed it - i want bidirectional iteration and adding elements (almost all the elements of a ListIterator)

Unfortunately LinkedHashMap sucks and the needed fields and methods are private and package protected.

My idea for the design would be to get to the linked list nodes (which are entries on the LinkedHashMap so they can be got with HashMap.getEntry) and use that (and the header and modcount...) to make a new List iterator:

ListIterator from(E elem)

Anyway, for the methods on the Set class above to continue to work, ListIterator.add (not set) would have to rebuild the Integer Values beyond when used on the Set context, that's the reason for the iteratorAddModulus.

I can't apparently reuse the LinkedHashset without copying the whole source file into my source tree (and putting it on 'java.util').

Am i being dumb and something with these characteristics - a set, which is directional, with bidirectional iterators that can set() and add(), that can check element > otherelement in O(1) and is (probably) fast already exist?

[i30817]

Can i copy and modify oracle classes into my project if it is LGPL?

Interesting ListIterator.set() and ListIterator.add() may change the iteration order of the thing

Since the set Elements are stored in the keys of a Map, ListIterator.set(K) involves removing the last entry key, adding a new one with K and the old V and inserting that new Entry in the place of the last returned one on the ListIterator.

'adding a new one with K and the old V' may move a subsequent entry in the ListIterator, but i don't really have a problem with that. I think it might be useful (although the original set is always insert order).

[i30817]

Ok i gave up on the 'efficient' way of subclassing the LinkedHashMap and just put in my nodes as values
3 or 4 'unneeded' references but it's clearer
if not really simple  

Anyway, i'd like some opinions and if anyone can spot a bug it'd be nice

edit: Anyone know of a test harness for Collections that deals with the jdk interfaces?
edit2: found the MOAT and fixed a few bugs found by those tests

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   38   39   40   41   42   43   44   45   46   47   48   49   50   51   52   53   54   55   56   57   58   59   60   61   62   63   64   65   66   67   68   69   70   71   72   73   74   75   76   77   78   79   80   81   82   83   84   85   86   87   88   89   90   91   92   93   94   95   96   97   98   99   100   101   102   103   104   105   106   107   108   109   110   111   112   113   114   115   116   117   118   119   120   121   122   123   124   125   126   127   128   129   130   131   132   133   134   135   136   137   138   139   140   141   142   143   144   145   146   147   148   149   150   151   152   153   154   155   156   157   158   159   160   161   162   163   164   165   166   167   168   169   170   171   172   173   174   175   176   177   178   179   180   181   182   183   184   185   186   187   188   189   190   191   192   193   194   195   196   197   198   199   200   201   202   203   204   205   206   207   208   209   210   211   212   213   214   215   216   217   218   219   220   221   222   223   224   225   226   227   228   229   230   231   232   233   234   235   236   237   238   239   240   241   242   243   244   245   246   247   248   249   250   251   252   253   254   255   256   257   258   259   260   261   262   263   264   265   266   267   268   269   270   271   272   273   274   275   276   277   278   279   280   281   282   283   284   285   286   287   288   289   290   291   292   293   294   295   296   297   298   299   300   301   302   303   304   305   306   307   308   309   310   311   312   313   314   315   316   317   318   319   320   321   322   323   324   325   326   327   328   329   330   331   332   333   334   335   336   337   338   339   340   341   342   343   344   345   346   347   348   349   350   351   352   353   354   355   356   357   358   359   360   361   362   363   364   365   366   367   368   369   370   371   372   373   374   375   376   377   378   379   380   381   382   383

package i3.util; import java.util.AbstractSet; import java.util.Collection; import java.util.ConcurrentModificationException; import java.util.HashMap; import java.util.Iterator; import java.util.ListIterator; import java.util.Map; import java.util.NoSuchElementException; /**  * This class is a like LinkedHashSet (insertion order) but it allows querying  * the relative position of a element and has a ListIterator that can set and  * insert anywhere.  *  * Warning: the iterator can change the order of the set by moving elements when  * setting or adding. Elements that already exist are not ignored, but moved the  * requested place. This changes iteration order  *  *  * The iterators of this class are fail fast and will throw a  * ConcurrentModificationException if their iterator are used with intervening  * main class (or other iterators) mutative calls  *  * @author i30817 <i30817@gmail.com>  */ public class LinkedSet<E> extends AbstractSet<E> {     //It holds the linked list    private Map<E, Node> m = new HashMap<E, Node>();     //head of that    protected Node head = new Node();     //this is copied to the map value in increments of iteratorAddStep on set.add    //(which only adds to the end, by insertion indexing)    private int monotonicallyIncreasing = 0;     //iterator add step may change when doing rebuilds of the 'space' between elements    //for the before/after functions on LinkedKeyIterator.add    private int iteratorAddStep = 10;     //for fail fast iterators    private int modCount;     /**      * Start iterating from elem (inclusive)      *      *      * @throws NoSuchElementException if E not part of the set      * @param elem a element of the set      * @return a ListIterator - doesn't support nextIndex() or previousIndex()      */     public ListIterator<E> from(E elem) {         Node e = m.get(elem);         if (e == null) {             throw new NoSuchElementException("the given element isn't part of the set");         }         return new LinkedKeyIterator(e);     }     @Override     public ListIterator<E> iterator() {         return new LinkedKeyIterator();     }     /**      * Returns true if the value target was added before (exclusive) limitElem      * in insertion order.      *      * If target or limit are not present on the set this method returns false      *      * @param limitElem a E that may be a element of the set or not.      * @return if target was added before limit (can be reset by removing and      * re-adding the target, that changes iteration order).      */     public boolean containsBefore(E target, E limitElem) {         if (isEmpty()) {             return false;         }         Integer targetN = m.get(target).relativeLocation;         Integer highN = m.get(limitElem).relativeLocation;         return targetN != null && highN != null && targetN < highN;     }     /**      * Returns true if the value target was added after (exclusive) previousElem      * in insertion order.      *      * If target or previous are not present on the set this method returns      * false      *      * @param previousElem a E that may be a element of the set or not.      * @return if target was added before previous (can be reset by removing and      * re-adding the target, that changes iteration order).      */     public boolean containsAfter(E target, E previousElem) {         if (isEmpty()) {             return false;         }         Integer targetN = m.get(target).relativeLocation;         Integer low = m.get(previousElem).relativeLocation;         return targetN != null && low != null && low < targetN;     }     @Override     public boolean add(E e) {         if (!m.containsKey(e)) {             Node n = new Node(e, monotonicallyIncreasing);             monotonicallyIncreasing += iteratorAddStep;             n.addBefore(head);//insertion order            m.put(e, n);             return true;         }         return false;     }     @Override     public int size() {         return m.size();     }     @Override     public boolean isEmpty() {         return m.isEmpty();     }     @Override     public boolean contains(Object o) {         return m.containsKey(o);     }     @Override     public Object[] toArray() {         Object[] result = new Object[size()];         int i = 0;         for (E e : this) {             result[i++] = e;         }         return result;     }     @Override     @SuppressWarnings("unchecked")     public <T> T[] toArray(T[] a) {         int size = size();         if (a.length < size) {             a = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);         }         int i = 0;         Object[] result = a;         for (E e : this) {             result[i++] = e;         }         if (a.length > size) {             //peculiar toArray contract where it doesn't care about the rest            a[size] = null;         }         return a;     }     @Override     public boolean remove(Object o) {         Node n = m.remove(o);         if (n != null) {             n.remove();             return true;         }         return false;     }     @Override     public boolean addAll(Collection<? extends E> c) {         boolean changed = false;         for (E e : c) {             changed |= add(e);         }         return changed;     }     @Override     public boolean containsAll(Collection<?> c) {         boolean all = true;         for (Object e : c) {             all &= m.containsKey(e);         }         return all;     }     @Override     public boolean retainAll(Collection<?> c) {         boolean changed = false;         Iterator<E> it = iterator();         while (it.hasNext()) {             E k = it.next();             if (!c.contains(k)) {                 it.remove();                 changed = true;             }         }         return changed;     }     @Override     public void clear() {         modCount++;         head.after = head.before = head;         m.clear();     }     @Override     public String toString() {         return m.keySet().toString();     }     //linkedlist node class    protected final class Node {         Node before, after;         int relativeLocation;         //needed for map removal during iteration        E key;         private void remove() {             before.after = after;             after.before = before;             modCount++;         }         private void addBefore(Node existingEntry) {             after = existingEntry;             before = existingEntry.before;             before.after = this;             after.before = this;             modCount++;         }         //head const        public Node() {             after = before = this;             relativeLocation = 0;         }         public Node(E key, int value) {             this.key = key;             this.relativeLocation = value;         }     }     protected class LinkedKeyIterator implements ListIterator<E> {         Node nextEntry;         Node lastReturned;         int expectedModCount = modCount;         public LinkedKeyIterator() {             nextEntry = head.after;         }         public LinkedKeyIterator(Node startAt) {             nextEntry = startAt;         }         public boolean hasPrevious() {             return nextEntry.before != head;         }         public boolean hasNext() {             return nextEntry != head;         }         public E next() {             if (modCount != expectedModCount) {                 throw new ConcurrentModificationException();             }             if (nextEntry == head) {                 throw new NoSuchElementException();             }             Node e = lastReturned = nextEntry;             nextEntry = e.after;             return e.key;         }         public E previous() {             if (modCount != expectedModCount) {                 throw new ConcurrentModificationException();             }             if (nextEntry.before == head) {                 throw new NoSuchElementException();             }             Node e = lastReturned = nextEntry.before;             nextEntry = e;             return e.key;         }         public void remove() {             if (lastReturned == null) {                 throw new IllegalStateException();             }             if (modCount != expectedModCount) {                 throw new ConcurrentModificationException();             }             m.remove(lastReturned.key);             nextEntry = lastReturned.after;             lastReturned.remove();             lastReturned = null;             expectedModCount = modCount;         }         @Override         public void set(E e) {             if (lastReturned == null) {                 throw new IllegalStateException();             }             if (modCount != expectedModCount) {                 throw new ConcurrentModificationException();             }             if (lastReturned.key.equals(e)) {                 //would not change anything                return;             }             //remove mapping for key since we are changing it            m.remove(lastReturned.key);             //put in the new one            lastReturned.key = e;             Node previousKeyOwner = m.put(e, lastReturned);             if (previousKeyOwner != null) {                 //as it is a list mutation call, guard against stale iterator                if(nextEntry == previousKeyOwner){                     nextEntry = nextEntry.after;                 }                 previousKeyOwner.remove();             }             //from m.remove and m.put, may help with 2 concurrent iterators on this instance            //this method may not change modCount if previousKeyOwner is null            expectedModCount = ++modCount;         }         @Override         public void add(E e) {             if (modCount != expectedModCount) {                 throw new ConcurrentModificationException();             }             //nuke it, as per contract of remove()            lastReturned = null;             //calculate a good relative location, updating subsequent ones if needed            int candidateLoc = nextEntry.before.relativeLocation + 1;             //opsss, it's full            if (candidateLoc == nextEntry.relativeLocation) {                 iteratorAddStep *= 1.6;                 for (Node current = nextEntry; current != head; current = current.after) {                     current.relativeLocation = current.relativeLocation + iteratorAddStep;                 }             }             Node n = m.get(e);             if (n == null) {                 n = new Node(e, candidateLoc);                 m.put(e, n);             } else {                 n.relativeLocation = candidateLoc;                 //as it is a list mutation call, guard against stale iterator                if(nextEntry == n){                     nextEntry = nextEntry.after;                 }                 n.remove();             }             n.addBefore(nextEntry);             expectedModCount = modCount;//add before changes modCount        }         @Override         public int nextIndex() {             throw new UnsupportedOperationException("Not supported yet.");         }         @Override         public int previousIndex() {             throw new UnsupportedOperationException("Not supported yet.");         }     } }

Games published by our own members! Check 'em out!

[gimbal]

Can i copy and modify oracle classes into my project if it is LGPL?

My advice: I'd copy the idea, not the actual code.