//todo
//melodies containing melodies

number_of_tracks = 2

ticks_per_beat = 24
beats_per_second = 80

heap = []
midi_file = []

is_digit = function(s)
{
   return (0 <= s && s <= 9)
}

is_note_literal = function(s)
{
   var note_or_var

   var tokens = s.toString().split(" ")
   
   if (tokens.length == 1)
   {
      note_or_var = tokens[0]
   }
   else
   {
      note_or_var = tokens[1]
   }

   var i = 0
   var is_number = true
   while (i < note_or_var.length)
   {
      if (!is_digit(note_or_var[i]))
      {
         is_number = false
         break;
      }
      i++
   }
   return is_number
}

do_math = function(math_tree, what, octave_size)
{

   var ret = []
   if (math_tree.length == 1)
   {
      ret = math_tree
   }
   else if (math_tree[0] == "?")
   {
      ret = get_var_from_heap(math_tree[1])[1][1][what]
   }
   else if (math_tree[0] == "+" || math_tree[0] == "-" || math_tree[0] == "*" || math_tree[0] == "/")
   {
      var i
      var num
      var num_list

      var left = do_math(math_tree[1], what, octave_size)
      var right = do_math(math_tree[2], what, octave_size)

      if (right.length == 1)
      {
         num_list = left
         num = right[0]
      }
      else if (left.length == 1)
      {
         num = left[0]
         num_list = right
      }
      else
      {
         //we shouldn't be doing this
      }

      for (i = 0; i < num_list.length; i++)
      {
         if (math_tree[0] == "+")
         {
            if (num_list == right)
            {
               if (num == 0)
                  ret = ret.concat(0)
               else if (num < 0 && num + num_list[i] >= 0)
                  ret = ret.concat(num + num_list[i] + 1)
               else
                  ret = ret.concat(num + num_list[i])               
            }
            else
               ret = ret.concat(num_list[i] + num)
         }
         else if (math_tree[0] == "*")
         {
            ret = ret.concat(num_list[i] * num)
         }
         else if (math_tree[0] == "-")
         {
            var result
            if (num_list == right)
            {
               if (num == 0)
                  ret = ret.concat(0)
               else if (num > 0 && num - num_list[i] <= 0)
                  ret = ret.concat(num - num_list[i] - 1)
               else
                  ret = ret.concat(num - num_list[i])
            }
            else
            {
               if (num_list[i] == 0)
                  ret = ret.concat(0)
               else if (num_list[i] > 0 && num_list[i] - num <= 0)
                  ret = ret.concat(num_list[i] - num - 1)
               else
                  ret = ret.concat(num_list[i] - num)
            }
         }
         else if (math_tree[0] == "/")
         {
            if (num_list == right)
               ret = ret.concat((num - (num % num_list[i])) / num_list[i])
            else
               ret = ret.concat((num_list[i] - (num_list[i] % num)) / num)
         }
      }
   }
   else if (math_tree[0] == "^" || math_tree[0] == "v")
   {
      var i
      for (i = 1; i < math_tree.length; i++)
      {
         var temp = do_math(math_tree[i], what, octave_size)
         var j
         for (j = 0; j < temp.length; j++)
         {
            if (math_tree[0] == "^")
            {
               if (temp[j] == 0)
                  ret = ret.concat(0)
               else if (temp[j] < 0 && temp[j] + octave_size >= 0)
                  ret = ret.concat(temp[j] + octave_size + 1)
               else
                  ret = ret.concat(temp[j] + octave_size)
            }
            else
            {
               if (temp[j] == 0)
                  ret = ret.concat(0)
               else if (temp[j] > 0 && temp[j] - octave_size <= 0)
                  ret = ret.concat(temp[j] - octave_size -1)
               else
                  ret = ret.concat(temp[j] - octave_size)
            }
         }
      }
   }
 
   return ret

}



//melody part is one of the following
// 0 -> tune
// 1 -> timing
// 2 -> scale
// 3 -> position
// melody = ["!", [...]]
// melody_part = [1, 2, 3, 4, "^^ 5", "x"]
expand_variable_part = function(melody, what, octave_size)
{
   var ret = []
   var i


   var melody_part = melody[1][what]

   //melody_part = [[1], [2], [3], ["+", 5, "x"]]
   for (i = 0; i < melody_part.length; i++)
   {  
      if (melody_part[i].length == 1)
      {        
         ret = ret.concat(melody_part[i][0])
      }
      else
      {  
         ret = ret.concat(do_math(melody_part[i], what, octave_size))
      }
   }

   return ret
}

