---

OpenList.java

Go to the documentation of this file.

class OpenList
{
public static String defaultLeftParen  = "[";
public static String defaultRightParen = "]";
public static String defaultSpacer     = ", ";

final public static OpenList nil = cons(null, null);  // cell for empty list

private Object First;                           // First element in the list
private OpenList Rest;                          // Rest of the list

// Constructor

private OpenList(Object _First, OpenList _Rest)
  {
  First = _First;
  Rest = _Rest;
  }


public static OpenList cons(Object _First, OpenList _Rest)
  {
  return new OpenList(_First, _Rest);
  }

public Object first() throws OpenListException
  {
  if( isEmpty() ) 
    {
    throw new OpenListException("first() of empty list");
    }
  return First;
  }

public static Object first(OpenList List) throws OpenListException
  {
  return List.first();
  }

public OpenList rest() throws OpenListException
  {
  if( isEmpty() ) 
    {
    throw new OpenListException("rest() of empty list");
    }
  return Rest;
  }

public static OpenList rest(OpenList List) throws OpenListException
  {
  return List.rest();
  }

public boolean isEmpty()
  {
  return this == nil;
  }

public boolean nonEmpty()
  {
  return this != nil;
  }

public static boolean isEmpty(OpenList List)
  {
  return List.isEmpty();
  }

public static boolean nonEmpty(OpenList List)
  {
  return List.nonEmpty();
  }


public static OpenList append(OpenList L1, OpenList L2)
  {
  if( L1.isEmpty() )
    {
    return L2;
    }
  else
    {
    return cons(L1.first(), append(L1.rest(), L2));
    }
  }


public static OpenList reverse(OpenList L1)
  {
  OpenList result = nil;

  while( L1.nonEmpty() )
    {
    result = cons(L1.first(), result);
    L1 = L1.rest();
    }
  return result;
  }

public int length()
  {
  OpenList L  = this;
  int result = 0;
  while( L.nonEmpty() )
    {
    L = L.rest();
    result++;
    }
  return result;
  }

public Object nth(int n)
  {
  OpenList L  = this;

  while( n > 0 )
    {
    L = L.rest();
    n--;
    }

  return L.first();
  }


public OpenList prefix(int n)
  {
  if( n > 0 )
    {
    return cons(first(), rest().prefix(n-1));
    }

  return nil;
  }


public static OpenList list()
  {
  return nil;
  }

public static OpenList list(Object x0)
  {
  return cons(x0, list());
  }


public static OpenList list(Object x0, Object x1)
  {
  return cons(x0, list(x1));
  }


public static OpenList list(Object x0, Object x1, Object x2)
  {
  return cons(x0, list(x1, x2));
  }


public Object second()
  {
  return rest().first();
  }

public Object third()
  {
  return rest().rest().first();
  }

public static OpenList map(Function1 f, OpenList L)
  {
  if( L.isEmpty() )
    return nil;
  else
    return cons(f.apply(L.first()), map(f, L.rest()));
  }

public OpenList map(Function1 f)
  {
  return map(f, this);
  }


public Object reduce(Function2 b, Object u)
  {
  OpenList L = this;
  Object result = u;
  while( L.nonEmpty() )
    {
    result = b.apply(result, L.first());
    L = L.rest();
    }  
  return result;
  }


/**
 * merge two sorted OpenLists.
 */

static OpenList merge(OpenList L, OpenList M)
  {
  if( L.isEmpty() ) return M;
  if( M.isEmpty() ) return L;

  String A = (String)L.first();
  String B = (String)M.first();

  if( A.compareTo(B) < 0 ) return cons(A, merge(L.rest(), M));
                      else return cons(B, merge(L, M.rest()));
  }


/**
 * Find out whether the first argument occurs as the first element of
 * any pair in the second argument, an association list. If it does,
 * return the entire pair.  If not, return the empty list.
 *
 *<pre>
 * assoc(S, []) => [];
 * 
 * assoc(S, [[S, T] | L]) => [S, T];
 *
 * assoc(S, [_ | L]) => assoc(S, L);
 *</pre>
 */

static OpenList assoc(String S, OpenList L)
  {
  if( L.isEmpty() )
    {
    return nil;
    }

  OpenList First = (OpenList)L.first();

  if( S.equals(First.first()) )
    {
    return First;
    }

  return assoc(S, L.rest());
  }


// Convert this OpenList to a String, using default punctuation.

public String toString()
  {
  return toString(defaultLeftParen, defaultSpacer, defaultRightParen);
  }


// Convert this OpenList to a String, 
// using the arguments as punctuation

public String toString(String leftParen, 
                       String spacer, 
                       String rightParen)
  {
  StringBuffer buffer = new StringBuffer();

  buffer.append(leftParen);

  if( nonEmpty() )
    {
    buffer.append(first().toString());
    OpenList remainder = rest();

    while( remainder.nonEmpty() )
      {
      buffer.append(spacer);
      buffer.append(remainder.first());
      remainder = remainder.rest();
      }
    }

  buffer.append(rightParen);
  return buffer.toString();
  }


// Test program

public static void main(String arg[])
  {
  OpenList L0 = nil;

  System.out.println("L0 = " + L0);

  OpenList L1 = cons("a", cons("b", cons("c", nil)));

  System.out.println("L1 = " + L1);

  OpenList L2 = cons(cons("b", cons("c", nil)), cons("d", nil));

  System.out.println("L2 = " + L2);

  OpenList L3 = cons(L1, cons(L2, nil));

  System.out.println("L3 = " + L3);

  OpenList L4 = cons(L1, L2);

  System.out.println("L4 = " + L4);

  OpenList L5 = cons(L2, L1);

  System.out.println("L5 = " + L5);

  OpenList L6 = cons(new Integer(1), nil);

  System.out.println("L6 = " + L6);

  OpenList L7 = cons(new Integer(1),
                     cons(new Integer(2),
                          cons(new Integer(3),
                               cons(new Integer(4),
                                    nil))));

  System.out.println("L7 = " + L7);

  System.out.println("append(L1, L2) = " + append(L1, L2));

  System.out.println("reverse(L5) = " + reverse(L5));

  System.out.println("append(reverse(L7), reverse(L1)) = "
                    + append(reverse(L7), reverse(L1)));

  System.out.println("reverse(append(L1, L7)) = "
                    + reverse(append(L1, L7)));

  System.out.println("L5.length() = " + L5.length());

  System.out.println("L5.nth(2) = " + L5.nth(2));

  System.out.println("L5.prefix(3) = " + L5.prefix(3));

  System.out.println("map(new Cuber(), L7) = " + map(new Cuber(), L7));

  System.out.println("map(new Scaler(3), L7) = " + map(new Scaler(3), L7));
  }

}

interface Function1
{
Object apply(Object x);
}

class Cuber implements Function1
{
public Object apply(Object x)
  {
  float value = ((Number)x).floatValue();
  return new Float(value*value*value);
  }
}

class Scaler implements Function1
{
private float factor;

Scaler(float _factor)
  {
  factor = _factor;
  }

public Object apply(Object x)
  {
  float value = ((Number)x).floatValue();
  return new Float(factor*value);
  }
}

---