ralsina/layout.py

## layout.py
import svgwrite

class Box():
    def __init__(self, x=0, y=0, w=1, h=1, red=False, blue=False, yellow=False, letter=None):
        self.x = x
        self.y = y
        self.w = w
        self.h = h
        self.red = red
        self.blue = blue
        self.yellow = yellow
        self.letter = letter

    def __str__(self):
        return self.letter or 'Box'

    def __repr__(self):
        return self.letter or 'Box'

big_box = Box(0, 0, 80, 1000)
pages = [big_box]


def draw_boxes(boxes, with_boxes=True):
    STYLES = """
    .red { fill: red;}
    .green { fill: green;}
    .blue {fill: blue;}
    .yellow {fill: yellow;}
    .bigbox {fill: cyan; }
    """
    dwg = svgwrite.Drawing('test.svg', profile='full', size=('%d' % big_box.w, '%d' % big_box.w))
    dwg.defs.add(dwg.style(STYLES))
    for bb in pages:
        dwg.add(dwg.rect(insert=(bb.x,bb.y), size=(bb.w, bb.h), class_='bigbox'))
    for box in boxes:
        if with_boxes:
            if box.red:
                dwg.add(dwg.rect(insert=(box.x, box.y), size=(box.w, box.h), class_='red'))
            elif box.blue:
                dwg.add(dwg.rect(insert=(box.x, box.y), size=(box.w, box.h), class_='blue'))
            elif box.yellow:
                dwg.add(dwg.rect(insert=(box.x, box.y), size=(box.w, box.h), class_='yellow'))
            else:
                dwg.add(dwg.rect(insert=(box.x, box.y), size=(box.w, box.h), class_='green'))
        if box.letter:
            dwg.add(dwg.text(box.letter, insert=(box.x, box.y + box.h), font_size=box.h, font_family='Arial'))
    dwg.save()


# So, how could we layout the many boxes inside the big_box?
many_boxes = [Box(0, 0, 1, 1) for _ in range(5000)]

# Do nothing ...
# They are all in the same place
# draw_boxes(many_boxes)

# Try to lay them out side by side
# They just go too wide
# We add a "separation" constant so you can see the boxes individually
separation = .2

def layout1(boxes):
    for i, box in enumerate(boxes):
        box.x = i * (1 + separation)

# Put each one next to the other until they reach a width,
# then go down. This is a monospaced layout.

def layout2(boxes):
    for i, box in enumerate(boxes[1:]):
        box.x = boxes[i-1].x + 1 + separation
        box.y = boxes[i-1].y
        if box.x > big_box.w:
            box.x = 0
            box.y = boxes[i-1].y + 1.1

# Now, what happens if some boxes are wider than the others?
# layout2 will make them overlap or have wide breaks between them
import random
many_boxes = [Box(0, 0, 1+random.randint(-2,2)/10, 1) for _ in range(5000)]

# So, we use each box's width instead of a fixed width
def layout3(boxes):
    for i, box in enumerate(boxes[1:], 1):
        prev_box = boxes[i-1]
        box.x = prev_box.x + prev_box.w + separation
        box.y = prev_box.y
        if box.x > big_box.w:
            box.x = 0
            box.y = prev_box.y + 1.1

# layout3(many_boxes)
# But the right side is ragged

# We can, when we break, put the remaining space spread between boxes
# This is a "justified" layout

def layout4(boxes):
    last_break = 0
    for i, box in enumerate(boxes[1:], 1):
        prev_box = boxes[i-1]
        box.x = prev_box.x + prev_box.w + separation
        box.y = prev_box.y
        if box.x > big_box.w:
            box.x = 0
            box.y = prev_box.y + 1.1
            slack = big_box.w - (prev_box.x + prev_box.w)
            mini_slack = slack / (i-last_break)
            for j, b in enumerate(boxes[last_break:i]):
                b.x += j * mini_slack
            last_break = i
# layout4(many_boxes)

# But what happens if some boxes are red?
for box in many_boxes:
    if random.randint(1,6) > 5:
        box.red = True
# Well, nothing much, other than they are red

# But what if red means "stretchy" and only those can stretch?
def layout5(boxes):
    last_break = 0
    for i, box in enumerate(boxes[1:], 1):
        prev_box = boxes[i-1]
        box.x = prev_box.x + prev_box.w + separation
        box.y = prev_box.y
        if box.x > big_box.w:
            box.x = 0
            box.y = prev_box.y + 1.1
            slack = big_box.w - (prev_box.x + prev_box.w)
            row = boxes[last_break:i]
            reds = [b for b in row if b.red]
            # sometimes there is no red in the row. Do nothing.
            if reds:
                mini_slack = slack / len(reds)
                for b in reds:
                    b.w += mini_slack
                for j, b in enumerate(row[1:], 1):
                    b.x = row[j-1].x + row[j-1].w + separation
            last_break = i

# But what happens if a few are blue?
for box in many_boxes:
    if random.randint(1,150) > 149:
        box.blue = True

# Well, nothing much, other than they are blue

# But what if blue means "this row ends here"?
def layout6(boxes):
    last_break = 0
    for i, box in enumerate(boxes[1:], 1):
        prev_box = boxes[i-1]
        box.x = prev_box.x + prev_box.w + separation
        box.y = prev_box.y
        if prev_box.blue or box.x > big_box.w:
            box.x = 0
            box.y = prev_box.y + 1.1
            slack = big_box.w - (prev_box.x + prev_box.w)
            row = boxes[last_break:i]
            reds = [b for b in row if b.red]
            # sometimes there is no red in the row. Do nothing.
            if reds:
                mini_slack = slack / len(reds)
                for b in reds:
                    b.w += mini_slack
                for j, b in enumerate(row[1:], 1):
                    b.x = row[j-1].x + row[j-1].w + separation
            last_break = i
# Some reds get reeeeeeealy stretchy! That is because rows that
# end because of a blue have very few boxes. So maybe we don't stretch those?

