util/src/com/intellij/util/containers/ContainerUtil.java

   1 /*
   2  * Copyright 2000-2007 JetBrains s.r.o.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 package com.intellij.util.containers;
  17
  18 import com.intellij.openapi.Disposable;
  19 import com.intellij.openapi.util.Condition;
  20 import com.intellij.openapi.util.Disposer;
  21 import com.intellij.openapi.util.Factory;
  22 import com.intellij.util.*;
  23 import gnu.trove.TObjectHashingStrategy;
  24 import org.jetbrains.annotations.NotNull;
  25 import org.jetbrains.annotations.Nullable;
  26
  27 import java.io.Serializable;
  28 import java.lang.reflect.Array;
  29 import java.util.*;
  30 import java.util.concurrent.CopyOnWriteArrayList;
  31
  32 public class ContainerUtil {
  33   public static List<Object> mergeSortedLists(List<Object> list1, List<Object> list2, Comparator<Object> comparator, boolean mergeEqualItems){
  34     ArrayList<Object> result = new ArrayList<Object>();
  35
  36     int index1 = 0;
  37     int index2 = 0;
  38     while(index1 < list1.size() || index2 < list2.size()){
  39       if (index1 >= list1.size()){
  40         result.add(list2.get(index2++));
  41       }
  42       else if (index2 >= list2.size()){
  43         result.add(list1.get(index1++));
  44       }
  45       else{
  46         Object element1 = list1.get(index1);
  47         Object element2 = list2.get(index2);
  48         int c = comparator.compare(element1,  element2);
  49         if (c < 0){
  50           result.add(element1);
  51           index1++;
  52         }
  53         else if (c > 0){
  54           result.add(element2);
  55           index2++;
  56         }
  57         else{
  58           result.add(element1);
  59           if (!mergeEqualItems){
  60             result.add(element2);
  61           }
  62           index1++;
  63           index2++;
  64         }
  65       }
  66     }
  67
  68     return result;
  69   }
  70
  71   public static <T> void addAll(Collection<T> collection, Iterator<T> iterator) {
  72     while (iterator.hasNext()) {
  73       T o = iterator.next();
  74       collection.add(o);
  75     }
  76   }
  77
  78   public static <T> ArrayList<T> collect(Iterator<T> iterator) {
  79     ArrayList<T> list = new ArrayList<T>();
  80     addAll(list, iterator);
  81     return list;
  82   }
  83
  84   public static <T> HashSet<T> collectSet(Iterator<T> iterator) {
  85     HashSet<T> hashSet = new HashSet<T>();
  86     addAll(hashSet, iterator);
  87     return hashSet;
  88   }
  89
  90   public static <K,V> HashMap<K, V> assignKeys(Iterator<V> iterator, Convertor<V, K> keyConvertor) {
  91     HashMap<K, V> hashMap = new HashMap<K, V>();
  92     while (iterator.hasNext()) {
  93       V value = iterator.next();
  94       hashMap.put(keyConvertor.convert(value), value);
  95     }
  96     return hashMap;
  97   }
  98
  99   public static <K,V> HashMap<K, Set<V>> classify(Iterator<V> iterator, Convertor<V, K> keyConvertor) {
 100     HashMap<K, Set<V>> hashMap = new HashMap<K, Set<V>>();
 101     while (iterator.hasNext()) {
 102       V value = iterator.next();
 103       final K key = keyConvertor.convert(value);
 104       Set<V> set = hashMap.get(key);
 105       if (set == null) {
 106         hashMap.put(key, set = new LinkedHashSet<V>()); // ordered set!!
 107       }
 108       set.add(value);
 109     }
 110     return hashMap;
 111   }
 112
 113   public static <K, V> HashMap<K, V> assignValues(Iterator<K> iterator, Convertor<K, V> valueConvertor) {
 114     HashMap<K, V> hashMap = new HashMap<K, V>();
 115     while (iterator.hasNext()) {
 116       K key = iterator.next();
 117       hashMap.put(key, valueConvertor.convert(key));
 118     }
 119     return hashMap;
 120   }
 121
 122   public static <T> Iterator<T> emptyIterator() {
 123     return EmptyIterator.getInstance();
 124   }
 125
 126   @Nullable
 127   public static <T> T find(T[] array, Condition<T> condition) {
 128     for (T element : array) {
 129       if (condition.value(element)) return element;
 130     }
 131     return null;
 132   }
 133
 134   public static <T> boolean process(Iterable<? extends T> iterable, Processor<T> processor) {
 135     for (final T t : iterable) {
 136       if (!processor.process(t)) {
 137         return false;
 138       }
 139     }
 140     return true;
 141   }
 142
 143   public static <T> boolean process(T[] iterable, Processor<? super T> processor) {
 144     for (final T t : iterable) {
 145       if (!processor.process(t)) {
 146         return false;
 147       }
 148     }
 149     return true;
 150   }
 151
 152   @Nullable
 153   public static <T,V extends T> V find(Iterable<V> iterable, Condition<T> condition) {
 154     return find(iterable.iterator(), condition);
 155   }
 156
 157   @Nullable
 158   public static <T> T find(Iterable<? extends T> iterable, final T equalTo) {
 159     return find(iterable, new Condition<T>() {
 160       public boolean value(final T object) {
 161         return equalTo == object || equalTo.equals(object);
 162       }
 163     });
 164   }
 165
 166   @Nullable
 167   public static <T,V extends T> V find(Iterator<V> iterator, Condition<T> condition) {
 168     while (iterator.hasNext()) {
 169       V value = iterator.next();
 170       if (condition.value(value)) return value;
 171     }
 172     return null;
 173   }
 174
 175   public static <T,V> List<V> map2List(T[] array, Function<T,V> mapper) {
 176     return map2List(Arrays.asList(array), mapper);
 177   }
 178
 179   public static <T,V> List<V> map2List(Collection<? extends T> collection, Function<T,V> mapper) {
 180     final ArrayList<V> list = new ArrayList<V>(collection.size());
 181     for (final T t : collection) {
 182       list.add(mapper.fun(t));
 183     }
 184     return list;
 185   }
 186
 187   public static <T,V> Set<V> map2Set(T[] collection, Function<T,V> mapper) {
 188     return map2Set(Arrays.asList(collection), mapper);
 189   }
 190
 191   public static <T,V> Set<V> map2Set(Collection<? extends T> collection, Function<T,V> mapper) {
 192     final HashSet<V> set = new HashSet<V>(collection.size());
 193     for (final T t : collection) {
 194       set.add(mapper.fun(t));
 195     }
 196     return set;
 197   }
 198
 199   public static <T> Object[] map2Array(T[] array, Function<T,Object> mapper) {
 200     return map2Array(array, Object.class, mapper);
 201   }
 202
 203   public static <T> Object[] map2Array(Collection<T> array, Function<T,Object> mapper) {
 204     return map2Array(array, Object.class, mapper);
 205   }
 206
 207   public static <T,V> V[] map2Array(T[] array, Class<? extends V> aClass, Function<T,V> mapper) {
 208     return map2Array(Arrays.asList(array), aClass, mapper);
 209   }
 210
 211   public static <T,V> V[] map2Array(Collection<? extends T> collection, Class<? extends V> aClass, Function<T,V> mapper) {
 212     final List<V> list = map2List(collection, mapper);
 213     return list.toArray((V[])Array.newInstance(aClass, list.size()));
 214   }
 215
 216   public static <T,V> V[] map2Array(Collection<? extends T> collection, V[] to, Function<T,V> mapper) {
 217     return map2List(collection, mapper).toArray(to);
 218   }
 219
 220   public static <T> List<T> findAll(T[] collection, Condition<? super T> condition) {
 221     return findAll(Arrays.asList(collection), condition);
 222   }
 223
 224   public static <T> List<T> findAll(Collection<? extends T> collection, Condition<? super T> condition) {
 225     final ArrayList<T> result = new ArrayList<T>();
 226     for (final T t : collection) {
 227       if (condition.value(t)) {
 228         result.add(t);
 229       }
 230     }
 231     return result;
 232   }
 233
 234   public static <T> List<T> skipNulls (Collection<? extends T> collection) {
 235     return findAll(collection, Condition.NOT_NULL);
 236   }
 237
 238   public static <T,V> List<V> findAll(T[] collection, Class<V> instanceOf) {
 239     return findAll(Arrays.asList(collection), instanceOf);
 240   }
 241
 242   public static <T,V> V[] findAllAsArray(T[] collection, Class<V> instanceOf) {
 243     List<V> list = findAll(Arrays.asList(collection), instanceOf);
 244     return list.toArray((V[])Array.newInstance(instanceOf, list.size()));
 245   }
 246
 247   public static <T,V> V[] findAllAsArray(Collection<? extends T> collection, Class<V> instanceOf) {
 248     List<V> list = findAll(collection, instanceOf);
 249     return list.toArray((V[])Array.newInstance(instanceOf, list.size()));
 250   }
 251
 252   public static <T,V> List<V> findAll(Collection<? extends T> collection, Class<V> instanceOf) {
 253     final ArrayList<V> result = new ArrayList<V>();
 254     for (final T t : collection) {
 255       if (instanceOf.isInstance(t)) {
 256         result.add((V)t);
 257       }
 258     }
 259     return result;
 260   }
 261
 262   public static <T> void removeDuplicates(Collection<T> collection) {
 263     Set<T> collected = new HashSet<T>();
 264     for (Iterator<T> iterator = collection.iterator(); iterator.hasNext();) {
 265       T t = iterator.next();
 266       if (!collected.contains(t)) {
 267         collected.add(t);
 268       }
 269       else {
 270         iterator.remove();
 271       }
 272     }
 273   }
 274
 275   public static <T> Iterator<T> iterate(T[] arrays) {
 276     return Arrays.asList(arrays).iterator();
 277   }
 278
 279   public static <T> Iterator<T> iterate(final Enumeration<T> enumeration) {
 280     return new Iterator<T>() {
 281       public boolean hasNext() {
 282         return enumeration.hasMoreElements();
 283       }
 284
 285       public T next() {
 286         return enumeration.nextElement();
 287       }
 288
 289       public void remove() {
 290         throw new UnsupportedOperationException();
 291       }
 292     };
 293   }
 294
 295   public static <E> void swapElements(final List<E> list, final int index1, final int index2) {
 296     E e1 = list.get(index1);
 297     E e2 = list.get(index2);
 298     list.set(index1, e2);
 299     list.set(index2, e1);
 300   }
 301
 302   public static <T> ArrayList<T> collect(Iterator<?> iterator, FilteringIterator.InstanceOf<T> instanceOf) {
 303     return collect(FilteringIterator.create(iterator, instanceOf));
 304   }
 305
 306   public static <T> void addAll(Collection<T> collection, Enumeration<T> enumeration) {
 307     while (enumeration.hasMoreElements()) {
 308       T element = enumeration.nextElement();
 309       collection.add(element);
 310     }
 311   }
 312
 313   public static <T, U extends T> U findInstance(Iterable<T> iterable, Class<U> aClass) {
 314     return findInstance(iterable.iterator(), aClass);
 315   }
 316
 317   public static <T, U extends T> U findInstance(Iterator<T> iterator, Class<U> aClass) {
 318     // uncomment for 1.5
 319     //return (U)find(iterator, new FilteringIterator.InstanceOf<U>(aClass));
 320     return (U)find(iterator, new FilteringIterator.InstanceOf<T>((Class<T>)aClass));
 321   }
 322
 323   @Nullable
 324   public static <T, U extends T> U findInstance(T[] array, Class<U> aClass) {
 325     return findInstance(Arrays.asList(array), aClass);
 326   }
 327
 328   public static <T,V> List<T> concat(V[] array, Function<V,Collection<? extends T>> fun) {
 329     return concat(Arrays.asList(array), fun);
 330   }
 331
 332   public static <T> List<T> concat(Iterable<? extends Collection<T>> list) {
 333     final ArrayList<T> result = new ArrayList<T>();
 334     for (final Collection<T> ts : list) {
 335       result.addAll(ts);
 336     }
 337     return result;
 338   }
 339
 340   public static <T> List<T> concat(@NotNull final List<? extends T> list1, @NotNull final List<? extends T> list2) {
 341     return new AbstractList<T>() {
 342       public T get(final int index) {
 343         T t;
 344         if (index < list1.size()) {
 345           t = list1.get(index);
 346         }
 347         else {
 348           t = list2.get(index - list1.size());
 349         }
 350         return t;
 351       }
 352
 353       public int size() {
 354         return list1.size() + list2.size();
 355       }
 356     };
 357   }
 358
 359   public static <T,V> List<T> concat(Iterable<? extends V> list, Function<V,Collection<? extends T>> fun) {
 360     final ArrayList<T> result = new ArrayList<T>();
 361     for (final V v : list) {
 362       result.addAll(fun.fun(v));
 363     }
 364     return result;
 365   }
 366
 367   public static <T> boolean intersects(Collection<? extends T> collection1, Collection<? extends T> collection2) {
 368     for (T t : collection1) {
 369       //noinspection SuspiciousMethodCalls
 370       if (collection2.contains(t)) {
 371         return true;
 372       }
 373     }
 374     return false;
 375   }
 376
 377   public static <T> T getFirstItem(final Collection<T> items, final T def) {
 378     return items == null || items.isEmpty()? def : items.iterator().next();
 379   }
 380
 381   public static <T> Collection<T> subtract(Collection<T> from, Collection<T> what) {
 382     final HashSet<T> set = new HashSet<T>(from);
 383     set.removeAll(what);
 384     return set;
 385   }
 386
 387   public static <T> T[] toArray(List<T> collection, T[] array){
 388     final int length = array.length;
 389     if (length < 20) {
 390       for (int i = 0; i < collection.size(); i++) {
 391         array[i] = collection.get(i);
 392       }
 393       return array;
 394     }
 395     else {
 396       return collection.toArray(array);
 397     }
 398   }
 399
 400   public static <T,V> List<V> map(Iterable<? extends T> iterable, Function<T, V> mapping) {
 401     List<V> result = new ArrayList<V>();
 402     for (T t : iterable) {
 403       result.add(mapping.fun(t));
 404     }
 405     return result;
 406   }
 407
 408   public static <T,V> List<V> mapNotNull(T[] array, Function<T, V> mapping) {
 409     return mapNotNull(Arrays.asList(array), mapping);
 410   }
 411
 412   public static <T,V> List<V> mapNotNull(Iterable<? extends T> iterable, Function<T, V> mapping) {
 413     List<V> result = new ArrayList<V>();
 414     for (T t : iterable) {
 415       final V o = mapping.fun(t);
 416       if (o != null) {
 417         result.add(o);
 418       }
 419     }
 420     return result;
 421   }
 422
 423   public static <T> List<T> packNullables(T... elements) {
 424     ArrayList<T> list = new ArrayList<T>();
 425     for (T element : elements) {
 426       addIfNotNull(element, list);
 427     }
 428     return list;
 429   }
 430
 431   public static <T,V> List<V> map(T[] arr, Function<T, V> mapping) {
 432     List<V> result = new ArrayList<V>();
 433     for (T t : arr) {
 434       result.add(mapping.fun(t));
 435     }
 436     return result;
 437   }
 438
 439   public static <T,V> V[] map(T[] arr, Function<T, V> mapping, V[] emptyArray) {
 440     List<V> result = new ArrayList<V>();
 441     for (T t : arr) {
 442       result.add(mapping.fun(t));
 443     }
 444     return result.toArray(emptyArray);
 445   }
 446
 447   public static <T> void addIfNotNull(final T element, final Collection<T> result) {
 448     if (element != null) {
 449       result.add(element);
 450     }
 451   }
 452
 453   public static <K, V> void putIfNotNull(final K key, final V value, final Map<K, V> result) {
 454     if (value != null) {
 455       result.put(key, value);
 456     }
 457   }
 458
 459   public static <T> void add(final T element, final Collection<T> result, final Disposable parentDisposable) {
 460     if (result.add(element)) {
 461       Disposer.register(parentDisposable, new Disposable() {
 462         public void dispose() {
 463           result.remove(element);
 464         }
 465       });
 466     }
 467   }
 468
 469   public static <T> List<T> createMaybeSingletonList(@Nullable T element) {
 470     return element == null ? Collections.<T>emptyList() : Arrays.asList(element);
 471   }
 472
 473   public static <T,V> V getOrCreate(final Map<T, V> result, final T key, final V defaultValue) {
 474     V value = result.get(key);
 475     if (value == null) {
 476       result.put(key, value = defaultValue);
 477     }
 478     return value;
 479   }
 480
 481   public static <T,V> V getOrCreate(final Map<T, V> result, final T key, final Factory<V> factory) {
 482     V value = result.get(key);
 483     if (value == null) {
 484       result.put(key, value = factory.create());
 485     }
 486     return value;
 487   }
 488
 489   public static <T> boolean and(T[] iterable, Condition<T> condition) {
 490     return and(Arrays.asList(iterable), condition);
 491   }
 492
 493   public static <T> boolean and(Iterable<T> iterable, Condition<T> condition) {
 494     for (final T t : iterable) {
 495       if (!condition.value(t)) return false;
 496     }
 497     return true;
 498   }
 499
 500   public static <T> boolean or(T[] iterable, Condition<T> condition) {
 501     return or(Arrays.asList(iterable), condition);
 502   }
 503
 504   public static <T> boolean or(Iterable<T> iterable, Condition<T> condition) {
 505     for (final T t : iterable) {
 506       if (condition.value(t)) return true;
 507     }
 508     return false;
 509   }
 510
 511   public static <T> List<T> unfold(@Nullable T t, @NotNull NullableFunction<T,T> next) {
 512     if (t == null) return Collections.emptyList();
 513
 514     final ArrayList<T> list = new ArrayList<T>();
 515     while (t != null) {
 516       list.add(t);
 517       t = next.fun(t);
 518     }
 519     return list;
 520   }
 521
 522   public static <T> List<T> dropTail(List<T> items) {
 523     return items.subList(0, items.size()-1);
 524   }
 525
 526   public static <T> List<T> list(T... items) {
 527     return Arrays.asList(items);
 528   }
 529
 530   // Generalized Quick Sort. Does neither array.clone() nor list.toArray()
 531   public static <T> void quickSort(List<T> list, Comparator<? super T> comparator) {
 532     quickSort(list, comparator, 0, list.size());
 533   }
 534
 535   private static <T> void quickSort(List<T> x, Comparator<? super T> comparator, int off, int len) {
 536     // Insertion sort on smallest arrays
 537     if (len < 7) {
 538       for (int i = off; i < len + off; i++) {
 539         for (int j = i; j > off && comparator.compare(x.get(j), x.get(j - 1)) < 0; j--) {
 540           swapElements(x, j, j - 1);
 541         }
 542       }
 543       return;
 544     }
 545
 546     // Choose a partition element, v
 547     int m = off + (len >> 1);       // Small arrays, middle element
 548     if (len > 7) {
 549       int l = off;
 550       int n = off + len - 1;
 551       if (len > 40) {        // Big arrays, pseudomedian of 9
 552         int s = len / 8;
 553         l = med3(x, comparator, l, l + s, l + 2 * s);
 554         m = med3(x, comparator, m - s, m, m + s);
 555         n = med3(x, comparator, n - 2 * s, n - s, n);
 556       }
 557       m = med3(x, comparator, l, m, n); // Mid-size, med of 3
 558     }
 559     T v = x.get(m);
 560
 561     // Establish Invariant: v* (<v)* (>v)* v*
 562     int a = off;
 563     int b = a;
 564     int c = off + len - 1;
 565     int d = c;
 566     while (true) {
 567       while (b <= c && comparator.compare(x.get(b), v) <= 0) {
 568         if (comparator.compare(x.get(b), v) == 0) {
 569           swapElements(x, a++, b);
 570         }
 571         b++;
 572       }
 573       while (c >= b && comparator.compare(v, x.get(c)) <= 0) {
 574         if (comparator.compare(x.get(c), v) == 0) {
 575           swapElements(x, c, d--);
 576         }
 577         c--;
 578       }
 579       if (b > c) break;
 580       swapElements(x, b++, c--);
 581     }
 582
 583     // Swap partition elements back to middle
 584     int n = off + len;
 585     int s = Math.min(a - off, b - a);
 586     vecswap(x, off, b - s, s);
 587     s = Math.min(d - c, n - d - 1);
 588     vecswap(x, b, n - s, s);
 589
 590     // Recursively sort non-partition-elements
 591     if ((s = b - a) > 1) quickSort(x, comparator, off, s);
 592     if ((s = d - c) > 1) quickSort(x, comparator, n - s, s);
 593   }
 594
 595   /**
 596    * Returns the index of the median of the three indexed longs.
 597    */
 598   private static <T> int med3(List<T> x, Comparator<? super T> comparator, int a, int b, int c) {
 599     return comparator.compare(x.get(a), x.get(b)) < 0 ? comparator.compare(x.get(b), x.get(c)) < 0
 600                                                         ? b
 601                                                         : comparator.compare(x.get(a), x.get(c)) < 0 ? c : a
 602                                                       : comparator.compare(x.get(c), x.get(b)) < 0
 603                                                         ? b
 604                                                         : comparator.compare(x.get(c), x.get(a)) < 0 ? c : a;
 605   }
 606
 607   /**
 608    * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
 609    */
 610   private static <T> void vecswap(List<T> x, int a, int b, int n) {
 611     for (int i = 0; i < n; i++, a++, b++) {
 612       swapElements(x, a, b);
 613     }
 614   }
 615
 616   public static <T> CopyOnWriteArrayList<T> createEmptyCOWList() {
 617     // does not create garbage new Object[0]
 618     return new CopyOnWriteArrayList<T>(ContainerUtil.<T>emptyList());
 619   }
 620
 621   public static <T> List<T> emptyList() {
 622     return (List<T>)EmptyList.INSTANCE;
 623   }
 624
 625   private static class EmptyList extends AbstractList<Object> implements RandomAccess, Serializable {
 626     private static final EmptyList INSTANCE = new EmptyList();
 627     public int size() {
 628       return 0;
 629     }
 630
 631     public boolean contains(Object obj) {
 632       return false;
 633     }
 634
 635     public Object get(int index) {
 636       throw new IndexOutOfBoundsException("Index: " + index);
 637     }
 638
 639     @Override
 640     public Object[] toArray() {
 641       return ArrayUtil.EMPTY_OBJECT_ARRAY;
 642     }
 643
 644     @Override
 645     public <T> T[] toArray(T[] a) {
 646       return a;
 647     }
 648   }
 649
 650   @NotNull
 651   public static <T> Set<T> singleton(final T o, @NotNull final TObjectHashingStrategy<T> strategy) {
 652     return new Set<T>() {
 653       public int size() {
 654         return 1;
 655       }
 656
 657       public boolean isEmpty() {
 658         return false;
 659       }
 660
 661       public boolean contains(Object elem) {
 662         return strategy.equals(o, (T)elem);
 663       }
 664
 665       public Iterator<T> iterator() {
 666         return new Iterator<T>() {
 667           boolean atEnd;
 668           public boolean hasNext() {
 669             return !atEnd;
 670           }
 671
 672           public T next() {
 673             if (atEnd) throw new NoSuchElementException();
 674             atEnd = true;
 675             return o;
 676           }
 677
 678           public void remove() {
 679             throw new IncorrectOperationException();
 680           }
 681         };
 682       }
 683
 684       public Object[] toArray() {
 685         return new Object[]{o};
 686       }
 687
 688       public <T> T[] toArray(T[] a) {
 689         assert a.length == 1;
 690         a[0] = (T)o;
 691         return a;
 692       }
 693
 694       public boolean add(T t) {
 695         throw new IncorrectOperationException();
 696       }
 697
 698       public boolean remove(Object o) {
 699         throw new IncorrectOperationException();
 700       }
 701
 702       public boolean containsAll(Collection<?> c) {
 703         return false;
 704       }
 705
 706       public boolean addAll(Collection<? extends T> c) {
 707         throw new IncorrectOperationException();
 708       }
 709
 710       public boolean retainAll(Collection<?> c) {
 711         throw new IncorrectOperationException();
 712       }
 713
 714       public boolean removeAll(Collection<?> c) {
 715         throw new IncorrectOperationException();
 716       }
 717
 718       public void clear() {
 719         throw new IncorrectOperationException();
 720       }
 721     };
 722   }
 723 }