The explanation below gives you a refresher on Batory's
work on class library generators.

We would like to use the Enumeration interface of Java
to iterate through collections, as Doug says.
This will require that P3 generates implementations of the
Enumeration interface.

P3 also seems to make assumptions about the repeated classes
which we need to resolve.

The example at the end tells you what kind of container
classes Jakarta/P3 can generate from small specs.

-- Karl

From dsb@cs.utexas.edu Tue Aug  5 12:11:38 1997
From: "Don Batory" <dsb@cs.utexas.edu>
To: lieber@ccs.neu.edu, dougo@ccs.neu.edu
Subject: comments
Cc: dsb@cs.utexas.edu

Doug, Karl:

I read the messages that you sent.  I have some suggestions to get you
to start thinking about the capabilities of P3, and to see where the
best fit with Demeter would lie.  

Doug - I recommend that you check the web page 

http://www.cs.utexas.edu/users/schwartz/

click on "Getting Started", and download and read the "Scalable
Software Libraries" paper and either of the "Reengineering..."
or "P2: A Lightweight..." papers.  The key ideas that you should
take from these papers are:

(1) P2/P3 provides a set of building blocks for creating very 
    complex containers.

(2) Access to elements of containers is via predicates (and not
    position).  Access to elements by position is something that
    we will add to P3, but this addition is rather simple.

(3) Access to containers (via cursors) is through a relational
    database paradigm.  More on this below.

Now, to your notes.  You presented me with the current Demeter/Java
container interface:

  public void addElement(Elt e);    // add to end
  public void push(Elt e);          // add to beginning
  public java.util.Enumeration elements();
  public int size();
  public boolean isEmpty();   

I assume that size() returns the number of elements in the container,
isEmpty() effectively tests the boolean (container.size() != 0). Right?

I don't know what the elements() method is, as it isn't part of
java.util.Enumeration.  I presume that you mean the two methods
of the Enumeration interface, right?  

addElement() and push() are useful if elements are stored in containers
that basically don't maintain key ordering of elements. Right?

Here's an overview of the P3 interface.  Containers and cursors are
declaratively specified.  Suppose I want a container of elements of
type foo, where foo has string attribute A and integer attribute B.
foo must be declared in the following way:

class foo {
   protected String A;
   protected int    B;

   public String A() { return A; }           // accessor to attribute A
   public int    B() { return B; }           // accessor to attribute B

   public String A( A x ) { return A = x; }  // modifier of attribute A
   public int    B( B x ) { return B = x; }  // modifier of attribute B

   ...
}

Note: P3 recognizes an attribute Z of type Q of a class if it sees the
following declarations:

     protected Q Z;
     public Q Z() { ... };
     public Q Z( Q x ) { ... };

That is, there is a protected data member Z, with an accessor and modifier
methods.  What exactly goes on in the accessor or modifier is up to the
user, but the typical bodies are illustrated above in class foo.  There
can be any number of other data members or methods.  However, for things
to work correctly, all accesses and updates of attributes (both by methods
defined inside a class and outside the class) *must* be through the accessors
and modifiers.

P3 generates class hierarchies (or really frameworks).  There are two
abstract classes: an abstract container class and an abstract cursor (iterator)
class.  Concrete subclasses of the abstract container class are (different)
concrete implementations of containers.  Concrete subclasses of the abstract
cursor class are concrete implementations of cursors (which will work only
with specific concrete container classes).

To declare an abstract container class "foocont" which stores elements of type foo, 
one writes in P3:

container<foo> foocont;

To declare an abstract cursor class "foocurs" that ranges over the abstract
container class foocont, one writes:

cursor<foocont> foocurs;

Both of these declarations are needed in any P3 program.  (At reduction time,
P3 replaces these declarations with the pure-Java class declarations).

To define a concrete container of foocont, named cont1, where foo elements are stored
on two distinct ordered lists, where the first list orders its elements
on attribute A and the second list orders its elements on attribute B, one
writes in P3:

container cont1                                // name of the concrete class to generate
   extends foocont                             // name of its abstract container class
   using odlist( A, odlist( B, malloc( ) ) );  // type equation to define implementation

This declaration will generate a class cont1 where each instance of cont1
will be a container object.  In many cases (e.g., look at the relational
database literature), there is only one instance of a container class.
(i.e., one defines a relation and there is but one instance of it).  Certain
optimizations can be made in these cases.  To declare that there will only
be one instance of a container class, use the modifier "static" in front
of the container declaration, e.g.:

static container cont1 
   extends foocont
   using odlist( A, odlist( B, malloc( ) ) );

For creating monitors, the modifier "synchronized" is used in front
of the container declaration, e.g.:

synchronized container cont1 
   extends foocont
   using odlist( A, odlist( B, malloc( ) ) );

Of course, synchronized static containers are also possible.