def layout7(boxes):
    last_break = 0
    for i, box in enumerate(boxes[1:], 1):
        prev_box = boxes[i-1]
        box.x = prev_box.x + prev_box.w + separation
        box.y = prev_box.y
        if prev_box.blue or box.x > big_box.w:
            box.x = 0
            box.y = prev_box.y + 1.1
            if not prev_box.blue:
                row = boxes[last_break:i]
                slack = big_box.w - (row[-1].x + row[-1].w)
                reds = [b for b in row if b.red]
                # sometimes there is no red in the row. Do nothing.
                if reds:
                    mini_slack = slack / len(reds)
                    for b in reds:
                        b.w += mini_slack
                    for j, b in enumerate(row[1:], 1):
                        b.x = row[j-1].x + row[j-1].w + separation
            last_break = i

# What if we want blue boxes break lines but also separate lines a little?

def layout8(boxes):
    last_break = 0
    for i, box in enumerate(boxes[1:], 1):
        prev_box = boxes[i-1]
        box.x = prev_box.x + prev_box.w + separation
        box.y = prev_box.y
        if prev_box.blue or box.x > big_box.w:
            box.x = 0
            if prev_box.blue:
                box.y = prev_box.y + 2.1
            else: # not blue
                box.y = prev_box.y + 1.1
                row = boxes[last_break:i]
                slack = big_box.w - (row[-1].x + row[-1].w)
                reds = [b for b in row if b.red]
                # sometimes there is no red in the row. Do nothing.
                if reds:
                    mini_slack = slack / len(reds)
                    for b in reds:
                        b.w += mini_slack
                    for j, b in enumerate(row[1:], 1):
                        b.x = row[j-1].x + row[j-1].w + separation
            last_break = i


# So ... what if each box has a letter or a space inside it?
for box in many_boxes:
    # More than one space so they appear often
    box.letter = random.choice('     abcdefghijklmnopqrstuvwxyz')

# Maybe we should make the box sizes depend on the letter inside it?
# This is complicated, sorry
import harfbuzz as hb
import freetype2 as ft

def adjust_widths_by_letter(boxes):
    buf = hb.Buffer.create()
    buf.add_str(''.join(b.letter for b in boxes))
    buf.guess_segment_properties()
    font_lib =  ft.get_default_lib()
    face = font_lib.find_face('Arial')
    face.set_char_size(size = 1, resolution=64)
    font = hb.Font.ft_create(face)
    hb.shape(font, buf)
    # at this point buf.glyph_positions has all the data we need
    for box, position in zip(boxes, buf.glyph_positions):
        box.w = position.x_advance

adjust_widths_by_letter(many_boxes)
# layout8(many_boxes)

# There is all that space between letters we added when they were boxes. Let's remove it.

separation = 0
layout8(many_boxes)

# How about we get the letters from a text instead of randomly?
p_and_p = open('pride-and-prejudice.txt').read()
text_boxes = []
for l in p_and_p:
    text_boxes.append(Box(letter=l))
adjust_widths_by_letter(text_boxes)
# layout8(text_boxes)
# Oh, it's all green now, and it's all one thing after another. We should make newlines blue!

for b in text_boxes:
    if b.letter == '\n':
        b.blue = True
# layout8(text_boxes)

# Better, but newlines should not really take any space should they?
def add_blue(boxes):
    for b in boxes:
        if b.letter == '\n':
            b.blue = True
            b.w = 0
add_blue(text_boxes)
# layout8(text_boxes)

# Our big_box is very wide now, that is why we have long lines. Let's make it narrower
big_box = Box(0, 0, 30, 1000)
# layout8(text_boxes)

# But our right side is ragged again! We should make spaces red.
def add_red(boxes):
    for b in boxes:
        if b.letter == ' ':
            b.red = True
add_red(text_boxes)
# layout8(text_boxes)

# The second paragraph of Chapter 1 shows a red space as first thing in the row, and that looks bad!
# So, when the 1st letter in a row is a space, let's make it take no width and not stretch

def layout9(boxes):
    last_break = 0
    for i, box in enumerate(boxes[1:], 1):
        prev_box = boxes[i-1]
        box.x = prev_box.x + prev_box.w + separation
        box.y = prev_box.y
        if prev_box.blue or box.x > big_box.w:
            box.x = 0
            if box.red:
                box.w = 0
            if prev_box.blue:
                box.y = prev_box.y + 2.1
            else: # not blue
                box.y = prev_box.y + 1.1
                row = boxes[last_break:i]
                slack = big_box.w - (row[-1].x + row[-1].w)
                # If the 1st thing is a red, that one doesn't stretch
                reds = [b for b in row[1:] if b.red]
                # sometimes there is no red in the row. Do nothing.
                if reds:
                    mini_slack = slack / len(reds)
                    for b in reds:
                        b.w += mini_slack
                    for j, b in enumerate(row[1:], 1):
                        b.x = row[j-1].x + row[j-1].w + separation
            last_break = i

# Just for fun, let's draw it without the colored boxes
# layout9(text_boxes)
# draw_boxes(text_boxes, False)

# XXX layout9 rewritten using pop(), need to backport this version

def layout10(_boxes):
    boxes = _boxes[:]  # Work on a copy
    prev_box = boxes.pop(0)
    row = [prev_box]
    while(boxes):
        box = boxes.pop(0)
        row.append(box)
        box.x = prev_box.x + prev_box.w + separation
        box.y = prev_box.y
        if prev_box.blue or box.x > big_box.w:
            box.x = 0
            row.pop()  # our box will go in the next row
            if box.red:
                box.w = 0
            if prev_box.blue:
                box.y = prev_box.y + 2.1

            else: # not blue
                box.y = prev_box.y + 1.1
                slack = big_box.w - (row[-1].x + row[-1].w)
                # If the 1st thing is a red, that one doesn't stretch
                reds = [b for b in row[1:] if b.red]
                # sometimes there is no red in the row. Do nothing.
                if reds:
                    mini_slack = slack / len(reds)
                    for b in reds:
                        b.w += mini_slack
                    for j, b in enumerate(row[1:], 1):
                        b.x = row[j-1].x + row[j-1].w + separation
            row = [box]
        prev_box = box

# layout10(text_boxes)

