# the size of the list of popular phrases
# that should be displayed to the user
HOTLIST_SIZE = 10

DUMMY = ""
 
#########################################################################
#                        MessageHistogram
#########################################################################
class MessageHistogram:

   def __init__(self):
      # create an empty dictionary
      # where the key is the phrase
      # and the value is the number of times the phrase has appeared
      self.phrases = dict()
      self.phrases[DUMMY] = -1

      # the top phrases seen so far
      # these should be displayed to the user, in order
      self.hotlist = []
      for i in range(0, HOTLIST_SIZE):
         self.hotlist.append(DUMMY)
      
      # the frequency for the the lowest entry on the hotlist
      # when a new phrase reaches this value, it should be added
      # to the hotlist
      self.freq_min = -1;
      
   def add_phrase(self, phrase):
      # ignore empty phrases
      if (phrase == None or phrase == ""): return
      freq = self.get_frequency(phrase) + 1
      self.phrases[phrase] = freq
      if (freq < self.freq_min): return
      # put phrase in hotlist
      if (self.hotlist.count(phrase) > 0):
         new_index = self.hotlist.index(phrase)
         while (new_index > 0):
            higher_phrase = self.hotlist[new_index - 1]
            higher_freq = self.phrases[higher_phrase]
            if (freq <= higher_freq): break
            new_index -= 1
         self.hotlist.remove(phrase)
         self.hotlist.insert(new_index, phrase)
      else:
         new_index = HOTLIST_SIZE
         while (new_index > 0):
            higher_phrase = self.hotlist[new_index - 1]
            higher_freq = self.phrases[higher_phrase]
            if (freq <= higher_freq): break
            new_index -= 1
         self.hotlist.pop()
         self.hotlist.insert(new_index, phrase)
      self.freq_min = self.get_frequency(self.hotlist[HOTLIST_SIZE - 1]);
      
   def get_frequency(self, phrase):
      if (phrase == None or phrase == ""): return 0
      if (self.phrases.has_key(phrase)):
         return self.phrases[phrase]
      return 0
   
   def get_hotlist(self):
      count = self.hotlist.count(DUMMY)
      if (count > 0):
         return self.hotlist[:-count]
      return self.hotlist[:]
   
   def debug(self):
      dstr = "Size of hotlist = " + str(HOTLIST_SIZE) + "\n"
      dstr += "Hotlist members = " + str(self.get_hotlist()) + "\n"
      dstr += "Histogram = " + str(self.phrases) + "\n"
      return dstr
   
   def print_debug(self):
      print self.debug()
         
#########################################################################
#                                  MAIN
#########################################################################
def main():

# code used for testing

   mh = MessageHistogram()
   mh.print_debug()
   mh.add_phrase('hello')
   mh.print_debug()
   mh.add_phrase('world')
   mh.print_debug()
   mh.add_phrase('hello')
   mh.print_debug()
   mh.add_phrase('world')
   mh.print_debug()
   mh.add_phrase('world')
   mh.print_debug()

   mh.add_phrase('!')
   mh.print_debug()
   mh.add_phrase('!')
   mh.print_debug()
   mh.add_phrase('!')
   mh.print_debug()
   mh.add_phrase('!')
   mh.print_debug()

   hl = mh.get_hotlist()
   print hl
   hl.pop()
   print hl
   mh.print_debug()

if __name__ == "__main__":
   main()