1. /*
  2. * @(#)LinkedList.java 1.61 04/02/19
  3. *
  4. * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
  5. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
  6. */
  7. package java.util;
  8. /**
  9. * Linked list implementation of the <tt>List</tt> interface. Implements all
  10. * optional list operations, and permits all elements (including
  11. * <tt>null</tt>). In addition to implementing the <tt>List</tt> interface,
  12. * the <tt>LinkedList</tt> class provides uniformly named methods to
  13. * <tt>get</tt>, <tt>remove</tt> and <tt>insert</tt> an element at the
  14. * beginning and end of the list. These operations allow linked lists to be
  15. * used as a stack, queue, or double-ended queue (deque).<p>
  16. *
  17. * The class implements the <tt>Queue</tt> interface, providing
  18. * first-in-first-out queue operations for <tt>add</tt>,
  19. * <tt>poll</tt>, etc. Other stack and deque operations could be
  20. * easily recast in terms of the standard list operations. They're
  21. * included here primarily for convenience, though they may run
  22. * slightly faster than the equivalent List operations.<p>
  23. *
  24. * All of the operations perform as could be expected for a doubly-linked
  25. * list. Operations that index into the list will traverse the list from
  26. * the beginning or the end, whichever is closer to the specified index.<p>
  27. *
  28. * <b>Note that this implementation is not synchronized.</b> If multiple
  29. * threads access a list concurrently, and at least one of the threads
  30. * modifies the list structurally, it <i>must</i> be synchronized
  31. * externally. (A structural modification is any operation that adds or
  32. * deletes one or more elements; merely setting the value of an element is not
  33. * a structural modification.) This is typically accomplished by
  34. * synchronizing on some object that naturally encapsulates the list. If no
  35. * such object exists, the list should be "wrapped" using the
  36. * Collections.synchronizedList method. This is best done at creation time,
  37. * to prevent accidental unsynchronized access to the list: <pre>
  38. * List list = Collections.synchronizedList(new LinkedList(...));
  39. * </pre><p>
  40. *
  41. * The iterators returned by the this class's <tt>iterator</tt> and
  42. * <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
  43. * structurally modified at any time after the iterator is created, in any way
  44. * except through the Iterator's own <tt>remove</tt> or <tt>add</tt> methods,
  45. * the iterator will throw a <tt>ConcurrentModificationException</tt>. Thus,
  46. * in the face of concurrent modification, the iterator fails quickly and
  47. * cleanly, rather than risking arbitrary, non-deterministic behavior at an
  48. * undetermined time in the future.
  49. *
  50. * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
  51. * as it is, generally speaking, impossible to make any hard guarantees in the
  52. * presence of unsynchronized concurrent modification. Fail-fast iterators
  53. * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
  54. * Therefore, it would be wrong to write a program that depended on this
  55. * exception for its correctness: <i>the fail-fast behavior of iterators
  56. * should be used only to detect bugs.</i><p>
  57. *
  58. * This class is a member of the
  59. * <a href="{@docRoot}/../guide/collections/index.html">
  60. * Java Collections Framework</a>.
  61. *
  62. * @author Josh Bloch
  63. * @version 1.61, 02/19/04
  64. * @see List
  65. * @see ArrayList
  66. * @see Vector
  67. * @see Collections#synchronizedList(List)
  68. * @since 1.2
  69. * @param <E> the type of elements held in this collection
  70. */
  71. public class LinkedList<E>
  72. extends AbstractSequentialList<E>
  73. implements List<E>, Queue<E>, Cloneable, java.io.Serializable
  74. {
  75. private transient Entry<E> header = new Entry<E>(null, null, null);
  76. private transient int size = 0;
  77. /**
  78. * Constructs an empty list.
  79. */
  80. public LinkedList() {
  81. header.next = header.previous = header;
  82. }
  83. /**
  84. * Constructs a list containing the elements of the specified
  85. * collection, in the order they are returned by the collection's
  86. * iterator.
  87. *
  88. * @param c the collection whose elements are to be placed into this list.
  89. * @throws NullPointerException if the specified collection is null.
  90. */
  91. public LinkedList(Collection<? extends E> c) {
  92. this();
  93. addAll(c);
  94. }
  95. /**
  96. * Returns the first element in this list.
  97. *
  98. * @return the first element in this list.
  99. * @throws NoSuchElementException if this list is empty.
  100. */
  101. public E getFirst() {
  102. if (size==0)
  103. throw new NoSuchElementException();
  104. return header.next.element;
  105. }
  106. /**
  107. * Returns the last element in this list.
  108. *
  109. * @return the last element in this list.
  110. * @throws NoSuchElementException if this list is empty.
  111. */
  112. public E getLast() {
  113. if (size==0)
  114. throw new NoSuchElementException();
  115. return header.previous.element;
  116. }
  117. /**
  118. * Removes and returns the first element from this list.
  119. *
  120. * @return the first element from this list.
  121. * @throws NoSuchElementException if this list is empty.
  122. */
  123. public E removeFirst() {
  124. return remove(header.next);
  125. }
  126. /**
  127. * Removes and returns the last element from this list.
  128. *
  129. * @return the last element from this list.
  130. * @throws NoSuchElementException if this list is empty.
  131. */
  132. public E removeLast() {
  133. return remove(header.previous);
  134. }
  135. /**
  136. * Inserts the given element at the beginning of this list.
  137. *
  138. * @param o the element to be inserted at the beginning of this list.
  139. */
  140. public void addFirst(E o) {
  141. addBefore(o, header.next);
  142. }
  143. /**
  144. * Appends the given element to the end of this list. (Identical in
  145. * function to the <tt>add</tt> method; included only for consistency.)
  146. *
  147. * @param o the element to be inserted at the end of this list.
  148. */
  149. public void addLast(E o) {
  150. addBefore(o, header);
  151. }
  152. /**
  153. * Returns <tt>true</tt> if this list contains the specified element.
  154. * More formally, returns <tt>true</tt> if and only if this list contains
  155. * at least one element <tt>e</tt> such that <tt>(o==null ? e==null
  156. * : o.equals(e))</tt>.
  157. *
  158. * @param o element whose presence in this list is to be tested.
  159. * @return <tt>true</tt> if this list contains the specified element.
  160. */
  161. public boolean contains(Object o) {
  162. return indexOf(o) != -1;
  163. }
  164. /**
  165. * Returns the number of elements in this list.
  166. *
  167. * @return the number of elements in this list.
  168. */
  169. public int size() {
  170. return size;
  171. }
  172. /**
  173. * Appends the specified element to the end of this list.
  174. *
  175. * @param o element to be appended to this list.
  176. * @return <tt>true</tt> (as per the general contract of
  177. * <tt>Collection.add</tt>).
  178. */
  179. public boolean add(E o) {
  180. addBefore(o, header);
  181. return true;
  182. }
  183. /**
  184. * Removes the first occurrence of the specified element in this list. If
  185. * the list does not contain the element, it is unchanged. More formally,
  186. * removes the element with the lowest index <tt>i</tt> such that
  187. * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> (if such an
  188. * element exists).
  189. *
  190. * @param o element to be removed from this list, if present.
  191. * @return <tt>true</tt> if the list contained the specified element.
  192. */
  193. public boolean remove(Object o) {
  194. if (o==null) {
  195. for (Entry<E> e = header.next; e != header; e = e.next) {
  196. if (e.element==null) {
  197. remove(e);
  198. return true;
  199. }
  200. }
  201. } else {
  202. for (Entry<E> e = header.next; e != header; e = e.next) {
  203. if (o.equals(e.element)) {
  204. remove(e);
  205. return true;
  206. }
  207. }
  208. }
  209. return false;
  210. }
  211. /**
  212. * Appends all of the elements in the specified collection to the end of
  213. * this list, in the order that they are returned by the specified
  214. * collection's iterator. The behavior of this operation is undefined if
  215. * the specified collection is modified while the operation is in
  216. * progress. (This implies that the behavior of this call is undefined if
  217. * the specified Collection is this list, and this list is nonempty.)
  218. *
  219. * @param c the elements to be inserted into this list.
  220. * @return <tt>true</tt> if this list changed as a result of the call.
  221. * @throws NullPointerException if the specified collection is null.
  222. */
  223. public boolean addAll(Collection<? extends E> c) {
  224. return addAll(size, c);
  225. }
  226. /**
  227. * Inserts all of the elements in the specified collection into this
  228. * list, starting at the specified position. Shifts the element
  229. * currently at that position (if any) and any subsequent elements to
  230. * the right (increases their indices). The new elements will appear
  231. * in the list in the order that they are returned by the
  232. * specified collection's iterator.
  233. *
  234. * @param index index at which to insert first element
  235. * from the specified collection.
  236. * @param c elements to be inserted into this list.
  237. * @return <tt>true</tt> if this list changed as a result of the call.
  238. * @throws IndexOutOfBoundsException if the specified index is out of
  239. * range (<tt>index < 0 || index > size()</tt>).
  240. * @throws NullPointerException if the specified collection is null.
  241. */
  242. public boolean addAll(int index, Collection<? extends E> c) {
  243. if (index < 0 || index > size)
  244. throw new IndexOutOfBoundsException("Index: "+index+
  245. ", Size: "+size);
  246. Object[] a = c.toArray();
  247. int numNew = a.length;
  248. if (numNew==0)
  249. return false;
  250. modCount++;
  251. Entry<E> successor = (index==size ? header : entry(index));
  252. Entry<E> predecessor = successor.previous;
  253. for (int i=0; i<numNew; i++) {
  254. Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
  255. predecessor.next = e;
  256. predecessor = e;
  257. }
  258. successor.previous = predecessor;
  259. size += numNew;
  260. return true;
  261. }
  262. /**
  263. * Removes all of the elements from this list.
  264. */
  265. public void clear() {
  266. Entry<E> e = header.next;
  267. while (e != header) {
  268. Entry<E> next = e.next;
  269. e.next = e.previous = null;
  270. e.element = null;
  271. e = next;
  272. }
  273. header.next = header.previous = header;
  274. size = 0;
  275. modCount++;
  276. }
  277. // Positional Access Operations
  278. /**
  279. * Returns the element at the specified position in this list.
  280. *
  281. * @param index index of element to return.
  282. * @return the element at the specified position in this list.
  283. *
  284. * @throws IndexOutOfBoundsException if the specified index is out of
  285. * range (<tt>index < 0 || index >= size()</tt>).
  286. */
  287. public E get(int index) {
  288. return entry(index).element;
  289. }
  290. /**
  291. * Replaces the element at the specified position in this list with the
  292. * specified element.
  293. *
  294. * @param index index of element to replace.
  295. * @param element element to be stored at the specified position.
  296. * @return the element previously at the specified position.
  297. * @throws IndexOutOfBoundsException if the specified index is out of
  298. * range (<tt>index < 0 || index >= size()</tt>).
  299. */
  300. public E set(int index, E element) {
  301. Entry<E> e = entry(index);
  302. E oldVal = e.element;
  303. e.element = element;
  304. return oldVal;
  305. }
  306. /**
  307. * Inserts the specified element at the specified position in this list.
  308. * Shifts the element currently at that position (if any) and any
  309. * subsequent elements to the right (adds one to their indices).
  310. *
  311. * @param index index at which the specified element is to be inserted.
  312. * @param element element to be inserted.
  313. *
  314. * @throws IndexOutOfBoundsException if the specified index is out of
  315. * range (<tt>index < 0 || index > size()</tt>).
  316. */
  317. public void add(int index, E element) {
  318. addBefore(element, (index==size ? header : entry(index)));
  319. }
  320. /**
  321. * Removes the element at the specified position in this list. Shifts any
  322. * subsequent elements to the left (subtracts one from their indices).
  323. * Returns the element that was removed from the list.
  324. *
  325. * @param index the index of the element to removed.
  326. * @return the element previously at the specified position.
  327. *
  328. * @throws IndexOutOfBoundsException if the specified index is out of
  329. * range (<tt>index < 0 || index >= size()</tt>).
  330. */
  331. public E remove(int index) {
  332. return remove(entry(index));
  333. }
  334. /**
  335. * Return the indexed entry.
  336. */
  337. private Entry<E> entry(int index) {
  338. if (index < 0 || index >= size)
  339. throw new IndexOutOfBoundsException("Index: "+index+
  340. ", Size: "+size);
  341. Entry<E> e = header;
  342. if (index < (size >> 1)) {
  343. for (int i = 0; i <= index; i++)
  344. e = e.next;
  345. } else {
  346. for (int i = size; i > index; i--)
  347. e = e.previous;
  348. }
  349. return e;
  350. }
  351. // Search Operations
  352. /**
  353. * Returns the index in this list of the first occurrence of the
  354. * specified element, or -1 if the List does not contain this
  355. * element. More formally, returns the lowest index i such that
  356. * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
  357. * there is no such index.
  358. *
  359. * @param o element to search for.
  360. * @return the index in this list of the first occurrence of the
  361. * specified element, or -1 if the list does not contain this
  362. * element.
  363. */
  364. public int indexOf(Object o) {
  365. int index = 0;
  366. if (o==null) {
  367. for (Entry e = header.next; e != header; e = e.next) {
  368. if (e.element==null)
  369. return index;
  370. index++;
  371. }
  372. } else {
  373. for (Entry e = header.next; e != header; e = e.next) {
  374. if (o.equals(e.element))
  375. return index;
  376. index++;
  377. }
  378. }
  379. return -1;
  380. }
  381. /**
  382. * Returns the index in this list of the last occurrence of the
  383. * specified element, or -1 if the list does not contain this
  384. * element. More formally, returns the highest index i such that
  385. * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, or -1 if
  386. * there is no such index.
  387. *
  388. * @param o element to search for.
  389. * @return the index in this list of the last occurrence of the
  390. * specified element, or -1 if the list does not contain this
  391. * element.
  392. */
  393. public int lastIndexOf(Object o) {
  394. int index = size;
  395. if (o==null) {
  396. for (Entry e = header.previous; e != header; e = e.previous) {
  397. index--;
  398. if (e.element==null)
  399. return index;
  400. }
  401. } else {
  402. for (Entry e = header.previous; e != header; e = e.previous) {
  403. index--;
  404. if (o.equals(e.element))
  405. return index;
  406. }
  407. }
  408. return -1;
  409. }
  410. // Queue operations.
  411. /**
  412. * Retrieves, but does not remove, the head (first element) of this list.
  413. * @return the head of this queue, or <tt>null</tt> if this queue is empty.
  414. * @since 1.5
  415. */
  416. public E peek() {
  417. if (size==0)
  418. return null;
  419. return getFirst();
  420. }
  421. /**
  422. * Retrieves, but does not remove, the head (first element) of this list.
  423. * @return the head of this queue.
  424. * @throws NoSuchElementException if this queue is empty.
  425. * @since 1.5
  426. */
  427. public E element() {
  428. return getFirst();
  429. }
  430. /**
  431. * Retrieves and removes the head (first element) of this list.
  432. * @return the head of this queue, or <tt>null</tt> if this queue is empty.
  433. * @since 1.5
  434. */
  435. public E poll() {
  436. if (size==0)
  437. return null;
  438. return removeFirst();
  439. }
  440. /**
  441. * Retrieves and removes the head (first element) of this list.
  442. * @return the head of this queue.
  443. * @throws NoSuchElementException if this queue is empty.
  444. * @since 1.5
  445. */
  446. public E remove() {
  447. return removeFirst();
  448. }
  449. /**
  450. * Adds the specified element as the tail (last element) of this list.
  451. *
  452. * @param o the element to add.
  453. * @return <tt>true</tt> (as per the general contract of
  454. * <tt>Queue.offer</tt>)
  455. * @since 1.5
  456. */
  457. public boolean offer(E o) {
  458. return add(o);
  459. }
  460. /**
  461. * Returns a list-iterator of the elements in this list (in proper
  462. * sequence), starting at the specified position in the list.
  463. * Obeys the general contract of <tt>List.listIterator(int)</tt>.<p>
  464. *
  465. * The list-iterator is <i>fail-fast</i>: if the list is structurally
  466. * modified at any time after the Iterator is created, in any way except
  467. * through the list-iterator's own <tt>remove</tt> or <tt>add</tt>
  468. * methods, the list-iterator will throw a
  469. * <tt>ConcurrentModificationException</tt>. Thus, in the face of
  470. * concurrent modification, the iterator fails quickly and cleanly, rather
  471. * than risking arbitrary, non-deterministic behavior at an undetermined
  472. * time in the future.
  473. *
  474. * @param index index of first element to be returned from the
  475. * list-iterator (by a call to <tt>next</tt>).
  476. * @return a ListIterator of the elements in this list (in proper
  477. * sequence), starting at the specified position in the list.
  478. * @throws IndexOutOfBoundsException if index is out of range
  479. * (<tt>index < 0 || index > size()</tt>).
  480. * @see List#listIterator(int)
  481. */
  482. public ListIterator<E> listIterator(int index) {
  483. return new ListItr(index);
  484. }
  485. private class ListItr implements ListIterator<E> {
  486. private Entry<E> lastReturned = header;
  487. private Entry<E> next;
  488. private int nextIndex;
  489. private int expectedModCount = modCount;
  490. ListItr(int index) {
  491. if (index < 0 || index > size)
  492. throw new IndexOutOfBoundsException("Index: "+index+
  493. ", Size: "+size);
  494. if (index < (size >> 1)) {
  495. next = header.next;
  496. for (nextIndex=0; nextIndex<index; nextIndex++)
  497. next = next.next;
  498. } else {
  499. next = header;
  500. for (nextIndex=size; nextIndex>index; nextIndex--)
  501. next = next.previous;
  502. }
  503. }
  504. public boolean hasNext() {
  505. return nextIndex != size;
  506. }
  507. public E next() {
  508. checkForComodification();
  509. if (nextIndex == size)
  510. throw new NoSuchElementException();
  511. lastReturned = next;
  512. next = next.next;
  513. nextIndex++;
  514. return lastReturned.element;
  515. }
  516. public boolean hasPrevious() {
  517. return nextIndex != 0;
  518. }
  519. public E previous() {
  520. if (nextIndex == 0)
  521. throw new NoSuchElementException();
  522. lastReturned = next = next.previous;
  523. nextIndex--;
  524. checkForComodification();
  525. return lastReturned.element;
  526. }
  527. public int nextIndex() {
  528. return nextIndex;
  529. }
  530. public int previousIndex() {
  531. return nextIndex-1;
  532. }
  533. public void remove() {
  534. checkForComodification();
  535. Entry<E> lastNext = lastReturned.next;
  536. try {
  537. LinkedList.this.remove(lastReturned);
  538. } catch (NoSuchElementException e) {
  539. throw new IllegalStateException();
  540. }
  541. if (next==lastReturned)
  542. next = lastNext;
  543. else
  544. nextIndex--;
  545. lastReturned = header;
  546. expectedModCount++;
  547. }
  548. public void set(E o) {
  549. if (lastReturned == header)
  550. throw new IllegalStateException();
  551. checkForComodification();
  552. lastReturned.element = o;
  553. }
  554. public void add(E o) {
  555. checkForComodification();
  556. lastReturned = header;
  557. addBefore(o, next);
  558. nextIndex++;
  559. expectedModCount++;
  560. }
  561. final void checkForComodification() {
  562. if (modCount != expectedModCount)
  563. throw new ConcurrentModificationException();
  564. }
  565. }
  566. private static class Entry<E> {
  567. E element;
  568. Entry<E> next;
  569. Entry<E> previous;
  570. Entry(E element, Entry<E> next, Entry<E> previous) {
  571. this.element = element;
  572. this.next = next;
  573. this.previous = previous;
  574. }
  575. }
  576. private Entry<E> addBefore(E o, Entry<E> e) {
  577. Entry<E> newEntry = new Entry<E>(o, e, e.previous);
  578. newEntry.previous.next = newEntry;
  579. newEntry.next.previous = newEntry;
  580. size++;
  581. modCount++;
  582. return newEntry;
  583. }
  584. private E remove(Entry<E> e) {
  585. if (e == header)
  586. throw new NoSuchElementException();
  587. E result = e.element;
  588. e.previous.next = e.next;
  589. e.next.previous = e.previous;
  590. e.next = e.previous = null;
  591. e.element = null;
  592. size--;
  593. modCount++;
  594. return result;
  595. }
  596. /**
  597. * Returns a shallow copy of this <tt>LinkedList</tt>. (The elements
  598. * themselves are not cloned.)
  599. *
  600. * @return a shallow copy of this <tt>LinkedList</tt> instance.
  601. */
  602. public Object clone() {
  603. LinkedList<E> clone = null;
  604. try {
  605. clone = (LinkedList<E>) super.clone();
  606. } catch (CloneNotSupportedException e) {
  607. throw new InternalError();
  608. }
  609. // Put clone into "virgin" state
  610. clone.header = new Entry<E>(null, null, null);
  611. clone.header.next = clone.header.previous = clone.header;
  612. clone.size = 0;
  613. clone.modCount = 0;
  614. // Initialize clone with our elements
  615. for (Entry<E> e = header.next; e != header; e = e.next)
  616. clone.add(e.element);
  617. return clone;
  618. }
  619. /**
  620. * Returns an array containing all of the elements in this list
  621. * in the correct order.
  622. *
  623. * @return an array containing all of the elements in this list
  624. * in the correct order.
  625. */
  626. public Object[] toArray() {
  627. Object[] result = new Object[size];
  628. int i = 0;
  629. for (Entry<E> e = header.next; e != header; e = e.next)
  630. result[i++] = e.element;
  631. return result;
  632. }
  633. /**
  634. * Returns an array containing all of the elements in this list in
  635. * the correct order; the runtime type of the returned array is that of
  636. * the specified array. If the list fits in the specified array, it
  637. * is returned therein. Otherwise, a new array is allocated with the
  638. * runtime type of the specified array and the size of this list.<p>
  639. *
  640. * If the list fits in the specified array with room to spare
  641. * (i.e., the array has more elements than the list),
  642. * the element in the array immediately following the end of the
  643. * collection is set to null. This is useful in determining the length
  644. * of the list <i>only</i> if the caller knows that the list
  645. * does not contain any null elements.
  646. *
  647. * @param a the array into which the elements of the list are to
  648. * be stored, if it is big enough; otherwise, a new array of the
  649. * same runtime type is allocated for this purpose.
  650. * @return an array containing the elements of the list.
  651. * @throws ArrayStoreException if the runtime type of a is not a
  652. * supertype of the runtime type of every element in this list.
  653. * @throws NullPointerException if the specified array is null.
  654. */
  655. public <T> T[] toArray(T[] a) {
  656. if (a.length < size)
  657. a = (T[])java.lang.reflect.Array.newInstance(
  658. a.getClass().getComponentType(), size);
  659. int i = 0;
  660. Object[] result = a;
  661. for (Entry<E> e = header.next; e != header; e = e.next)
  662. result[i++] = e.element;
  663. if (a.length > size)
  664. a[size] = null;
  665. return a;
  666. }
  667. private static final long serialVersionUID = 876323262645176354L;
  668. /**
  669. * Save the state of this <tt>LinkedList</tt> instance to a stream (that
  670. * is, serialize it).
  671. *
  672. * @serialData The size of the list (the number of elements it
  673. * contains) is emitted (int), followed by all of its
  674. * elements (each an Object) in the proper order.
  675. */
  676. private void writeObject(java.io.ObjectOutputStream s)
  677. throws java.io.IOException {
  678. // Write out any hidden serialization magic
  679. s.defaultWriteObject();
  680. // Write out size
  681. s.writeInt(size);
  682. // Write out all elements in the proper order.
  683. for (Entry e = header.next; e != header; e = e.next)
  684. s.writeObject(e.element);
  685. }
  686. /**
  687. * Reconstitute this <tt>LinkedList</tt> instance from a stream (that is
  688. * deserialize it).
  689. */
  690. private void readObject(java.io.ObjectInputStream s)
  691. throws java.io.IOException, ClassNotFoundException {
  692. // Read in any hidden serialization magic
  693. s.defaultReadObject();
  694. // Read in size
  695. int size = s.readInt();
  696. // Initialize header
  697. header = new Entry<E>(null, null, null);
  698. header.next = header.previous = header;
  699. // Read in all elements in the proper order.
  700. for (int i=0; i<size; i++)
  701. addBefore((E)s.readObject(), header);
  702. }
  703. }