Here are some other sample declarations:

container cont2
   extends foocont
   using dlist( malloc() );    // container that is a doubly-linked list

container cont3
   extends foocont
   using rbtree( A, hash( B, 40, malloc() ) );

                               // container that stores elements onto a red-black tree
                               // with key A; the same elements are stored in a hash
                               // table with 40 buckets hashing attribute B.

And so on.

Among the building blocks that we have now in P3 are:

   rbtree       red-black trees
   bintree      binary trees
   dlist        doubly-linked lists
   odlist       ordered doubly-linked list
   predindx     predicate index (links together elements that satisfies a predicate)
   hashcmp      hash-speedup of equality comparisons
   hash         hash table
   malloc       storage of container in transient memory

more to follow...

To declare concrete cursors, one optionally must specify a selection predicate
and a sort declaration.  The selection predicate is a predicate that elements
to be retrieved must satisfy.  Thus, the predicate defines the subset of elements
of a container to retrieve.  If there is a particular order in which these
elements are to be retrieved, then a sort declaration is used.  Here are
some examples.

A cursor class "all" that ranges over all elements of cont1 containers is defined by:

cursor all( cont1 e );

A cursor class "some" that ranges over elements of cont1 containers that
satisfy the predicate A == "Don" && B == 4 is defined by:

cursor some( cont1 e ) where A() == "Don" && B() == 4;

A cursor class "some_ordered" that retrieves the same elements as some, but in
attribute B order is defined by:

cursor some_ordered( cont1 e ) where A() == "Don" && B() == 4 orderby B;

A cursor class "parameterized_some" that ranges over elements of cont1
containers that satisfy the predicate "B < x", where x is a parameter of
the cursor is defined by:

cursor parameterized_some( cont1 e, int x ) where B() < x;

There are other features, but this should give you the idea.  At reduction
time, P3 replaces the above specifications with pure-Java class implementations
of the declared classes.

Note: all attributes have the operators <, <=, ==, !=, >=, >.  P3 does
the appropriate translation into pure Java.  Besides integers and Strings, 
arbitrary object types can be attribute types.  < is translated into the method
gtr(), <= maps to geq(), etc.  Thus, a standard set of comparison methods should
be present if user-defined types are to be used as P3 attribute types.

Here's the current P3 abstract container interface that's generated - 
you'll see that it is rather simple, and is extensible (e.g., to handle
the size() operation).

abstract class foocont {
   abstract boolean is_full();
   abstract void insert( foo e );
   abstract void insert( String A, int B );
} 

There are two insert operations - the first is essentialy a copy constructor,
the second takes the individual attributes of an element and creates an element
directly from it.

The current P3 abstract cursor interface is a bit more complex:

abstract class foocurs {
   abstract foo obj();
   abstract void insert( foo e );
   abstract void insert( String A, int B );
   abstract foo first();
   abstract boolean more();
   abstract foo next();
   abstract void remove();
}

the obj() method returns the currently referenced element of a cursor.

the insert methods are the same as that for containers, and is a hold-over
from non-OO designs of embedded relational query languages.  May be removed
in the future.

first, more, next are used to iterate through the elements (that satisfy the
selection predicate of a concrete cursor, returned in the appropriate order)

remove deletes the current element from a container.

here's some sample source code:

cont1 c = new cont1();            // create a container c
all   a = new all(c);             // create an "all" cursor
some  s = new some(c);            // create a "some" cursor
foo   e;                          // element variable

for (...) {                       // manufacture element e and insert it
   c.insert(e);                   // into container c
}

for (a.first(); a.more(); a.next()) {  
   // print all elements
   e = a.obj();
   e.print();
}

for (e = s.first().obj(); s.more(); e = s.next().obj()) { 
   // print and then delete all elements that satisfy the predicate
   // A = "Don" && B == 4;
   e.print();
   s.remove();
}

// for the remaining elements, increment the B attribute

for (a.first(); a.more(); a.next()) {  
   // print all elements
   e = a.obj();
   e.B( e.B() + 1);
}


In general, P3 programmers can update attributes at random, not having
to know if attributes are key fields (of trees, ordered lists etc.). P3
will update its data structures automatically, so that P3 users can
concentrate on the application at hand, rather than on container data
structure details.

For your interest, I'm including the source code for some test programs.
Some of these programs are P3 programs, others are those that P3 generated,
the last program is one that tests the P3 program.

if you have questions, you know where to reach me.

don

-------------------------
// a P3 program

interface empty { };

container<emp> empcont;

cursor<empcont> empcursor;

static container empcont1 extends empcont implements empty
   using odlist( empno, malloc( ) );

cursor old(empcont1 e) where age() > 40   && age() < 50 /*orderby name*/;

cursor all(empcont1 e);

cursor allname(empcont1 e, int x ) where age() == x orderby name;

