Advertisement
Guest User

LL

a guest
Mar 20th, 2018
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.24 KB | None | 0 0
  1. /*
  2. * Derived from materials:
  3. * Copyright 2014, Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser
  4. *
  5. * Developed for use with the book:
  6. *
  7. * Data Structures and Algorithms in Java, Sixth Edition
  8. * Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser
  9. * John Wiley & Sons, 2014
  10. *
  11. * This program is free software: you can redistribute it and/or modify
  12. * it under the terms of the GNU General Public License as published by
  13. * the Free Software Foundation, either version 3 of the License, or
  14. * (at your option) any later version.
  15. *
  16. * This program is distributed in the hope that it will be useful,
  17. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  19. * GNU General Public License for more details.
  20. *
  21. * You should have received a copy of the GNU General Public License
  22. * along with this program. If not, see <http://www.gnu.org/licenses/>.
  23. */
  24.  
  25. public class LinkedEnhancedPositionalList<E> implements EnhancedPositionalList<E> {
  26.  
  27. /**
  28. * Implementation of a positional list stored as a doubly linked list.
  29. *
  30. * @author Michael T. Goodrich
  31. * @author Roberto Tamassia
  32. * @author Michael H. Goldwasser
  33. */
  34. // ---------------- nested Node class ----------------
  35. /**
  36. * Node of a doubly linked list, which stores a reference to its element and
  37. * to both the previous and next node in the list.
  38. */
  39. private static class Node<E> implements Position<E> {
  40.  
  41. /** The element stored at this node */
  42. private E element; // reference to the element stored at this node
  43.  
  44. /** A reference to the preceding node in the list */
  45. private Node<E> prev; // reference to the previous node in the list
  46.  
  47. /** A reference to the subsequent node in the list */
  48. private Node<E> next; // reference to the subsequent node in the list
  49.  
  50. /**
  51. * Creates a node with the given element and next node.
  52. *
  53. * @param e
  54. * the element to be stored
  55. * @param p
  56. * reference to a node that should precede the new node
  57. * @param n
  58. * reference to a node that should follow the new node
  59. */
  60. public Node(E e, Node<E> p, Node<E> n) {
  61. element = e;
  62. prev = p;
  63. next = n;
  64. }
  65.  
  66. // public accessor methods
  67. /**
  68. * Returns the element stored at the node.
  69. *
  70. * @return the stored element
  71. * @throws IllegalStateException
  72. * if node not currently linked to others
  73. */
  74. public E getElement() throws IllegalStateException {
  75. if (next == null) // convention for defunct node
  76. throw new IllegalStateException("Position no longer valid");
  77. return element;
  78. }
  79.  
  80. /**
  81. * Returns the node that precedes this one (or null if no such node).
  82. *
  83. * @return the preceding node
  84. */
  85. public Node<E> getPrev() {
  86. return prev;
  87. }
  88.  
  89. /**
  90. * Returns the node that follows this one (or null if no such node).
  91. *
  92. * @return the following node
  93. */
  94. public Node<E> getNext() {
  95. return next;
  96. }
  97.  
  98. // Update methods
  99. /**
  100. * Sets the node's element to the given element e.
  101. *
  102. * @param e
  103. * the node's new element
  104. */
  105. public void setElement(E e) {
  106. element = e;
  107. }
  108.  
  109. /**
  110. * Sets the node's previous reference to point to Node n.
  111. *
  112. * @param p
  113. * the node that should precede this one
  114. */
  115. public void setPrev(Node<E> p) {
  116. prev = p;
  117. }
  118.  
  119. /**
  120. * Sets the node's next reference to point to Node n.
  121. *
  122. * @param n
  123. * the node that should follow this one
  124. */
  125. public void setNext(Node<E> n) {
  126. next = n;
  127. }
  128. } // ----------- end of nested Node class -----------
  129.  
  130. // instance variables of the LinkedPositionalList
  131. /** Sentinel node at the beginning of the list */
  132. private Node<E> header; // header sentinel
  133.  
  134. /** Sentinel node at the end of the list */
  135. private Node<E> trailer; // trailer sentinel
  136.  
  137. /** Number of elements in the list (not including sentinels) */
  138. private int size = 0; // number of elements in the list
  139.  
  140. /** Constructs a new empty list. */
  141. public LinkedEnhancedPositionalList() {
  142. header = new Node<>(null, null, null); // create header
  143. trailer = new Node<>(null, header, null); // trailer is preceded by header
  144. header.setNext(trailer); // header is followed by trailer
  145. }
  146.  
  147. // private utilities
  148. /**
  149. * Verifies that a Position belongs to the appropriate class, and is not one
  150. * that has been previously removed. Note that our current implementation
  151. * does not actually verify that the position belongs to this particular
  152. * list instance.
  153. *
  154. * @param p
  155. * a Position (that should belong to this list)
  156. * @return the underlying Node instance at that position
  157. * @throws IllegalArgumentException
  158. * if an invalid position is detected
  159. */
  160. private Node<E> validate(Position<E> p) throws IllegalArgumentException {
  161. if (!(p instanceof Node))
  162. throw new IllegalArgumentException("Invalid p");
  163. Node<E> node = (Node<E>) p; // safe cast
  164. if (node.getNext() == null) // convention for defunct node
  165. throw new IllegalArgumentException("p is no longer in the list");
  166. return node;
  167. }
  168.  
  169. /**
  170. * Returns the given node as a Position, unless it is a sentinel, in which
  171. * case null is returned (so as not to expose the sentinels to the user).
  172. */
  173. private Position<E> position(Node<E> node) {
  174. if (node == header || node == trailer)
  175. return null; // do not expose user to the sentinels
  176. return node;
  177. }
  178.  
  179. // public accessor methods
  180. /**
  181. * Returns the number of elements in the list.
  182. *
  183. * @return number of elements in the list
  184. */
  185. @Override
  186. public int size() {
  187. return size;
  188. }
  189.  
  190. /**
  191. * Tests whether the list is empty.
  192. *
  193. * @return true if the list is empty, false otherwise
  194. */
  195. @Override
  196. public boolean isEmpty() {
  197. return size == 0;
  198. }
  199.  
  200. /**
  201. * Returns the first Position in the list.
  202. *
  203. * @return the first Position in the list (or null, if empty)
  204. */
  205. @Override
  206. public Position<E> first() {
  207. return position(header.getNext());
  208. }
  209.  
  210. /**
  211. * Returns the last Position in the list.
  212. *
  213. * @return the last Position in the list (or null, if empty)
  214. */
  215. @Override
  216. public Position<E> last() {
  217. return position(trailer.getPrev());
  218. }
  219.  
  220. /**
  221. * Returns the Position immediately before Position p.
  222. *
  223. * @param p
  224. * a Position of the list
  225. * @return the Position of the preceding element (or null, if p is first)
  226. * @throws IllegalArgumentException
  227. * if p is not a valid position for this list
  228. */
  229. @Override
  230. public Position<E> before(Position<E> p) throws IllegalArgumentException {
  231. Node<E> node = validate(p);
  232. return position(node.getPrev());
  233. }
  234.  
  235. /**
  236. * Returns the Position immediately after Position p.
  237. *
  238. * @param p
  239. * a Position of the list
  240. * @return the Position of the following element (or null, if p is last)
  241. * @throws IllegalArgumentException
  242. * if p is not a valid position for this list
  243. */
  244. @Override
  245. public Position<E> after(Position<E> p) throws IllegalArgumentException {
  246. Node<E> node = validate(p);
  247. return position(node.getNext());
  248. }
  249.  
  250. // private utilities
  251. /**
  252. * Adds an element to the linked list between the given nodes. The given
  253. * predecessor and successor should be neighboring each other prior to the
  254. * call.
  255. *
  256. * @param pred
  257. * node just before the location where the new element is
  258. * inserted
  259. * @param succ
  260. * node just after the location where the new element is inserted
  261. * @return the new element's node
  262. */
  263. private Position<E> addBetween(E e, Node<E> pred, Node<E> succ) {
  264. Node<E> newest = new Node<>(e, pred, succ); // create and link a new
  265. // node
  266. pred.setNext(newest);
  267. succ.setPrev(newest);
  268. size++;
  269. return newest;
  270. }
  271.  
  272. // public update methods
  273. /**
  274. * Inserts an element at the front of the list.
  275. *
  276. * @param e
  277. * the new element
  278. * @return the Position representing the location of the new element
  279. */
  280. @Override
  281. public Position<E> addFirst(E e) {
  282. return addBetween(e, header, header.getNext()); // just after the header
  283. }
  284.  
  285. /**
  286. * Inserts an element at the back of the list.
  287. *
  288. * @param e
  289. * the new element
  290. * @return the Position representing the location of the new element
  291. */
  292. @Override
  293. public Position<E> addLast(E e) {
  294. return addBetween(e, trailer.getPrev(), trailer); // just before the
  295. // trailer
  296. }
  297.  
  298. /**
  299. * Inserts an element immediately before the given Position.
  300. *
  301. * @param p
  302. * the Position before which the insertion takes place
  303. * @param e
  304. * the new element
  305. * @return the Position representing the location of the new element
  306. * @throws IllegalArgumentException
  307. * if p is not a valid position for this list
  308. */
  309. @Override
  310. public Position<E> addBefore(Position<E> p, E e) throws IllegalArgumentException {
  311. Node<E> node = validate(p);
  312. return addBetween(e, node.getPrev(), node);
  313. }
  314.  
  315. /**
  316. * Inserts an element immediately after the given Position.
  317. *
  318. * @param p
  319. * the Position after which the insertion takes place
  320. * @param e
  321. * the new element
  322. * @return the Position representing the location of the new element
  323. * @throws IllegalArgumentException
  324. * if p is not a valid position for this list
  325. */
  326. @Override
  327. public Position<E> addAfter(Position<E> p, E e) throws IllegalArgumentException {
  328. Node<E> node = validate(p);
  329. return addBetween(e, node, node.getNext());
  330. }
  331.  
  332. /**
  333. * Replaces the element stored at the given Position and returns the
  334. * replaced element.
  335. *
  336. * @param p
  337. * the Position of the element to be replaced
  338. * @param e
  339. * the new element
  340. * @return the replaced element
  341. * @throws IllegalArgumentException
  342. * if p is not a valid position for this list
  343. */
  344. @Override
  345. public E set(Position<E> p, E e) throws IllegalArgumentException {
  346. Node<E> node = validate(p);
  347. E answer = node.getElement();
  348. node.setElement(e);
  349. return answer;
  350. }
  351.  
  352. /**
  353. * Removes the element stored at the given Position and returns it. The
  354. * given position is invalidated as a result.
  355. *
  356. * @param p
  357. * the Position of the element to be removed
  358. * @return the removed element
  359. * @throws IllegalArgumentException
  360. * if p is not a valid position for this list
  361. */
  362. @Override
  363. public E remove(Position<E> p) throws IllegalArgumentException {
  364. Node<E> node = validate(p);
  365. Node<E> predecessor = node.getPrev();
  366. Node<E> successor = node.getNext();
  367. predecessor.setNext(successor);
  368. successor.setPrev(predecessor);
  369. size--;
  370. E answer = node.getElement();
  371. node.setElement(null); // help with garbage collection
  372. node.setNext(null); // and convention for defunct node
  373. node.setPrev(null);
  374. return answer;
  375. }
  376.  
  377. // ---------------- INFO1105 code starts here ------------------
  378. // You should not need to modify any code above this point!
  379. // -------------------------------------------------------------
  380.  
  381. @Override
  382. public Position<E> addBefore(Position<E> p, PositionalList<E> sublist) throws IllegalArgumentException {
  383.  
  384. if (this.size() != 0) {
  385. Position<E> temp = sublist.first();
  386. for (int i = 0; i < sublist.size(); i++) {
  387.  
  388. this.addBefore(p, temp.getElement());
  389.  
  390. temp = after(temp);
  391.  
  392.  
  393. }
  394.  
  395.  
  396. }
  397.  
  398. return sublist.first();
  399.  
  400. }
  401.  
  402. @Override
  403. public Position<E> addAfter(Position<E> p, PositionalList<E> sublist) throws IllegalArgumentException {
  404. if (this.size() != 0) {
  405. Position<E> temp = sublist.first();
  406. for (int i = 0; i < sublist.size(); i++) {
  407. this.addAfter(p, temp.getElement());
  408.  
  409. p = after(p);
  410. temp = after(temp);
  411.  
  412. }
  413.  
  414.  
  415. }
  416.  
  417. return sublist.first();
  418. }
  419.  
  420. @Override
  421. public Position<E> addFirst(PositionalList<E> sublist) {
  422. if (this.size() != 0) {
  423. Position<E> temp = sublist.last();
  424. for (int i = 0; i < sublist.size(); i++) {
  425. this.addBefore(this.first(), temp.getElement());
  426. temp = this.before(temp);
  427. }
  428.  
  429. return this.first();
  430. }
  431.  
  432. Position<E> tempTwo = sublist.first();
  433.  
  434. for (int i = 0; i < sublist.size(); i++) {
  435. this.addLast(tempTwo.getElement());
  436. tempTwo = this.after(tempTwo);
  437. }
  438.  
  439. return this.first();
  440. }
  441.  
  442. @Override
  443. public Position<E> addLast(PositionalList<E> sublist) {
  444. if (this.size() != 0) {
  445. Position<E> temp = sublist.first();
  446. for (int i = 0; i < sublist.size(); i++) {
  447. this.addAfter(this.last(), temp.getElement());
  448. temp = this.after(temp);
  449. }
  450.  
  451. return this.first();
  452. }
  453.  
  454. Position<E> tempTwo = sublist.first();
  455. for (int i = 0; i < sublist.size(); i++) {
  456. this.addLast(tempTwo.getElement());
  457. tempTwo = this.after(tempTwo);
  458. }
  459.  
  460. return this.first();
  461. //works
  462. }
  463.  
  464. @Override
  465. public Position<E> search(E e) {
  466. Node a = header.getNext();
  467.  
  468. while (a!=trailer) {
  469. if (a.getElement().equals(e)) {
  470. return position(a);
  471. }
  472. a=a.getNext();
  473. }
  474.  
  475.  
  476. return null;
  477. }
  478.  
  479. @Override
  480. public int distance(Position<E> a, Position<E> b) throws IllegalArgumentException {
  481. return 0;
  482. }
  483. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement