LinkedQueue, allows endless iteration

Discussion in 'Resources' started by 1Rogue, Nov 23, 2013.

Thread Status:
Not open for further replies.
  1. Offline

    1Rogue

    The class:
    Show Spoiler
    Code:java
    1. /*
    2.  * Copyright (C) 2013 Spencer Alderman
    3.  *
    4.  * This program is free software: you can redistribute it and/or modify
    5.  * it under the terms of the GNU General Public License as published by
    6.  * the Free Software Foundation, either version 3 of the License, or
    7.  * (at your option) any later version.
    8.  *
    9.  * This program is distributed in the hope that it will be useful,
    10.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
    11.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    12.  * GNU General Public License for more details.
    13.  *
    14.  * You should have received a copy of the GNU General Public License
    15.  * along with this program. If not, see <[url]http://www.gnu.org/licenses/>[/url].
    16.  */
    17.  
    18. import java.util.Arrays;
    19. import java.util.Collection;
    20. import java.util.Iterator;
    21.  
    22. /**
    23.  * LinkedQueue that allows to iterate over the method endlessly
    24.  *
    25.  * @author 1Rogue
    26.  */
    27. public final class LinkedQueue<E> implements Collection<E> {
    28.  
    29. private int size = 0;
    30. private QueueNode<E> node;
    31. private QueueNode<E> loc;
    32.  
    33. /**
    34.   * Creates a LinkedQueue object with the provided values
    35.   *
    36.   * @param inits Values to add
    37.   */
    38. public LinkedQueue(E... inits) {
    39. this.addAll(Arrays.asList(inits));
    40. }
    41.  
    42. /**
    43.   * Creates an empty LinkedQueue object
    44.   */
    45. public LinkedQueue() {
    46. this.node = new QueueNode(null, null, null);
    47. }
    48.  
    49. /**
    50.   * Add an object to the end of the queue.
    51.   *
    52.   * @param newElement The object to be added to the queue.
    53.   */
    54. @Override
    55. public boolean add(E newElement) {
    56. if (size == 0) {
    57. node = new QueueNode(null, newElement, null);
    58. this.size++;
    59. return true;
    60. } else {
    61. QueueNode<E> temp = this.node;
    62. while (temp.getNextNode() != null) {
    63. if (temp.getNextNode() != null) {
    64. temp = temp.getNextNode();
    65. }
    66. }
    67. temp.setNextNode(new QueueNode(this.node, newElement, null));
    68. this.size++;
    69. return true;
    70. }
    71. }
    72.  
    73. /**
    74.   * Return the item at the front of the queue without deleting it.
    75.   *
    76.   * @return the item at the front of the queue
    77.   *
    78.   * @exception IllegalStateException thrown if the queue is empty. Message
    79.   * associated with the exception is: "LinkedQueue getFront problem"
    80.   */
    81. public E getFront() {
    82. if (this.size == 0) {
    83. throw new IllegalStateException("LinkedQueue is empty!");
    84. } else {
    85. return this.node.getValue();
    86. }
    87. }
    88.  
    89. /**
    90.   * Remove and return the first element in the queue
    91.   *
    92.   * @return the first element in the queue
    93.   *
    94.   * @exception IllegalStateException thrown if the queue is empty. Message
    95.   * associated with the exception is: "LinkedQueue dequeue problem"
    96.   */
    97. public E dequeue() {
    98. if (this.size == 0) {
    99. throw new IllegalStateException("LinkedQueue is empty!");
    100. } else {
    101. E val = this.node.getValue();
    102. this.remove(val);
    103. this.size--;
    104. return val;
    105. }
    106. }
    107.  
    108. /**
    109.   * Removes the given item from the queue. The item can appear anywhere in
    110.   * the list.
    111.   *
    112.   * @param itemToRemove The item to be removed from the queue.
    113.   *
    114.   * @return true if the item was removed
    115.   */
    116. @Override
    117. public boolean remove(Object itemToRemove) {
    118. QueueNode<E> temp = this.node;
    119. while (temp.getNextNode() != null) {
    120. if (temp.getValue() == itemToRemove) {
    121. if (temp.getPreviousNode() == null) {
    122. temp.getNextNode().setPreviousNode(null);
    123. this.node = temp.getNextNode();
    124. } else if (temp.getNextNode() == null) {
    125. temp.getPreviousNode().setNextNode(null);
    126. } else {
    127. temp.getPreviousNode().setNextNode(temp.getNextNode());
    128. temp.getNextNode().setPreviousNode(temp.getPreviousNode());
    129. }
    130. this.size--;
    131. return true;
    132. } else {
    133. temp = temp.getNextNode();
    134. }
    135. }
    136. return false;
    137. }
    138.  
    139. /**
    140.   * Inserts an items BEFORE the given item (cut in line)
    141.   *
    142.   * @param itemToInsert The item to be inserted
    143.   * @param insertBefore Which item in the queue the inserted items gets
    144.   * inserted before
    145.   * @return true if we were able to insert the element, false otherwise
    146.   */
    147. public boolean insertBefore(E itemToInsert, E insertBefore) {
    148. QueueNode<E> temp = this.node;
    149. while (temp.getNextNode() != null) {
    150. if (temp.getValue() == insertBefore) {
    151. QueueNode<E> insert = new QueueNode(temp.getPreviousNode(), itemToInsert, temp);
    152. if (temp.getPreviousNode() != null) {
    153. temp.getPreviousNode().setNextNode(insert);
    154. }
    155. temp.setPreviousNode(insert);
    156. this.size++;
    157. return true;
    158. } else {
    159. temp = temp.getNextNode();
    160. }
    161. }
    162. return false;
    163. }
    164.  
    165. /**
    166.   * Return the number of elements currently in this queue.
    167.   *
    168.   * @return the number of elements in this queue.
    169.   */
    170. public int getSize() {
    171. return this.size;
    172. }
    173.  
    174. /**
    175.   * Return the state of the queue; return true if the queue is empty,
    176.   * otherwise return false.
    177.   *
    178.   * @return true if the queue is empty, otherwise return false.
    179.   */
    180. public boolean isEmpty() {
    181. return this.size == 0;
    182. }
    183.  
    184. /**
    185.   * Returns the next value in the LinkedQueue. If the queue contains one
    186.   * value, this will return the same value every time.
    187.   *
    188.   * @return The next value in the queue.
    189.   */
    190. public E getNext() {
    191. if (this.loc == null) {
    192. this.loc = this.node;
    193. } else {
    194. this.loc = this.loc.getNextNode();
    195. }
    196. if (this.loc == null) {
    197. this.loc = this.node;
    198. }
    199. return this.loc.getValue();
    200. }
    201.  
    202. /**
    203.   * Returns the size of the queue
    204.   *
    205.   * @return The queue's size
    206.   */
    207. @Override
    208. public int size() {
    209. return this.size;
    210. }
    211.  
    212. /**
    213.   * Returns whether or not there is the relevant object in the queue
    214.   *
    215.   * @param o The object to check for
    216.   * @return True if it is within the Queue, false otherwise
    217.   */
    218. @Override
    219. public boolean contains(Object o) {
    220. QueueNode<E> next = this.node;
    221. while (next != null) {
    222. if (next.getValue() == o) {
    223. return true;
    224. }
    225. next = next.getNextNode();
    226. }
    227. return false;
    228. }
    229.  
    230. /**
    231.   * Returns an iterator of this class
    232.   *
    233.   * @return The iterator of this class
    234.   */
    235. @Override
    236. public Iterator iterator() {
    237. return new Itr(this.node);
    238. }
    239.  
    240. /**
    241.   * Returns an array of this class
    242.   *
    243.   * @return This class as an array
    244.   */
    245. @Override
    246. public Object[] toArray() {
    247. Object[] back = new Object[this.size];
    248. QueueNode<E> next = this.node;
    249. for (int i = 0; i < this.size; i++) {
    250. back[[b][/b]i] = next.getValue();
    251. next = next.getNextNode();
    252. }
    253. return back;
    254. }
    255.  
    256. /**
    257.   * Returns an array in the given object type of array, or null if it is
    258.   * unsupported
    259.   *
    260.   * @param a The array type to use
    261.   * @return The new array, or null if impossible
    262.   */
    263. @Override
    264. public <T> T[] toArray(T[] a) {
    265. QueueNode<E> next = this.node;
    266. try {
    267. return (T[]) this.toArray();
    268. } catch (ClassCastException e) {
    269. return null;
    270. }
    271. }
    272.  
    273. /**
    274.   * Returns whether or not this queue contains all objects in the collection
    275.   *
    276.   * @param c The collection to check against
    277.   * @return True if all items are in the queue, false otherwise
    278.   */
    279. @Override
    280. public boolean containsAll(Collection<?> c) {
    281. boolean all = true;
    282. for (Object o : c) {
    283. if (!this.contains(o)) {
    284. all = false;
    285. }
    286. }
    287. return all;
    288. }
    289.  
    290. /**
    291.   * Adds all items in the collection to this queue
    292.   *
    293.   * @param c The collection to add from
    294.   * @return True if all items were added, false otherwise
    295.   */
    296. @Override
    297. public boolean addAll(Collection<? extends E> c) {
    298. boolean all = true;
    299. for (E o : c) {
    300. this.add(o);
    301. }
    302. return all;
    303. }
    304.  
    305. /**
    306.   * Removes all items from the queue provided by the relevant collection
    307.   *
    308.   * @param c The collection to remove against
    309.   * @return True if all items are removed, false otherwise
    310.   */
    311. @Override
    312. public boolean removeAll(Collection<?> c) {
    313. boolean all = true;
    314. for (Object o : c) {
    315. try {
    316. this.remove((E) o);
    317. } catch (ClassCastException e) {
    318. all = false;
    319. }
    320. }
    321. return all;
    322. }
    323.  
    324. /**
    325.   * Retains all objects in this queue that are within the provided collection
    326.   *
    327.   * @param c The collection to check against
    328.   * @return True if all are retained, false otherwise
    329.   */
    330. @Override
    331. public boolean retainAll(Collection<?> c) {
    332. boolean all = true;
    333. LinkedQueue<E> nodes = new LinkedQueue();
    334. for (Object o : this) {
    335. if (!c.contains(o)) {
    336. try {
    337. nodes.add((E) o);
    338. } catch (ClassCastException e) {
    339. all = false;
    340. }
    341. }
    342. }
    343. this.removeAll(nodes);
    344. return all;
    345. }
    346.  
    347. /**
    348.   * Clears the current queue
    349.   */
    350. @Override
    351. public void clear() {
    352. this.node = new QueueNode(null, null, null);
    353. this.size = 0;
    354. }
    355. }
    356.  
    357. /**
    358.  * Private node for the LinkedQueue class
    359.  *
    360.  * @author Spencer Alderman
    361.  */
    362. class QueueNode<E> {
    363.  
    364. private E value;
    365. private QueueNode<E> previous;
    366. private QueueNode<E> next;
    367.  
    368. /**
    369.   * Creates a QueueNode<E> object
    370.   *
    371.   * @param previous The previous QueueNode<E> in the sequence
    372.   * @param value The value of this node
    373.   * @param next The next QueueNode<E> in the sequence
    374.   */
    375. public QueueNode(QueueNode<E> previous, E value, QueueNode<E> next) {
    376. this.previous = previous;
    377. this.next = next;
    378. this.value = value;
    379. }
    380.  
    381. /**
    382.   * Gets the previous QueueNode<E> in the sequence relative to the current.
    383.   *
    384.   * @return The previous QueueNode<E>
    385.   */
    386. public QueueNode<E> getPreviousNode() {
    387. return this.previous;
    388. }
    389.  
    390. /**
    391.   * Gets the next QueueNode<E> in the sequence relative to the current.
    392.   *
    393.   * @return The next QueueNode<E>
    394.   */
    395. public QueueNode<E> getNextNode() {
    396. return this.next;
    397. }
    398.  
    399. /**
    400.   * Gets the value associated with this QueueNode<E>
    401.   *
    402.   * @return The value of the current QueueNode<E>
    403.   */
    404. public E getValue() {
    405. return this.value;
    406. }
    407.  
    408. /**
    409.   * Sets the node that occurs after the current node
    410.   *
    411.   * @param next The node to set
    412.   */
    413. public void setNextNode(QueueNode<E> next) {
    414. this.next = next;
    415. }
    416.  
    417. /**
    418.   * Sets the node that occurs before the current node
    419.   *
    420.   * @param previous The node to set
    421.   */
    422. public void setPreviousNode(QueueNode<E> previous) {
    423. this.previous = previous;
    424. }
    425.  
    426. /**
    427.   * Sets the value associated with the current node
    428.   *
    429.   * @param value The value to set
    430.   */
    431. public void setValue(E value) {
    432. this.value = value;
    433. }
    434. }
    435.  
    436. class Itr<E> implements Iterator {
    437.  
    438. private QueueNode<E> itr;
    439. private boolean first = true;
    440.  
    441. public Itr(QueueNode<E> first) {
    442. this.itr = first;
    443. }
    444.  
    445. /**
    446.   * Returns whether or not it is the end of the collection
    447.   *
    448.   * @return True if not the end, false otherwise
    449.   */
    450. @Override
    451. public boolean hasNext() {
    452. return this.itr.getNextNode() != null;
    453. }
    454.  
    455. /**
    456.   * Gets the next value in the queue iterator
    457.   *
    458.   * @return The next iterator value
    459.   */
    460. @Override
    461. public E next() {
    462. if (this.first) {
    463. this.first = false;
    464. } else if (this.hasNext()) {
    465. this.itr = this.itr.getNextNode();
    466. }
    467. return this.itr.getValue();
    468. }
    469.  
    470. /**
    471.   * Removes an object from the iterator, unsupported
    472.   */
    473. @Override
    474. public void remove() {
    475. throw new UnsupportedOperationException("Cannot remove content from iterator");
    476. }
    477. }


    You can call it very similarly to an ArrayList, and it will allow you to grab the next message endlessly:

    Code:java
    1. LinkedQueue<String> queue = new LinkedQueue();
    2. queue.add("Test one");
    3. queue.add("Test two");
    4. queue.add("Test three");
    5. System.out.println("contents:");
    6. for (String s : queue) {
    7. System.out.print("Test: ");
    8. System.out.println(s);
    9. }
    10. System.out.println("contents (x9):");
    11. for (int i = 0; i < 9; i++) {
    12. System.out.println(queue.getNext());
    13. }


    Would print:
    Code:
    contents:
    Test: Test one
    Test: Test two
    Test: Test three
    contents (x9):
    Test one
    Test two
    Test three
    Test one
    Test two
    Test three
    Test one
    Test two
    Test three
    This essentially turns repeated messages into a one-line system via .getNext(); :)
     
  2. Offline

    turt2live

    I don't think this classifies as a Queue, and your implementation mimics a doubly-ended linked list (just add an if access > tail, return head + offset).

    Neat concept though :)
     
    bobacadodl and DSH105 like this.
  3. Offline

    1Rogue

    DoubleyLinkedList sounds like a lame class though ;)
     
  4. Offline

    sgavster

    Very nice!
     
  5. Offline

    turt2live

    It's called a LinkedList in Java :p

    All this does is provide a wrap around, which is technically not a true LinkedList in that case.
     
    1Rogue likes this.
Thread Status:
Not open for further replies.

Share This Page