//expands something like 
//["&", ["?", "x"], ["!", [tune, timing, scale, position] ]
expand_variables_whole = function(melody)
{
   var ret = []
 
   //we know what we are dealing with by looking at melody[0]

   //melody literals
   if (melody[0] == "!")
   {
      var scale = expand_variable_part(melody, 2)
      var octave_size = scale.length - 1
      ret = ["!", 
              [  expand_variable_part(melody, 0, octave_size),
                 expand_variable_part(melody, 1, octave_size),
                 expand_variable_part(melody, 2, octave_size),
                 expand_variable_part(melody, 3, octave_size)
              ]
            ]
   }

   //variables
   else if (melody[0] == "?")
   {
      ret = get_var_from_heap(melody[1])[1] 
   }

   //melody transformation
   else
   {
      ret = [melody[0], expand_variables_whole(melody[1]), expand_variables_whole(melody[2])]      
   }

   return ret
}

get_var_from_heap = function(variable_name)
{
   var get_var_from_heap_ret = []

   for (i = 0; i < heap.length; i++)
      if (heap[i][0] == variable_name)
      {   get_var_from_heap_ret = heap[i]
          break
      }

   return get_var_from_heap_ret
}



add_var_to_heap = function(arg)
{
   //the final thing to add to the heap
   var result = []

   //the variable name
   result = result.concat(arg[0])
   result = result.concat([expand_variables_whole(arg[1])])

   heap = heap.concat([result])
}

num2ff = function(num)
{
   first_loop = true
   num2ff_ret = [0]

   while (num > 0)
   {
      remainder = num % 256
      num = num - remainder
      num = num/256

      if (first_loop)
      {
         num2ff_ret = [remainder]
         first_loop = false
      }
      else
      {
         num2ff_ret = [remainder].concat(num2ff_ret)
      }
   }

   return num2ff_ret
}

num2vlen = function(num)
{
   first_loop = true
   num2vlen_ret = [0]

   while (num > 0)
   {
      remainder = num % 128
      num = num - remainder
      num = num/128

      if (first_loop)
      {
         num2vlen_ret = [remainder]
         first_loop = false
      }
      else
      {
         num2vlen_ret = [remainder+128].concat(num2vlen_ret)
      }
   }

   return num2vlen_ret
}

key2num = function(key)
{
   key2num_ret = -1
   
   if (key == "c" || key == "C")
      key2num_ret = 0;
   else if (key == "c#" || key == "C#" || key == "db" || key == "Db")
      key2num_ret = 1;
   else if (key == "d" || key == "D")
      key2num_ret = 2;
   else if (key == "d#" || key == "D#" || key == "eb" || key == "Eb")
      key2num_ret = 3;
   else if (key == "e" || key == "E")
      key2num_ret = 4;
   else if (key == "f" || key == "F")
      key2num_ret = 5;
   else if (key == "f#" || key == "F#" || key == "gb" || key == "Gb")
      key2num_ret = 6;
   else if (key == "g" || key == "G")
      key2num_ret = 7;
   else if (key == "g#" || key == "G#" || key == "ab" || key == "Ab")
      key2num_ret = 8;
   else if (key == "a" || key == "A")
      key2num_ret = 9;
   else if (key == "a#" || key == "A#" || key == "bb" || key == "Bb")
      key2num_ret = 10;
   else if (key == "b" || key == "B")
      key2num_ret = 11;

   return parseInt(key2num_ret);
}

track_header = function(size_of_track)
{
   //MTrk
   track_header_ret = [77, 84, 114, 107]
   //size of track
   ff_size_of_track = num2ff(size_of_track)
   while (ff_size_of_track.length < 4)
      ff_size_of_track = [0].concat(ff_size_of_track)
   track_header_ret = track_header_ret.concat(ff_size_of_track)
   return track_header_ret
}

bpm2ff = function(bpm)
{
   return num2ff((60000000 - (60000000 % bpm))/bpm)
}

file_header = function()
{
   //MThd
   file_header_ret = [77, 84, 104, 100]
   //size
   file_header_ret = file_header_ret.concat([0, 0, 0, 6])
   //file format
   file_header_ret = file_header_ret.concat([0, 1])
   //number of tracks
   //should be less than 256
   file_header_ret = file_header_ret.concat([0, number_of_tracks])
   //time unit
   fftpb = num2ff(ticks_per_beat)
   if (fftpb.length < 2)
     fftpb = [0].concat(fftpb)
   file_header_ret = file_header_ret.concat(fftpb)

   //track 0 for meta info
   //the size of this track is 17
   file_header_ret = file_header_ret.concat(track_header(17))

   //key signature 0 flats/sharps and major
   file_header_ret = file_header_ret.concat([0, 255, 89, 2, 0, 0])

   //tempo setting 
   file_header_ret = file_header_ret.concat([0, 255, 81, 3])
   fftempo = bpm2ff(beats_per_second)
   while (fftempo.length < 3)
      fftempo = [0].concat(fftempo)
   file_header_ret = file_header_ret.concat(fftempo)

   //end of track
   file_header_ret = file_header_ret.concat(end_of_track())
   return file_header_ret
}

