#include <iostream>
#include <sstream>
#include <set>

// Declare (but do not define) allocator functions
void Init(int *heapStart, int heapSize);
int New(int n);
void Delete(int *addr);

// Set up the heap
static constexpr int heapSize = 2410000;
static int heapStart[heapSize];

// Track which blocks are allocated/free for debugging purposes
std::set<int> allocatedIndices;

// Prints a representation of the heap.
// Allocated blocks are indicated with square brackets and have the format:
// [index:size]
// Free blocks are indicated with curly braces and have the format:
// [index:size nextIndex]
// This function makes the following assumptions about your heap:
// - Each block (allocated or free) stores the size in the first slot.
// - The size is the number of slots (ints) in the block, not the size in bytes.
// - Each free block stores the offset/index of the next free block (not the raw address)
//   in the second slot, or a negative number to terminate the free list.
// - New returns the offset/index of the second slot of the allocated block.
//   (Since the first slot holds the size)
// - Delete expects to be passed the address of the second slot of the block to delete.
//   (Since the first slot holds the size)
// If your allocator does not follow these conventions, this function may have
// unexpected behavior (like looping infinitely) and you may need to modify
// either this function, or your allocator.
void debugPrint() {
  int *start = heapStart;
  int *end = heapStart + heapSize;
  int *current = start;
  if(*current == 0) {
    std::cout << "ERROR: Heap not properly initialized (size of first block is 0)\n";
    return;
  }
  std::stringstream buffer;
  while(current < end) {
    int index = current-start;
    int size = current[0];
    if(*current <= 1) { // A useless block of size 0 or 1 is found
      // Don't print it, store it in a buffer and only print if we
      // encounter a normal block later on
      buffer << "(" << size << ")";
      current++;
    } else { // A normal block is found
      // Print the useless blocks (if any)
      std::cout << buffer.str();
      buffer.clear();
      // Print the normal block
      if(allocatedIndices.count(index+1) == 0) {
        // The block is free
        int second = current[1];
        // If the second word is negative, print NULL
        // Otherwise, it is an index, print it normally
        std::cout << "{" << index << ":" << size << " ";
        if (second < 0) {
          std::cout << "NULL";
        } else {
          std::cout << second;
        }
        std::cout << "}";
      } else {
        // The block is allocated
        std::cout << "[" << index << ":" << size << "]";
      }
    }
    current += size;
  }
  std::cout << std::endl;
}

// Interactive tool for testing your allocator.
// Type "n size" to allocate a block of size 'size'.
// If allocation succeeds, the index that was returned to the user will be printed.
// Type "d index" to delete the block at a given index.
// It must be an index previously returned by New and not already deleted.
// At the start of the program, and after each command, a representation of the heap is printed.
// Press Ctrl+D to stop.
int main() {
  Init(heapStart, heapSize);
  std::string line;
  debugPrint();
  std::cout << ">>> ";
  while(getline(std::cin,line)) {
    std::stringstream ss(line);
    std::string command;
    int value;
    ss >> command;
    if(ss >> value) {
      if(command[0] == 'n') {
        int index = New(value);
        if(index < 0) {
          std::cout << "allocation failed (returned NULL)";
        } else {
          std::cout << "allocated block index: " << index;
          allocatedIndices.insert(index);
        }
        std::cout << '\n';
      }
      if(command[0] == 'd') {
        if(allocatedIndices.count(value) != 0) {
          allocatedIndices.erase(value);
          Delete(heapStart+value);
        } else {
          std::cout << "ERROR: attempting to delete a block that is not currently allocated, ignoring";
        }
      }
    }
    std::cout << '\n';
    debugPrint();
    std::cout << ">>> ";
  }
}