#! /usr/bin/env python
#########################################################################
# This program is free software; you can  redistribute  it  and/or
# modify  it  under the terms of the GNU General Public License as
# published by the Free Software Foundation; either version  2  of
# the License, or (at your option) any later version.
#   
# This program is distributed in the hope that it will be  useful,
# but  WITHOUT  ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
# General Public License for more details.
#
# You should have received  a  copy  of  the  GNU  General  Public
# License  along  with  this  program;  if  not, write to the Free
# Software Foundation, Inc., 59 Temple Place - Suite 330,  Boston,
# MA 02111-1307, USA.
#########################################################################
#
# This is a small python script that  reads  ascii  text  from  standard
# input  and  writes a left and right justified text to standard output.
# It can be used in several ways.
# 
# First: cat Text.txt | mywrap.py -w 65
# 
# This will try to justify text with a line width of 65. If that is  not
# possible  a  line  width  of  64 is used. If that does not work a line
# width of 66 is used. If that does not work a line width of 63 is used.
# And so on between the margins of 45 and 85.
# 
# Second: cat Text.txt | mywrap.py [-f|--from] 50 [-t|--to] 80
# 
# This will print out a list that contains all numbers that are feasible
# line widths between 50 and 80.
# 
# Third: cat Text.txt | mywrap.py [-f|--from] 50 [-t|--to] 80 -o
# 
# This will justify the text with the line width between 50 and 80  that
# has the lowest number of added blanks.

import sys, string, getopt

class NotJustifyable(Exception):
    __message = ""
    
    def __init__(self, message):
        self.__message = message

    def __str__(self):
        return self.__message
        

class Line:
    __line = ""
    __line_limit = 0
    
    def __init__(self, line, line_limit):
        self.__line = string.strip(line)
        self.__line_limit = line_limit

    def set_line_width(self, line_width):
        self.__line_limit = line_width    
        
    def missing_blanks(self):
        return self.__line_limit - len(self.__line)

    def num_blanks(self):
        return len(string.split(self.__line)) - 1

    def get_left_padded_line(self):
        if self.missing_blanks() > self.num_blanks():
            raise NotJustifyable("Line:\n" + self.__line + "\nis not justifiable!")
        
        padded_line = string.replace( self.__line, " ", "  ", self.missing_blanks())
        return padded_line

    def get_right_padded_line(self):
        __words = string.split(self.__line)
        __blank_num = self.num_blanks()
        __padded_line = ""

        if self.missing_blanks() > self.num_blanks():
            raise NotJustifyable("Line:\n" + self.__line + "\nis not justifiable!")
        for i in range(0, len(__words) - self.missing_blanks() - 1):
            __padded_line += (__words[i] + " ")
            i += 1

        for j in range(len(__words) - self.missing_blanks() - 1, len(__words) ):
            __padded_line += (__words[j] + "  ")
            j += 1
        __padded_line = string.strip(__padded_line)
        return __padded_line

    def get_line(self):
        return self.__line

class LineBreaker:
    __string = ""
    __line_limit = 80
    __words = []
    __lines = []
    __actual_line_length = 0
    __actual_line = ""    

    def __init__(self, input_string, line_limit):
        self.__string = input_string
        self.__line_limit = line_limit
        self.__words = []
        self.__lines = []
        self.__actual_line_length = 0
        self.__actual_line = ""            
        tmp_words = string.split(self.__string)

        for w in tmp_words:
            self.__words.append(w)
            self.__words.append(" ")

    def compute_lines(self):
        for word in self.__words:
            if len(word) + self.__actual_line_length > self.__line_limit :
                self.__lines.append(Line(self.__actual_line, self.__line_limit))
                if word == " ":
                    self.__actual_line_length = 0
                    self.__actual_line = ""
                else :
                    self.__actual_line_length = len(word)
                    self.__actual_line = word
            else :
                self.__actual_line_length += len(word)
                self.__actual_line += word
        self.__lines.append(Line(self.__actual_line, self.__line_limit))

    def get_lines(self):
        return self.__lines