note_on = function(vlength_time, ffnote, channel)
{
   return vlength_time.concat([144+channel, ffnote, 127])
}

note_off = function(vlength_time, ffnote, channel)
{
   return vlength_time.concat([128+channel, ffnote, 0])
}

end_of_track = function()
{
   return [0, 255, 47, 0]
}

program_change = function(channel, instrument)
{
   return [0, 192+channel, instrument]
}

note2ff = function(note, scale, position)
{
   var ret
   if (note == 0)
      ret = -1
   else if (note < 0)
   {
      var positive = 0 - note
      var scale_width = scale.length - 1
      var scale_height = scale[scale_width] - scale[0]
      var remainder = positive % scale_width
      var octave_count = (positive - remainder)/scale_width + 1
      if (remainder == 0)
         ret = position - (octave_count - 1) * scale_height + scale[0] - 1
      else
         ret = position - octave_count * scale_height + scale[scale_width - remainder] - 1
   }
   else
   {
      var scale_width = scale.length - 1
      var scale_height = scale[scale_width] - scale[0]
      var remainder = (note - 1) % scale_width
      var octave_count = (note - 1 - remainder)/scale_width
      ret = position + octave_count * scale_height + scale[remainder] - 1
   }

   return ret
}


heap2ir = function(melody)
{
   var note_on_ir = []
   var note_off_ir = []

   //our arg has the format
   //["x", [sub1], [sub2], [sub3]...]
   var sub_count = melody.length - 1
   var sub_melody = []
   var sub_length = []
   var sub_index = []
   var sub_timing = []
   var i
   var j
   for (i = 0; i < sub_count; i++)
   {
      //fill in the melody array
      sub_melody = sub_melody.concat([melody[i+1]]) 

      //reformat the timing from [24, 24, 24, 24] to [[0, 24, 48, 72], [24, 48, 72, 96]]
      var start_timing = []
      var end_timing = []
      var current_time = 0
      var timing = sub_melody[i][1] 

      for (j = 0; j < timing.length; j++)
      {
         start_timing = start_timing.concat(current_time)
         end_timing = end_timing.concat(parseInt(current_time) + parseInt(timing[j]))
         current_time += timing[j]
      }

      sub_timing = sub_timing.concat([[start_timing, end_timing]])

      //get the length of each submelodies
      sub_length = sub_length.concat(sub_melody[i][0].length)

      //this is for indexing each submelody
      sub_index = sub_index.concat([[0, 0]])
   }

   var winner_start
   var winner_stop
   var time_to_exit = false
   while (!time_to_exit)
   {

      var min_start = 999999
      var min_stop = 999999
      winner_start = -1
      winner_stop = -1

      for (i = 0; i < sub_count; i++)
      {
         //do the start timing part
         var index_of_timing = sub_index[i][0]
         var length_of_timing = sub_length[i]
         if (index_of_timing < length_of_timing)
         {
            var current_start_timing = sub_timing[i][0][index_of_timing]
            if (current_start_timing < min_start)
            {
               min_start = current_start_timing
               winner_start = i
            }
         }             

         //do the stop timing part
         index_of_timing = sub_index[i][1]
         length_of_timing = sub_length[i]
         if (index_of_timing < length_of_timing)
         {
            var current_stop_timing = sub_timing[i][1][index_of_timing]
            if (current_stop_timing < min_stop)
            {
               min_stop = current_stop_timing
               winner_stop = i
            }
         }     
      }      

      var winner_start_note_ff = note2ff(sub_melody[winner_start][0][sub_index[winner_start][0]], sub_melody[winner_start][2], sub_melody[winner_start][3])
      
      if (winner_start_note_ff != -1)
         note_on_ir = note_on_ir.concat([[min_start, winner_start_note_ff]])

      sub_index[winner_start][0]++

      var winner_stop_note_ff = note2ff(sub_melody[winner_stop][0][sub_index[winner_stop][1]], sub_melody[winner_stop][2], sub_melody[winner_stop][3])

      if (winner_stop_note_ff != -1)
         note_off_ir = note_off_ir.concat([[min_stop, winner_stop_note_ff]])

      sub_index[winner_stop][1]++

      time_to_exit = true

      for (j = 0; j < sub_count; j++)
      {
         if (sub_index[j][0] < sub_length[j] || sub_index[j][1] < sub_length[j])
         {
            time_to_exit = false
            break
         }
      }
   }

   return [note_on_ir, note_off_ir]
}

