Allocating Memory

type mem_status =
  | Free
  | Occupied

type memory = (mem_status * int) list

You'll be working with a very simple model of (unlimited) memory. In this model, memory is represented as a list of pairs, each representing a chunk of memory. The first entry of the pair determines whether the chunk is Free or Occupied, and the second determines how many units of memory the chunk occupies. Furthermore, we require that memory has the following properties:

there are no adjacent Free chunks of memory (there may be adjacent chunks of Occupied memory);
there is no Free chunk of memory at the end of the list, i.e., either the list is empty or the last element is an Occupied chunk.

For example, the list:

[(Free, 3); (Occupied, 1); (Occupied, 3); (Free, 2); (Occupied, 1)]

represents the following layout.

┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───
│ F │ F │ F │ O │ O │ O │ O │ F │ F │ O │ F │ F │ ...
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───
 0   1   2   3   4   5   6   7   8   9   10  11   ...

In this problem, you'll be implementing a simple allocator for this model.

type alloc_result =
  | Success of int * memory
  | Invalid_size

Implement the function

val allocate : int -> memory -> alloc_result

so that allocate size mem is an alloc_result according to the following allocation strategy:

If size is not positive, then it is invalid.
Otherwise, allocate size mem is the same as mem except with an Occupied chunk of memory of size size in the leftmost possible position, together with the position itself.

It's possible to allocate a chunk of memory at position i of size size if the positions i through i + size - 1 are Free. After allocation, these positions become Occupied. In the above example, it should be possible to allocate a chunk of memory of size 2 at position 0, giving us the list:

[(Occupied, 2); (Free, 1); (Occupied, 1); (Occupied, 3); (Free, 2); (Occupied, 1)]

which represents the following layout.

┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───
│ O │ O │ F │ O │ O │ O │ O │ F │ F │ O │ F │ F │ ...
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───
 0   1   2   3   4   5   6   7   8   9   10  11   ...

The leftmost place to allocate a chunk of memory of size 5 is at position 10, giving us the list:

[(Free, 3); (Occupied, 1); (Occupied, 3); (Free, 2); (Occupied, 1); (Occupied, 5)]

which represents the following layout.

┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───
│ F │ F │ F │ O │ O │ O │ O │ F │ F │ O │ O │ O │ O │ O │ O │ F │ F │ ...
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───
 0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16   ...

Examples

let m0 = [(Free, 3); (Occupied, 1); (Occupied, 3); (Free, 2); (Occupied, 1)]

let _ = assert (allocate 0 m0 = Invalid_size)
let _ = assert (allocate (-1) m0 = Invalid_size)
let _ = assert (allocate 2 m0 =
                 Success (0, [(Occupied, 2); (Free, 1); (Occupied, 1);
                              (Occupied, 3); (Free, 2); (Occupied, 1)]))
let _ = assert (allocate 5 m0 =
                 Success (10, [(Free, 3); (Occupied, 1); (Occupied, 3);
                               (Free, 2); (Occupied, 1); (Occupied, 5)]))