class ParagraphFormater:
    __text = ""
    __line_limit = 0
    __formated_paragraph = ""

    def __init__(self, text, line_limit):
        self.__text = text
        self.__line_limit = line_limit

    def format(self):
        self.__formated_paragraph = ""
        breaker = LineBreaker(self.__text, self.__line_limit)
        breaker.compute_lines()
        lines = breaker.get_lines()

        left = 0
        for line_num in range(0, len(lines) - 1):
            try:
                if left == 1:
                    self.__formated_paragraph += lines[line_num].get_left_padded_line()
                    self.__formated_paragraph += "\n"
                    left = 0
                else:
                    self.__formated_paragraph += lines[line_num].get_right_padded_line() 
                    self.__formated_paragraph += "\n"                    
                    left = 1
            except NotJustifyable, e:
                return 0
        self.__formated_paragraph += lines[len(lines) - 1].get_line()
        return 1

    def format_width(self, line_limit):
        self.__line_limit = line_limit
        return self.format()    

    def get_paragraph(self):
        return self.__formated_paragraph

    def get_missing_nums(self, line_limit):
        breaker = LineBreaker(self.__text, line_limit)
        breaker.compute_lines()
        tmp_lines = breaker.get_lines()
        ret_list = []
        for line in tmp_lines:
            ret_list.append(line.missing_blanks())
        return ret_list

    def get_missing_blanks_count(self, line_limit):
        retval = 0
        num_list = self.get_missing_nums(line_limit)
        for i in range(0, len(num_list) - 1):
            retval += num_list[i]
        return retval

class ParagraphList:
    __paragraph_list = []

    def read_from_stdin(self):
        text = ""
        input = sys.stdin
        while 1:
            l = input.readline()
            if not l: break
            if l == "\n":
                self.__paragraph_list.append(ParagraphFormater(text, 80))
                text = ""
            else:
                text += l
        del input
        if text != "":
            self.__paragraph_list.append(ParagraphFormater(text, 80))

    def get_feasible_width_list(self, _from, _to):
        search_list = range(_from,_to + 1)
        for i in range(_from, _to + 1):
            for par in self.__paragraph_list:
                if par.format_width(i) == 0:
                    search_list.remove(i)
                    break
                else:
                    pass
        return search_list

    def get_missing_blanks(self, line_width):
        retval = 0
        for par in self.__paragraph_list:
            retval += par.get_missing_blanks_count(line_width)
        return retval

    def get_feasible_width_with_blanks_count(self, _from, _to):
        ret_dict = {}
        feasible_list = self.get_feasible_width_list(_from, _to)
        for i in feasible_list:
            ret_dict[i] = self.get_missing_blanks(i)
        return ret_dict

    def print_paragraph_list(self, line_width):
        tmp_width = line_width
        flag = -1
        for j in range(0,40):
            tmp_width = tmp_width + flag * j
            if flag > 0:
                flag = -1
            else:
                flag = 1
            width_is_feaseable = 1
            for par in self.__paragraph_list:
                if par.format_width(tmp_width) == 0:
                    width_is_feaseable = 0
                    break
                else:
                    pass
            if (width_is_feaseable == 1):
                for paragraph in self.__paragraph_list:
                   print paragraph.get_paragraph()
                   print ""
                return
    def print_optimal_paragraph_list(self, _from, _to):
        tmp = self.get_feasible_width_with_blanks_count(_from, _to)
        tmp_line_width = 0
        tmp_missing_blanks = _to
        for i in tmp.keys():
            if tmp[i] < tmp_missing_blanks:
                tmp_missing_blanks = tmp[i]
                tmp_line_width = i
        return self.print_paragraph_list(tmp_line_width)

def usage():
    print "mywrap  -w line_width OR "
    print "mywrap [-f|--from] lower_bound [-t|--to] upper_bound"
    print "mywrap [-f|--from] lower_bound [-t|--to] upper_bound"
    
def main():
    try:
        opts, args = getopt.getopt(sys.argv[1:], "w:f:t:o",
                                   ["line-width=", "from=", "to=", "format"])
    except getopt.GetoptError:
        usage()
        sys.exit(2)

    global_line_width = -1
    global_from = -1
    global_to = -1
    global_output_enabled = 0
    
    for o, a in opts:
        if o in ("-w", "--line-width"):
            global_line_width = string.atoi(a)
        if o in ("-f", "--from"):
            global_from = string.atoi(a)
        if o in ("-t", "--to"):
            global_to = string.atoi(a)
        if o in ("-o", "--format"):
            global_output_enabled = 1

    par_list = ParagraphList()
    par_list.read_from_stdin()


    if (global_from != -1) & (global_to != -1) & (global_line_width == -1) & (global_output_enabled == 0):
        print par_list.get_feasible_width_with_blanks_count(global_from, global_to)
    elif(global_from != -1) & (global_to != -1) & (global_line_width == -1) & (global_output_enabled == 1):
        par_list.print_optimal_paragraph_list(global_from, global_to)
        sys.exit(0)
    elif (global_from == -1) & (global_to == -1) & (global_line_width != -1) & (global_output_enabled == 0):
        par_list.print_paragraph_list(global_line_width)
        sys.exit(0)
    else:
        usage()

if __name__ == "__main__":
    main()