//expecting ir to be [note_on_ir, note_off_ir]
ir2midi = function(ir, channel)
{
   //similar to merge sort
   i_on = 0
   i_off = 0
   note_on_ir = ir[0]
   note_off_ir = ir[1]
   current_time = 0   
   ir2midi_ret = []

   while (i_on < note_on_ir.length || i_off < note_off_ir.length)
   {

      //if one of the indices reach its limit, do the other
      if (i_on == note_on_ir.length)
      {
         delta = note_off_ir[i_off][0]-current_time
         ir2midi_ret = ir2midi_ret.concat(note_off(num2vlen(delta), note_off_ir[i_off][1], channel))
         i_off++
         current_time += delta
         continue
      }
      if (i_off == note_off_ir.length)
      {
         delta = note_on_ir[i_on][0]-current_time
         ir2midi_ret = ir2midi_ret.concat(note_on(num2vlen(delta), note_on_ir[i_on][1], channel))
         i_on++
         current_time += delta
         continue
      }
      
      //compare their elapsed time
      if (note_on_ir[i_on][0] < note_off_ir[i_off][0])
      {
         delta = note_on_ir[i_on][0]-current_time
         ir2midi_ret = ir2midi_ret.concat(note_on(num2vlen(delta), note_on_ir[i_on][1], channel))
         i_on++
         current_time += delta
      }
      else 
      {
         delta = note_off_ir[i_off][0] - current_time
         ir2midi_ret = ir2midi_ret.concat(note_off(num2vlen(delta), note_off_ir[i_off][1], channel))
         i_off++ 
         current_time += delta
      }
   }

  return ir2midi_ret
}

write2file = function(input)
{
   midi_file = midi_file.concat(input)
}

create_binary = function()
{  
   var raw_data
   eval("""
   uuencode64 = function(bytes) {
     var keyStr = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/="
     var output = ""
     var b1, b2, b3
     var e1, e2, e3, e4
     var i = 0
     while (i < bytes.length) {
       b1 = bytes[i++]
       b2 = bytes[i++]
       b3 = bytes[i++]
       e1 = b1 >> 2
       e2 = ((b1 &  3) << 4) | (b2 >> 4)
       e3 = ((b2 & 15) << 2) | (b3 >> 6)
       e4 = b3 & 63
       if      (isNaN(b2)) { e3 = e4 = 64 }
       else if (isNaN(b3)) { e4 = 64      }
       output += keyStr.charAt(e1) + keyStr.charAt(e2) + keyStr.charAt(e3) + keyStr.charAt(e4)
     }
     return output
   }

   raw_data  = uuencode64(midi_file)
   """)

   midi = document.createElement("embed")
   midi.setAttribute('src', 'data:audio/midi;base64,' + raw_data)
   $('playArea').appendChild(midi)
}


// melody =  [!, [[1, 2, 9], [24, 24, 24], [1, 3, 5, 6, 8, 10, 12], [48]]]]
melody2ir = function(melody)
{
   var note_on_ir = []
   var note_off_ir = []
   
   if (melody[0] == "!")
   {
      var i
      var elapsed = 0
      var tune = melody[1][0]
      var timing = melody[1][1]
      var scale = melody[1][2]
      var position = melody[1][3]
      for (i = 0; i < tune.length; i++)
      {  

         var note_ff = note2ff(tune[i], scale, position[0])
         note_on_ir = note_on_ir.concat([[elapsed, note_ff]])
         elapsed += timing[i]
         note_off_ir = note_off_ir.concat([[elapsed, note_ff]])
      }
   }
   else if (melody[0] == "&")
   {
      var left = melody2ir(melody[1])
      var right = melody2ir(melody[2])

      var i = 0
      var j = 0

      //merge the note on part
      while (i < left[0].length || j < right[0].length)
      {
         if (i == left[0].length)
         {
            note_on_ir = note_on_ir.concat([right[0][j]])
            j++
            continue
         }
         if (j == right[0].length)
         {
            note_on_ir = note_on_ir.concat([left[0][i]])
            i++
            continue
         }

         if (left[0][i][0] < right[0][j][0])
         {
            note_on_ir = note_on_ir.concat([left[0][i]])
            i++
         }
         else
         {
            note_on_ir = note_on_ir.concat([right[0][j]])
            j++
         }            
      }

      //merge the note off part
      i = 0
      j = 0
      while (i < left[1].length || j < right[1].length)
      {
         if (i == left[1].length)
         {
            note_off_ir = note_off_ir.concat([right[1][j]])
            j++
            continue
         }
         if (j == right[1].length)
         {
            note_off_ir = note_off_ir.concat([left[1][i]])
            i++
            continue
         }

         if (left[1][i][0] < right[1][j][0])
         {
            note_off_ir = note_off_ir.concat([left[1][i]])
            i++
         }
         else
         {
            note_off_ir = note_off_ir.concat([right[1][j]])
            j++
         }            
      }
   }
   return [note_on_ir, note_off_ir]
}