# Looks good, except that the words are broken wrong. You can't break good like: g
# ood!

# What if we only break on spaces?

def layout11(_boxes):
    boxes = _boxes[:]  # Work on a copy
    prev_box = boxes.pop(0)
    row = [prev_box]
    while(boxes):
        box = boxes.pop(0)
        row.append(box)
        box.x = prev_box.x + prev_box.w + separation
        box.y = prev_box.y
        if prev_box.blue or (box.x > big_box.w and box.red) :
            row.pop()  # our box will go in the next row
            box.x = 0
            if box.red:
                box.w = 0
            if prev_box.blue:
                box.y = prev_box.y + 2.1

            else: # not blue
                box.y = prev_box.y + 1.1
                slack = big_box.w - (row[-1].x + row[-1].w)
                # If the 1st thing is a red, that one doesn't stretch
                reds = [b for b in row[1:] if b.red]
                # sometimes there is no red in the row. Do nothing.
                if reds:
                    mini_slack = slack / len(reds)
                    for b in reds:
                        b.w += mini_slack
                    for j, b in enumerate(row[1:], 1):
                        b.x = row[j-1].x + row[j-1].w + separation
            row = [box]
        prev_box = box

# layout11(text_boxes)

# That actually ... worked? Except that when we need to fit something wider than
# big_box because we did not break the row, the slack is NEGATIVE and words get
# smushed together!

# What we actually need is hyphenation.
# We can use pyphen to insert soft-hyphen characters wherever words can break.
# And we can mark those positions yellow.

import pyphen
hyphenator = pyphen.Pyphen(lang='en_GB')  # These things are language dependent

p_and_p = open('pride-and-prejudice.txt').readlines()
for i, l in enumerate(p_and_p):
    words = l.split(' ')
    p_and_p[i] = ' '.join(hyphenator.inserted(w, '\u00AD') for w in words)
p_and_p = ''.join(p_and_p)

text_boxes = []
for l in p_and_p:
    text_boxes.append(Box(letter=l))


# This makes the characters '\u00AD' (soft-hyphen) yellow.
def add_yellow(boxes):
    for b in boxes:
        if b.letter == '\u00AD':
            b.yellow = True

add_blue(text_boxes)
add_red(text_boxes)
add_yellow(text_boxes)
adjust_widths_by_letter(text_boxes)

# And create a new layout function that also breaks on yellow boxes.

def layout12(_boxes):
    boxes = _boxes[:]  # Work on a copy
    prev_box = boxes.pop(0)
    row = [prev_box]
    while(boxes):
        box = boxes.pop(0)
        row.append(box)
        box.x = prev_box.x + prev_box.w + separation
        box.y = prev_box.y
        if prev_box.blue or (box.x > big_box.w and (box.red or box.yellow)) :
            row.pop()  # our box will go in the next row
            box.x = 0
            if box.red:
                box.w = 0
            if prev_box.blue:
                box.y = prev_box.y + 2.1

            else: # not blue
                box.y = prev_box.y + 1.1
                slack = big_box.w - (row[-1].x + row[-1].w)
                # If the 1st thing is a red, that one doesn't stretch
                reds = [b for b in row[1:] if b.red]
                # sometimes there is no red in the row. Do nothing.
                if reds:
                    mini_slack = slack / len(reds)
                    for b in reds:
                        b.w += mini_slack
                    for j, b in enumerate(row[1:], 1):
                        b.x = row[j-1].x + row[j-1].w + separation
            row = [box]
        prev_box = box

# layout12(text_boxes)

# Better! Since we have more break chances, there is less word-smushing.
# However our typography is wrong, because we are hyphenating but not showing a hyphen!
# So, we need to ADD a box when we hyphenate. That special box is hyphenbox():

def hyphenbox():  # Yes, this is not optimal
    b = Box(letter='-', yellow=True)
    adjust_widths_by_letter([b])
    return b

def layout13(_boxes):
    boxes = _boxes[:]  # Work on a copy
    prev_box = boxes.pop(0)
    row = [prev_box]
    while(boxes):
        box = boxes.pop(0)
        row.append(box)
        box.x = prev_box.x + prev_box.w + separation
        box.y = prev_box.y
        if prev_box.blue or (box.x > big_box.w and (box.red or box.yellow)):
            row.pop()  # our box will go in the next row
            if box.yellow:  # We need to insert the hyphen!
                h_b = hyphenbox()
                h_b.x = prev_box.x + prev_box.w + separation
                h_b.y = prev_box.y
                _boxes.append(h_b)  # So it's drawn
                row.append(h_b) # So it's justified
            box.x = 0
            if box.red:
                box.w = 0
            if prev_box.blue:
                box.y = prev_box.y + 2.1

            else: # not blue
                box.y = prev_box.y + 1.1
                slack = big_box.w - (row[-1].x + row[-1].w)
                # If the 1st thing is a red, that one doesn't stretch
                reds = [b for b in row[1:] if b.red]
                # sometimes there is no red in the row. Do nothing.
                if reds:
                    mini_slack = slack / len(reds)
                    for b in reds:
                        b.w += mini_slack
                    for j, b in enumerate(row[1:], 1):
                        b.x = row[j-1].x + row[j-1].w + separation
            row = [box]
        prev_box = box


# layout13(text_boxes)

# Good. However, we still have smushing. It's usually considered better to make spaces
# between words grow, rather than shrink. So, what we should do is, instead of breaking
# in the 1st yellow/red PAST the break, go back and break in the last BEFORE the break!

# XXX backport simplifications from layout14: separation of blue case

