libjava/classpath/java/util/BitSet.java

   1 /* BitSet.java -- A vector of bits.
   2    Copyright (C) 1998, 1999, 2000, 2001, 2004, 2005  Free Software Foundation, Inc.
   3
   4 This file is part of GNU Classpath.
   5
   6 GNU Classpath is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU Classpath is distributed in the hope that it will be useful, but
  12 WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU Classpath; see the file COPYING.  If not, write to the
  18 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301 USA.
  20
  21 Linking this library statically or dynamically with other modules is
  22 making a combined work based on this library.  Thus, the terms and
  23 conditions of the GNU General Public License cover the whole
  24 combination.
  25
  26 As a special exception, the copyright holders of this library give you
  27 permission to link this library with independent modules to produce an
  28 executable, regardless of the license terms of these independent
  29 modules, and to copy and distribute the resulting executable under
  30 terms of your choice, provided that you also meet, for each linked
  31 independent module, the terms and conditions of the license of that
  32 module.  An independent module is a module which is not derived from
  33 or based on this library.  If you modify this library, you may extend
  34 this exception to your version of the library, but you are not
  35 obligated to do so.  If you do not wish to do so, delete this
  36 exception statement from your version. */
  37
  38 package java.util;
  39
  40 import gnu.java.lang.CPStringBuilder;
  41
  42 import java.io.Serializable;
  43
  44 /* Written using "Java Class Libraries", 2nd edition, ISBN 0-201-31002-3
  45  * hashCode algorithm taken from JDK 1.2 docs.
  46  */
  47
  48 /**
  49  * This class can be thought of in two ways.  You can see it as a
  50  * vector of bits or as a set of non-negative integers.  The name
  51  * <code>BitSet</code> is a bit misleading.
  52  *
  53  * It is implemented by a bit vector, but its equally possible to see
  54  * it as set of non-negative integer; each integer in the set is
  55  * represented by a set bit at the corresponding index.  The size of
  56  * this structure is determined by the highest integer in the set.
  57  *
  58  * You can union, intersect and build (symmetric) remainders, by
  59  * invoking the logical operations and, or, andNot, resp. xor.
  60  *
  61  * This implementation is NOT synchronized against concurrent access from
  62  * multiple threads. Specifically, if one thread is reading from a bitset
  63  * while another thread is simultaneously modifying it, the results are
  64  * undefined.
  65  *
  66  * @author Jochen Hoenicke
  67  * @author Tom Tromey (tromey@cygnus.com)
  68  * @author Eric Blake (ebb9@email.byu.edu)
  69  * @status updated to 1.4
  70  */
  71 public class BitSet implements Cloneable, Serializable
  72 {
  73   /**
  74    * Compatible with JDK 1.0.
  75    */
  76   private static final long serialVersionUID = 7997698588986878753L;
  77
  78   /**
  79    * A common mask.
  80    */
  81   private static final int LONG_MASK = 0x3f;
  82
  83   /**
  84    * The actual bits.
  85    * @serial the i'th bit is in bits[i/64] at position i%64 (where position
  86    *         0 is the least significant).
  87    */
  88   private long[] bits;
  89
  90   /**
  91    * Create a new empty bit set. All bits are initially false.
  92    */
  93   public BitSet()
  94   {
  95     this(64);
  96   }
  97
  98   /**
  99    * Create a new empty bit set, with a given size.  This
 100    * constructor reserves enough space to represent the integers
 101    * from <code>0</code> to <code>nbits-1</code>.
 102    *
 103    * @param nbits the initial size of the bit set
 104    * @throws NegativeArraySizeException if nbits &lt; 0
 105    */
 106   public BitSet(int nbits)
 107   {
 108     if (nbits < 0)
 109       throw new NegativeArraySizeException();
 110
 111     int length = nbits >>> 6;
 112     if ((nbits & LONG_MASK) != 0)
 113       ++length;
 114     bits = new long[length];
 115   }
 116
 117   /**
 118    * Performs the logical AND operation on this bit set and the
 119    * given <code>set</code>.  This means it builds the intersection
 120    * of the two sets.  The result is stored into this bit set.
 121    *
 122    * @param bs the second bit set
 123    * @throws NullPointerException if bs is null
 124    */
 125   public void and(BitSet bs)
 126   {
 127     int max = Math.min(bits.length, bs.bits.length);
 128     int i;
 129     for (i = 0; i < max; ++i)
 130       bits[i] &= bs.bits[i];
 131     while (i < bits.length)
 132       bits[i++] = 0;
 133   }
 134
 135   /**
 136    * Performs the logical AND operation on this bit set and the
 137    * complement of the given <code>bs</code>.  This means it
 138    * selects every element in the first set, that isn't in the
 139    * second set.  The result is stored into this bit set and is
 140    * effectively the set difference of the two.
 141    *
 142    * @param bs the second bit set
 143    * @throws NullPointerException if bs is null
 144    * @since 1.2
 145    */
 146   public void andNot(BitSet bs)
 147   {
 148     int i = Math.min(bits.length, bs.bits.length);
 149     while (--i >= 0)
 150       bits[i] &= ~bs.bits[i];
 151   }
 152
 153   /**
 154    * Returns the number of bits set to true.
 155    *
 156    * @return the number of true bits
 157    * @since 1.4
 158    */
 159   public int cardinality()
 160   {
 161     int card = 0;
 162     for (int i = bits.length - 1; i >= 0; i--)
 163       {
 164         long a = bits[i];
 165         // Take care of common cases.
 166         if (a == 0)
 167           continue;
 168         if (a == -1)
 169           {
 170             card += 64;
 171             continue;
 172           }
 173
 174         // Successively collapse alternating bit groups into a sum.
 175         a = ((a >> 1) & 0x5555555555555555L) + (a & 0x5555555555555555L);
 176         a = ((a >> 2) & 0x3333333333333333L) + (a & 0x3333333333333333L);
 177         int b = (int) ((a >>> 32) + a);
 178         b = ((b >> 4) & 0x0f0f0f0f) + (b & 0x0f0f0f0f);
 179         b = ((b >> 8) & 0x00ff00ff) + (b & 0x00ff00ff);
 180         card += ((b >> 16) & 0x0000ffff) + (b & 0x0000ffff);
 181       }
 182     return card;
 183   }
 184
 185   /**
 186    * Sets all bits in the set to false.
 187    *
 188    * @since 1.4
 189    */
 190   public void clear()
 191   {
 192     Arrays.fill(bits, 0);
 193   }
 194
 195   /**
 196    * Removes the integer <code>pos</code> from this set. That is
 197    * the corresponding bit is cleared.  If the index is not in the set,
 198    * this method does nothing.
 199    *
 200    * @param pos a non-negative integer
 201    * @throws IndexOutOfBoundsException if pos &lt; 0
 202    */
 203   public void clear(int pos)
 204   {
 205     int offset = pos >> 6;
 206     ensure(offset);
 207     // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
 208     // so we'll just let that be our exception.
 209     bits[offset] &= ~(1L << pos);
 210   }
 211
 212   /**
 213    * Sets the bits between from (inclusive) and to (exclusive) to false.
 214    *
 215    * @param from the start range (inclusive)
 216    * @param to the end range (exclusive)
 217    * @throws IndexOutOfBoundsException if from &lt; 0 || to &lt; 0 ||
 218    *         from &gt; to
 219    * @since 1.4
 220    */
 221   public void clear(int from, int to)
 222   {
 223     if (from < 0 || from > to)
 224       throw new IndexOutOfBoundsException();
 225     if (from == to)
 226       return;
 227     int lo_offset = from >>> 6;
 228     int hi_offset = to >>> 6;
 229     ensure(hi_offset);
 230     if (lo_offset == hi_offset)
 231       {
 232         bits[hi_offset] &= ((1L << from) - 1) | (-1L << to);
 233         return;
 234       }
 235
 236     bits[lo_offset] &= (1L << from) - 1;
 237     bits[hi_offset] &= -1L << to;
 238     for (int i = lo_offset + 1; i < hi_offset; i++)
 239       bits[i] = 0;
 240   }
 241
 242   /**
 243    * Create a clone of this bit set, that is an instance of the same
 244    * class and contains the same elements.  But it doesn't change when
 245    * this bit set changes.
 246    *
 247    * @return the clone of this object.
 248    */
 249   public Object clone()
 250   {
 251     try
 252       {
 253         BitSet bs = (BitSet) super.clone();
 254         bs.bits = (long[]) bits.clone();
 255         return bs;
 256       }
 257     catch (CloneNotSupportedException e)
 258       {
 259         // Impossible to get here.
 260         return null;
 261       }
 262   }
 263
 264   /**
 265    * Returns true if the <code>obj</code> is a bit set that contains
 266    * exactly the same elements as this bit set, otherwise false.
 267    *
 268    * @param obj the object to compare to
 269    * @return true if obj equals this bit set
 270    */
 271   public boolean equals(Object obj)
 272   {
 273     if (!(obj instanceof BitSet))
 274       return false;
 275     BitSet bs = (BitSet) obj;
 276     int max = Math.min(bits.length, bs.bits.length);
 277     int i;
 278     for (i = 0; i < max; ++i)
 279       if (bits[i] != bs.bits[i])
 280         return false;
 281     // If one is larger, check to make sure all extra bits are 0.
 282     for (int j = i; j < bits.length; ++j)
 283       if (bits[j] != 0)
 284         return false;
 285     for (int j = i; j < bs.bits.length; ++j)
 286       if (bs.bits[j] != 0)
 287         return false;
 288     return true;
 289   }
 290
 291   /**
 292    * Sets the bit at the index to the opposite value.
 293    *
 294    * @param index the index of the bit
 295    * @throws IndexOutOfBoundsException if index is negative
 296    * @since 1.4
 297    */
 298   public void flip(int index)
 299   {
 300     int offset = index >> 6;
 301     ensure(offset);
 302     // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
 303     // so we'll just let that be our exception.
 304     bits[offset] ^= 1L << index;
 305   }
 306
 307   /**
 308    * Sets a range of bits to the opposite value.
 309    *
 310    * @param from the low index (inclusive)
 311    * @param to the high index (exclusive)
 312    * @throws IndexOutOfBoundsException if from &gt; to || from &lt; 0 ||
 313    *         to &lt; 0
 314    * @since 1.4
 315    */
 316   public void flip(int from, int to)
 317   {
 318     if (from < 0 || from > to)
 319       throw new IndexOutOfBoundsException();
 320     if (from == to)
 321       return;
 322     int lo_offset = from >>> 6;
 323     int hi_offset = to >>> 6;
 324     ensure(hi_offset);
 325     if (lo_offset == hi_offset)
 326       {
 327         bits[hi_offset] ^= (-1L << from) & ((1L << to) - 1);
 328         return;
 329       }
 330
 331     bits[lo_offset] ^= -1L << from;
 332     bits[hi_offset] ^= (1L << to) - 1;
 333     for (int i = lo_offset + 1; i < hi_offset; i++)
 334       bits[i] ^= -1;
 335   }
 336
 337   /**
 338    * Returns true if the integer <code>bitIndex</code> is in this bit
 339    * set, otherwise false.
 340    *
 341    * @param pos a non-negative integer
 342    * @return the value of the bit at the specified position
 343    * @throws IndexOutOfBoundsException if the pos is negative
 344    */
 345   public boolean get(int pos)
 346   {
 347     int offset = pos >> 6;
 348     if (offset >= bits.length)
 349       return false;
 350     // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
 351     // so we'll just let that be our exception.
 352     return (bits[offset] & (1L << pos)) != 0;
 353   }
 354
 355   /**
 356    * Returns a new <code>BitSet</code> composed of a range of bits from
 357    * this one.
 358    *
 359    * @param from the low index (inclusive)
 360    * @param to the high index (exclusive)
 361    * @throws IndexOutOfBoundsException if from &gt; to || from &lt; 0 ||
 362    *         to &lt; 0
 363    * @since 1.4
 364    */
 365   public BitSet get(int from, int to)
 366   {
 367     if (from < 0 || from > to)
 368       throw new IndexOutOfBoundsException();
 369     BitSet bs = new BitSet(to - from);
 370     int lo_offset = from >>> 6;
 371     if (lo_offset >= bits.length || to == from)
 372       return bs;
 373
 374     int lo_bit = from & LONG_MASK;
 375     int hi_offset = to >>> 6;
 376     if (lo_bit == 0)
 377       {
 378         int len = Math.min(hi_offset - lo_offset + 1, bits.length - lo_offset);
 379         System.arraycopy(bits, lo_offset, bs.bits, 0, len);
 380         if (hi_offset < bits.length)
 381           bs.bits[hi_offset - lo_offset] &= (1L << to) - 1;
 382         return bs;
 383       }
 384
 385     int len = Math.min(hi_offset, bits.length - 1);
 386     int reverse = 64 - lo_bit;
 387     int i;
 388     for (i = 0; lo_offset < len; lo_offset++, i++)
 389       bs.bits[i] = ((bits[lo_offset] >>> lo_bit)
 390                     | (bits[lo_offset + 1] << reverse));
 391     if ((to & LONG_MASK) > lo_bit)
 392       bs.bits[i++] = bits[lo_offset] >>> lo_bit;
 393     if (hi_offset < bits.length)
 394       bs.bits[i - 1] &= (1L << (to - from)) - 1;
 395     return bs;
 396   }
 397
 398   /**
 399    * Returns a hash code value for this bit set.  The hash code of
 400    * two bit sets containing the same integers is identical.  The algorithm
 401    * used to compute it is as follows:
 402    *
 403    * Suppose the bits in the BitSet were to be stored in an array of
 404    * long integers called <code>bits</code>, in such a manner that
 405    * bit <code>k</code> is set in the BitSet (for non-negative values
 406    * of <code>k</code>) if and only if
 407    *
 408    * <code>((k/64) &lt; bits.length)
 409    * && ((bits[k/64] & (1L &lt;&lt; (bit % 64))) != 0)
 410    * </code>
 411    *
 412    * Then the following definition of the hashCode method
 413    * would be a correct implementation of the actual algorithm:
 414    *
 415    *
 416 <pre>public int hashCode()
 417 {
 418   long h = 1234;
 419   for (int i = bits.length-1; i &gt;= 0; i--)
 420   {
 421     h ^= bits[i] * (i + 1);
 422   }
 423
 424   return (int)((h >> 32) ^ h);
 425 }</pre>
 426    *
 427    * Note that the hash code values changes, if the set is changed.
 428    *
 429    * @return the hash code value for this bit set.
 430    */
 431   public int hashCode()
 432   {
 433     long h = 1234;
 434     for (int i = bits.length; i > 0; )
 435       h ^= i * bits[--i];
 436     return (int) ((h >> 32) ^ h);
 437   }
 438
 439   /**
 440    * Returns true if the specified BitSet and this one share at least one
 441    * common true bit.
 442    *
 443    * @param set the set to check for intersection
 444    * @return true if the sets intersect
 445    * @throws NullPointerException if set is null
 446    * @since 1.4
 447    */
 448   public boolean intersects(BitSet set)
 449   {
 450     int i = Math.min(bits.length, set.bits.length);
 451     while (--i >= 0)
 452       if ((bits[i] & set.bits[i]) != 0)
 453         return true;
 454     return false;
 455   }
 456
 457   /**
 458    * Returns true if this set contains no true bits.
 459    *
 460    * @return true if all bits are false
 461    * @since 1.4
 462    */
 463   public boolean isEmpty()
 464   {
 465     for (int i = bits.length - 1; i >= 0; i--)
 466       if (bits[i] != 0)
 467         return false;
 468     return true;
 469   }
 470
 471   /**
 472    * Returns the logical number of bits actually used by this bit
 473    * set.  It returns the index of the highest set bit plus one.
 474    * Note that this method doesn't return the number of set bits.
 475    *
 476    * @return the index of the highest set bit plus one.
 477    */
 478   public int length()
 479   {
 480     // Set i to highest index that contains a non-zero value.
 481     int i;
 482     for (i = bits.length - 1; i >= 0 && bits[i] == 0; --i)
 483       ;
 484
 485     // if i < 0 all bits are cleared.
 486     if (i < 0)
 487       return 0;
 488
 489     // Now determine the exact length.
 490     long b = bits[i];
 491     int len = (i + 1) * 64;
 492     // b >= 0 checks if the highest bit is zero.
 493     while (b >= 0)
 494       {
 495         --len;
 496         b <<= 1;
 497       }
 498
 499     return len;
 500   }
 501
 502   /**
 503    * Returns the index of the next false bit, from the specified bit
 504    * (inclusive).
 505    *
 506    * @param from the start location
 507    * @return the first false bit
 508    * @throws IndexOutOfBoundsException if from is negative
 509    * @since 1.4
 510    */
 511   public int nextClearBit(int from)
 512   {
 513     int offset = from >> 6;
 514     long mask = 1L << from;
 515     while (offset < bits.length)
 516       {
 517         // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
 518         // so we'll just let that be our exception.
 519         long h = bits[offset];
 520         do
 521           {
 522             if ((h & mask) == 0)
 523               return from;
 524             mask <<= 1;
 525             from++;
 526           }
 527         while (mask != 0);
 528         mask = 1;
 529         offset++;
 530       }
 531     return from;
 532   }
 533
 534   /**
 535    * Returns the index of the next true bit, from the specified bit
 536    * (inclusive). If there is none, -1 is returned. You can iterate over
 537    * all true bits with this loop:<br>
 538    *
 539 <pre>for (int i = bs.nextSetBit(0); i &gt;= 0; i = bs.nextSetBit(i + 1))
 540 {
 541   // operate on i here
 542 }</pre>
 543    *
 544    * @param from the start location
 545    * @return the first true bit, or -1
 546    * @throws IndexOutOfBoundsException if from is negative
 547    * @since 1.4
 548    */
 549   public int nextSetBit(int from)
 550   {
 551     int offset = from >> 6;
 552     long mask = 1L << from;
 553     while (offset < bits.length)
 554       {
 555         // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
 556         // so we'll just let that be our exception.
 557         long h = bits[offset];
 558         do
 559           {
 560             if ((h & mask) != 0)
 561               return from;
 562             mask <<= 1;
 563             from++;
 564           }
 565         while (mask != 0);
 566         mask = 1;
 567         offset++;
 568       }
 569     return -1;
 570   }
 571
 572   /**
 573    * Performs the logical OR operation on this bit set and the
 574    * given <code>set</code>.  This means it builds the union
 575    * of the two sets.  The result is stored into this bit set, which
 576    * grows as necessary.
 577    *
 578    * @param bs the second bit set
 579    * @throws NullPointerException if bs is null
 580    */
 581   public void or(BitSet bs)
 582   {
 583     ensure(bs.bits.length - 1);
 584     for (int i = bs.bits.length - 1; i >= 0; i--)
 585       bits[i] |= bs.bits[i];
 586   }
 587
 588   /**
 589    * Add the integer <code>bitIndex</code> to this set.  That is
 590    * the corresponding bit is set to true.  If the index was already in
 591    * the set, this method does nothing.  The size of this structure
 592    * is automatically increased as necessary.
 593    *
 594    * @param pos a non-negative integer.
 595    * @throws IndexOutOfBoundsException if pos is negative
 596    */
 597   public void set(int pos)
 598   {
 599     int offset = pos >> 6;
 600     ensure(offset);
 601     // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException,
 602     // so we'll just let that be our exception.
 603     bits[offset] |= 1L << pos;
 604   }
 605
 606   /**
 607    * Sets the bit at the given index to the specified value. The size of
 608    * this structure is automatically increased as necessary.
 609    *
 610    * @param index the position to set
 611    * @param value the value to set it to
 612    * @throws IndexOutOfBoundsException if index is negative
 613    * @since 1.4
 614    */
 615   public void set(int index, boolean value)
 616   {
 617     if (value)
 618       set(index);
 619     else
 620       clear(index);
 621   }
 622
 623   /**
 624    * Sets the bits between from (inclusive) and to (exclusive) to true.
 625    *
 626    * @param from the start range (inclusive)
 627    * @param to the end range (exclusive)
 628    * @throws IndexOutOfBoundsException if from &lt; 0 || from &gt; to ||
 629    *         to &lt; 0
 630    * @since 1.4
 631    */
 632   public void set(int from, int to)
 633   {
 634     if (from < 0 || from > to)
 635       throw new IndexOutOfBoundsException();
 636     if (from == to)
 637       return;
 638     int lo_offset = from >>> 6;
 639     int hi_offset = to >>> 6;
 640     ensure(hi_offset);
 641     if (lo_offset == hi_offset)
 642       {
 643         bits[hi_offset] |= (-1L << from) & ((1L << to) - 1);
 644         return;
 645       }
 646
 647     bits[lo_offset] |= -1L << from;
 648     bits[hi_offset] |= (1L << to) - 1;
 649     for (int i = lo_offset + 1; i < hi_offset; i++)
 650       bits[i] = -1;
 651   }
 652
 653   /**
 654    * Sets the bits between from (inclusive) and to (exclusive) to the
 655    * specified value.
 656    *
 657    * @param from the start range (inclusive)
 658    * @param to the end range (exclusive)
 659    * @param value the value to set it to
 660    * @throws IndexOutOfBoundsException if from &lt; 0 || from &gt; to ||
 661    *         to &lt; 0
 662    * @since 1.4
 663    */
 664   public void set(int from, int to, boolean value)
 665   {
 666     if (value)
 667       set(from, to);
 668     else
 669       clear(from, to);
 670   }
 671
 672   /**
 673    * Returns the number of bits actually used by this bit set.  Note
 674    * that this method doesn't return the number of set bits, and that
 675    * future requests for larger bits will make this automatically grow.
 676    *
 677    * @return the number of bits currently used.
 678    */
 679   public int size()
 680   {
 681     return bits.length * 64;
 682   }
 683
 684   /**
 685    * Returns the string representation of this bit set.  This
 686    * consists of a comma separated list of the integers in this set
 687    * surrounded by curly braces.  There is a space after each comma.
 688    * A sample string is thus "{1, 3, 53}".
 689    * @return the string representation.
 690    */
 691   public String toString()
 692   {
 693     CPStringBuilder r = new CPStringBuilder("{");
 694     boolean first = true;
 695     for (int i = 0; i < bits.length; ++i)
 696       {
 697         long bit = 1;
 698         long word = bits[i];
 699         if (word == 0)
 700           continue;
 701         for (int j = 0; j < 64; ++j)
 702           {
 703             if ((word & bit) != 0)
 704               {
 705                 if (! first)
 706                   r.append(", ");
 707                 r.append(64 * i + j);
 708                 first = false;
 709               }
 710             bit <<= 1;
 711           }
 712       }
 713     return r.append("}").toString();
 714   }
 715
 716   /**
 717    * Performs the logical XOR operation on this bit set and the
 718    * given <code>set</code>.  This means it builds the symmetric
 719    * remainder of the two sets (the elements that are in one set,
 720    * but not in the other).  The result is stored into this bit set,
 721    * which grows as necessary.
 722    *
 723    * @param bs the second bit set
 724    * @throws NullPointerException if bs is null
 725    */
 726   public void xor(BitSet bs)
 727   {
 728     ensure(bs.bits.length - 1);
 729     for (int i = bs.bits.length - 1; i >= 0; i--)
 730       bits[i] ^= bs.bits[i];
 731   }
 732
 733   /**
 734    * Make sure the vector is big enough.
 735    *
 736    * @param lastElt the size needed for the bits array
 737    */
 738   private void ensure(int lastElt)
 739   {
 740     if (lastElt >= bits.length)
 741       {
 742         long[] nd = new long[lastElt + 1];
 743         System.arraycopy(bits, 0, nd, 0, bits.length);
 744         bits = nd;
 745       }
 746   }
 747
 748   // This is used by EnumSet for efficiency.
 749   final boolean containsAll(BitSet other)
 750   {
 751     for (int i = other.bits.length - 1; i >= 0; i--)
 752       {
 753         if ((bits[i] & other.bits[i]) != other.bits[i])
 754           return false;
 755       }
 756     return true;
 757   }
 758 }