import java.util.*;


/******************************************************************

  This class and its main method simply test the classes and
methods of Assigment 3, CS 146, Fall 2002.

******************************************************************/


public class A3
{

  /**
      Traverses a structure with a bidirectional iterator in
      the forward direction, beginning at the current
      position of the iterator, and ending at the last element.
      @param bi the bidirectional iterator
  */

  public static void traverseForward(BidirectionalIterator bi) {
    while (bi.hasNext())                        {
      Integer ii = (Integer) bi.next();
      System.out.print(ii + " ");               }
    System.out.println();                                      }


  /**
      Traverses a structure with a bidirectional iterator in
      the backward direction, beginning at the current
      position of the iterator, and ending at the last element.
      @param bi the bidirectional iterator
  */

  public static void traverseBackward(BidirectionalIterator bi){
    while (bi.hasPrevious())                    {
      Integer ii = (Integer) bi.previous();
      System.out.print(ii + " ");               }
    System.out.println();                                      }


  public static void main(String args[])                {

    int n=5;
    HeapColl hs = new HeapColl();
    for (int i=1; i<=n; i++)                    {
      hs.insert(new Integer(i));
      hs.insert(new Integer(-i));               }

    BidirectionalIterator it = hs.iterator();
    traverseForward(it);
    traverseBackward(it);

    it = hs.iterator();
    for (int i=1; i<=n; i++)                    {
      Integer ii = (Integer) it.next();
      System.out.print(ii + " ");               }
    System.out.println();

    BidirectionalIterator it2 = hs.iterator();
    for (int i=1; i<=n-1; i++)                  {
      Integer ii = (Integer) it2.next();
      System.out.print(ii + " ");               }
    System.out.println();

    System.out.print((Integer) it.previous() + " ");
    System.out.print((Integer) it.previous() + " ");

    traverseForward(it);
    traverseForward(it2);

    hs.deleteMin();
    hs.insert(new Integer(9));
    hs.deleteMin();

    traverseBackward(it);
    traverseForward(it);
    traverseBackward(it);

    BidirectionalIterator it3 = hs.iterator();
    traverseForward(it3);
    traverseBackward(it3);


    HeapColl hc = new HeapColl();
    Random r = new Random(3);
    for (int i=1; i<=200; i++)
      hc.insert(new Integer(r.nextInt(1000)));

    it = hc.iterator();
    traverseForward(it);
    traverseBackward(it);


    Iterable dc = new Iterable();
    for (int i=1; i<=n; i++)                    {
      dc.insert(new Integer(10*i));
      dc.insert(new Integer(-10*i));            }

    traverseForward(dc);
    traverseBackward(dc);

    for (int i=1; i<=n; i++)                    {
      Integer ii = (Integer) dc.next();
      System.out.print(ii + " ");               }
    System.out.println();

    dc.insert(new Integer(15));
    dc.insert(new Integer(-15));

    System.out.print((Integer) dc.previous() + " ");
    System.out.print((Integer) dc.previous() + " ");

    traverseForward(dc);
    traverseBackward(dc);
    System.out.println();
    System.out.println();

    System.out.print((Integer) dc.next() + " ");
    System.out.print((Integer) dc.next() + " ");
    dc.reset();
    traverseForward(dc);

    System.out.print((Integer) dc.previous() + " ");
    System.out.print((Integer) dc.previous() + " ");
    dc.reset();
    traverseForward(dc);


    Iterable d = new Iterable();
    r = new Random(3);
    for (int i=1; i<=200; i++)
      d.insert(new Integer(r.nextInt(1000)));

    traverseForward(d);
    traverseBackward(d);                                }


};