Java-Gaming.org    
Featured games (91)
games approved by the League of Dukes
Games in Showcase (580)
games submitted by our members
Games in WIP (500)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Designing a Collection  (Read 1503 times)
0 Members and 1 Guest are viewing this topic.
Offline i30817

Junior Member





« Posted 2012-08-18 19:49:50 »

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?
Offline i30817

Junior Member





« Reply #1 - Posted 2012-08-18 21:30:27 »

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).
Offline i30817

Junior Member





« Reply #2 - Posted 2012-08-19 01:39:14 »

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  Pointing

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!
Legends of Yore - The Casual Retro Roguelike
Offline gimbal

JGO Coder


Medals: 25



« Reply #3 - Posted 2012-08-20 10:07:56 »

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.
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

xsi3rr4x (50 views)
2014-04-15 18:08:23

BurntPizza (46 views)
2014-04-15 03:46:01

UprightPath (62 views)
2014-04-14 17:39:50

UprightPath (44 views)
2014-04-14 17:35:47

Porlus (61 views)
2014-04-14 15:48:38

tom_mai78101 (84 views)
2014-04-10 04:04:31

BurntPizza (142 views)
2014-04-08 23:06:04

tom_mai78101 (242 views)
2014-04-05 13:34:39

trollwarrior1 (201 views)
2014-04-04 12:06:45

CJLetsGame (208 views)
2014-04-01 02:16:10
List of Learning Resources
by SHC
2014-04-18 03:17:39

List of Learning Resources
by Longarmx
2014-04-08 03:14:44

Good Examples
by matheus23
2014-04-05 13:51:37

Good Examples
by Grunnt
2014-04-03 15:48:46

Good Examples
by Grunnt
2014-04-03 15:48:37

Good Examples
by matheus23
2014-04-01 18:40:51

Good Examples
by matheus23
2014-04-01 18:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:22:30
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!