001/* Copyright (C) 2013 TU Dortmund
002 * This file is part of AutomataLib, http://www.automatalib.net/.
003 * 
004 * AutomataLib is free software; you can redistribute it and/or
005 * modify it under the terms of the GNU Lesser General Public
006 * License version 3.0 as published by the Free Software Foundation.
007 * 
008 * AutomataLib is distributed in the hope that it will be useful,
009 * but WITHOUT ANY WARRANTY; without even the implied warranty of
010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
011 * Lesser General Public License for more details.
012 * 
013 * You should have received a copy of the GNU Lesser General Public
014 * License along with AutomataLib; if not, see
015 * http://www.gnu.de/documents/lgpl.en.html.
016 */
017package net.automatalib.commons.smartcollections;
018
019import java.util.Iterator;
020
021
022/**
023 * Abstract base class for linked lists.
024 * 
025 * This class implements the base functionality for dealing with
026 * linked lists of elements implementing the {@link LinkedListEntry}
027 * interface. It provides the logic for the basic operations (esp.
028 * the (re-/un-)linking of elements), but not how entries into the
029 * lists are created. Therefore, it can be used by both 
030 * intrusive and non-intrusive linked lists.
031 * 
032 * @author Malte Isberner <malte.isberner@gmail.com>
033 *
034 * @param <E> element type
035 * @param <T> linked list entry type
036 * 
037 * @see IntrusiveLinkedList
038 * @see DefaultLinkedList
039 */
040public abstract class AbstractLinkedList<E, T extends LinkedListEntry<E, T>>
041extends AbstractSmartCollection<E> implements
042SmartSequence<E> {
043
044        
045        // head element (may be null if list is empty)
046        private T head;
047        // last element (may be null if list is empty)
048        private T last;
049        // number of elements in the list
050        private int size;
051
052        /**
053         * Iterator that follows the linked structure of the
054         * elements.
055         * 
056         * @author Malte Isberner <malte.isberner@cs.uni-dortmund.de>
057         */
058        private class LinkedListEntryIterator
059        implements Iterator<T> {
060                // current entry
061                private T current;
062
063                /*
064                 * Constructor.
065                 */
066                public LinkedListEntryIterator(T head) {
067                        this.current = head;
068                }
069
070                /*
071                 * (non-Javadoc)
072                 * @see java.util.Iterator#hasNext()
073                 */
074                @Override
075                public boolean hasNext() {
076                        return (current != null);
077                }
078
079                /*
080                 * (non-Javadoc)
081                 * @see java.util.Iterator#next()
082                 */
083                @Override
084                public T next() {
085                        T e = current;
086                        current = current.getNext();
087                        return e;
088                }
089
090                /*
091                 * (non-Javadoc)
092                 * @see java.util.Iterator#remove()
093                 */
094                @Override
095                public void remove() {
096                        T next = current.getNext();
097                        removeEntry(current);
098                        current = next;
099                }
100        }
101        
102        private class ElementIterator
103        implements Iterator<E> {
104                // current entry
105                private T current;
106
107                /*
108                 * Constructor.
109                 */
110                public ElementIterator(T head) {
111                        this.current = head;
112                }
113
114                /*
115                 * (non-Javadoc)
116                 * @see java.util.Iterator#hasNext()
117                 */
118                @Override
119                public boolean hasNext() {
120                        return (current != null);
121                }
122
123                /*
124                 * (non-Javadoc)
125                 * @see java.util.Iterator#next()
126                 */
127                @Override
128                public E next() {
129                        E e = current.getElement();
130                        current = current.getNext();
131                        return e;
132                }
133
134                /*
135                 * (non-Javadoc)
136                 * @see java.util.Iterator#remove()
137                 */
138                @Override
139                public void remove() {
140                        T next = current.getNext();
141                        removeEntry(current);
142                        current = next;
143                }
144        }
145
146
147
148        /**
149         * Adds an entry at the beginning of the list.
150         * @param e the entry to add.
151         */
152        protected void pushFrontEntry(T e) {
153                e.setPrev(null);
154                e.setNext(head);
155                if (head != null)
156                        head.setPrev(e);
157                else
158                        last = e;
159                head = e;
160                size++;
161        }
162
163        /**
164         * Adds an entry at the end of the list.
165         * @param e the entry to add.
166         */
167        protected void pushBackEntry(T e) {
168                e.setNext(null);
169                e.setPrev(last);
170                if (last != null)
171                        last.setNext(e);
172                else
173                        head = e;
174                last = e;
175                size++;
176        }
177
178        /**
179         * Retrieves the first entry in the list, or <code>null</code>
180         * if the list is empty.
181         * @return the first entry or <code>null</code>.
182         */
183        protected T getFrontEntry() {
184                return head;
185        }
186
187        /**
188         * Retrieves the last entry in the list, or <code>null</code>
189         * if the list is empty.
190         * @return the first entry or <code>null</code>.
191         */
192        protected T getBackEntry() {
193                return last;
194        }
195
196        /**
197         * Removes and returns the first entry in the list. If the
198         * list is empty, it remains unmodified and <code>null</code>
199         * is returned.
200         * @return the previously first entry in the list, or
201         * <code>null</code>.
202         */
203        protected T popFrontEntry() {
204                if (head == null)
205                        return null;
206                T next = head.getNext();
207                if (next != null)
208                        next.setPrev(null);
209                else
210                        last = null;
211                T e = head;
212                head = next;
213                e.setNext(null);
214                size--;
215                return e;
216        }
217
218        /**
219         * Removes and returns the last entry in the list. If the
220         * list is empty, it remains unmodified and <code>null</code>
221         * is returned.
222         * @return the previously first entry in the list, or
223         * <code>null</code>.
224         */
225        protected T popBackEntry() {
226                if (last == null)
227                        return null;
228                T prev = last.getPrev();
229                if (prev != null)
230                        prev.setNext(null);
231                else
232                        head = null;
233                T e = last;
234                last = prev;
235                e.setPrev(null);
236                size--;
237                return e;
238        }
239
240        /**
241         * Inserts a new entry <i>before</i> a given one.
242         * @param e the entry to add.
243         * @param insertPos the entry before which to add the new one.
244         */
245        protected void insertBeforeEntry(T e, T insertPos) {
246                T oldPrev = insertPos.getPrev();
247                e.setNext(insertPos);
248                e.setPrev(oldPrev);
249                insertPos.setPrev(e);
250                if (oldPrev != null)
251                        oldPrev.setNext(e);
252                else
253                        head = e;
254                size++;
255        }
256
257        /**
258         * Inserts a new entry <i>after</i> a given one.
259         * @param e the entry to add.
260         * @param insertPos the entry before which to add the new one.
261         */
262        protected void insertAfterEntry(T e, T insertPos) {
263                T oldNext = insertPos.getNext();
264                e.setNext(oldNext);
265                e.setPrev(insertPos);
266                insertPos.setNext(e);
267                if (oldNext != null)
268                        oldNext.setPrev(e);
269                else
270                        last = e;
271                size++;
272        }
273
274        /**
275         * Removes an entry from the list.
276         * @param entry the entry to remove.
277         */
278        protected void removeEntry(T entry) {
279                T prev = entry.getPrev();
280                T next = entry.getNext();
281                if (prev != null)
282                        prev.setNext(next);
283                else
284                        head = next;
285                if (next != null)
286                        next.setPrev(prev);
287                else
288                        last = prev;
289                size--;
290        }
291
292        /**
293         * Replaces an entry in the list.
294         * @param oldEntry the entry to be replaced. 
295         * @param newEntry the replacement entry.
296         */
297        protected void replaceEntry(T oldEntry, T newEntry) {
298                T prev = oldEntry.getPrev();
299                T next = newEntry.getNext();
300                if(prev != null)
301                        prev.setNext(newEntry);
302                else
303                        head = newEntry;
304                if(next != null)
305                        next.setPrev(newEntry);
306                else
307                        last = newEntry;
308        }
309
310
311        /*
312         * (non-Javadoc)
313         * @see java.util.AbstractCollection#isEmpty()
314         */
315        @Override
316        public boolean isEmpty() {
317                return (head == null);
318        }
319
320        /*
321         * (non-Javadoc)
322         * @see java.util.AbstractCollection#clear()
323         */
324        @Override
325        public void clear() {
326                head = last = null;
327                size = 0;
328        }
329
330        /**
331         * Deprecated. Use {@link #concat(AbstractLinkedList)}.
332         */
333        @Deprecated
334        public void addCompletely(AbstractLinkedList<? extends E, ? extends T> other) {
335                concat(other);
336        }
337
338        /**
339         * Concatenates two linked lists. All elements of the specified list
340         * (which will be empty afterwards) are added at the end of this list.
341         * This operation runs in constant time. 
342         * @param other the list to append,
343         */
344        public void concat(AbstractLinkedList<? extends E,? extends T> other) {
345                if (other.isEmpty())
346                        return;
347
348                if (isEmpty()) {
349                        head = other.head;
350                        last = other.last;
351                } else {
352                        last.setNext(other.head);
353                        other.head.setPrev(last);
354                        last = other.last;
355                }
356                size += other.size;
357                other.clear();
358        }
359
360
361
362        /*
363         * (non-Javadoc)
364         * @see de.ls5.smartcollections.AbstractSmartCollection#choose()
365         */
366        @Override
367        public E choose() {
368                return head.getElement();
369        }
370
371        /*
372         * (non-Javadoc)
373         * @see de.ls5.smartcollections.AbstractSmartCollection#chooseRef()
374         */
375        @Override
376        public ElementReference chooseRef() {
377                return head;
378        }
379
380        /*
381         * (non-Javadoc)
382         * @see de.ls5.smartcollections.SmartCollection#get(de.ls5.smartcollections.ElementReference)
383         */
384        @Override
385        @SuppressWarnings("unchecked")
386        public E get(ElementReference ref) {
387                return ((T)ref).getElement();
388        }
389
390        /*
391         * (non-Javadoc)
392         * @see de.ls5.smartcollections.SmartCollection#referenceIterator()
393         */
394        @Override
395        @SuppressWarnings("unchecked")
396        public Iterator<ElementReference> referenceIterator() {
397                return (Iterator<ElementReference>)(Iterator<?>)new LinkedListEntryIterator(head);
398        }
399        
400        @Override
401        public Iterator<E> iterator() {
402                return new ElementIterator(head);
403        }
404
405        /*
406         * (non-Javadoc)
407         * @see de.ls5.smartcollections.SmartCollection#referencedAdd(java.lang.Object)
408         */
409        @Override
410        public ElementReference referencedAdd(E elem) {
411                T entry = makeEntry(elem);
412                pushBackEntry(entry);
413                return entry;
414        }
415
416
417        /*
418         * (non-Javadoc)
419         * @see de.ls5.smartcollections.SmartCollection#remove(de.ls5.smartcollections.ElementReference)
420         */
421        @Override
422        @SuppressWarnings("unchecked")
423        public void remove(ElementReference elem) {
424                removeEntry((T)elem);
425        }
426
427
428        /*
429         * (non-Javadoc)
430         * @see java.util.AbstractCollection#size()
431         */
432        @Override
433        public int size() {
434                return size;
435        }
436
437
438        /*
439         * (non-Javadoc)
440         * @see de.ls5.smartcollections.SmartCollection#replace(de.ls5.smartcollections.ElementReference, java.lang.Object)
441         */
442        @Override
443        @SuppressWarnings("unchecked")
444        public void replace(ElementReference ref, E newElement) {
445                T newEntry = makeEntry(newElement);
446                replaceEntry((T)ref, newEntry);
447        }
448
449
450        /**
451         * Retrieves the last element in the list. If the list is empty,
452         * a {@link NullPointerException} may be thrown.
453         * @return the last element in the list.
454         */
455        public E getBack() {
456                return last.getElement();
457        }
458
459        /**
460         * Retrieves a reference to the last element in the list. If the list is
461         * empty, <code>null</code> is returned.
462         * @return a reference to the last element, or <code>null</code>.
463         */
464        public ElementReference getBackReference() {
465                return last;
466        }
467
468        /**
469         * Retrieves the first element in the list. If the list is empty,
470         * a {@link NullPointerException} may be thrown.
471         * @return the first element in the list.
472         */
473        public E getFront() {
474                return head.getElement();
475        }
476
477        /**
478         * Retrieves a reference to the first element in the list. If the list is
479         * empty, <code>null</code> is returned.
480         * @return a reference to the first element, or <code>null</code>.
481         */
482        public ElementReference getFrontReference() {
483                return head;
484        }
485
486        /*
487         * (non-Javadoc)
488         * @see de.ls5.smartcollections.SmartSequence#insertAfter(java.lang.Object, de.ls5.smartcollections.ElementReference)
489         */
490        @Override
491        @SuppressWarnings("unchecked")
492        public ElementReference insertAfter(E element, ElementReference ref) {
493                T entry = makeEntry(element);
494                insertAfterEntry(entry, (T)ref);
495                return entry;
496        }
497
498        /*
499         * (non-Javadoc)
500         * @see de.ls5.smartcollections.SmartSequence#insertBefore(java.lang.Object, de.ls5.smartcollections.ElementReference)
501         */
502        @Override
503        @SuppressWarnings("unchecked")
504        public ElementReference insertBefore(E element, ElementReference ref) {
505                T entry = makeEntry(element);
506                insertBeforeEntry(entry, (T)ref);
507                return entry;
508        }
509
510        /**
511         * Retrieves and removes the last element in the list. If the list is
512         * empty, a {@link NullPointerException} may be thrown.
513         * @return the formerly last element in the list.
514         */
515        public E popBack() {
516                return popBackEntry().getElement();
517        }
518
519        /**
520         * Retrieves and removes the first element in the list. If the list is
521         * empty, a {@link NullPointerException} may be thrown.
522         * @return the formerly first element in the list.
523         */
524        public E popFront() {
525                return popFrontEntry().getElement();
526        }
527
528        /**
529         * Adds an element at the end of the list.
530         * @param element the element to add.
531         * @return a reference to the newly added element.
532         */
533        public ElementReference pushBack(E element) {
534                T entry = makeEntry(element);
535                pushBackEntry(entry);
536                return entry;
537        }
538
539        /**
540         * Adds an element at the beginning of the list.
541         * @param element the element to add.
542         * @return a reference to the newly added element.
543         */
544        public ElementReference pushFront(E element) {
545                T entry = makeEntry(element);
546                pushFrontEntry(entry);
547                return entry;
548        }
549
550        /**
551         * Creates (if necessary) a {@link LinkedListEntry} for the given element.
552         * For intrusive linked lists, e.g., the argument itself is returned.
553         * @param element the element for which to retrieve an entry.
554         * @return the entry for the given element.
555         */
556        protected abstract T makeEntry(E element);
557
558
559        /**
560         * Helper function for casting a general {@link ElementReference}
561         * to the specific linked list entry type.
562         * @param ref the reference.
563         * @return the argument cast to the entry type.
564         */
565        @SuppressWarnings("unchecked")
566        protected T castRef(ElementReference ref) {
567                return (T)ref;
568        }
569        
570
571        /*
572         * (non-Javadoc)
573         * @see de.ls5.smartcollections.SmartSequence#pred(de.ls5.smartcollections.ElementReference)
574         */
575        @Override
576        public ElementReference pred(ElementReference ref) {
577                return castRef(ref).getPrev();
578        }
579
580        /*
581         * (non-Javadoc)
582         * @see de.ls5.smartcollections.SmartSequence#succ(de.ls5.smartcollections.ElementReference)
583         */
584        @Override
585        public ElementReference succ(ElementReference ref) {
586                return castRef(ref).getNext();
587        }
588
589        /**
590         * Swaps the contents of two linked lists with the same entry types.
591         * This method runs in constant time.
592         * @param other the other list to swap contents with.
593         */
594        public void swap(AbstractLinkedList<E,T> other) {
595                int sizeTmp = this.size;
596                T headTmp = this.head;
597                T lastTmp = this.last;
598                this.size = other.size;
599                this.head = other.head;
600                this.last = other.last;
601                other.size = sizeTmp;
602                other.head = headTmp;
603                other.last = lastTmp;
604        }
605
606}