| 1 | /* |
| 2 | * Copyright (C) 2010 The Android Open Source Project |
| 3 | * Copyright (C) 2012 Google Inc. |
| 4 | * |
| 5 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 6 | * you may not use this file except in compliance with the License. |
| 7 | * You may obtain a copy of the License at |
| 8 | * |
| 9 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 10 | * |
| 11 | * Unless required by applicable law or agreed to in writing, software |
| 12 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 13 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 14 | * See the License for the specific language governing permissions and |
| 15 | * limitations under the License. |
| 16 | */ |
| 17 | |
| 18 | package com.google.gson.internal; |
| 19 | |
| 20 | import java.io.ObjectStreamException; |
| 21 | import java.io.Serializable; |
| 22 | import java.util.AbstractMap; |
| 23 | import java.util.AbstractSet; |
| 24 | import java.util.Comparator; |
| 25 | import java.util.ConcurrentModificationException; |
| 26 | import java.util.Iterator; |
| 27 | import java.util.LinkedHashMap; |
| 28 | import java.util.NoSuchElementException; |
| 29 | import java.util.Set; |
| 30 | |
| 31 | /** |
| 32 | * A map of comparable keys to values. Unlike {@code TreeMap}, this class uses |
| 33 | * insertion order for iteration order. Comparison order is only used as an |
| 34 | * optimization for efficient insertion and removal. |
| 35 | * |
| 36 | * <p>This implementation was derived from Android 4.1's TreeMap class. |
| 37 | */ |
| 38 | public final class LinkedTreeMap<K, V> extends AbstractMap<K, V> implements Serializable { |
| 39 | @SuppressWarnings({ "unchecked", "rawtypes" }) // to avoid Comparable<Comparable<Comparable<...>>> |
| 40 | private static final Comparator<Comparable> NATURAL_ORDER = new Comparator<Comparable>() { |
| 41 | public int compare(Comparable a, Comparable b) { |
| 42 | return a.compareTo(b); |
| 43 | } |
| 44 | }; |
| 45 | |
| 46 | Comparator<? super K> comparator; |
| 47 | Node<K, V> root; |
| 48 | int size = 0; |
| 49 | int modCount = 0; |
| 50 | |
| 51 | // Used to preserve iteration order |
| 52 | final Node<K, V> header = new Node<K, V>(); |
| 53 | |
| 54 | /** |
| 55 | * Create a natural order, empty tree map whose keys must be mutually |
| 56 | * comparable and non-null. |
| 57 | */ |
| 58 | @SuppressWarnings("unchecked") // unsafe! this assumes K is comparable |
| 59 | public LinkedTreeMap() { |
| 60 | this((Comparator<? super K>) NATURAL_ORDER); |
| 61 | } |
| 62 | |
| 63 | /** |
| 64 | * Create a tree map ordered by {@code comparator}. This map's keys may only |
| 65 | * be null if {@code comparator} permits. |
| 66 | * |
| 67 | * @param comparator the comparator to order elements with, or {@code null} to |
| 68 | * use the natural ordering. |
| 69 | */ |
| 70 | @SuppressWarnings({ "unchecked", "rawtypes" }) // unsafe! if comparator is null, this assumes K is comparable |
| 71 | public LinkedTreeMap(Comparator<? super K> comparator) { |
| 72 | this.comparator = comparator != null |
| 73 | ? comparator |
| 74 | : (Comparator) NATURAL_ORDER; |
| 75 | } |
| 76 | |
| 77 | @Override public int size() { |
| 78 | return size; |
| 79 | } |
| 80 | |
| 81 | @Override public V get(Object key) { |
| 82 | Node<K, V> node = findByObject(key); |
| 83 | return node != null ? node.value : null; |
| 84 | } |
| 85 | |
| 86 | @Override public boolean containsKey(Object key) { |
| 87 | return findByObject(key) != null; |
| 88 | } |
| 89 | |
| 90 | @Override public V put(K key, V value) { |
| 91 | if (key == null) { |
| 92 | throw new NullPointerException("key == null"); |
| 93 | } |
| 94 | Node<K, V> created = find(key, true); |
| 95 | V result = created.value; |
| 96 | created.value = value; |
| 97 | return result; |
| 98 | } |
| 99 | |
| 100 | @Override public void clear() { |
| 101 | root = null; |
| 102 | size = 0; |
| 103 | modCount++; |
| 104 | |
| 105 | // Clear iteration order |
| 106 | Node<K, V> header = this.header; |
| 107 | header.next = header.prev = header; |
| 108 | } |
| 109 | |
| 110 | @Override public V remove(Object key) { |
| 111 | Node<K, V> node = removeInternalByKey(key); |
| 112 | return node != null ? node.value : null; |
| 113 | } |
| 114 | |
| 115 | /** |
| 116 | * Returns the node at or adjacent to the given key, creating it if requested. |
| 117 | * |
| 118 | * @throws ClassCastException if {@code key} and the tree's keys aren't |
| 119 | * mutually comparable. |
| 120 | */ |
| 121 | Node<K, V> find(K key, boolean create) { |
| 122 | Comparator<? super K> comparator = this.comparator; |
| 123 | Node<K, V> nearest = root; |
| 124 | int comparison = 0; |
| 125 | |
| 126 | if (nearest != null) { |
| 127 | // Micro-optimization: avoid polymorphic calls to Comparator.compare(). |
| 128 | @SuppressWarnings("unchecked") // Throws a ClassCastException below if there's trouble. |
| 129 | Comparable<Object> comparableKey = (comparator == NATURAL_ORDER) |
| 130 | ? (Comparable<Object>) key |
| 131 | : null; |
| 132 | |
| 133 | while (true) { |
| 134 | comparison = (comparableKey != null) |
| 135 | ? comparableKey.compareTo(nearest.key) |
| 136 | : comparator.compare(key, nearest.key); |
| 137 | |
| 138 | // We found the requested key. |
| 139 | if (comparison == 0) { |
| 140 | return nearest; |
| 141 | } |
| 142 | |
| 143 | // If it exists, the key is in a subtree. Go deeper. |
| 144 | Node<K, V> child = (comparison < 0) ? nearest.left : nearest.right; |
| 145 | if (child == null) { |
| 146 | break; |
| 147 | } |
| 148 | |
| 149 | nearest = child; |
| 150 | } |
| 151 | } |
| 152 | |
| 153 | // The key doesn't exist in this tree. |
| 154 | if (!create) { |
| 155 | return null; |
| 156 | } |
| 157 | |
| 158 | // Create the node and add it to the tree or the table. |
| 159 | Node<K, V> header = this.header; |
| 160 | Node<K, V> created; |
| 161 | if (nearest == null) { |
| 162 | // Check that the value is comparable if we didn't do any comparisons. |
| 163 | if (comparator == NATURAL_ORDER && !(key instanceof Comparable)) { |
| 164 | throw new ClassCastException(key.getClass().getName() + " is not Comparable"); |
| 165 | } |
| 166 | created = new Node<K, V>(nearest, key, header, header.prev); |
| 167 | root = created; |
| 168 | } else { |
| 169 | created = new Node<K, V>(nearest, key, header, header.prev); |
| 170 | if (comparison < 0) { // nearest.key is higher |
| 171 | nearest.left = created; |
| 172 | } else { // comparison > 0, nearest.key is lower |
| 173 | nearest.right = created; |
| 174 | } |
| 175 | rebalance(nearest, true); |
| 176 | } |
| 177 | size++; |
| 178 | modCount++; |
| 179 | |
| 180 | return created; |
| 181 | } |
| 182 | |
| 183 | @SuppressWarnings("unchecked") |
| 184 | Node<K, V> findByObject(Object key) { |
| 185 | try { |
| 186 | return key != null ? find((K) key, false) : null; |
| 187 | } catch (ClassCastException e) { |
| 188 | return null; |
| 189 | } |
| 190 | } |
| 191 | |
| 192 | /** |
| 193 | * Returns this map's entry that has the same key and value as {@code |
| 194 | * entry}, or null if this map has no such entry. |
| 195 | * |
| 196 | * <p>This method uses the comparator for key equality rather than {@code |
| 197 | * equals}. If this map's comparator isn't consistent with equals (such as |
| 198 | * {@code String.CASE_INSENSITIVE_ORDER}), then {@code remove()} and {@code |
| 199 | * contains()} will violate the collections API. |
| 200 | */ |
| 201 | Node<K, V> findByEntry(Entry<?, ?> entry) { |
| 202 | Node<K, V> mine = findByObject(entry.getKey()); |
| 203 | boolean valuesEqual = mine != null && equal(mine.value, entry.getValue()); |
| 204 | return valuesEqual ? mine : null; |
| 205 | } |
| 206 | |
| 207 | private boolean equal(Object a, Object b) { |
| 208 | return a == b || (a != null && a.equals(b)); |
| 209 | } |
| 210 | |
| 211 | /** |
| 212 | * Removes {@code node} from this tree, rearranging the tree's structure as |
| 213 | * necessary. |
| 214 | * |
| 215 | * @param unlink true to also unlink this node from the iteration linked list. |
| 216 | */ |
| 217 | void removeInternal(Node<K, V> node, boolean unlink) { |
| 218 | if (unlink) { |
| 219 | node.prev.next = node.next; |
| 220 | node.next.prev = node.prev; |
| 221 | } |
| 222 | |
| 223 | Node<K, V> left = node.left; |
| 224 | Node<K, V> right = node.right; |
| 225 | Node<K, V> originalParent = node.parent; |
| 226 | if (left != null && right != null) { |
| 227 | |
| 228 | /* |
| 229 | * To remove a node with both left and right subtrees, move an |
| 230 | * adjacent node from one of those subtrees into this node's place. |
| 231 | * |
| 232 | * Removing the adjacent node may change this node's subtrees. This |
| 233 | * node may no longer have two subtrees once the adjacent node is |
| 234 | * gone! |
| 235 | */ |
| 236 | |
| 237 | Node<K, V> adjacent = (left.height > right.height) ? left.last() : right.first(); |
| 238 | removeInternal(adjacent, false); // takes care of rebalance and size-- |
| 239 | |
| 240 | int leftHeight = 0; |
| 241 | left = node.left; |
| 242 | if (left != null) { |
| 243 | leftHeight = left.height; |
| 244 | adjacent.left = left; |
| 245 | left.parent = adjacent; |
| 246 | node.left = null; |
| 247 | } |
| 248 | |
| 249 | int rightHeight = 0; |
| 250 | right = node.right; |
| 251 | if (right != null) { |
| 252 | rightHeight = right.height; |
| 253 | adjacent.right = right; |
| 254 | right.parent = adjacent; |
| 255 | node.right = null; |
| 256 | } |
| 257 | |
| 258 | adjacent.height = Math.max(leftHeight, rightHeight) + 1; |
| 259 | replaceInParent(node, adjacent); |
| 260 | return; |
| 261 | } else if (left != null) { |
| 262 | replaceInParent(node, left); |
| 263 | node.left = null; |
| 264 | } else if (right != null) { |
| 265 | replaceInParent(node, right); |
| 266 | node.right = null; |
| 267 | } else { |
| 268 | replaceInParent(node, null); |
| 269 | } |
| 270 | |
| 271 | rebalance(originalParent, false); |
| 272 | size--; |
| 273 | modCount++; |
| 274 | } |
| 275 | |
| 276 | Node<K, V> removeInternalByKey(Object key) { |
| 277 | Node<K, V> node = findByObject(key); |
| 278 | if (node != null) { |
| 279 | removeInternal(node, true); |
| 280 | } |
| 281 | return node; |
| 282 | } |
| 283 | |
| 284 | private void replaceInParent(Node<K, V> node, Node<K, V> replacement) { |
| 285 | Node<K, V> parent = node.parent; |
| 286 | node.parent = null; |
| 287 | if (replacement != null) { |
| 288 | replacement.parent = parent; |
| 289 | } |
| 290 | |
| 291 | if (parent != null) { |
| 292 | if (parent.left == node) { |
| 293 | parent.left = replacement; |
| 294 | } else { |
| 295 | assert (parent.right == node); |
| 296 | parent.right = replacement; |
| 297 | } |
| 298 | } else { |
| 299 | root = replacement; |
| 300 | } |
| 301 | } |
| 302 | |
| 303 | /** |
| 304 | * Rebalances the tree by making any AVL rotations necessary between the |
| 305 | * newly-unbalanced node and the tree's root. |
| 306 | * |
| 307 | * @param insert true if the node was unbalanced by an insert; false if it |
| 308 | * was by a removal. |
| 309 | */ |
| 310 | private void rebalance(Node<K, V> unbalanced, boolean insert) { |
| 311 | for (Node<K, V> node = unbalanced; node != null; node = node.parent) { |
| 312 | Node<K, V> left = node.left; |
| 313 | Node<K, V> right = node.right; |
| 314 | int leftHeight = left != null ? left.height : 0; |
| 315 | int rightHeight = right != null ? right.height : 0; |
| 316 | |
| 317 | int delta = leftHeight - rightHeight; |
| 318 | if (delta == -2) { |
| 319 | Node<K, V> rightLeft = right.left; |
| 320 | Node<K, V> rightRight = right.right; |
| 321 | int rightRightHeight = rightRight != null ? rightRight.height : 0; |
| 322 | int rightLeftHeight = rightLeft != null ? rightLeft.height : 0; |
| 323 | |
| 324 | int rightDelta = rightLeftHeight - rightRightHeight; |
| 325 | if (rightDelta == -1 || (rightDelta == 0 && !insert)) { |
| 326 | rotateLeft(node); // AVL right right |
| 327 | } else { |
| 328 | assert (rightDelta == 1); |
| 329 | rotateRight(right); // AVL right left |
| 330 | rotateLeft(node); |
| 331 | } |
| 332 | if (insert) { |
| 333 | break; // no further rotations will be necessary |
| 334 | } |
| 335 | |
| 336 | } else if (delta == 2) { |
| 337 | Node<K, V> leftLeft = left.left; |
| 338 | Node<K, V> leftRight = left.right; |
| 339 | int leftRightHeight = leftRight != null ? leftRight.height : 0; |
| 340 | int leftLeftHeight = leftLeft != null ? leftLeft.height : 0; |
| 341 | |
| 342 | int leftDelta = leftLeftHeight - leftRightHeight; |
| 343 | if (leftDelta == 1 || (leftDelta == 0 && !insert)) { |
| 344 | rotateRight(node); // AVL left left |
| 345 | } else { |
| 346 | assert (leftDelta == -1); |
| 347 | rotateLeft(left); // AVL left right |
| 348 | rotateRight(node); |
| 349 | } |
| 350 | if (insert) { |
| 351 | break; // no further rotations will be necessary |
| 352 | } |
| 353 | |
| 354 | } else if (delta == 0) { |
| 355 | node.height = leftHeight + 1; // leftHeight == rightHeight |
| 356 | if (insert) { |
| 357 | break; // the insert caused balance, so rebalancing is done! |
| 358 | } |
| 359 | |
| 360 | } else { |
| 361 | assert (delta == -1 || delta == 1); |
| 362 | node.height = Math.max(leftHeight, rightHeight) + 1; |
| 363 | if (!insert) { |
| 364 | break; // the height hasn't changed, so rebalancing is done! |
| 365 | } |
| 366 | } |
| 367 | } |
| 368 | } |
| 369 | |
| 370 | /** |
| 371 | * Rotates the subtree so that its root's right child is the new root. |
| 372 | */ |
| 373 | private void rotateLeft(Node<K, V> root) { |
| 374 | Node<K, V> left = root.left; |
| 375 | Node<K, V> pivot = root.right; |
| 376 | Node<K, V> pivotLeft = pivot.left; |
| 377 | Node<K, V> pivotRight = pivot.right; |
| 378 | |
| 379 | // move the pivot's left child to the root's right |
| 380 | root.right = pivotLeft; |
| 381 | if (pivotLeft != null) { |
| 382 | pivotLeft.parent = root; |
| 383 | } |
| 384 | |
| 385 | replaceInParent(root, pivot); |
| 386 | |
| 387 | // move the root to the pivot's left |
| 388 | pivot.left = root; |
| 389 | root.parent = pivot; |
| 390 | |
| 391 | // fix heights |
| 392 | root.height = Math.max(left != null ? left.height : 0, |
| 393 | pivotLeft != null ? pivotLeft.height : 0) + 1; |
| 394 | pivot.height = Math.max(root.height, |
| 395 | pivotRight != null ? pivotRight.height : 0) + 1; |
| 396 | } |
| 397 | |
| 398 | /** |
| 399 | * Rotates the subtree so that its root's left child is the new root. |
| 400 | */ |
| 401 | private void rotateRight(Node<K, V> root) { |
| 402 | Node<K, V> pivot = root.left; |
| 403 | Node<K, V> right = root.right; |
| 404 | Node<K, V> pivotLeft = pivot.left; |
| 405 | Node<K, V> pivotRight = pivot.right; |
| 406 | |
| 407 | // move the pivot's right child to the root's left |
| 408 | root.left = pivotRight; |
| 409 | if (pivotRight != null) { |
| 410 | pivotRight.parent = root; |
| 411 | } |
| 412 | |
| 413 | replaceInParent(root, pivot); |
| 414 | |
| 415 | // move the root to the pivot's right |
| 416 | pivot.right = root; |
| 417 | root.parent = pivot; |
| 418 | |
| 419 | // fixup heights |
| 420 | root.height = Math.max(right != null ? right.height : 0, |
| 421 | pivotRight != null ? pivotRight.height : 0) + 1; |
| 422 | pivot.height = Math.max(root.height, |
| 423 | pivotLeft != null ? pivotLeft.height : 0) + 1; |
| 424 | } |
| 425 | |
| 426 | private EntrySet entrySet; |
| 427 | private KeySet keySet; |
| 428 | |
| 429 | @Override public Set<Entry<K, V>> entrySet() { |
| 430 | EntrySet result = entrySet; |
| 431 | return result != null ? result : (entrySet = new EntrySet()); |
| 432 | } |
| 433 | |
| 434 | @Override public Set<K> keySet() { |
| 435 | KeySet result = keySet; |
| 436 | return result != null ? result : (keySet = new KeySet()); |
| 437 | } |
| 438 | |
| 439 | static final class Node<K, V> implements Entry<K, V> { |
| 440 | Node<K, V> parent; |
| 441 | Node<K, V> left; |
| 442 | Node<K, V> right; |
| 443 | Node<K, V> next; |
| 444 | Node<K, V> prev; |
| 445 | final K key; |
| 446 | V value; |
| 447 | int height; |
| 448 | |
| 449 | /** Create the header entry */ |
| 450 | Node() { |
| 451 | key = null; |
| 452 | next = prev = this; |
| 453 | } |
| 454 | |
| 455 | /** Create a regular entry */ |
| 456 | Node(Node<K, V> parent, K key, Node<K, V> next, Node<K, V> prev) { |
| 457 | this.parent = parent; |
| 458 | this.key = key; |
| 459 | this.height = 1; |
| 460 | this.next = next; |
| 461 | this.prev = prev; |
| 462 | prev.next = this; |
| 463 | next.prev = this; |
| 464 | } |
| 465 | |
| 466 | public K getKey() { |
| 467 | return key; |
| 468 | } |
| 469 | |
| 470 | public V getValue() { |
| 471 | return value; |
| 472 | } |
| 473 | |
| 474 | public V setValue(V value) { |
| 475 | V oldValue = this.value; |
| 476 | this.value = value; |
| 477 | return oldValue; |
| 478 | } |
| 479 | |
| 480 | @SuppressWarnings("rawtypes") |
| 481 | @Override public boolean equals(Object o) { |
| 482 | if (o instanceof Entry) { |
| 483 | Entry other = (Entry) o; |
| 484 | return (key == null ? other.getKey() == null : key.equals(other.getKey())) |
| 485 | && (value == null ? other.getValue() == null : value.equals(other.getValue())); |
| 486 | } |
| 487 | return false; |
| 488 | } |
| 489 | |
| 490 | @Override public int hashCode() { |
| 491 | return (key == null ? 0 : key.hashCode()) |
| 492 | ^ (value == null ? 0 : value.hashCode()); |
| 493 | } |
| 494 | |
| 495 | @Override public String toString() { |
| 496 | return key + "=" + value; |
| 497 | } |
| 498 | |
| 499 | /** |
| 500 | * Returns the first node in this subtree. |
| 501 | */ |
| 502 | public Node<K, V> first() { |
| 503 | Node<K, V> node = this; |
| 504 | Node<K, V> child = node.left; |
| 505 | while (child != null) { |
| 506 | node = child; |
| 507 | child = node.left; |
| 508 | } |
| 509 | return node; |
| 510 | } |
| 511 | |
| 512 | /** |
| 513 | * Returns the last node in this subtree. |
| 514 | */ |
| 515 | public Node<K, V> last() { |
| 516 | Node<K, V> node = this; |
| 517 | Node<K, V> child = node.right; |
| 518 | while (child != null) { |
| 519 | node = child; |
| 520 | child = node.right; |
| 521 | } |
| 522 | return node; |
| 523 | } |
| 524 | } |
| 525 | |
| 526 | private abstract class LinkedTreeMapIterator<T> implements Iterator<T> { |
| 527 | Node<K, V> next = header.next; |
| 528 | Node<K, V> lastReturned = null; |
| 529 | int expectedModCount = modCount; |
| 530 | |
| 531 | public final boolean hasNext() { |
| 532 | return next != header; |
| 533 | } |
| 534 | |
| 535 | final Node<K, V> nextNode() { |
| 536 | Node<K, V> e = next; |
| 537 | if (e == header) { |
| 538 | throw new NoSuchElementException(); |
| 539 | } |
| 540 | if (modCount != expectedModCount) { |
| 541 | throw new ConcurrentModificationException(); |
| 542 | } |
| 543 | next = e.next; |
| 544 | return lastReturned = e; |
| 545 | } |
| 546 | |
| 547 | public final void remove() { |
| 548 | if (lastReturned == null) { |
| 549 | throw new IllegalStateException(); |
| 550 | } |
| 551 | removeInternal(lastReturned, true); |
| 552 | lastReturned = null; |
| 553 | expectedModCount = modCount; |
| 554 | } |
| 555 | } |
| 556 | |
| 557 | class EntrySet extends AbstractSet<Entry<K, V>> { |
| 558 | @Override public int size() { |
| 559 | return size; |
| 560 | } |
| 561 | |
| 562 | @Override public Iterator<Entry<K, V>> iterator() { |
| 563 | return new LinkedTreeMapIterator<Entry<K, V>>() { |
| 564 | public Entry<K, V> next() { |
| 565 | return nextNode(); |
| 566 | } |
| 567 | }; |
| 568 | } |
| 569 | |
| 570 | @Override public boolean contains(Object o) { |
| 571 | return o instanceof Entry && findByEntry((Entry<?, ?>) o) != null; |
| 572 | } |
| 573 | |
| 574 | @Override public boolean remove(Object o) { |
| 575 | if (!(o instanceof Entry)) { |
| 576 | return false; |
| 577 | } |
| 578 | |
| 579 | Node<K, V> node = findByEntry((Entry<?, ?>) o); |
| 580 | if (node == null) { |
| 581 | return false; |
| 582 | } |
| 583 | removeInternal(node, true); |
| 584 | return true; |
| 585 | } |
| 586 | |
| 587 | @Override public void clear() { |
| 588 | LinkedTreeMap.this.clear(); |
| 589 | } |
| 590 | } |
| 591 | |
| 592 | class KeySet extends AbstractSet<K> { |
| 593 | @Override public int size() { |
| 594 | return size; |
| 595 | } |
| 596 | |
| 597 | @Override public Iterator<K> iterator() { |
| 598 | return new LinkedTreeMapIterator<K>() { |
| 599 | public K next() { |
| 600 | return nextNode().key; |
| 601 | } |
| 602 | }; |
| 603 | } |
| 604 | |
| 605 | @Override public boolean contains(Object o) { |
| 606 | return containsKey(o); |
| 607 | } |
| 608 | |
| 609 | @Override public boolean remove(Object key) { |
| 610 | return removeInternalByKey(key) != null; |
| 611 | } |
| 612 | |
| 613 | @Override public void clear() { |
| 614 | LinkedTreeMap.this.clear(); |
| 615 | } |
| 616 | } |
| 617 | |
| 618 | /** |
| 619 | * If somebody is unlucky enough to have to serialize one of these, serialize |
| 620 | * it as a LinkedHashMap so that they won't need Gson on the other side to |
| 621 | * deserialize it. Using serialization defeats our DoS defence, so most apps |
| 622 | * shouldn't use it. |
| 623 | */ |
| 624 | private Object writeReplace() throws ObjectStreamException { |
| 625 | return new LinkedHashMap<K, V>(this); |
| 626 | } |
| 627 | } |