/**
   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.
   Fall 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
//