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}