com/intendico/data/Relation.java

   1 /*********************************************************************
   2 Copyright 2012, Ralph Ronnquist.
   3
   4 This file is part of GORITE.
   5
   6 GORITE is free software: you can redistribute it and/or modify it
   7 under the terms of the Lesser GNU General Public License as published
   8 by the Free Software Foundation, either version 3 of the License, or
   9 (at your option) any later version.
  10
  11 GORITE is distributed in the hope that it will be useful, but WITHOUT
  12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  14 License for more details.
  15
  16 You should have received a copy of the Lesser GNU General Public
  17 License along with GORITE.  If not, see <http://www.gnu.org/licenses/>.
  18 **********************************************************************/
  19
  20 package com.intendico.data;
  21
  22 import java.util.HashSet;
  23 import java.util.Hashtable;
  24 import java.util.Iterator;
  25 import java.util.Observable;
  26 import java.util.Observer;
  27 import java.util.Vector;
  28
  29 /**
  30  * A Relation is a set of tuples of the same size. It is created by
  31  * enumerating the types of its columns.
  32  *
  33  * <p> A relation may have one or more <em>key constraints</em>. A key
  34  * constraint combines one or more fields into a <em>key</em>, which
  35  * the relation may hold only one tuple for any combination of
  36  * values. The key constraints are used by the {@link #add} method,
  37  * such that addition of a new tuple may cause the removal of prior
  38  * tuples that are equal in some key combination of fields.
  39  *
  40  * <p> A relation is modified via the {@link #add} and {@link #remove}
  41  * methods. Both of these notify observers if the relation is changed.
  42  *
  43  * <p> A relation can be queried via the {@link #query} method, which
  44  * returns an {@link java.util.Iterator} for the matching tuples, or
  45  * by the {@link #get} method, which instead returns a {@link
  46  * Relation.Cursor} that implements the {@link Query} interface.
  47  */
  48 public class Relation extends Observable implements Store, Inquirable {
  49
  50     /**
  51      * Utility method to create a copy of an object array. Only the
  52      * array is copied, not its values.
  53      */
  54     public static Object [] copyArray(Object[] in)
  55     {
  56         Object [] out = new Object [ in.length ];
  57         System.arraycopy( in, 0, out, 0, in.length);
  58         return out;
  59     }
  60
  61     /**
  62      * An instance name for this relation.
  63      */
  64     public final String name;
  65
  66     /**
  67      * The required field types.
  68      */
  69     public final Class [] column_types;
  70
  71     /**
  72      * The special key pattern for all fields being key.
  73      */
  74     public final KeyPattern main_key;
  75
  76     /**
  77      * Holds the relation data in a layered structure. First hash
  78      * index is the key pattern, and second hash index is the key (of
  79      * a pattern). Actual data is a HashSet of Tuple objects, which
  80      * are compared by using {@link java.lang.Object#equals} of their
  81      * fields.
  82      */
  83     public Hashtable/*<KeyPattern,Hashtable<Tuple,HashSet<Tuple>>>*/ indexes =
  84         new Hashtable/*<KeyPattern,Hashtable<Tuple,HashSet<Tuple>>>*/();
  85
  86     /**
  87      * Holds the collection of constraining key patterns. When a tuple
  88      * is added, any already existing tuple of the same key (according
  89      * to any constraining key pattern) is seen as an opposing tuple,
  90      * which is removed (without observer notification).
  91      */
  92     public HashSet/*<KeyPattern>*/ constraints;
  93
  94     /**
  95      * The ArityException is thrown when a relation is accessed with a
  96      * wrong number of fields.
  97      */
  98     public class ArityException extends Exception {
  99
 100         /**
 101          * Version identity required for serialization.
 102          */
 103         public static final long serialVersionUID = 1L;
 104
 105         /**
 106          * Telling the required number of fields.
 107          */
 108         public final int requires;
 109
 110         /**
 111          * Telling the given number of fields.
 112          */
 113         public final int attempted;
 114
 115         /**
 116          * Constructor.
 117          */
 118         public ArityException(int r,int a) {
 119             requires = r;
 120             attempted = a;
 121         }
 122     }
 123
 124     /**
 125      * The ColumnTypeException exception is thrown when a realtion is
 126      * accessed by means of wrong field types.
 127      */
 128     public class ColumnTypeException extends Exception {
 129
 130         /**
 131          * Version identity required for serialization.
 132          */
 133         public static final long serialVersionUID = 1L;
 134
 135         /**
 136          * The required type of the first erroneous field.
 137          */
 138         public final Class requires;
 139
 140         /**
 141          * The given type of the first erroneous field.
 142          */
 143         public final Class attempted;
 144
 145         /**
 146          * The field index.
 147          */
 148         public final int index;
 149
 150         /**
 151          * Constructor.
 152          */
 153         public ColumnTypeException(int i,Class r,Class a) {
 154             requires = r;
 155             attempted = a;
 156             index = i;
 157         }
 158     }
 159
 160     /**
 161      * Constructor. This defines both the relation arity and the
 162      * individual types of the fields.
 163      */
 164     public Relation(String n,Class/*...*/ [] types) {
 165         name = n;
 166         column_types = types;
 167         main_key = new KeyPattern();
 168     }
 169
 170     /**
 171      * Alternative constructor with name and arity only.
 172      */
 173     public Relation(String n,int arity) {
 174         name = n;
 175         column_types = new Class [ arity ];
 176         for ( int i = 0; i < arity; i++ ) {
 177             column_types[ i ] = Object.class;
 178         }
 179         main_key = new KeyPattern();
 180     }
 181
 182     /**
 183      * Clears the relation, i.e. removes all its tuples. Its key
 184      * constraints are unchanged.
 185      */
 186     public void clear() {
 187         indexes =
 188             new Hashtable/*<KeyPattern,Hashtable<Tuple,HashSet<Tuple>>>*/();
 189         setChanged();
 190         notifyObservers();
 191     }
 192
 193     /**
 194      * Returning an Observable that notifies about subsequent changes
 195      * to this Relation.
 196      */
 197     public Observable getMonitor() {
 198         return this;
 199     }
 200
 201     /**
 202      * Adds a constraining key pattern. The relation is managed to
 203      * allow at most one tuple of any key of the constraining key
 204      * patterns. This is enforced when new tuples are added, which
 205      * thus results in that a prior tuple of the same key is removed
 206      * (without observer notification).
 207      *
 208      * <p> Note that a relation that violates the key constraint when
 209      * the constraint is added will not be corrected until an opposing
 210      * tuple is added. It does make good sense to add all key
 211      * constraints before any tuples are added.
 212      */
 213     public Relation addConstraint(boolean/*...*/ [] pattern)
 214         throws ArityException
 215     {
 216         if ( constraints == null )
 217             constraints = new HashSet/*<KeyPattern>*/();
 218         constraints.add( new KeyPattern( pattern ) );
 219         return this;
 220     }
 221
 222     /**
 223      * Removes a constraining key pattern.
 224      *
 225      * <p> Note that the general advice is <em>aginst</em> removing
 226      * key constraints, but rather creating a new relation with the
 227      * reduced set of constraints and then populate that.
 228      */
 229     public void removeConstraint(boolean/*...*/ [] pattern)
 230         throws ArityException
 231     {
 232         if ( constraints == null )
 233             return;
 234         constraints.remove( new KeyPattern( pattern ) );
 235         if ( constraints.size() == 0 )
 236             constraints = null;
 237     }
 238
 239     /**
 240      * Utility method to remove all tuples opposed to a given tuple
 241      * according to a given key pattern. Tuples are removed without
 242      * observer notification.
 243      */
 244     public void applyConstraint(KeyPattern constraint,Tuple adding)
 245         throws ArityException, ColumnTypeException
 246     {
 247         Tuple key = constraint.getKey( adding );
 248         for ( Iterator/*<Tuple>*/ i = query( key ); i.hasNext(); ) {
 249             addPending( (Tuple) i.next() );
 250         }
 251         processPending( false );
 252     }
 253
 254     /**
 255      * Utility method to remove all tuples that are opposite to the
 256      * given tuple with respect to the constraining key patterns.
 257      * Tuples are removed without observer notification.
 258      */
 259     public void applyConstraints(Tuple adding)
 260         throws ArityException, ColumnTypeException
 261     {
 262         if ( constraints == null )
 263             return;
 264         for ( Iterator/*<KeyPattern>*/ i =
 265                   constraints.iterator(); i.hasNext(); ) {
 266             applyConstraint( (KeyPattern) i.next(), adding );
 267         }
 268     }
 269
 270     /**
 271      * Utility method that investigates that fields are appropriate
 272      * for the relation. Any violations are reported by throwing the
 273      * appropriate exception.
 274      * @throws ArityException if there is a wrong number of fields.
 275      * @throws ColumnTypeException if any field is of wrong type.
 276      */
 277     public void runtimeTyping(Object/*...*/ [] fields)
 278         throws ArityException, ColumnTypeException
 279     {
 280         if ( column_types == null ) {
 281             if ( fields == null )
 282                 return;
 283             throw new ArityException( 0, fields.length );
 284         }
 285
 286         if ( fields == null )
 287             throw new ArityException( column_types.length, 0 );
 288
 289         if ( fields.length != column_types.length )
 290             throw new ArityException( column_types.length, fields.length );
 291
 292         for ( int i = 0; i < fields.length; i++ ) {
 293             Object x = Ref.deref( fields[ i ] );
 294             if ( x == null )
 295                 continue;
 296             if ( column_types[ i ].isInstance( x ) )
 297                 continue;
 298             throw new ColumnTypeException(
 299                 i, column_types[ i ], x.getClass() );
 300         }
 301     }
 302
 303
 304     /**
 305      * Represents an I/O key pattern for the relation. This is used
 306      * for identifying keyed access tables.
 307      */
 308     public class KeyPattern {
 309
 310         /**
 311          * The I/O pattern expressed as a boolean array. A true means
 312          * input, and a false means output.
 313          */
 314         boolean [] pattern;
 315
 316         /**
 317          * Constructor by boolean indicators. True indicates an input
 318          * field, and false indicates an output field.
 319          */
 320         public KeyPattern(boolean/*...*/ [] io)
 321             throws ArityException
 322         {
 323             if ( io.length != column_types.length )
 324                 throw new ArityException( column_types.length, io.length );
 325             pattern = io;
 326         }
 327
 328         /**
 329          * Default constructor, with all fields key fields.
 330          */
 331         public KeyPattern() {
 332             pattern = new boolean[ column_types.length ];
 333             for ( int i = 0; i < pattern.length; i++ )
 334                 pattern[ i ] = false;
 335         }
 336
 337         /**
 338          * Constructor by field presence. The constructor is called
 339          * with the right number of fields, leaving output fields as
 340          * null and input fields non-null.
 341          */
 342         public KeyPattern(Object/*...*/ [] io)
 343             throws ArityException
 344         {
 345             if ( io.length != column_types.length )
 346                 throw new ArityException( column_types.length, io.length );
 347             // check types as well?
 348             pattern = new boolean [ io.length ];
 349             for ( int i = 0; i < io.length; i++ )
 350                 pattern[ i ] = Ref.deref( io[ i ] ) != null;
 351         }
 352
 353         /**
 354          * Equality of KeyPattern objects is determined by comparing
 355          * their boolean patterns.
 356          */
 357         public boolean equals(Object p) {
 358             return p instanceof KeyPattern ? equals( (KeyPattern) p ) : false ;
 359         }
 360
 361         /**
 362          * Equality of KeyPattern objects is determined by comparing
 363          * their boolean patterns.
 364          */
 365         public boolean equals(KeyPattern p) {
 366             if ( pattern == null || p.pattern == null )
 367                 return pattern == null && p.pattern == null;
 368             if ( pattern.length != p.pattern.length )
 369                 return false;
 370             for ( int i = 0; i < pattern.length; i++ )
 371                 if ( pattern[ i ] != p.pattern[ i ] )
 372                     return false;
 373             return true;
 374         }
 375
 376         /**
 377          * The hashCode of a KeyPattern is derived by treating its
 378          * boolean pattern as a bit pattern.
 379          */
 380         public int hashCode() {
 381             int code = 0;
 382             for ( int i = 0; i < pattern.length; i++ )
 383                 code = ( code << 1 ) + ( pattern[ i ]? 1 : 0 );
 384             return code;
 385         }
 386
 387         /**
 388          * Returns a tuple by projecting the given tuple through this
 389          * key pattern.
 390          */
 391         public Tuple getKey(Tuple t) {
 392             return new Tuple( t, pattern );
 393         }
 394
 395         /**
 396          * Returns a String representation of the KeyPattern object.
 397          */
 398         public String toString() {
 399             StringBuffer s = new StringBuffer();
 400             String sep = "";
 401             for ( int i = 0; i < pattern.length; i++ ) {
 402                 s.append( sep );
 403                 s.append( pattern[ i ] );
 404                 sep = ",";
 405             }
 406             return "KeyPattern(" + s.toString() +")";
 407         }
 408     }
 409
 410     /**
 411      * Representation of relation row. In a contents row, all fields
 412      * of a tuple should be non-<em>null</em>. Tuples that represent
 413      * access patterns typically have <em>null</em>-valued {@link Ref}
 414      * objects, or are <em>null</em> directly, for the output fields,
 415      * whereas the input fields provide values to match with.
 416      */
 417     public class Tuple {
 418
 419         /**
 420          * Holds the field values.
 421          */
 422         public Object [] fields;
 423
 424         /**
 425          * Constructor.
 426          */
 427         public Tuple() {
 428             fields = new Object[ column_types.length ];
 429         }
 430
 431         /**
 432          * Constructor.
 433          */
 434         public Tuple(Object/*...*/ [] tuple) {
 435             fields = copyArray( tuple );
 436         }
 437
 438         /**
 439          * Returns the number of <em>null</em> fields of this tuple.
 440          */
 441         public int nullCount() {
 442             int x = 0;
 443             for (int i = 0; i < fields.length; i++) {
 444                 if ( Ref.deref( fields[ i ] ) == null )
 445                     x += 1;
 446             }
 447             return x;
 448         }
 449
 450         /**
 451          * Key constructor. Creates a copy of the given tuple, but
 452          * clears the output fields, as given by the key pattern.
 453          */
 454         public Tuple(Tuple t,boolean [] pattern) {
 455             this();
 456             for (int i = 0; i < fields.length; i++) {
 457                 if ( pattern[ i ] )
 458                     fields[ i ] = Ref.deref( t.fields[ i ] );
 459                 else if ( fields[ i ] instanceof Ref )
 460                     ((Ref) fields[ i ]).clear();
 461             }
 462         }
 463
 464         /**
 465          * Utility method to clear this tuple according to the key
 466          * pattern.
 467          */
 468         public void clear(boolean [] pattern) {
 469             for ( int i = 0; i < pattern.length; i++ ) {
 470                 if ( pattern[ i ] )
 471                     continue;
 472                 if ( fields[ i ] instanceof Ref )
 473                     ((Ref) fields[ i ] ).clear();
 474                 else
 475                     fields[ i ] = null;
 476             }
 477         }
 478
 479         /**
 480          * Determine whether a given query matches this tuple, by
 481          * comparing all non-null query fields with the tuple fields
 482          * using the equals method.
 483          *
 484          * @return <em>true</em> if this tuple matches the given query
 485          * tuple when ignoring its <em>null</em> fields, and
 486          * <em>false</em> otherwise.
 487          */
 488         public boolean match(Tuple query) {
 489             for ( int i = 0; i < fields.length; i++ ) {
 490                 Object x = Ref.deref( query.fields[ i ] );
 491                 if ( x == null )
 492                     continue;
 493                 if ( ! x.equals( Ref.deref( fields[ i ] ) ) )
 494                     return false;
 495             }
 496             return true;
 497         }
 498
 499         /**
 500          * Fill in the fields of a query from this tuple using the
 501          * given key pattern.
 502          */
 503         //@SuppressWarnings("unchecked")
 504         public void getFields(KeyPattern kp, Object [] output) {
 505             for ( int i = 0; i < fields.length; i++ ) {
 506                 if ( ! kp.pattern[ i ] ) {
 507                     if ( output[ i ] instanceof Ref )
 508                         ((Ref) output[ i ]).set( fields[ i ] );
 509                     else
 510                         output[ i ] = fields[ i ];
 511                 }
 512             }
 513         }
 514
 515         /**
 516          * Returns a given field value.
 517          */
 518         public Object getField(int index) {
 519             return fields[ index ];
 520         }
 521
 522         /**
 523          * Determine whether this tuple is equal to a given object.
 524          */
 525         public boolean equals(Object x) {
 526             return x instanceof Tuple? equals( (Tuple) x ) : false;
 527         }
 528
 529         /**
 530          * Determine whether this tuple is equal to another. The
 531          * method dereferences any {@link Ref} objects of both this
 532          * tuple and the other tuple.
 533          *
 534          * @return <em>true</em> if all field values (after
 535          * dereference) are equal, and <em>false</em> otherwise.
 536          */
 537         public boolean equals(Tuple x) {
 538             for ( int i = 0; i < fields.length; i++ ) {
 539                 if ( ! equalFields(
 540                          Ref.deref( fields[ i ] ),
 541                          Ref.deref( x.fields[ i ] ) ) )
 542                     return false;
 543             }
 544             return true;
 545         }
 546
 547         /**
 548          * Utility method to compare field values that may be
 549          * <em>null</em>.
 550          *
 551          * @return <em>true</em> if the field values are equal, and
 552          * <em>false</em> otherwise.
 553          */
 554         public boolean equalFields(Object a,Object b) {
 555             return ( a == null || b == null )? a == b : a.equals( b );
 556         }
 557
 558         /**
 559          * Compute a tuple hash code, by combining the dereferenced
 560          * field values in a deterministic way.
 561          *
 562          * <p> Note that tuples may have the same hash code without
 563          * being equal.
 564          *
 565          * @return the hash code.
 566          */
 567         public int hashCode() {
 568             int x = 0;
 569             for ( int i = 0; i < fields.length; i++ ) {
 570                 x <<= 2 ;
 571                 x += ( Ref.deref( fields[ i ] ) == null?
 572                        0 :
 573                        Ref.deref( fields[ i ] ).hashCode() );
 574             }
 575             return x;
 576         }
 577
 578         /**
 579          * Support method to queue up this tuple for removal from its
 580          * relation. Use method {@link #processPending} to process
 581          * delayed removals.
 582          *
 583          * <p> This method is intended to simplify the combination of
 584          * iterating over several tuples of the relation while
 585          * removing some of them, without this causing problems due to
 586          * {@link java.util.ConcurrentModificationException} being
 587          * thrown. (Please refer to notes about {@link
 588          * java.util.HashSet}).
 589          */
 590         public void delayedRemove() {
 591             addPending( this );
 592         }
 593
 594         /**
 595          * Returns a String representation of this tuple.
 596          */
 597         public String toString() {
 598             StringBuffer s = new StringBuffer("<");
 599             for ( int i = 0; i < fields.length; i++ ) {
 600                 if ( i > 0 )
 601                     s.append( "," );
 602                 s.append( fields[ i ] == null? "null" : fields[ i ].toString() );
 603             }
 604             s.append( ">" );
 605             return s.toString();
 606         }
 607
 608         /**
 609          * Utility method to collect Ref objects in the fields.
 610          */
 611         public Vector/*<Ref>*/ getRefs(Vector/*<Ref>*/ v) {
 612             for ( int i = 0; i < fields.length; i++ ) {
 613                 if ( fields[ i ] instanceof Ref ) {
 614                     Ref r = (Ref) fields[ i ];
 615                     if ( ! v.contains( r ) )
 616                         v.add( r );
 617                 }
 618             }
 619             return v;
 620         }
 621
 622     }
 623
 624     /**
 625      * Utility method for accessing the data table of a key pattern
 626      * and keying tuple.
 627      */
 628     public HashSet/*<Tuple>*/ getData(KeyPattern kp,Tuple tuple,boolean add) {
 629         Hashtable/*<Tuple,HashSet<Tuple>>*/ table =
 630             (Hashtable/*<Tuple,HashSet<Tuple>>*/) indexes.get( kp );
 631         if ( table == null ) {
 632             table = new Hashtable/*<Tuple,HashSet<Tuple>>*/();
 633             indexes.put( kp, table );
 634         }
 635         Tuple key = kp.getKey( tuple );
 636         HashSet/*<Tuple>*/ data = (HashSet/*<Tuple>*/) table.get( key );
 637         if ( add && data == null ) {
 638             data = new HashSet/*<Tuple>*/();
 639             table.put( key, data );
 640         }
 641         return data;
 642     }
 643
 644     /**
 645      * Utility method to obtain an iterator over existing key
 646      * patterns.
 647      */
 648     public Iterator/*<KeyPattern>*/ keyPatterns() {
 649         return indexes.keySet().iterator();
 650     }
 651
 652     /**
 653      * Access method to add a tuple to the relation. Returns false if
 654      * the relation already contains the tuple. Otherwise all tables
 655      * are updated, and the method returns true.
 656      *
 657      * <p> Note that all values a dereferenced before being added to
 658      * the relation.
 659      *
 660      * @return <em>true</em> if the relation is changed, and
 661      * <em>false</em> otherwise.
 662      *
 663      * @see #runtimeTyping
 664      * @see #remove
 665      */
 666     synchronized public boolean add(Object/*...*/ [] values)
 667         throws ArityException, ColumnTypeException
 668     {
 669         runtimeTyping( values );
 670
 671         for ( int i=0; i < values.length; i++ )
 672             values[ i ] = Ref.deref( values[ i ] );
 673
 674         Tuple tuple = new Tuple( values );
 675
 676         HashSet/*<Tuple>*/ data = getData( main_key, tuple, true );
 677         if ( data.contains( tuple ) ) {
 678             return false;
 679         }
 680
 681         applyConstraints( tuple );
 682
 683         for (Iterator/*<KeyPattern>*/ kpi = keyPatterns(); kpi.hasNext(); ) {
 684             getData( (KeyPattern) kpi.next(), tuple, true ).add( tuple );
 685         }
 686
 687         setChanged();
 688         notifyObservers();
 689         return true;
 690     }
 691
 692     /**
 693      * Access method to remove a tuple from the relation. Returns
 694      * false if the tuple is missing from the relation. Otherwise all
 695      * tables are updated, and the method returns true.
 696      *
 697      * @see #runtimeTyping
 698      * @see #add
 699      */
 700     synchronized public boolean remove(Object/*...*/ [] values)
 701         throws ArityException, ColumnTypeException
 702     {
 703         if ( removeQuietly( values ) ) {
 704             setChanged();
 705             notifyObservers();
 706             return true;
 707         }
 708         return false;
 709     }
 710
 711     /**
 712      * Internal working method to remove tuples without notifying any
 713      * observer. The remove function is split up in this way in order
 714      * to allow the {@link #add} method to apply the key constraints
 715      * without notifications of key constraint knock-outs.
 716      */
 717     public boolean removeQuietly(Object/*...*/ [] values)
 718         throws ArityException, ColumnTypeException
 719     {
 720         runtimeTyping( values );
 721         Tuple tuple = new Tuple( values );
 722
 723         HashSet/*<Tuple>*/ data = getData( main_key, tuple, true );
 724         if ( !data.contains( tuple ) )
 725             return false;
 726
 727         for (Iterator/*<KeyPattern>*/ kpi = keyPatterns(); kpi.hasNext(); ) {
 728             getData( (KeyPattern) kpi.next(), tuple, true ).remove( tuple );
 729         }
 730         return true;
 731     }
 732
 733     /**
 734      * Returns the size of the relation, i.e., the number of key
 735      * tuples in the {@link #main_key} collection.
 736      */
 737     synchronized public int size() {
 738         Hashtable/*<Tuple,HashSet<Tuple>>*/ table =
 739             (Hashtable/*<Tuple,HashSet<Tuple>>*/) indexes.get( main_key );
 740         return table == null? 0 : table.size();
 741     }
 742
 743     /**
 744      * Returns the projected size of the relation, i.e., the number of
 745      * tuples matching to the tuple of the given values, with null
 746      * values (or unbound Ref objects) indicating non-key columns.
 747      */
 748     public int size(Object/*...*/ [] values) {
 749         return size( new Tuple( values ) );
 750     }
 751
 752     /**
 753      * Returns the projected size of the relation, i.e., the number of
 754      * tuples matching to the given key tuple.
 755      */
 756     synchronized public int size(Tuple key) {
 757         try {
 758             KeyPattern kp = new KeyPattern( key.fields );
 759             if ( indexes.get( kp ) == null ) {
 760                 return 0;
 761             }
 762             HashSet/*<Tuple>*/ data = getData( kp, key, false );
 763             return data == null? 0 : data.size();
 764         } catch (Exception e) {
 765             e.printStackTrace();
 766             return 0;
 767         }
 768     }
 769
 770     /**
 771      * Utility method to populate a HashSet matching to a key
 772      */
 773     public void populate(KeyPattern kp)
 774     {
 775         Hashtable/*<Tuple,HashSet<Tuple>>*/ table =
 776             new Hashtable/*<Tuple,HashSet<Tuple>>*/();
 777         indexes.put( kp, table );
 778         HashSet/*<Tuple>*/ db = getData( main_key, new Tuple(), true );
 779         for ( Iterator/*<Tuple>*/ i = db.iterator(); i.hasNext(); ) {
 780             Tuple t = (Tuple) i.next();
 781             HashSet/*<Tuple>*/ data = getData( kp, kp.getKey( t ), true );
 782             data.add( t );
 783         }
 784     }
 785
 786     /**
 787      * Utility method to obtain an Iterator for the tuple set that
 788      * matches the given key values.
 789      */
 790     public Iterator/*<Tuple>*/ query(Object/*...*/ [] values)
 791         throws ArityException, ColumnTypeException
 792     {
 793         runtimeTyping( values );
 794         Tuple key = new Tuple( values );
 795         return query( key );
 796     }
 797
 798     /**
 799      * Utility method to obtain an Iterator for the tuple set that
 800      * matches the given key tuple.
 801      */
 802     synchronized public Iterator/*<Tuple>*/ query(Tuple key)
 803         throws ArityException, ColumnTypeException
 804     {
 805         KeyPattern kp = new KeyPattern( key.fields );
 806         if ( indexes.get( kp ) == null ) {
 807             populate( kp );
 808         }
 809         HashSet/*<Tuple>*/ data = getData( kp, key, true );
 810         return data.iterator();
 811     }
 812
 813     /**
 814      * The Cursor class provides Query processing support for a
 815      * relation.
 816      */
 817     public class Cursor implements Query {
 818
 819         /**
 820          * A {@link Relation.Tuple} object that is updated for new
 821          * mathing values.
 822          */
 823         public Tuple output;
 824
 825         /**
 826          * The querying key pattern.
 827          */
 828         public KeyPattern key_pattern;
 829
 830         /**
 831          * The result iterator.
 832          */
 833         public Iterator/*<Tuple>*/ current;
 834
 835         /**
 836          * Constructor for key values. Output fields are marked by
 837          * {@link Ref} objects of <em>null</em> values, and ignored
 838          * fields are marked by <em>null</em>.
 839          */
 840         public Cursor(Object/*...*/ [] values)
 841             throws ArityException, ColumnTypeException
 842         {
 843             output = new Tuple( values );
 844             key_pattern = new KeyPattern( output.fields );
 845             reset();
 846         }
 847
 848         /**
 849          * The {@link Query#copy} method implemented by creating a new
 850          * Cursor with new {@link Ref} objects.
 851          */
 852         //@SuppressWarnings("unchecked")
 853         public Query copy(Vector/*<Ref>*/ newrefs) throws Exception {
 854             Object [] fields = copyArray( output.fields );
 855             for ( int i = 0; i < fields.length; i++ ) {
 856                 if ( fields[ i ] instanceof Ref ) {
 857                     fields[ i ] = ((Ref) fields[ i ]).find( newrefs );
 858                 }
 859             }
 860             return new Cursor( fields );
 861         }
 862
 863         /**
 864          * The {@link Query#reset} method implemented by recomputing
 865          * the key pattern and the matching tuple set.
 866          */
 867         public void reset()
 868             throws ArityException, ColumnTypeException
 869         {
 870             key_pattern = new KeyPattern( output.fields );
 871             current = query( key_pattern.getKey( output ) );
 872         }
 873
 874         /**
 875          * The {@link Query#next} method implemented by binding the
 876          * output {@link Ref} objects for the next match.
 877          */
 878         public boolean next() {
 879             if ( ! current.hasNext() ) {
 880                 output.clear( key_pattern.pattern );
 881                 return false;
 882             }
 883             ((Tuple) current.next()).getFields( key_pattern, output.fields );
 884             return true;
 885         }
 886
 887         /**
 888          * The {@link Query#getRefs} method implemented by returning the
 889          * {@link Ref} objects given to this Cursor object.
 890          */
 891         public Vector/*<Ref>*/ getRefs(Vector/*<Ref>*/ v) {
 892             return output.getRefs( v );
 893         }
 894
 895         /**
 896          * The {@link Query#addObserver} method implemented by adding
 897          * the observer to the relation.
 898          */
 899         public void addObserver(Observer x) {
 900             Relation.this.addObserver( x );
 901         }
 902
 903         /**
 904          * The {@link Query#deleteObserver} method implemented by
 905          * removing the observer from the relation.
 906          */
 907         public void deleteObserver(Observer x) {
 908             Relation.this.deleteObserver( x );
 909         }
 910
 911         /**
 912          * Implements the {@link Query#addable} method by verifying
 913          * that all {@link Ref} objects are non-<em>null</em>.
 914          */
 915         public boolean addable()
 916         {
 917             return output.nullCount() == 0;
 918         }
 919
 920         /**
 921          * The {@link Query#add} method implemented by adding to
 922          * current output tuple to the relation, provided that all its
 923          * {@link Ref} objects are non-<em>null</em>.
 924          */
 925         public boolean add()
 926         {
 927             try {
 928                 if ( output.nullCount() == 0 ) {
 929                     Object [] fields = new Object [ output.fields.length ];
 930                     System.arraycopy(
 931                         output.fields, 0, fields, 0, fields.length );
 932                     return Relation.this.add( fields );
 933                 }
 934             } catch (Exception e) {
 935                 e.printStackTrace();
 936                 System.err.println( "** ignored **" );
 937             }
 938             return false;
 939         }
 940
 941         /**
 942          * Implements {@link Query#removable} by checking that the
 943          * indicated tuple is stored.
 944          */
 945         public boolean removable() {
 946             HashSet/*<Tuple>*/ data = getData( main_key, output, true );
 947             return data.contains( output );
 948         }
 949
 950         /**
 951          * Implements {@link Query#remove} by removing the indicated
 952          * tuple.
 953          *
 954          * @return <em>true</em> if tuple was removed, and
 955          * <em>false</em> otherwise.
 956          */
 957         public boolean remove() {
 958             try {
 959                 return Relation.this.remove( output.fields );
 960             } catch (Exception e) {
 961                 e.printStackTrace();
 962                 return false;
 963             }
 964         }
 965
 966         /**
 967          * Returns a {link java.lang.String} representation of this
 968          * Cursor. This uses the {@link Relation#name} field as well
 969          * as the {@link Ref#name} field of any {@link Ref} object
 970          * involved (both input and output).
 971          */
 972         public String toString() {
 973             StringBuffer s = new StringBuffer();
 974             s.append( Relation.this.name );
 975             s.append( "(" );
 976             for ( int i = 0; i < output.fields.length; i++ ) {
 977                 if ( i > 0 )
 978                     s.append( "," );
 979                 s.append( " " );
 980                 if ( output.fields[ i ] instanceof Ref ) {
 981                     s.append( ((Ref) output.fields[ i ] ).getName() );
 982                     s.append( "=" );
 983                 }
 984                 s.append( output.fields[ i ] );
 985             }
 986             s.append( " )" );
 987             return s.toString();
 988         }
 989
 990     }
 991
 992     /**
 993      * An interface method to obtain a {@link Query} implementation
 994      * object, {@link Relation.Cursor} for given key. The output
 995      * fields would be marked by <em>null</em> valued {@link Ref}
 996      * objects, which get successively assigned for the matching
 997      * tuples.
 998      */
 999     public Query get(Object/*...*/ [] values) throws Exception {
1000         return new Cursor( values );
1001     }
1002
1003     /**
1004      * Interface method to obtain the Inquirable name.
1005      */
1006     public String getName() {
1007         return name;
1008     }
1009
1010     //
1011     // Pending removal support
1012     //
1013
1014     /**
1015      * Transient support for delayed removal of tuples.
1016      */
1017     public HashSet/*<Tuple>*/ pending;
1018
1019     /**
1020      * Adds a tuple to the pending table.
1021      *
1022      * @see Relation.Tuple#delayedRemove
1023      */
1024     synchronized public void addPending(Tuple t) {
1025         if ( pending == null )
1026             pending = new HashSet/*<Tuple>*/();
1027         pending.add( t );
1028     }
1029
1030     /**
1031      * Utility method to remove all pending tuples. Invokes {@link
1032      * #processPending(boolean)} with argument <em>true</em>.
1033      * @return <em>true</em> if the relation is changed, and
1034      *<em>false</em> otherwise.
1035      *
1036      * @return <em>true</em> if the relation is changed, and
1037      * <em>false</em> otherwise.
1038      *
1039      * @see #processPending(boolean)
1040      */
1041     synchronized public boolean processPending()
1042     {
1043         return processPending( true );
1044     }
1045
1046     /**
1047      * Utility method to remove all pending tuples. The noise argument
1048      * marks whether (<em>true</em>) or not (<em>false</em>) to notify
1049      * observers if the relation is changed.
1050      *
1051      * @return <em>true</em> if the relation is changed, and
1052      *<em>false</em> otherwise.
1053      *
1054      * @see #removeQuietly
1055      */
1056     synchronized public boolean processPending(boolean noise)
1057     {
1058         if ( pending == null )
1059             return false;
1060         boolean removed = false;
1061         for ( Iterator/*<Tuple>*/ i = pending.iterator(); i.hasNext(); ) {
1062             try {
1063                 removed |= removeQuietly( ((Tuple) i.next()).fields );
1064             } catch (Exception e) {
1065                 System.err.println( "processPending: " + e.toString() );
1066             }
1067         }
1068         pending = null;
1069         if ( noise && removed ) {
1070             setChanged();
1071             notifyObservers();
1072         }
1073         return removed;
1074     }
1075
1076     ///
1077     /// Convenience methods
1078     ///
1079
1080     /**
1081      * Convenience method for unary relation key constraint setting.
1082      */
1083     public void addConstraint(boolean x)
1084         throws ArityException {
1085         addConstraint( new boolean [] { x } );
1086     }
1087
1088     /**
1089      * Convenience method for unary relation assertion.
1090      */
1091     public boolean add(Object x)
1092         throws ArityException, ColumnTypeException {
1093         return add( new Object [] { x } );
1094     }
1095
1096     /**
1097      * Convenience method for unary relation retraction.
1098      */
1099     public boolean remove(Object x)
1100         throws ArityException, ColumnTypeException {
1101         return remove( new Object [] { x } );
1102     }
1103
1104
1105     /**
1106      * Convenience method for binary relation key constraint setting.
1107      */
1108     public void addConstraint(boolean x1,boolean x2)
1109         throws ArityException {
1110         addConstraint( new boolean [] { x1, x2 } );
1111     }
1112
1113     /**
1114      * Convenience method for binary relation assertion.
1115      */
1116     public boolean add(Object x1,Object x2)
1117         throws ArityException, ColumnTypeException {
1118         return add( new Object [] { x1, x2 } );
1119     }
1120
1121     /**
1122      * Convenience method for binary relation retraction.
1123      */
1124     public boolean remove(Object x1,Object x2)
1125         throws ArityException, ColumnTypeException {
1126         return remove( new Object [] { x1, x2 } );
1127     }
1128
1129
1130     /**
1131      * Convenience method for tertiary relation key constraint setting.
1132      */
1133     public void addConstraint(boolean x1,boolean x2,boolean x3)
1134         throws ArityException {
1135         addConstraint( new boolean [] { x1, x2, x3 } );
1136     }
1137
1138     /**
1139      * Convenience method for tertiary relation assertion.
1140      */
1141     public boolean add(Object x1,Object x2,Object x3)
1142         throws ArityException, ColumnTypeException {
1143         return add( new Object [] { x1, x2, x3 } );
1144     }
1145
1146     /**
1147      * Convenience method for tertiary relation retraction.
1148      */
1149     public boolean remove(Object x1,Object x2,Object x3)
1150         throws ArityException, ColumnTypeException {
1151         return remove( new Object [] { x1, x2, x3 } );
1152     }
1153
1154     /**
1155      * Returns a String representation of this relation.
1156      */
1157     public String toString() {
1158         return indexes.toString();
1159     }
1160 }