cursor allname1(empcont1 e) deletion update age, name where name() =="Don";

------------------------
// the generated java program

interface empty { }; abstract class empcont {
   abstract boolean is_full();
   abstract void insert( emp e );
   abstract void insert( int empno, int age, java.lang.String dept, java.lang.String name );
} abstract class empcursor {
   abstract emp obj();
   abstract void insert( emp e );
   abstract void insert( int empno, int age, java.lang.String dept, java.lang.String name );
   abstract emp first();
   abstract boolean more();
   abstract emp next();
   abstract void remove();
}
final class empcont1 extends empcont implements empty { emp_1 first_1, last_1; empcont1() { 
      if ( emp_1.cont == null ) emp_1.cont = this;
      else { System.err.println("Error: creating more than one instance");
             System.exit(1);
      }
     first_1 = last_1 = null;
   }

   public boolean is_full() {
      return false;
   }

   public void insert( emp e ) {
      new emp_1 ( this, e );
   }

   public void insert( int empno, int age, java.lang.String dept, java.lang.String name ) {
      new emp_1( this, empno, age, dept, name );
   }
     }
final class emp_1 extends emp { static public empcont1 cont = null; emp_1 left_1, right_1; emp_1 ( ) { } emp_1 ( empcont1 c, emp e ) {
     super(e);
      odlist_relink_1();
   } emp_1 ( empcont1 c, int empno, int age, java.lang.String dept, java.lang.String name ) {
     super( empno, age, dept, name );
      odlist_relink_1();
   }
   final void odlist_relink_1( ) { emp_1 tmp;
  
      // Step 1: if container is empty, add first element

      if (cont.first_1 == null) {
         right_1 = left_1 = null;
         cont.first_1 = cont.last_1 = this;
         return;
      }

      // Step 2: see if the element becomes the first element of a nonnull list

      if ( cont.first_1. empno() >= empno ) {
         right_1 = cont.first_1;
         left_1  = null;
         right_1.left_1 = this;
         cont.first_1 = this;
         return;
      }

      // Step 3: if not head, find element to the immediate right of insertion point

      for (tmp = cont.first_1; tmp != null && tmp. empno() < empno; tmp = tmp.right_1 );

      // Step 4: add to end of list (if tmp == null); note list might be empty

      if (tmp == null) {
          if (cont.last_1 == null) {
             cont.first_1 = cont.last_1 = this;
             left_1 = right_1 = null;
             return;
          }
          left_1 = cont.last_1;
          right_1 = null;
          cont.last_1 = this;
          left_1.right_1 = this;
          return;
      }

      // Step 5: else, add to middle of list

      right_1 = tmp;
      left_1  = tmp.left_1;
      if (left_1 != null) left_1.right_1 = this;
      tmp.left_1 = this;
   }
   final void odlist_unlink_1() {
      if (left_1 != null) left_1.right_1 = right_1;
      if (right_1 != null) right_1.left_1 = left_1;
      if (cont.first_1 == this) cont.first_1 = right_1;
      if (cont.last_1 == this) cont.last_1 = left_1;
   }
                   public int empno() { return empno; }
                   public int age() { return age; }
                   public java.lang.String dept() { return dept; }
                   public java.lang.String name() { return name; }
                   public int empno( int _newvalue ) { 
      odlist_unlink_1(); empno = _newvalue;
      odlist_relink_1();
                      return empno; 
                   }
                   public int age( int _newvalue ) { age = _newvalue;
                      return age; 
                   }
                   public java.lang.String dept( java.lang.String _newvalue ) { dept = _newvalue;
                      return dept; 
                   }
                   public java.lang.String name( java.lang.String _newvalue ) { name = _newvalue;
                      return name; 
                   }
}

abstract class empcursor_1 extends empcursor {

   // encapsulates only added data members and insert/remove methods

   public emp_1 obj;
   public empcont1 cont;

   public emp obj() { return obj; }

   public void insert( emp e ) {
      obj = new emp_1 ( cont, e );
   }

   public void insert( int empno, int age, java.lang.String dept, java.lang.String name ) {
      obj = new emp_1( cont, empno, age, dept, name );
   }

   // note: once element is unlinked, it is effectively deleted from the container
   //       and will be garbage collected by Java once the cursor no longer points
   //       to it.

   public void remove() {
      obj.odlist_unlink_1();
   }
      final protected void adv_1() { obj = obj.right_1; }
      final protected void start_1() { obj = cont.first_1; }
      final protected void back_1() { obj = obj.left_1; }
      final protected void end_1() { obj = cont.last_1; }
}
final class old extends empcursor_1 { // cursor-specific generated fields

   public old (empcont1 cont000 ) {
      obj = null; cont = cont000;
   }

