/**
   Simple-minded code to compare the performance of a linked list using a free
   list to manage links to a linked list using new and garbage collection.

   After compiling, run with "java -ea flm".

   Data Structures and Algorithms, CS 305 and 503.
   Spring 2010
 */

import java.util.Random;


class flm {


  private static int []
  genTurns() {

    final int turns [] = new int [100000];
    int total = 0;
    final Random rint = new Random(System.currentTimeMillis());

    for (int i = 0; i < turns.length - 1; i += 2) {
      total += (turns[i] = (rint.nextInt(10) + 1)*10);
      total -= (turns[i] = (rint.nextInt(total) + 1));
      assert total > -1;
      }
    
    return turns;
    }


  public static void 
  main(String args[]) {

    final int turns [] = genTurns();
    final double 
      std = (double) runIt(turns, new basicAllocator()),
      free = (double) runIt(turns, new freeListAllocator());

    System.out.printf("std/free-list = %g.\n", std/free);
    }


  private static long
  runIt(int turns[], allocator a) {

    link head = null;
    final long now = System.currentTimeMillis();

    for (int i = 0; i < turns.length; i += 2) {
      for (int j = turns[i]; j > -1; j--)
	head = a.newLink(head);
      for (int j = turns[i + 1]; j > -1; j--) {
	final link l = head.next;
	a.freeLink(head);
	head = l;
        }
      }

    return System.currentTimeMillis() - now;
    }


  private interface allocator {
    link newLink(link l);
    void freeLink(link l);
    }


  private static class 
  basicAllocator
  implements allocator {

    public link newLink(link l) {
      return new link(l);
      }

    public void freeLink(link l) {
      }
    }


  private static class 
  freeListAllocator
  implements allocator {

    private link freeList = null;

    public link newLink(link l) {
      if (freeList != null) {
	final link n = freeList;
	freeList = n.next;
	n.next = l;
	return n;
        }
      return new link(l);
      }

    public void freeLink(link l) {
      l.next = freeList;
      freeList = l;
      }
    }


  private static class link { 
    link next;
    link(link n) { next = n; }
    }
  }


// $Log: flm.java,v $
// Revision 1.1  2010/02/16 01:17:57  rclayton
// Initial revision
//