def layout14(_boxes):
    boxes = _boxes[:]  # Work on a copy
    row = [boxes.pop(0)]
    while(boxes):
        prev_box = row[-1]
        box = boxes.pop(0)
        row.append(box)
        box.x = prev_box.x + prev_box.w + separation
        box.y = prev_box.y
        if prev_box.blue:
            box.x = 0
            box.y = prev_box.y + 2.1
            row.pop()
            row=[box]

        elif box.x > big_box.w:
            while not (box.red or box.yellow):  # backtrack onw
                boxes.insert(0, row.pop())
                # tip of row is now box, previous one is prev_box
                box = row[-1]
                prev_box = row[-2]

            row.pop()  # Breaking box goes in next row
            if box.yellow:  # We need to insert the hyphen!
                h_b = hyphenbox()
                h_b.x = prev_box.x + prev_box.w + separation
                h_b.y = prev_box.y
                _boxes.append(h_b)  # So it's drawn
                row.append(h_b) # So it's justified
            box.x = 0
            box.y = prev_box.y + 1.1
            if box.red:
                box.w = 0
            slack = big_box.w - (row[-1].x + row[-1].w)
            # If the 1st thing is a red, that one doesn't stretch
            reds = [b for b in row[1:] if b.red]
            # sometimes there is no red in the row. Do nothing.
            if reds:
                mini_slack = slack / len(reds)
                for b in reds:
                    b.w += mini_slack
                for j, b in enumerate(row[1:], 1):
                    b.x = row[j-1].x + row[j-1].w + separation
            row = [box]

# With a little separation for niceness, the result is not half bad!
separation = 0.05
# layout14(text_boxes)

# So far, our big_box has been very, very tall. What would happen if it were short?
big_box = Box(0, 0, 30, 60)
# layout14(text_boxes)

# Well, that our text flows straight out of the box! And our initial problem was
# "So, how could we layout the many boxes inside the big_box?" !
# That won't do. Clearly, if we have more text than fits in a box, we need more than one
# box. Like pages.

# So, let's make many big boxes.


pages = [Box(0, i * 65, 30, 60) for i in range(50)]

# layout14(text_boxes)

# Of course our layout engine does nothing with those pages. Let's fix that.

def layout15(_boxes):
    boxes = _boxes[:]  # Work on a copy
    row = [boxes.pop(0)]

    # Put the 1st box in the beginning of the 1st page
    page = 0
    row[0].x = pages[page].x
    row[0].y = pages[page].y

    while(boxes):
        prev_box = row[-1]
        box = boxes.pop(0)
        row.append(box)
        box.x = prev_box.x + prev_box.w + separation
        box.y = prev_box.y
        if prev_box.blue:
            box.x = 0
            box.y = prev_box.y + 2.1
            row.pop()
            row=[box]

        elif box.x > pages[page].w:
            while not (box.red or box.yellow):  # backtrack onw
                boxes.insert(0, row.pop())
                # tip of row is now box, previous one is prev_box
                box = row[-1]
                prev_box = row[-2]

            row.pop()  # Breaking box goes in next row
            if box.yellow:  # We need to insert the hyphen!
                h_b = hyphenbox()
                h_b.x = prev_box.x + prev_box.w + separation
                h_b.y = prev_box.y
                _boxes.append(h_b)  # So it's drawn
                row.append(h_b) # So it's justified
            box.x = 0
            box.y = prev_box.y + 1.1
            if box.red:
                box.w = 0
            slack = pages[page].w - (row[-1].x + row[-1].w)
            # If the 1st thing is a red, that one doesn't stretch
            reds = [b for b in row[1:] if b.red]
            # sometimes there is no red in the row. Do nothing.
            if reds:
                mini_slack = slack / len(reds)
                for b in reds:
                    b.w += mini_slack
                for j, b in enumerate(row[1:], 1):
                    b.x = row[j-1].x + row[j-1].w + separation
            row = [box]

        if box.y + box.h > pages[page].y + pages[page].h:
            # We need to go to the next page
            page = page + 1
            box.y = pages[page].y


# layout15(text_boxes)
# And there you go, pagination

# What happens if pages are organized differently?
# Let's put them left-to-right
pages = [Box(i*35, 0, 30, 60) for i in range(50)]
# layout15(text_boxes)

# Everything is in the same page, because we are resetting x to 0 on line breaks.
# You always need to find your hidden assumptions.

def layout16(_boxes):
    boxes = _boxes[:]  # Work on a copy
    row = [boxes.pop(0)]

    # Put the 1st box in the beginning of the 1st page
    page = 0
    row[0].x = pages[page].x
    row[0].y = pages[page].y

    while(boxes):
        prev_box = row[-1]
        box = boxes.pop(0)
        row.append(box)
        box.x = prev_box.x + prev_box.w + separation
        box.y = prev_box.y
        if prev_box.blue:
            box.x = pages[page].x
            box.y = prev_box.y + 2.1
            row.pop()
            row=[box]

        elif box.x > pages[page].w + pages[page].x:
            while not (box.red or box.yellow):  # backtrack onw
                boxes.insert(0, row.pop())
                # tip of row is now box, previous one is prev_box
                box = row[-1]
                prev_box = row[-2]

            row.pop()  # Breaking box goes in next row
            if box.yellow:  # We need to insert the hyphen!
                h_b = hyphenbox()
                h_b.x = prev_box.x + prev_box.w + separation
                h_b.y = prev_box.y
                _boxes.append(h_b)  # So it's drawn
                row.append(h_b) # So it's justified
            box.x = pages[page].x
            box.y = prev_box.y + 1.1
            if box.red:
                box.w = 0
            slack = (pages[page].w + pages[page].x) - (row[-1].x + row[-1].w)
            # If the 1st thing is a red, that one doesn't stretch
            reds = [b for b in row[1:] if b.red]
            # sometimes there is no red in the row. Do nothing.
            if reds:
                mini_slack = slack / len(reds)
                for b in reds:
                    b.w += mini_slack
                for j, b in enumerate(row[1:], 1):
                    b.x = row[j-1].x + row[j-1].w + separation
            row = [box]

        # We may need to go to the next page
        if box.y + box.h > pages[page].y + pages[page].h:
            page = page + 1
            # Since the location of a page is arbitrary, both coordinates are reset
            box.y = pages[page].y
            box.x = pages[page].x

# This may even work with oddly-sized pages!
pages = [Box(i*35, 0, 20, 60 + random.randint(-20, 20)) for i in range(50)]

layout16(text_boxes)
draw_boxes(text_boxes, False)