   public emp first() { start_1();
       while ( obj != null && !( obj. age() > 40 && obj. age() < 50) ) { adv_1();
       }
      return obj;
   }

   public boolean more() {
      return obj != null;
   }

   public emp next() { adv_1();
       while ( obj != null && !( obj. age() > 40 && obj. age() < 50) ) { adv_1();
       }
      return obj;
   }
}
final class all extends empcursor_1 { // cursor-specific generated fields

   public all (empcont1 cont000 ) {
      obj = null; cont = cont000;
   }

   public emp first() { start_1();
      return obj;
   }

   public boolean more() {
      return obj != null;
   }

   public emp next() { adv_1();
      return obj;
   }
}
final class allname extends empcursor_1 { public int x;
         java.util.Vector vbuf_39; emp_1 []      buffer_39;
         int              index_39;
         int              asize_39; // cursor-specific generated fields

   public allname (empcont1 cont000, int x000 ) {
      obj = null; cont = cont000; x = x000;
   }

   public emp first() {
         vbuf_39 = new java.util.Vector( ); start_1();
       while ( obj != null && !( obj. age() == x) ) { adv_1();
       }
         while ( obj != null ){
            vbuf_39.addElement( obj ); adv_1();
       while ( obj != null && !( obj. age() == x) ) { adv_1();
       }
         }

         asize_39 = vbuf_39.size( );
         buffer_39 = new emp_1[asize_39 + 1];
         vbuf_39.copyInto( buffer_39 );
         /* 
          * add an extra null element to the array so that the 
          * code for nextMethod() could be as simple as possible
          */
         buffer_39[asize_39] = null;
            int incr = asize_39 / 2;
            while ( incr >= 1 ) {
               for ( int i = incr; i < asize_39; i++ ) { emp_1 tmp = buffer_39[i];
                  int j = i;
                  while ( j >= incr && tmp. name().compareTo( 
               buffer_39[j - incr]. name( )) <0 ) {
                     buffer_39[j] = buffer_39[j - incr];
                     j-= incr;
                  }
                  buffer_39[j] = tmp;
               }
               incr /= 2;
            }

         /* return the first element */
         obj = buffer_39[0];
         index_39 = 1;
      return obj;
   }

   public boolean more() {
      return index_39 <= asize_39;
   }

   public emp next() { obj = buffer_39[index_39++];
      return obj;
   }
}
final class allname1 extends empcursor_1 { // cursor-specific generated fields

   public allname1 (empcont1 cont000 ) {
      obj = null; cont = cont000;
   }

   public emp first() { start_1();
       while ( obj != null && !( obj.name().compareTo("Don") == 0) ) { adv_1();
       }
      return obj;
   }

   public boolean more() {
      return obj != null;
   }

   public emp next() { adv_1();
       while ( obj != null && !( obj.name().compareTo("Don") == 0) ) { adv_1();
       }
      return obj;
   }
}
----------------------
// a test program that should run it:

/* this java file illustrates the basic organization of classes that will
   be generated by P3.
*/

class basic {

   public static void main( String args[] ) {
      empcont   ec;
      empcursor all;
      empcursor moreall;
      empcursor some;
      empcont1  ec1;
      emp       obj;

      emp[] rawdata = {
                         new emp( 10000,60,"Biology","Akers, Mark" ),
                         new emp( 10070,22,"CompSci","Andrews, Kay" ),
                         new emp( 10020,21,"Biology","Alexander, Joe" ),
                         new emp( 10010,40,"Physics","Akin, Monica" ),
                         new emp( 10050,42,"Biology","Akerson, Suzanne" ),
                         new emp( 10040,53,"Astrono","Akerson, Mary" ),
                         new emp( 10060,61,"CompSci","Andrews, John" ),
                         new emp( 10030,23,"Biology","Akerson, Gwyn" )
                      };
      int i;

      ec = ec1 = new empcont1();
      all = new all( ec1 );
      moreall = new all( ec1 );
      some = new old( ec1 );

      System.out.println("original employee data\n");

      for (i=0; i<rawdata.length; i++) {
         all.insert(rawdata[i]);
         all.obj().print();
      }

      System.out.println("increment ages of all employees\n\n");

      for (obj = all.first(); all.more(); obj = all.next()) {
         obj.print();
         obj.birthday();
      }

      System.out.println("read again");
    
      for (all.first(); all.more(); all.next()) {
         all.obj().print();
      }

      System.out.println("print old emps and delete\n\n");

      for (some.first(); some.more(); some.next()) {
         some.obj().print();
         some.remove();
         for (moreall.first(); moreall.more(); moreall.next()) {
            System.out.print("   ");
            moreall.obj().print();
         }
      }

      System.out.println("print remaining emps\n\n");

      for (all.first(); all.more(); all.next()) {
         all.obj().print();
      }

      System.out.println("\n\nDone");
   }
}