class HeapManager {
  private Object[] memory;

  public class Pointer {
    private final int address;

    /**
     * Create a null pointer: one that doesn't point to anything
     */
    public Pointer() {
      address = -1;
    }

    /**
     * Create a pointer to a particular address.
     * (not public, to avoid client creating bad pointers.)
     * @param a index into memory array
     */
    Pointer(int a) {
      address = a;
    }

    /**
     * Return whether the pointer is null.
     * @return true when pointer represents the null pointer
     */
    public boolean isNull() {
      return address < 0;
    }

    /**
     * Return the address of the pointer.
     * (Not public, so that clients cannot use it.)
     */
    int getAddress() {
      return address;
    }

    /**
     * Get the memory item pointed at.
     * This will crash if the pointer is null.
     * @param address offset amount to move address before dereferencing
     * @return contents of memory pointed to
     */
    public Object peek(int offset) {
      int a = address;
      // avoid dereferencing null pointers:
      if (a >= 0) a += offset;
      return memory[a];
    }

    /**
     * Change the memory pointed to by this pointer.
     * This will crash if the pointer is null.
     * @param address offset amount to move address before dereferencing
     * @param value new contents of memory pointed to
     */
    public void poke(int offset, Object value) {
      int a = address;
      // avoid dereferencing null pointers:
      if (a >= 0) a += offset;
      memory[a] = value;
    }

    public String toString() {
      return "Pointer(" + address + ")";
    }
  }

  private Pointer freelist;
  private boolean[] markBits;
  private Pointer current_frame;

  /**
   * Create a new HeapManager which creates its own array and
   * parcels out memory as needed.  It uses garbage collection
   * when needed.  The current frame pointer is used as the
   * root of garbage collection.
   */
  public HeapManager(int size) {
    memory = new Object[size];
    markBits = new boolean[size];
    memory[0] = new Integer(size);
    memory[1] = new Pointer();
    freelist = new Pointer(0);
    current_frame = new Pointer();
  }

  public Pointer getNullPointer() {
    return new Pointer();
  }

  public Pointer getCurrentFrame() {
    return current_frame;
  }

  public void setCurrentFrame(Pointer p) {
    current_frame = p;
  }

  /** Allocate a block of given size and return a pointer to
   * the first cell.  It uses first-fit on the free list,
   * but if there is not enough memory, it uses garbage collection.
   * Therefore, anything being used must be accessible from
   * the current frame pointer when this method is called.
   * If this is not possible, we return a "null pointer"
   * (a pointer for which isNull() returns true.)
   */
  public Pointer allocate(int n) {
    // First try first-fit, using code such as we did in
    // class or in the book (except using peek/poke etc)

    Pointer p = findInFreeList(n);
    if (p.isNull()) {
      // try to garbage collect first:
      System.out.print("Garbage collecting...");
      collect();
      System.out.println();
      p = findInFreeList(n);
    }
    if (p.isNull()) {
      System.out.println("Warning: Couldn't allocate any memory.");
    }
    return p;
  }


  /**
   * Look in the free list using first-fit as in
   * lecture or in the book except with peek/poke etc.
   * @return a pointer object (which may be null if no memory was found)
   */
  private Pointer findInFreeList(int n) {
    // Your code here (about 20 lines)

    // If we can't find anything in list, return a null Pointer:
    return new Pointer();
  }

  /**
   * Perform mark-sweep garbage collection
   * and reconstruct the freelist.
   * We mark all blocks that are accessible from
   * the current frame pointer, and then put together
   * a new free list from contiguous sections of unmarked
   * storage.
   */
  void collect() {
    // You may assume that before this routine is called, the mark array
    // is all false, if you clear the array afterwards in the sweep phase.

    // You will want to use a recursive helper function to mark.

    // Your code here
  }

  // Your private helper functions here

}