# This is a good point to STOP. Look at the code, and clean house.
	import svgwrite

	class Box():
	def __init__(self, x=0, y=0, w=1, h=1, red=False, blue=False, yellow=False, letter=None):
	self.x = x
	self.y = y
	self.w = w
	self.h = h
	self.red = red
	self.blue = blue
	self.yellow = yellow
	self.letter = letter

	def __str__(self):
	return self.letter or 'Box'

	def __repr__(self):
	return self.letter or 'Box'

	big_box = Box(0, 0, 80, 1000)
	pages = [big_box]


	def draw_boxes(boxes, with_boxes=True):
	STYLES = """
	.red { fill: red;}
	.green { fill: green;}
	.blue {fill: blue;}
	.yellow {fill: yellow;}
	.bigbox {fill: cyan; }
	"""
	dwg = svgwrite.Drawing('test.svg', profile='full', size=('%d' % big_box.w, '%d' % big_box.w))
	dwg.defs.add(dwg.style(STYLES))
	for bb in pages:
	dwg.add(dwg.rect(insert=(bb.x,bb.y), size=(bb.w, bb.h), class_='bigbox'))
	for box in boxes:
	if with_boxes:
	if box.red:
	dwg.add(dwg.rect(insert=(box.x, box.y), size=(box.w, box.h), class_='red'))
	elif box.blue:
	dwg.add(dwg.rect(insert=(box.x, box.y), size=(box.w, box.h), class_='blue'))
	elif box.yellow:
	dwg.add(dwg.rect(insert=(box.x, box.y), size=(box.w, box.h), class_='yellow'))
	else:
	dwg.add(dwg.rect(insert=(box.x, box.y), size=(box.w, box.h), class_='green'))
	if box.letter:
	dwg.add(dwg.text(box.letter, insert=(box.x, box.y + box.h), font_size=box.h, font_family='Arial'))
	dwg.save()



	# So, how could we layout the many boxes inside the big_box?
	many_boxes = [Box(0, 0, 1, 1) for _ in range(5000)]

	# Do nothing ...
	# They are all in the same place
	# draw_boxes(many_boxes)

	# Try to lay them out side by side
	# They just go too wide
	# We add a "separation" constant so you can see the boxes individually
	separation = .2

	def layout1(boxes):
	for i, box in enumerate(boxes):
	box.x = i * (1 + separation)

	# Put each one next to the other until they reach a width,
	# then go down. This is a monospaced layout.

	def layout2(boxes):
	for i, box in enumerate(boxes[1:]):
	box.x = boxes[i-1].x + 1 + separation
	box.y = boxes[i-1].y
	if box.x > big_box.w:
	box.x = 0
	box.y = boxes[i-1].y + 1.1

	# Now, what happens if some boxes are wider than the others?
	# layout2 will make them overlap or have wide breaks between them
	import random
	many_boxes = [Box(0, 0, 1+random.randint(-2,2)/10, 1) for _ in range(5000)]

	# So, we use each box's width instead of a fixed width
	def layout3(boxes):
	for i, box in enumerate(boxes[1:], 1):
	prev_box = boxes[i-1]
	box.x = prev_box.x + prev_box.w + separation
	box.y = prev_box.y
	if box.x > big_box.w:
	box.x = 0
	box.y = prev_box.y + 1.1

	# layout3(many_boxes)
	# But the right side is ragged

	# We can, when we break, put the remaining space spread between boxes
	# This is a "justified" layout

	def layout4(boxes):
	last_break = 0
	for i, box in enumerate(boxes[1:], 1):
	prev_box = boxes[i-1]
	box.x = prev_box.x + prev_box.w + separation
	box.y = prev_box.y
	if box.x > big_box.w:
	box.x = 0
	box.y = prev_box.y + 1.1
	slack = big_box.w - (prev_box.x + prev_box.w)
	mini_slack = slack / (i-last_break)
	for j, b in enumerate(boxes[last_break:i]):
	b.x += j * mini_slack
	last_break = i
	# layout4(many_boxes)

	# But what happens if some boxes are red?
	for box in many_boxes:
	if random.randint(1,6) > 5:
	box.red = True
	# Well, nothing much, other than they are red

	# But what if red means "stretchy" and only those can stretch?
	def layout5(boxes):
	last_break = 0
	for i, box in enumerate(boxes[1:], 1):
	prev_box = boxes[i-1]
	box.x = prev_box.x + prev_box.w + separation
	box.y = prev_box.y
	if box.x > big_box.w:
	box.x = 0
	box.y = prev_box.y + 1.1
	slack = big_box.w - (prev_box.x + prev_box.w)
	row = boxes[last_break:i]
	reds = [b for b in row if b.red]
	# sometimes there is no red in the row. Do nothing.
	if reds:
	mini_slack = slack / len(reds)
	for b in reds:
	b.w += mini_slack
	for j, b in enumerate(row[1:], 1):
	b.x = row[j-1].x + row[j-1].w + separation
	last_break = i

	# But what happens if a few are blue?
	for box in many_boxes:
	if random.randint(1,150) > 149:
	box.blue = True

	# Well, nothing much, other than they are blue

	# But what if blue means "this row ends here"?
	def layout6(boxes):
	last_break = 0
	for i, box in enumerate(boxes[1:], 1):
	prev_box = boxes[i-1]
	box.x = prev_box.x + prev_box.w + separation
	box.y = prev_box.y
	if prev_box.blue or box.x > big_box.w:
	box.x = 0
	box.y = prev_box.y + 1.1
	slack = big_box.w - (prev_box.x + prev_box.w)
	row = boxes[last_break:i]
	reds = [b for b in row if b.red]
	# sometimes there is no red in the row. Do nothing.
	if reds:
	mini_slack = slack / len(reds)
	for b in reds:
	b.w += mini_slack
	for j, b in enumerate(row[1:], 1):
	b.x = row[j-1].x + row[j-1].w + separation
	last_break = i
	# Some reds get reeeeeeealy stretchy! That is because rows that
	# end because of a blue have very few boxes. So maybe we don't stretch those?

	def layout7(boxes):
	last_break = 0
	for i, box in enumerate(boxes[1:], 1):
	prev_box = boxes[i-1]
	box.x = prev_box.x + prev_box.w + separation
	box.y = prev_box.y
	if prev_box.blue or box.x > big_box.w:
	box.x = 0
	box.y = prev_box.y + 1.1
	if not prev_box.blue:
	row = boxes[last_break:i]
	slack = big_box.w - (row[-1].x + row[-1].w)
	reds = [b for b in row if b.red]
	# sometimes there is no red in the row. Do nothing.
	if reds:
	mini_slack = slack / len(reds)
	for b in reds:
	b.w += mini_slack
	for j, b in enumerate(row[1:], 1):
	b.x = row[j-1].x + row[j-1].w + separation
	last_break = i

	# What if we want blue boxes break lines but also separate lines a little?

	def layout8(boxes):
	last_break = 0
	for i, box in enumerate(boxes[1:], 1):
	prev_box = boxes[i-1]
	box.x = prev_box.x + prev_box.w + separation
	box.y = prev_box.y
	if prev_box.blue or box.x > big_box.w:
	box.x = 0
	if prev_box.blue:
	box.y = prev_box.y + 2.1
	else: # not blue
	box.y = prev_box.y + 1.1
	row = boxes[last_break:i]
	slack = big_box.w - (row[-1].x + row[-1].w)
	reds = [b for b in row if b.red]
	# sometimes there is no red in the row. Do nothing.
	if reds:
	mini_slack = slack / len(reds)
	for b in reds:
	b.w += mini_slack
	for j, b in enumerate(row[1:], 1):
	b.x = row[j-1].x + row[j-1].w + separation
	last_break = i


	# So ... what if each box has a letter or a space inside it?
	for box in many_boxes:
	# More than one space so they appear often
	box.letter = random.choice(' abcdefghijklmnopqrstuvwxyz')

	# Maybe we should make the box sizes depend on the letter inside it?
	# This is complicated, sorry
	import harfbuzz as hb
	import freetype2 as ft

	def adjust_widths_by_letter(boxes):
	buf = hb.Buffer.create()
	buf.add_str(''.join(b.letter for b in boxes))
	buf.guess_segment_properties()
	font_lib = ft.get_default_lib()
	face = font_lib.find_face('Arial')
	face.set_char_size(size = 1, resolution=64)
	font = hb.Font.ft_create(face)
	hb.shape(font, buf)
	# at this point buf.glyph_positions has all the data we need
	for box, position in zip(boxes, buf.glyph_positions):
	box.w = position.x_advance

	adjust_widths_by_letter(many_boxes)
	# layout8(many_boxes)

	# There is all that space between letters we added when they were boxes. Let's remove it.

	separation = 0
	layout8(many_boxes)

	# How about we get the letters from a text instead of randomly?
	p_and_p = open('pride-and-prejudice.txt').read()
	text_boxes = []
	for l in p_and_p:
	text_boxes.append(Box(letter=l))
	adjust_widths_by_letter(text_boxes)
	# layout8(text_boxes)
	# Oh, it's all green now, and it's all one thing after another. We should make newlines blue!

	for b in text_boxes:
	if b.letter == '\n':
	b.blue = True
	# layout8(text_boxes)

	# Better, but newlines should not really take any space should they?
	def add_blue(boxes):
	for b in boxes:
	if b.letter == '\n':
	b.blue = True
	b.w = 0
	add_blue(text_boxes)
	# layout8(text_boxes)

	# Our big_box is very wide now, that is why we have long lines. Let's make it narrower
	big_box = Box(0, 0, 30, 1000)
	# layout8(text_boxes)

	# But our right side is ragged again! We should make spaces red.
	def add_red(boxes):
	for b in boxes:
	if b.letter == ' ':
	b.red = True
	add_red(text_boxes)
	# layout8(text_boxes)

	# The second paragraph of Chapter 1 shows a red space as first thing in the row, and that looks bad!
	# So, when the 1st letter in a row is a space, let's make it take no width and not stretch

	def layout9(boxes):
	last_break = 0
	for i, box in enumerate(boxes[1:], 1):
	prev_box = boxes[i-1]
	box.x = prev_box.x + prev_box.w + separation
	box.y = prev_box.y
	if prev_box.blue or box.x > big_box.w:
	box.x = 0
	if box.red:
	box.w = 0
	if prev_box.blue:
	box.y = prev_box.y + 2.1
	else: # not blue
	box.y = prev_box.y + 1.1
	row = boxes[last_break:i]
	slack = big_box.w - (row[-1].x + row[-1].w)
	# If the 1st thing is a red, that one doesn't stretch
	reds = [b for b in row[1:] if b.red]
	# sometimes there is no red in the row. Do nothing.
	if reds:
	mini_slack = slack / len(reds)
	for b in reds:
	b.w += mini_slack
	for j, b in enumerate(row[1:], 1):
	b.x = row[j-1].x + row[j-1].w + separation
	last_break = i

	# Just for fun, let's draw it without the colored boxes
	# layout9(text_boxes)
	# draw_boxes(text_boxes, False)

	# XXX layout9 rewritten using pop(), need to backport this version

	def layout10(_boxes):
	boxes = _boxes[:] # Work on a copy
	prev_box = boxes.pop(0)
	row = [prev_box]
	while(boxes):
	box = boxes.pop(0)
	row.append(box)
	box.x = prev_box.x + prev_box.w + separation
	box.y = prev_box.y
	if prev_box.blue or box.x > big_box.w:
	box.x = 0
	row.pop() # our box will go in the next row
	if box.red:
	box.w = 0
	if prev_box.blue:
	box.y = prev_box.y + 2.1

	else: # not blue
	box.y = prev_box.y + 1.1
	slack = big_box.w - (row[-1].x + row[-1].w)
	# If the 1st thing is a red, that one doesn't stretch
	reds = [b for b in row[1:] if b.red]
	# sometimes there is no red in the row. Do nothing.
	if reds:
	mini_slack = slack / len(reds)
	for b in reds:
	b.w += mini_slack
	for j, b in enumerate(row[1:], 1):
	b.x = row[j-1].x + row[j-1].w + separation
	row = [box]
	prev_box = box

	# layout10(text_boxes)

	# Looks good, except that the words are broken wrong. You can't break good like: g
	# ood!

	# What if we only break on spaces?

	def layout11(_boxes):
	boxes = _boxes[:] # Work on a copy
	prev_box = boxes.pop(0)
	row = [prev_box]
	while(boxes):
	box = boxes.pop(0)
	row.append(box)
	box.x = prev_box.x + prev_box.w + separation
	box.y = prev_box.y
	if prev_box.blue or (box.x > big_box.w and box.red) :
	row.pop() # our box will go in the next row
	box.x = 0
	if box.red:
	box.w = 0
	if prev_box.blue:
	box.y = prev_box.y + 2.1

	else: # not blue
	box.y = prev_box.y + 1.1
	slack = big_box.w - (row[-1].x + row[-1].w)
	# If the 1st thing is a red, that one doesn't stretch
	reds = [b for b in row[1:] if b.red]
	# sometimes there is no red in the row. Do nothing.
	if reds:
	mini_slack = slack / len(reds)
	for b in reds:
	b.w += mini_slack
	for j, b in enumerate(row[1:], 1):
	b.x = row[j-1].x + row[j-1].w + separation
	row = [box]
	prev_box = box

	# layout11(text_boxes)

	# That actually ... worked? Except that when we need to fit something wider than
	# big_box because we did not break the row, the slack is NEGATIVE and words get
	# smushed together!

	# What we actually need is hyphenation.
	# We can use pyphen to insert soft-hyphen characters wherever words can break.
	# And we can mark those positions yellow.

	import pyphen
	hyphenator = pyphen.Pyphen(lang='en_GB') # These things are language dependent

	p_and_p = open('pride-and-prejudice.txt').readlines()
	for i, l in enumerate(p_and_p):
	words = l.split(' ')
	p_and_p[i] = ' '.join(hyphenator.inserted(w, '\u00AD') for w in words)
	p_and_p = ''.join(p_and_p)

	text_boxes = []
	for l in p_and_p:
	text_boxes.append(Box(letter=l))


	# This makes the characters '\u00AD' (soft-hyphen) yellow.
	def add_yellow(boxes):
	for b in boxes:
	if b.letter == '\u00AD':
	b.yellow = True

	add_blue(text_boxes)
	add_red(text_boxes)
	add_yellow(text_boxes)
	adjust_widths_by_letter(text_boxes)

	# And create a new layout function that also breaks on yellow boxes.

	def layout12(_boxes):
	boxes = _boxes[:] # Work on a copy
	prev_box = boxes.pop(0)
	row = [prev_box]
	while(boxes):
	box = boxes.pop(0)
	row.append(box)
	box.x = prev_box.x + prev_box.w + separation
	box.y = prev_box.y
	if prev_box.blue or (box.x > big_box.w and (box.red or box.yellow)) :
	row.pop() # our box will go in the next row
	box.x = 0
	if box.red:
	box.w = 0
	if prev_box.blue:
	box.y = prev_box.y + 2.1

	else: # not blue
	box.y = prev_box.y + 1.1
	slack = big_box.w - (row[-1].x + row[-1].w)
	# If the 1st thing is a red, that one doesn't stretch
	reds = [b for b in row[1:] if b.red]
	# sometimes there is no red in the row. Do nothing.
	if reds:
	mini_slack = slack / len(reds)
	for b in reds:
	b.w += mini_slack
	for j, b in enumerate(row[1:], 1):
	b.x = row[j-1].x + row[j-1].w + separation
	row = [box]
	prev_box = box

	# layout12(text_boxes)

	# Better! Since we have more break chances, there is less word-smushing.
	# However our typography is wrong, because we are hyphenating but not showing a hyphen!
	# So, we need to ADD a box when we hyphenate. That special box is hyphenbox():

	def hyphenbox(): # Yes, this is not optimal
	b = Box(letter='-', yellow=True)
	adjust_widths_by_letter([b])
	return b

	def layout13(_boxes):
	boxes = _boxes[:] # Work on a copy
	prev_box = boxes.pop(0)
	row = [prev_box]
	while(boxes):
	box = boxes.pop(0)
	row.append(box)
	box.x = prev_box.x + prev_box.w + separation
	box.y = prev_box.y
	if prev_box.blue or (box.x > big_box.w and (box.red or box.yellow)):
	row.pop() # our box will go in the next row
	if box.yellow: # We need to insert the hyphen!
	h_b = hyphenbox()
	h_b.x = prev_box.x + prev_box.w + separation
	h_b.y = prev_box.y
	_boxes.append(h_b) # So it's drawn
	row.append(h_b) # So it's justified
	box.x = 0
	if box.red:
	box.w = 0
	if prev_box.blue:
	box.y = prev_box.y + 2.1

	else: # not blue
	box.y = prev_box.y + 1.1
	slack = big_box.w - (row[-1].x + row[-1].w)
	# If the 1st thing is a red, that one doesn't stretch
	reds = [b for b in row[1:] if b.red]
	# sometimes there is no red in the row. Do nothing.
	if reds:
	mini_slack = slack / len(reds)
	for b in reds:
	b.w += mini_slack
	for j, b in enumerate(row[1:], 1):
	b.x = row[j-1].x + row[j-1].w + separation
	row = [box]
	prev_box = box


	# layout13(text_boxes)

	# Good. However, we still have smushing. It's usually considered better to make spaces
	# between words grow, rather than shrink. So, what we should do is, instead of breaking
	# in the 1st yellow/red PAST the break, go back and break in the last BEFORE the break!

	# XXX backport simplifications from layout14: separation of blue case

	def layout14(_boxes):
	boxes = _boxes[:] # Work on a copy
	row = [boxes.pop(0)]
	while(boxes):
	prev_box = row[-1]
	box = boxes.pop(0)
	row.append(box)
	box.x = prev_box.x + prev_box.w + separation
	box.y = prev_box.y
	if prev_box.blue:
	box.x = 0
	box.y = prev_box.y + 2.1
	row.pop()
	row=[box]

	elif box.x > big_box.w:
	while not (box.red or box.yellow): # backtrack onw
	boxes.insert(0, row.pop())
	# tip of row is now box, previous one is prev_box
	box = row[-1]
	prev_box = row[-2]

	row.pop() # Breaking box goes in next row
	if box.yellow: # We need to insert the hyphen!
	h_b = hyphenbox()
	h_b.x = prev_box.x + prev_box.w + separation
	h_b.y = prev_box.y
	_boxes.append(h_b) # So it's drawn
	row.append(h_b) # So it's justified
	box.x = 0
	box.y = prev_box.y + 1.1
	if box.red:
	box.w = 0
	slack = big_box.w - (row[-1].x + row[-1].w)
	# If the 1st thing is a red, that one doesn't stretch
	reds = [b for b in row[1:] if b.red]
	# sometimes there is no red in the row. Do nothing.
	if reds:
	mini_slack = slack / len(reds)
	for b in reds:
	b.w += mini_slack
	for j, b in enumerate(row[1:], 1):
	b.x = row[j-1].x + row[j-1].w + separation
	row = [box]

	# With a little separation for niceness, the result is not half bad!
	separation = 0.05
	# layout14(text_boxes)

	# So far, our big_box has been very, very tall. What would happen if it were short?
	big_box = Box(0, 0, 30, 60)
	# layout14(text_boxes)

	# Well, that our text flows straight out of the box! And our initial problem was
	# "So, how could we layout the many boxes inside the big_box?" !
	# That won't do. Clearly, if we have more text than fits in a box, we need more than one
	# box. Like pages.

	# So, let's make many big boxes.


	pages = [Box(0, i * 65, 30, 60) for i in range(50)]

	# layout14(text_boxes)

	# Of course our layout engine does nothing with those pages. Let's fix that.

	def layout15(_boxes):
	boxes = _boxes[:] # Work on a copy
	row = [boxes.pop(0)]

	# Put the 1st box in the beginning of the 1st page
	page = 0
	row[0].x = pages[page].x
	row[0].y = pages[page].y

	while(boxes):
	prev_box = row[-1]
	box = boxes.pop(0)
	row.append(box)
	box.x = prev_box.x + prev_box.w + separation
	box.y = prev_box.y
	if prev_box.blue:
	box.x = 0
	box.y = prev_box.y + 2.1
	row.pop()
	row=[box]

	elif box.x > pages[page].w:
	while not (box.red or box.yellow): # backtrack onw
	boxes.insert(0, row.pop())
	# tip of row is now box, previous one is prev_box
	box = row[-1]
	prev_box = row[-2]

	row.pop() # Breaking box goes in next row
	if box.yellow: # We need to insert the hyphen!
	h_b = hyphenbox()
	h_b.x = prev_box.x + prev_box.w + separation
	h_b.y = prev_box.y
	_boxes.append(h_b) # So it's drawn
	row.append(h_b) # So it's justified
	box.x = 0
	box.y = prev_box.y + 1.1
	if box.red:
	box.w = 0
	slack = pages[page].w - (row[-1].x + row[-1].w)
	# If the 1st thing is a red, that one doesn't stretch
	reds = [b for b in row[1:] if b.red]
	# sometimes there is no red in the row. Do nothing.
	if reds:
	mini_slack = slack / len(reds)
	for b in reds:
	b.w += mini_slack
	for j, b in enumerate(row[1:], 1):
	b.x = row[j-1].x + row[j-1].w + separation
	row = [box]

	if box.y + box.h > pages[page].y + pages[page].h:
	# We need to go to the next page
	page = page + 1
	box.y = pages[page].y


	# layout15(text_boxes)
	# And there you go, pagination

	# What happens if pages are organized differently?
	# Let's put them left-to-right
	pages = [Box(i*35, 0, 30, 60) for i in range(50)]
	# layout15(text_boxes)

	# Everything is in the same page, because we are resetting x to 0 on line breaks.
	# You always need to find your hidden assumptions.

	def layout16(_boxes):
	boxes = _boxes[:] # Work on a copy
	row = [boxes.pop(0)]

	# Put the 1st box in the beginning of the 1st page
	page = 0
	row[0].x = pages[page].x
	row[0].y = pages[page].y

	while(boxes):
	prev_box = row[-1]
	box = boxes.pop(0)
	row.append(box)
	box.x = prev_box.x + prev_box.w + separation
	box.y = prev_box.y
	if prev_box.blue:
	box.x = pages[page].x
	box.y = prev_box.y + 2.1
	row.pop()
	row=[box]

	elif box.x > pages[page].w + pages[page].x:
	while not (box.red or box.yellow): # backtrack onw
	boxes.insert(0, row.pop())
	# tip of row is now box, previous one is prev_box
	box = row[-1]
	prev_box = row[-2]

	row.pop() # Breaking box goes in next row
	if box.yellow: # We need to insert the hyphen!
	h_b = hyphenbox()
	h_b.x = prev_box.x + prev_box.w + separation
	h_b.y = prev_box.y
	_boxes.append(h_b) # So it's drawn
	row.append(h_b) # So it's justified
	box.x = pages[page].x
	box.y = prev_box.y + 1.1
	if box.red:
	box.w = 0
	slack = (pages[page].w + pages[page].x) - (row[-1].x + row[-1].w)
	# If the 1st thing is a red, that one doesn't stretch
	reds = [b for b in row[1:] if b.red]
	# sometimes there is no red in the row. Do nothing.
	if reds:
	mini_slack = slack / len(reds)
	for b in reds:
	b.w += mini_slack
	for j, b in enumerate(row[1:], 1):
	b.x = row[j-1].x + row[j-1].w + separation
	row = [box]

	# We may need to go to the next page
	if box.y + box.h > pages[page].y + pages[page].h:
	page = page + 1
	# Since the location of a page is arbitrary, both coordinates are reset
	box.y = pages[page].y
	box.x = pages[page].x

	# This may even work with oddly-sized pages!
	pages = [Box(i*35, 0, 20, 60 + random.randint(-20, 20)) for i in range(50)]

	layout16(text_boxes)
	draw_boxes(text_boxes, False)

	# This is a good point to STOP. Look at the code, and clean house.