import math, random

# Given a period OrbitTime for an orbit and the time intervals when there is
# ground coverage, find the minimal set of satellites and their offsets
# to cover the entire period.



# computecoverage takes the points already covered in the dictionary "alreadycovered" That is a dictionary that has for each minute the number of satellites covering that minute.
# adds in an offset "offset" and the intervals covered by a satellite "satcovered"
# and returns the intervals that would be covered if a satellite were
# added at offset.
# Intervals are measured as a list of start and end points such that
# no two intervals intersect. An interval [x,y] means that minute x 
# up to the beginning of minute y are covered.
# Globals: mincover; satcovered; alreadycovered; OrbitTime
def computecoverage(offset):
  global mincover, satcovered, alreadycovered, OrbitTime
  outcovered = alreadycovered.copy()
  outlist = []
  for x in satcovered:
    outlist.append([(z + offset) % OrbitTime for z in x])
  # print("outlist is: ")
  # print(outlist)
  for x in outlist:
    if (x[0] < x[1]):
      myrange = range(x[0], x[1])
      for i in myrange:
        # print("i is: " + str(i))
        outcovered[i]+= 1 # one more satellite covers it
    else: 
      myrange = range(x[0], OrbitTime)
      for i in myrange:
        outcovered[i]+= 1 # one more satellite covers it
      myrange = range(0,x[1])
      for i in myrange:
        outcovered[i]+= 1 # one more satellite covers it
  mycount = len([m for m in outcovered.values() if m >= mincover ])
  return (outcovered, mycount)

# Return the offset that increases the count by the most
# Globals: OrbitTime -- the number of minutes for the whole orbit; alreadycovered
# alreadycovered must be declared global because of the side effect
def findbestoffset():
  global alreadycovered, OrbitTime
  maxcount = 0
  bestoffset = -1
  for i in range(OrbitTime):
    pair = computecoverage(i)
    if pair[1] > maxcount:
      bestoffset = i
      maxcount = pair[1]
  pair = computecoverage(bestoffset)
  alreadycovered = pair[0].copy()
  print("=============")
  print(bestoffset)
  outlist = []
  for x in satcovered:
    outlist.append([(z + bestoffset) % OrbitTime for z in x])
  print(outlist)
  print(alreadycovered)
  return(bestoffset, pair[1])

# Keep adding satellites until we get the amount of coverage we want
# Globals:  OrbitTime
def chooseoffsets():
  global OrbitTime
  offsets = []
  numcovered = 0
  while (numcovered < OrbitTime):
    pair = findbestoffset()
    offsets.append(pair[0])
    numcovered = pair[1]
  print("All offsets: ")
  return(offsets)
  
# generates a random set of intervals
def gensatcovered(OrbitTime, inlength, outlength):
  out = []
  highest = 0
  while(highest < OrbitTime):
    x = random.randint(1,inlength)
    if (highest +x ) < OrbitTime:
      out.append([highest, highest+x])
    y = random.randint(1,outlength)
    highest+= x + y
  return(out)
    
    
  
   

    
  
  
# CONSTANTS

OrbitTime = 90 # time to orbit the earth
mincover = 1 # want at least one satellite per location
inlength = 3 # maximum length of coverage intervals
outlength = 3 # maximum length of non-coverage intervals
numtests = 100
# ALGORITHM
for j in range(numtests):
  print()
  print("+++++++++++++++++++++++++++++++++")
  print()
  satcovered = gensatcovered(OrbitTime, inlength, outlength)
  print(satcovered)
  totcover = 0
  for x in satcovered:
    totcover+= x[1] - x[0]
  print("totcover is: " + str(totcover))
  print("Minimum possible number of satellites is  " + str(mincover*math.ceil(OrbitTime/(totcover+0.0))))
  smallestpossible = mincover*math.ceil(OrbitTime/(totcover+0.0))
  L1 = range(OrbitTime)
  L2 = [0] * OrbitTime
  alreadycovered = dict(zip(L1,L2))
  x = chooseoffsets()
  print("Offsets are: ")
  print(x)
  print("Ratio of number of satellites to minimum possible number: " + str(len(x)/smallestpossible))

# One more

satcovered = [[0,10], [20,35], [40,55], [65,75]]
print(satcovered)
totcover = 0
for x in satcovered:
  totcover+= x[1] - x[0]
  print("totcover is: " + str(totcover))
print("Minimum possible number of satellites is  " + str(mincover*math.ceil(OrbitTime/(totcover+0.0))))
smallestpossible = mincover*math.ceil(OrbitTime/(totcover+0.0))
L1 = range(OrbitTime)
L2 = [0] * OrbitTime
alreadycovered = dict(zip(L1,L2))
x = chooseoffsets()
print("Offsets are: ")
print(x)
print("Ratio of number of satellites to minimum possible number: " + str(len(x)/smallestpossible))