// Package bits provides a bit vector backed with uints
package bits

import (
	"strconv"
)

// The Vector interface defines methods on the bit vector
type Vector interface {
	// Retrieves the bit at the designated position
	Peek(uint) bool
	// Sets the bit at the designated position
	Poke(uint, bool)
	// Flips the bit at the designated position
	Flip(uint)
	// Returns the total number of elements supported by the vector
	Len() uint
}

type boolvector []bool

// Retrieves the bit at the designated position
func (v boolvector) Peek(pos uint) bool {
	return v[pos]
}

// Sets the bit at the designated position
func (v boolvector) Poke(pos uint, val bool) {
	v[pos] = val
}

// Flips the bit at the designated position
func (v boolvector) Flip(pos uint) {
	v[pos] = !v[pos]
}

// Returns the total number of elements supported by the vector
func (v boolvector) Len() uint {
	return uint(len(v))
}

type vector []uint

// Retrieves the bit at the designated position
func (v vector) Peek(pos uint) bool {
	var slot, offset uint = at(pos)
	return (v[slot] & (1 << offset)) > 0
}

// Sets the bit at the designated position
func (v vector) Poke(pos uint, val bool) {
	var slot, offset uint = at(pos)
	if val {
		v[slot] |= (1 << offset)
	} else {
		v[slot] &^= (1 << offset)
	}
}

// Flips the bit at the designated position
func (v vector) Flip(pos uint) {
	var slot, offset uint = at(pos)
	v[slot] ^= (1 << offset)
}

// Returns the total number of elements supported by the vector
func (v vector) Len() uint {
	return uint(len(v) * strconv.IntSize)
}

func at(pos uint) (uint, uint) {
	return pos / strconv.IntSize, pos % strconv.IntSize
}

// Create a new bit vector sized up to the desired number of elements
func New(size uint) Vector {
	var length uint = size / strconv.IntSize

	if size%strconv.IntSize > 0 {
		// Allocate one additional slot if the desired
		// size is does not divide by 32/64
		length++
	}

	var slice []uint = make([]uint, length)
	return vector(slice)
}

func NewBool(size uint) Vector {
	var slice []bool = make([]bool, size)
	return boolvector(slice)
}

package bits

import (
	"strconv"
	"testing"
)

func TestSize(t *testing.T) {
	sizes := []uint{0, 31, 32, 33, 61, 63, 64, 127, 128, 129}

	for _, size := range sizes {
		v := New(size)
		if v.Len() < size || v.Len() > size+strconv.IntSize {
			t.Error("Invalid length", v.Len(), "expected", size)
		}
	}
}

func TestEmpty(t *testing.T) {
	var size uint = 128
	v := New(size)

	// Check if it is empty by default
	for i := uint(0); i < size; i++ {
		if v.Peek(i) {
			t.Error("Invalid raised bit at", i)
		}
	}
}

func TestBasic(t *testing.T) {
	var size uint = 128
	v := New(size)

	// Raise and lower each position explicitly
	for i := uint(0); i < size; i++ {
		v.Poke(i, true)
		if !v.Peek(i) {
			t.Error("Invalid lowered bit at", i)
		}

		v.Poke(i, false)
		if v.Peek(i) {
			t.Error("Invalid raised bit at", i)
		}
	}
}

func TestFlip(t *testing.T) {
	var size uint = 128
	v := New(size)

	// Raise and lower each position by flipping
	for i := uint(0); i < size; i++ {
		v.Flip(i)
		if !v.Peek(i) {
			t.Error("Invalid lowered bit at", i)
		}

		v.Flip(i)
		if v.Peek(i) {
			t.Error("Invalid raised bit at", i)
		}
	}
}

package main

import (
	diff "0dev.org/diff"
	"bufio"
	"flag"
	"fmt"
	"hash"
	"hash/fnv"
	"io"
	"os"
)

const usage = "Usage: plaindiff <file1> <file2>"

func main() {
	flag.Parse()

	var args []string = flag.Args()
	if len(args) != 2 {
		os.Stderr.WriteString(usage)
		os.Exit(1)
	}

	var hd hashDiff
	hd.hash = fnv.New64a()
	hd.first = read(args[0], hd.hash)
	hd.second = read(args[1], hd.hash)

	var result diff.Delta = diff.Diff(&hd)
	//var marks []diff.Mark = make([]diff.Mark, len(result.Added)+len(result.Removed))

	//var added, removed []diff.Mark = result.Added, result.Removed
	fmt.Println(result)

	gen := source(result)
	for have, added, mark := gen(); have; have, added, mark = gen() {
		var from []line
		if added {
			from = hd.second
		} else {
			from = hd.first
		}

		fmt.Println()
		for i := mark.From; i < mark.Length; i++ {
			fmt.Print(i)
			if added {
				fmt.Print(" > ")
			} else {
				fmt.Print(" < ")
			}
			fmt.Println(from[i].text)
		}
	}

}

func source(d diff.Delta) func() (bool, bool, diff.Mark) {
	var addedAt, removedAt int = 0, 0
	return func() (bool, bool, diff.Mark) {
		var addsOver bool = addedAt == len(d.Added)
		var removesOver bool = removedAt == len(d.Removed)

		var add, remove diff.Mark

		// Check whether both mark slices have been exhausted
		if addsOver && removesOver {
			return false, false, diff.Mark{}
		}

		// Return an add if removes are over
		if removesOver {
			add = d.Added[addedAt]
			addedAt++
			return true, true, add
		}

		// Return a remove if the adds are over
		if addsOver {
			remove = d.Removed[removedAt]
			removedAt++
			return true, false, remove
		}

		add = d.Added[addedAt]
		remove = d.Removed[removedAt]

		// Prioritize a remove if it happens before an add
		if remove.From <= add.From {
			removedAt++
			return true, false, remove
		}

		// Else
		addedAt++
		return true, true, add

	}
}

// A line-based diff.Interface implementation
type hashDiff struct {
	first, second []line
	hash          hash.Hash64
}

func (h *hashDiff) Equal(i, j int) bool {
	// return h.first[i].text == h.second[j].text
	if h.first[i].hash != h.second[j].hash {
		return false
	} else {
		return h.first[i].text == h.second[j].text
	}
}

func (h *hashDiff) Len() (int, int) {
	return len(h.first), len(h.second)
}

type line struct {
	hash uint64
	text string
}

// Reads all lines in a file and returns a line entry for each
func read(name string, h hash.Hash64) []line {
	var f *os.File
	var e error

	f, e = os.Open(name)
	fatal(e)

	var result []line = lines(f, h)
	fatal(f.Close())

	return result
}

// Reads all lines and returns a line entry for each
func lines(r io.Reader, h hash.Hash64) []line {
	var scanner *bufio.Scanner = bufio.NewScanner(r)
	var result []line = make([]line, 0)
	for scanner.Scan() {
		h.Reset()
		h.Write(scanner.Bytes())
		result = append(result, line{hash: h.Sum64(), text: scanner.Text()})
	}
	return result
}

// Write an error to stderr
func stderr(e error) {
	if e != nil {
		os.Stderr.WriteString(e.Error())
	}
}

// Write an error to stderr and exit
func fatal(e error) {
	if e != nil {
		stderr(e)
		os.Exit(1)
	}
}

It is an ancient Mariner,
And he stoppeth one of three.
'By thy long grey beard and glittering eye,
Now wherefore stopp'st thou me?

The Bridegroom's doors are opened wide,
And I am next of kin;
The guests are met, the feast is set:
May'st hear the merry din.'

He holds him with his skinny hand,
'There was a ship,' quoth he.
'Hold off! unhand me, grey-beard loon!'
Eftsoons his hand dropt he.

He holds him with his glittering eye—
The Wedding-Guest stood still,
And listens like a three years' child:
The Mariner hath his will.

The Wedding-Guest sat on a stone:
He cannot choose but hear;
And thus spake on that ancient man,
The bright-eyed Mariner.

'The ship was cheered, the harbour cleared,
Merrily did we drop
Below the kirk, below the hill,
Below the lighthouse top.

The Sun came up upon the left,
Out of the sea came he!
And he shone bright, and on the right
Went down into the sea.

Higher and higher every day,
Till over the mast at noon—'
The Wedding-Guest here beat his breast,
For he heard the loud bassoon.

The bride hath paced into the hall,
Red as a rose is she;
Nodding their heads before her goes
The merry minstrelsy.

The Wedding-Guest he beat his breast,
Yet he cannot choose but hear;
And thus spake on that ancient man,
The bright-eyed Mariner.

And now the STORM-BLAST came, and he
Was tyrannous and strong:
He struck with his o'ertaking wings,
And chased us south along.

With sloping masts and dipping prow,
As who pursued with yell and blow
Still treads the shadow of his foe,
And forward bends his head,
The ship drove fast, loud roared the blast,
And southward aye we fled.

And now there came both mist and snow,
And it grew wondrous cold:
And ice, mast-high, came floating by,
As green as emerald.

And through the drifts the snowy clifts
Did send a dismal sheen:
Nor shapes of men nor beasts we ken—
The ice was all between.

The ice was here, the ice was there,
The ice was all around:
It cracked and growled, and roared and howled,
Like noises in a swound!

At length did cross an Albatross,
Thorough the fog it came;
As if it had been a Christian soul,
We hailed it in God's name.

It ate the food it ne'er had eat,
And round and round it flew.
The ice did split with a thunder-fit;
The helmsman steered us through!

And a good south wind sprung up behind;
The Albatross did follow,
And every day, for food or play,
Came to the mariner's hollo!

In mist or cloud, on mast or shroud,
It perched for vespers nine;
Whiles all the night, through fog-smoke white,
Glimmered the white Moon-shine.'

'God save thee, ancient Mariner!
From the fiends, that plague thee thus!—
Why look'st thou so?'—With my cross-bow
I shot the ALBATROSS.

PART II
The Sun now rose upon the right:
Out of the sea came he,
Still hid in mist, and on the left
Went down into the sea.

And the good south wind still blew behind,
But no sweet bird did follow,
Nor any day for food or play
Came to the mariner's hollo!

And I had done a hellish thing,
And it would work 'em woe:
For all averred, I had killed the bird
That made the breeze to blow.
Ah wretch! said they, the bird to slay,
That made the breeze to blow!

Nor dim nor red, like God's own head,
The glorious Sun uprist:
Then all averred, I had killed the bird
That brought the fog and mist.
'Twas right, said they, such birds to slay,
That bring the fog and mist.

The fair breeze blew, the white foam flew,
The furrow followed free;
We were the first that ever burst
Into that silent sea.

Down dropt the breeze, the sails dropt down,
'Twas sad as sad could be;
And we did speak only to break
The silence of the sea!

All in a hot and copper sky,
The bloody Sun, at noon,
Right up above the mast did stand,
No bigger than the Moon.

Day after day, day after day,
We stuck, nor breath nor motion;
As idle as a painted ship
Upon a painted ocean.

Water, water, every where,
And all the boards did shrink;
Water, water, every where,
Nor any drop to drink.

The very deep did rot: O Christ!
That ever this should be!
Yea, slimy things did crawl with legs
Upon the slimy sea.

About, about, in reel and rout
The death-fires danced at night;
The water, like a witch's oils,
Burnt green, and blue and white.

And some in dreams assurèd were
Of the Spirit that plagued us so;
Nine fathom deep he had followed us
From the land of mist and snow.

And every tongue, through utter drought,
Was withered at the root;
We could not speak, no more than if
We had been choked with soot.

Ah! well a-day! what evil looks
Had I from old and young!
Instead of the cross, the Albatross
About my neck was hung.

PART III
There passed a weary time. Each throat
Was parched, and glazed each eye.
A weary time! a weary time!
How glazed each weary eye,

When looking westward, I beheld
A something in the sky.

At first it seemed a little speck,
And then it seemed a mist;
It moved and moved, and took at last
A certain shape, I wist.

A speck, a mist, a shape, I wist!
And still it neared and neared:
As if it dodged a water-sprite,
It plunged and tacked and veered.

With throats unslaked, with black lips baked,
We could nor laugh nor wail;
Through utter drought all dumb we stood!
I bit my arm, I sucked the blood,
And cried, A sail! a sail!

With throats unslaked, with black lips baked,
Agape they heard me call:
Gramercy! they for joy did grin,
And all at once their breath drew in.
As they were drinking all.

See! see! (I cried) she tacks no more!
Hither to work us weal;
Without a breeze, without a tide,
She steadies with upright keel!

The western wave was all a-flame.
The day was well nigh done!
Almost upon the western wave
Rested the broad bright Sun;
When that strange shape drove suddenly
Betwixt us and the Sun.

And straight the Sun was flecked with bars,
(Heaven's Mother send us grace!)
As if through a dungeon-grate he peered
With broad and burning face.

Alas! (thought I, and my heart beat loud)
How fast she nears and nears!
Are those her sails that glance in the Sun,
Like restless gossameres?

Are those her ribs through which the Sun
Did peer, as through a grate?
And is that Woman all her crew?
Is that a DEATH? and are there two?
Is DEATH that woman's mate?

Her lips were red, her looks were free,
Her locks were yellow as gold:
Her skin was as white as leprosy,
The Night-mare LIFE-IN-DEATH was she,
Who thicks man's blood with cold.

The naked hulk alongside came,
And the twain were casting dice;
'The game is done! I've won! I've won!'
Quoth she, and whistles thrice.

The Sun's rim dips; the stars rush out;
At one stride comes the dark;
With far-heard whisper, o'er the sea,
Off shot the spectre-bark.

We listened and looked sideways up!
Fear at my heart, as at a cup,
My life-blood seemed to sip!
The stars were dim, and thick the night,
The steersman's face by his lamp gleamed white;
From the sails the dew did drip—
Till clomb above the eastern bar
The hornèd Moon, with one bright star
Within the nether tip.

One after one, by the star-dogged Moon,
Too quick for groan or sigh,
Each turned his face with a ghastly pang,
And cursed me with his eye.

Four times fifty living men,
(And I heard nor sigh nor groan)
With heavy thump, a lifeless lump,
They dropped down one by one.

The souls did from their bodies fly,—
They fled to bliss or woe!
And every soul, it passed me by,
Like the whizz of my cross-bow!

PART IV
'I fear thee, ancient Mariner!
I fear thy skinny hand!
And thou art long, and lank, and brown,
As is the ribbed sea-sand.

I fear thee and thy glittering eye,
And thy skinny hand, so brown.'—
Fear not, fear not, thou Wedding-Guest!
This body dropt not down.

Alone, alone, all, all alone,
Alone on a wide wide sea!
And never a saint took pity on
My soul in agony.

The many men, so beautiful!
And they all dead did lie:
And a thousand thousand slimy things
Lived on; and so did I.

I looked upon the rotting sea,
And drew my eyes away;
I looked upon the rotting deck,
And there the dead men lay.

I looked to heaven, and tried to pray;
But or ever a prayer had gusht,
A wicked whisper came, and made
My heart as dry as dust.

I closed my lids, and kept them close,
And the balls like pulses beat;
For the sky and the sea, and the sea and the sky
Lay dead like a load on my weary eye,
And the dead were at my feet.

The cold sweat melted from their limbs,
Nor rot nor reek did they:
The look with which they looked on me
Had never passed away.

An orphan's curse would drag to hell
A spirit from on high;
But oh! more horrible than that
Is the curse in a dead man's eye!
Seven days, seven nights, I saw that curse,
And yet I could not die.

The moving Moon went up the sky,
And no where did abide:
Softly she was going up,
And a star or two beside—

Her beams bemocked the sultry main,
Like April hoar-frost spread;
But where the ship's huge shadow lay,
The charmèd water burnt alway
A still and awful red.

Beyond the shadow of the ship,
I watched the water-snakes:
They moved in tracks of shining white,
And when they reared, the elfish light
Fell off in hoary flakes.

Within the shadow of the ship
I watched their rich attire:
Blue, glossy green, and velvet black,
They coiled and swam; and every track
Was a flash of golden fire.

O happy living things! no tongue
Their beauty might declare:
A spring of love gushed from my heart,
And I blessed them unaware:
Sure my kind saint took pity on me,
And I blessed them unaware.

The self-same moment I could pray;
And from my neck so free
The Albatross fell off, and sank
Like lead into the sea.

PART V
Oh sleep! it is a gentle thing,
Beloved from pole to pole!
To Mary Queen the praise be given!
She sent the gentle sleep from Heaven,
That slid into my soul.

The silly buckets on the deck,
That had so long remained,
I dreamt that they were filled with dew;
And when I awoke, it rained.

My lips were wet, my throat was cold,
My garments all were dank;
Sure I had drunken in my dreams,
And still my body drank.

I moved, and could not feel my limbs:
I was so light—almost
I thought that I had died in sleep,
And was a blessed ghost.

And soon I heard a roaring wind:
It did not come anear;
But with its sound it shook the sails,
That were so thin and sere.

The upper air burst into life!
And a hundred fire-flags sheen,
To and fro they were hurried about!
And to and fro, and in and out,
The wan stars danced between.

And the coming wind did roar more loud,
And the sails did sigh like sedge,
And the rain poured down from one black cloud;
The Moon was at its edge.

The thick black cloud was cleft, and still
The Moon was at its side:
Like waters shot from some high crag,
The lightning fell with never a jag,
A river steep and wide.

The loud wind never reached the ship,
Yet now the ship moved on!
Beneath the lightning and the Moon
The dead men gave a groan.

They groaned, they stirred, they all uprose,
Nor spake, nor moved their eyes;
It had been strange, even in a dream,
To have seen those dead men rise.

The helmsman steered, the ship moved on;
Yet never a breeze up-blew;
The mariners all 'gan work the ropes,
Where they were wont to do;
They raised their limbs like lifeless tools—
We were a ghastly crew.

The body of my brother's son
Stood by me, knee to knee:
The body and I pulled at one rope,
But he said nought to me.

'I fear thee, ancient Mariner!'
Be calm, thou Wedding-Guest!
'Twas not those souls that fled in pain,
Which to their corses came again,
But a troop of spirits blest:

For when it dawned—they dropped their arms,
And clustered round the mast;
Sweet sounds rose slowly through their mouths,
And from their bodies passed.

Around, around, flew each sweet sound,
Then darted to the Sun;
Slowly the sounds came back again,
Now mixed, now one by one.

Sometimes a-dropping from the sky
I heard the sky-lark sing;
Sometimes all little birds that are,
How they seemed to fill the sea and air
With their sweet jargoning!

And now 'twas like all instruments,
Now like a lonely flute;
And now it is an angel's song,
That makes the heavens be mute.

It ceased; yet still the sails made on
A pleasant noise till noon,
A noise like of a hidden brook
In the leafy month of June,
That to the sleeping woods all night
Singeth a quiet tune.

Till noon we quietly sailed on,
Yet never a breeze did breathe:
Slowly and smoothly went the ship,
Moved onward from beneath.

Under the keel nine fathom deep,
From the land of mist and snow,
The spirit slid: and it was he
That made the ship to go.
The sails at noon left off their tune,
And the ship stood still also.

The Sun, right up above the mast,
Had fixed her to the ocean:
But in a minute she 'gan stir,
With a short uneasy motion—
Backwards and forwards half her length
With a short uneasy motion.

Then like a pawing horse let go,
She made a sudden bound:
It flung the blood into my head,
And I fell down in a swound.

How long in that same fit I lay,
I have not to declare;
But ere my living life returned,
I heard and in my soul discerned
Two voices in the air.

'Is it he?' quoth one, 'Is this the man?
By him who died on cross,
With his cruel bow he laid full low
The harmless Albatross.

The spirit who bideth by himself
In the land of mist and snow,
He loved the bird that loved the man
Who shot him with his bow.'

The other was a softer voice,
As soft as honey-dew:
Quoth he, 'The man hath penance done,
And penance more will do.'

PART VI

First Voice
'But tell me, tell me! speak again,
Thy soft response renewing—
What makes that ship drive on so fast?
What is the ocean doing?'

Second Voice
Still as a slave before his lord,
The ocean hath no blast;
His great bright eye most silently
Up to the Moon is cast—

If he may know which way to go;
For she guides him smooth or grim.
See, brother, see! how graciously
She looketh down on him.'

First Voice
'But why drives on that ship so fast,
Without or wave or wind?'

Second Voice
'The air is cut away before,
And closes from behind.

Fly, brother, fly! more high, more high!
Or we shall be belated:
For slow and slow that ship will go,
When the Mariner's trance is abated.'

I woke, and we were sailing on
As in a gentle weather:
'Twas night, calm night, the moon was high;
The dead men stood together.

All stood together on the deck,
For a charnel-dungeon fitter:
All fixed on me their stony eyes,
That in the Moon did glitter.

The pang, the curse, with which they died,
Had never passed away:
I could not draw my eyes from theirs,
Nor turn them up to pray.

And now this spell was snapt: once more
I viewed the ocean green,
And looked far forth, yet little saw
Of what had else been seen—

Like one, that on a lonesome road
Doth walk in fear and dread,
And having once turned round walks on,
And turns no more his head;
Because he knows, a frightful fiend
Doth close behind him tread.

But soon there breathed a wind on me,
Nor sound nor motion made:
Its path was not upon the sea,
In ripple or in shade.

It raised my hair, it fanned my cheek
Like a meadow-gale of spring—
It mingled strangely with my fears,
Yet it felt like a welcoming.

Swiftly, swiftly flew the ship,
Yet she sailed softly too:
Sweetly, sweetly blew the breeze—
On me alone it blew.

Oh! dream of joy! is this indeed
The light-house top I see?
Is this the hill? is this the kirk?
Is this mine own countree?

We drifted o'er the harbour-bar,
And I with sobs did pray—
O let me be awake, my God!
Or let me sleep alway.

The harbour-bay was clear as glass,
So smoothly it was strewn!
And on the bay the moonlight lay,
And the shadow of the Moon.

The rock shone bright, the kirk no less,
That stands above the rock:
The moonlight steeped in silentness
The steady weathercock.

And the bay was white with silent light,
Till rising from the same,
Full many shapes, that shadows were,
In crimson colours came.

A little distance from the prow
Those crimson shadows were:
I turned my eyes upon the deck—
Oh, Christ! what saw I there!

Each corse lay flat, lifeless and flat,
And, by the holy rood!
A man all light, a seraph-man,
On every corse there stood.

This seraph-band, each waved his hand:
It was a heavenly sight!
They stood as signals to the land,
Each one a lovely light;

This seraph-band, each waved his hand,
No voice did they impart—
No voice; but oh! the silence sank
Like music on my heart.

But soon I heard the dash of oars,
I heard the Pilot's cheer;
My head was turned perforce away
And I saw a boat appear.

The Pilot and the Pilot's boy,
I heard them coming fast:
Dear Lord in Heaven! it was a joy
The dead men could not blast.

I saw a third—I heard his voice:
It is the Hermit good!
He singeth loud his godly hymns
That he makes in the wood.
He'll shrieve my soul, he'll wash away
The Albatross's blood.

PART VII
This Hermit good lives in that wood
Which slopes down to the sea.
How loudly his sweet voice he rears!
He loves to talk with marineres
That come from a far countree.

He kneels at morn, and noon, and eve—
He hath a cushion plump:
It is the moss that wholly hides
The rotted old oak-stump.

The skiff-boat neared: I heard them talk,
'Why, this is strange, I trow!
Where are those lights so many and fair,
That signal made but now?'

'Strange, by my faith!' the Hermit said—
'And they answered not our cheer!
The planks looked warped! and see those sails,
How thin they are and sere!
I never saw aught like to them,
Unless perchance it were

Brown skeletons of leaves that lag
My forest-brook along;
When the ivy-tod is heavy with snow,
And the owlet whoops to the wolf below,
That eats the she-wolf's young.'

'Dear Lord! it hath a fiendish look—
(The Pilot made reply)
I am a-feared'—'Push on, push on!'
Said the Hermit cheerily.

The boat came closer to the ship,
But I nor spake nor stirred;
The boat came close beneath the ship,
And straight a sound was heard.

Under the water it rumbled on,
Still louder and more dread:
It reached the ship, it split the bay;
The ship went down like lead.

Stunned by that loud and dreadful sound,
Which sky and ocean smote,
Like one that hath been seven days drowned
My body lay afloat;
But swift as dreams, myself I found
Within the Pilot's boat.

Upon the whirl, where sank the ship,
The boat spun round and round;
And all was still, save that the hill
Was telling of the sound.

I moved my lips—the Pilot shrieked
And fell down in a fit;
The holy Hermit raised his eyes,
And prayed where he did sit.

I took the oars: the Pilot's boy,
Who now doth crazy go,
Laughed loud and long, and all the while
His eyes went to and fro.
'Ha! ha!' quoth he, 'full plain I see,
The Devil knows how to row.'

And now, all in my own countree,
I stood on the firm land!
The Hermit stepped forth from the boat,
And scarcely he could stand.

'O shrieve me, shrieve me, holy man!'
The Hermit crossed his brow.
'Say quick,' quoth he, 'I bid thee say—
What manner of man art thou?'

Forthwith this frame of mine was wrenched
With a woful agony,
Which forced me to begin my tale;
And then it left me free.


Since then, at an uncertain hour,
That agony returns:
And till my ghastly tale is told,
This heart within me burns.

I pass, like night, from land to land;
I have strange power of speech;
That moment that his face I see,
I know the man that must hear me:
To him my tale I teach.

What loud uproar bursts from that door!
The wedding-guests are there:
But in the garden-bower the bride
And bride-maids singing are:
And hark the little vesper bell,
Which biddeth me to prayer!

O Wedding-Guest! this soul hath been
Alone on a wide wide sea:
So lonely 'twas, that God himself
Scarce seemèd there to be.

O sweeter than the marriage-feast,
'Tis sweeter far to me,
To walk together to the kirk
With a goodly company!—

To walk together to the kirk,
And all together pray,
While each to his great Father bends,
Old men, and babes, and loving friends
And youths and maidens gay!

Farewell, farewell! but this I tell
To thee, thou Wedding-Guest!
He prayeth well, who loveth well
Both man and bird and beast.

He prayeth best, who loveth best
All things both great and small;
For the dear God who loveth us,
He made and loveth all.

The Mariner, whose eye is bright,
Whose beard with age is hoar,
Is gone: and now the Wedding-Guest
Turned from the bridegroom's door.

He went like one that hath been stunned,
And is of sense forlorn:
A sadder and a wiser man,
He rose the morrow morn.

It is an ancient Mariner,
And he stoppeth one of three.
'By thy long grey beard and glittering eye,
Now wherefore stopp'st thou me?

The Bridegroom's doors are opened wide,
And I am next of kin;
The guests are met, the feast is set:
May'st hear the merry din.'

The Bridegroom's doors are opened wide,
And I am next of kin;
The guests are met, the feast is set:
May'st hear the merry din.'


He holds him with his skinny hand,
'There was a ship,' quoth he.
'Hold off! unhand me, grey-beard loon!'
Eftsoons his hand dropt he.

He holds him with his glittering eye—
The Wedding-Guest stood still,
And listens like a three years' child:
The Mariner hath his will.

The Wedding-Guest sat on a stone:
He cannot choose but hear;
And thus spake on that ancient man,
The bright-eyed Mariner.

'The ship was cheered, the harbour cleared,
Merrily did we drop
Below the kirk, below the hill,
Below the lighthouse top.

The Sun came up upon the left,
Out of the sea came he!
And he shone bright, and on the right
Went down into the sea.

Higher and higher every day,
Till over the mast at noon—'
The Wedding-Guest here beat his breast,
For he heard the loud bassoon.

The bride hath paced into the hall,
Red as a rose is she;
Nodding their heads before her goes
The merry minstrelsy.

The Wedding-Guest he beat his breast,
Yet he cannot choose but hear;
And thus spake on that ancient man,
The bright-eyed Mariner.

And now the STORM-BLAST came, and he
Was tyrannous and strong:
He struck with his o'ertaking wings,
And chased us south along.

With sloping masts and dipping prow,
As who pursued with yell and blow
Still treads the shadow of his foe,
And forward bends his head,
The ship drove fast, loud roared the blast,
And southward aye we fled.

And now there came both mist and snow,
And it grew wondrous cold:
And ice, mast-high, came floating by,
As green as emerald.

And through the drifts the snowy clifts
Did send a dismal sheen:
Nor shapes of men nor beasts we ken—
The ice was all between.

The ice was here, the ice was there,
The ice was all around:
It cracked and growled, and roared and howled,
Like noises in a swound!

At length did cross an Albatross,
Thorough the fog it came;
As if it had been a Christian soul,
We hailed it in God's name.

It ate the food it ne'er had eat,
And round and round it flew.
The ice did split with a thunder-fit;
The helmsman steered us through!

And a good south wind sprung up behind;
The Albatross did follow,
And every day, for food or play,
Came to the mariner's hollo!

In mist or cloud, on mast or shroud,
It perched for vespers nine;
Whiles all the night, through fog-smoke white,
Glimmered the white Moon-shine.'

'God save thee, ancient Mariner!
From the fiends, that plague thee thus!—
Why look'st thou so?'—With my cross-bow
I shot the ALBATROSS.

PART II
The Sun now rose upon the right:
Out of the sea came he,
Still hid in mist, and on the left
Went down into the sea.

And the good south wind still blew behind,
But no sweet bird did follow,
Nor any day for food or play
Came to the mariner's hollo!

And I had done a hellish thing,
And it would work 'em woe:
For all averred, I had killed the bird
That made the breeze to blow.
Ah wretch! said they, the bird to slay,
That made the breeze to blow!

Nor dim nor red, like God's own head,
The glorious Sun uprist:
Then all averred, I had killed the bird
That brought the fog and mist.
'Twas right, said they, such birds to slay,
That bring the fog and mist.

The fair breeze blew, the white foam flew,
The furrow followed free;
We were the first that ever burst
Into that silent sea.

Down dropt the breeze, the sails dropt down,
'Twas sad as sad could be;
And we did speak only to break
The silence of the sea!

All in a hot and copper sky,
The bloody Sun, at noon,
Right up above the mast did stand,
No bigger than the Moon.

Day after day, day after day,
We stuck, nor breath nor motion;
As idle as a painted ship
Upon a painted ocean.

Water, water, every where,
And all the boards did shrink;
Water, water, every where,
Nor any drop to drink.

The very deep did rot: O Christ!
That ever this should be!
Yea, slimy things did crawl with legs
Upon the slimy sea.

About, about, in reel and rout
The death-fires danced at night;
The water, like a witch's oils,
Burnt green, and blue and white.

And some in dreams assurèd were
Of the Spirit that plagued us so;
Nine fathom deep he had followed us
From the land of mist and snow.

And every tongue, through utter drought,
Was withered at the root;
We could not speak, no more than if
We had been choked with soot.

Ah! well a-day! what evil looks
Had I from old and young!
Instead of the cross, the Albatross
About my neck was hung.

PART III
There passed a weary time. Each throat
Was parched, and glazed each eye.
A weary time! a weary time!
How glazed each weary eye,

When looking westward, I beheld
A something in the sky.

At first it seemed a little speck,
And then it seemed a mist;
It moved and moved, and took at last
A certain shape, I wist.

A speck, a mist, a shape, I wist!
And still it neared and neared:
As if it dodged a water-sprite,
It plunged and tacked and veered.

With throats unslaked, with black lips baked,
We could nor laugh nor wail;
Through utter drought all dumb we stood!
I bit my arm, I sucked the blood,
And cried, A sail! a sail!

With throats unslaked, with black lips baked,
Agape they heard me call:
Gramercy! they for joy did grin,
And all at once their breath drew in.
As they were drinking all.

See! see! (I cried) she tacks no more!
Hither to work us weal;
Without a breeze, without a tide,
She steadies with upright keel!

The western wave was all a-flame.
The day was well nigh done!
Almost upon the western wave
Rested the broad bright Sun;
When that strange shape drove suddenly
Betwixt us and the Sun.

And straight the Sun was flecked with bars,
(Heaven's Mother send us grace!)
As if through a dungeon-grate he peered
With broad and burning face.

Alas! (thought I, and my heart beat loud)
How fast she nears and nears!
Are those her sails that glance in the Sun,
Like restless gossameres?

Are those her ribs through which the Sun
Did peer, as through a grate?
And is that Woman all her crew?
Is that a DEATH? and are there two?
Is DEATH that woman's mate?

Her lips were red, her looks were free,
Her locks were yellow as gold:
Her skin was as white as leprosy,
The Night-mare LIFE-IN-DEATH was she,
Who thicks man's blood with cold.

The naked hulk alongside came,
And the twain were casting dice;
'The game is done! I've won! I've won!'
Quoth she, and whistles thrice.

The Sun's rim dips; the stars rush out;
At one stride comes the dark;
With far-heard whisper, o'er the sea,
Off shot the spectre-bark.

One after one, by the star-dogged Moon,
Too quick for groan or sigh,
Each turned his face with a ghastly pang,
And cursed me with his eye.

We listened and looked sideways up!
Fear at my heart, as at a cup,
My life-blood seemed to sip!
The stars were dim, and thick the night,
The steersman's face by his lamp gleamed white;
From the sails the dew did drip—
Till clomb above the eastern bar
The hornèd Moon, with one bright star
Within the nether tip.

Four times fifty living men,
(And I heard nor sigh nor groan)
With heavy thump, a lifeless lump,
They dropped down one by one.

The souls did from their bodies fly,—
They fled to bliss or woe!
And every soul, it passed me by,
Like the whizz of my cross-bow!

PART IV
'I fear thee, ancient Mariner!
I fear thy skinny hand!
And thou art long, and lank, and brown,
As is the ribbed sea-sand.

I fear thee and thy glittering eye,
And thy skinny hand, so brown.'—
Fear not, fear not, thou Wedding-Guest!
This body dropt not down.

Alone, alone, all, all alone,
Alone on a wide wide sea!
And never a saint took pity on
My soul in agony.

The many men, so beautiful!
And they all dead did lie:
And a thousand thousand slimy things
Lived on; and so did I.

I looked upon the rotting sea,
And drew my eyes away;
I looked upon the rotting deck,
And there the dead men lay.

I looked to heaven, and tried to pray;
But or ever a prayer had gusht,
A wicked whisper came, and made
My heart as dry as dust.

I closed my lids, and kept them close,
And the balls like pulses beat;
For the sky and the sea, and the sea and the sky
Lay dead like a load on my weary eye,
And the dead were at my feet.

The cold sweat melted from their limbs,
Nor rot nor reek did they:
The look with which they looked on me
Had never passed away.

An orphan's curse would drag to hell
A spirit from on high;
But oh! more horrible than that
Is the curse in a dead man's eye!
Seven days, seven nights, I saw that curse,
And yet I could not die.

The moving Moon went up the sky,
And no where did abide:
Softly she was going up,
And a star or two beside—

Her beams bemocked the sultry main,
Like April hoar-frost spread;
But where the ship's huge shadow lay,
The charmèd water burnt alway
A still and awful red.

Beyond the shadow of the ship,
I watched the water-snakes:
They moved in tracks of shining white,
And when they reared, the elfish light
Fell off in hoary flakes.

Within the shadow of the ship
I watched their rich attire:
Blue, glossy green, and velvet black,
They coiled and swam; and every track
Was a flash of golden fire.

O happy living things! no tongue
Their beauty might declare:
A spring of love gushed from my heart,
And I blessed them unaware:
Sure my kind saint took pity on me,
And I blessed them unaware.

The self-same moment I could pray;
And from my neck so free
The Albatross fell off, and sank
Like lead into the sea.

PART V
Oh sleep! it is a gentle thing,
Beloved from pole to pole!
To Mary Queen the praise be given!
She sent the gentle sleep from Heaven,
That slid into my soul.

The silly buckets on the deck,
That had so long remained,
I dreamt that they were filled with dew;
And when I awoke, it rained.

My lips were wet, my throat was cold,
My garments all were dank;
Sure I had drunken in my dreams,
And still my body drank.

I moved, and could not feel my limbs:
I was so light—almost
I thought that I had died in sleep,
And was a blessed ghost.

And soon I heard a roaring wind:
It did not come anear;
But with its sound it shook the sails,
That were so thin and sere.

The upper air burst into life!
And a hundred fire-flags sheen,
To and fro they were hurried about!
And to and fro, and in and out,
The wan stars danced between.

And the coming wind did roar more loud,
And the sails did sigh like sedge,
And the rain poured down from one black cloud;
The Moon was at its edge.

The thick black cloud was cleft, and still
The Moon was at its side:
Like waters shot from some high crag,
The lightning fell with never a jag,
A river steep and wide.

The loud wind never reached the ship,
Yet now the ship moved on!
Beneath the lightning and the Moon
The dead men gave a groan.

They groaned, they stirred, they all uprose,
Nor spake, nor moved their eyes;
It had been strange, even in a dream,
To have seen those dead men rise.

The helmsman steered, the ship moved on;
Yet never a breeze up-blew;
The mariners all 'gan work the ropes,
Where they were wont to do;
They raised their limbs like lifeless tools—
We were a ghastly crew.

The body of my brother's son
Stood by me, knee to knee:
The body and I pulled at one rope,
But he said nought to me.

'I fear thee, ancient Mariner!'
Be calm, thou Wedding-Guest!
'Twas not those souls that fled in pain,
Which to their corses came again,
But a troop of spirits blest:

For when it dawned—they dropped their arms,
And clustered round the mast;
Sweet sounds rose slowly through their mouths,
And from their bodies passed.

Around, around, flew each sweet sound,
Then darted to the Sun;
Slowly the sounds came back again,
Now mixed, now one by one.

Sometimes a-dropping from the sky
I heard the sky-lark sing;
Sometimes all little birds that are,
How they seemed to fill the sea and air
With their sweet jargoning!

And now 'twas like all instruments,
Now like a lonely flute;
And now it is an angel's song,
That makes the heavens be mute.

It ceased; yet still the sails made on
A pleasant noise till noon,
A noise like of a hidden brook
In the leafy month of June,
That to the sleeping woods all night
Singeth a quiet tune.

Till noon we quietly sailed on,
Yet never a breeze did breathe:
Slowly and smoothly went the ship,
Moved onward from beneath.

Under the keel nine fathom deep,
From the land of mist and snow,
The spirit slid: and it was he
That made the ship to go.
The sails at noon left off their tune,
And the ship stood still also.

The Sun, right up above the mast,
Had fixed her to the ocean:
But in a minute she 'gan stir,
With a short uneasy motion—
Backwards and forwards half her length
With a short uneasy motion.

Then like a pawing horse let go,
She made a sudden bound:
It flung the blood into my head,
And I fell down in a swound.

How long in that same fit I lay,
I have not to declare;
But ere my living life returned,
I heard and in my soul discerned
Two voices in the air.

'Is it he?' quoth one, 'Is this the man?
By him who died on cross,
With his cruel bow he laid full low
The harmless Albatross.

The spirit who bideth by himself
In the land of mist and snow,
He loved the bird that loved the man
Who shot him with his bow.'

The other was a softer voice,
As soft as honey-dew:
Quoth he, 'The man hath penance done,
And penance more will do.'

PART VI

First Voice
'But tell me, tell me! speak again,
Thy soft response renewing—
What makes that ship drive on so fast?
What is the ocean doing?'

Second Voice
Still as a slave before his lord,
The ocean hath no blast;
His great bright eye most silently
Up to the Moon is cast—

If he may know which way to go;
For she guides him smooth or grim.
See, brother, see! how graciously
She looketh down on him.'

First Voice
'But why drives on that ship so fast,
Without or wave or wind?'

Second Voice
'The air is cut away before,
And closes from behind.

Fly, brother, fly! more high, more high!
Or we shall be belated:
For slow and slow that ship will go,
When the Mariner's trance is abated.'

I woke, and we were sailing on
As in a gentle weather:
'Twas night, calm night, the moon was high;
The dead men stood together.

All stood together on the deck,
For a charnel-dungeon fitter:
All fixed on me their stony eyes,
That in the Moon did glitter.

The pang, the curse, with which they died,
Had never passed away:
I could not draw my eyes from theirs,
Nor turn them up to pray.

And now this spell was snapt: once more
I viewed the ocean green,
And looked far forth, yet little saw
Of what had else been seen—

Like one, that on a lonesome road
Doth walk in fear and dread,
And having once turned round walks on,
And turns no more his head;
Because he knows, a frightful fiend
Doth close behind him tread.

But soon there breathed a wind on me,
Nor sound nor motion made:
Its path was not upon the sea,
In ripple or in shade.

It raised my hair, it fanned my cheek
Like a meadow-gale of spring—
It mingled strangely with my fears,
Yet it felt like a welcoming.

Swiftly, swiftly flew the ship,
Yet she sailed softly too:
Sweetly, sweetly blew the breeze—
On me alone it blew.

Oh! dream of joy! is this indeed
The light-house top I see?
Is this the hill? is this the kirk?
Is this mine own countree?

We drifted o'er the harbour-bar,
And I with sobs did pray—
O let me be awake, my God!
Or let me sleep alway.

The harbour-bay was clear as glass,
So smoothly it was strewn!
And on the bay the moonlight lay,
And the shadow of the Moon.

The rock shone bright, the kirk no less,
That stands above the rock:
The moonlight steeped in silentness
The steady weathercock.

And the bay was white with silent light,
Till rising from the same,
Full many shapes, that shadows were,
In crimson colours came.

A little distance from the prow
Those crimson shadows were:
I turned my eyes upon the deck—
Oh, Christ! what saw I there!

Each corse lay flat, lifeless and flat,
And, by the holy rood!
A man all light, a seraph-man,
On every corse there stood.

This seraph-band, each waved his hand:
It was a heavenly sight!
They stood as signals to the land,
Each one a lovely light;

This seraph-band, each waved his hand,
No voice did they impart—
No voice; but oh! the silence sank
Like music on my heart.

But soon I heard the dash of oars,
I heard the Pilot's cheer;
My head was turned perforce away
And I saw a boat appear.

The Pilot and the Pilot's boy,
I heard them coming fast:
Dear Lord in Heaven! it was a joy
The dead men could not blast.

I saw a third—I heard his voice:
It is the Hermit good!
He singeth loud his godly hymns
That he makes in the wood.
He'll shrieve my soul, he'll wash away
The Albatross's blood.

PART VII
This Hermit good lives in that wood
Which slopes down to the sea.
How loudly his sweet voice he rears!
He loves to talk with marineres
That come from a far countree.

He kneels at morn, and noon, and eve—
He hath a cushion plump:
It is the moss that wholly hides
The rotted old oak-stump.

The skiff-boat neared: I heard them talk,
'Why, this is strange, I trow!
Where are those lights so many and fair,
That signal made but now?'

'Strange, by my faith!' the Hermit said—
'And they answered not our cheer!
The planks looked warped! and see those sails,
How thin they are and sere!
I never saw aught like to them,
Unless perchance it were

Brown skeletons of leaves that lag
My forest-brook along;
When the ivy-tod is heavy with snow,
And the owlet whoops to the wolf below,
That eats the she-wolf's young.'

'Dear Lord! it hath a fiendish look—
(The Pilot made reply)
I am a-feared'—'Push on, push on!'
Said the Hermit cheerily.

The boat came closer to the ship,
But I nor spake nor stirred;
The boat came close beneath the ship,
And straight a sound was heard.

Under the water it rumbled on,
Still louder and more dread:
It reached the ship, it split the bay;
The ship went down like lead.

Stunned by that loud and dreadful sound,
Which sky and ocean smote,
Like one that hath been seven days drowned
My body lay afloat;
But swift as dreams, myself I found
Within the Pilot's boat.

Upon the whirl, where sank the ship,
The boat spun round and round;
And all was still, save that the hill
Was telling of the sound.

I moved my lips—the Pilot shrieked
And fell down in a fit;
The holy Hermit raised his eyes,
And prayed where he did sit.

I took the oars: the Pilot's boy,
Who now doth crazy go,
Laughed loud and long, and all the while
His eyes went to and fro.
'Ha! ha!' quoth he, 'full plain I see,
The Devil knows how to row.'

And now, all in my own countree,
I stood on the firm land!
The Hermit stepped forth from the boat,
And scarcely he could stand.

'O shrieve me, shrieve me, holy man!'
The Hermit crossed his brow.
'Say quick,' quoth he, 'I bid thee say—
What manner of man art thou?'

Forthwith this frame of mine was wrenched
With a woful agony,
Which forced me to begin my tale;
And then it left me free.


Since then, at an uncertain hour,
That agony returns:
And till my ghastly tale is told,
This heart within me burns.

I pass, like night, from land to land;
I have strange power of speech;
That moment that his face I see,
I know the man that must hear me:
To him my tale I teach.

What loud uproar bursts from that door!
The wedding-guests are there:
But in the garden-bower the bride
And bride-maids singing are:
And hark the little vesper bell,
Which biddeth me to prayer!

O Wedding-Guest! this soul hath been
Alone on a wide wide sea:
So lonely 'twas, that God himself
Scarce seemèd there to be.

O sweeter than the marriage-feast,
'Tis sweeter far to me,
To walk together to the kirk
With a goodly company!—

To walk together to the kirk,
And all together pray,
While each to his great Father bends,
Old men, and babes, and loving friends
And youths and maidens gay!

Farewell, farewell! but this I tell
To thee, thou Wedding-Guest!
He prayeth well, who loveth well
Both man and bird and beast.

He prayeth best, who loveth best
All things both great and small;
For the dear God who loveth us,
He made and loveth all.

He went like one that hath been stunned,
And is of sense forlorn:
A sadder and a wiser man,
He rose the morrow morn.

// Package diff provides a diff implementation
// for finite, indexable sequences with comparable elements
package diff

import (
	bits "0dev.org/bits"
)

// Interface abstracts the required knowledge to perform a diff
// on any two comparable, fixed-length sequences
type Interface interface {
	// The sequences' lengths
	Len() (int, int)
	// True when the sequences' elements at those indices are equal
	Equal(int, int) bool
}

// A Mark struct marks a length in sequence starting with an offset
type Mark struct {
	From   int
	Length int
}

// A Delta struct is the result of a Diff operation
type Delta struct {
	Added   []Mark
	Removed []Mark
}

// Diffs the provided data and returns e Delta struct
// with added entries' indices in the second sequence and removed from the first
func Diff(data Interface) Delta {
	var len1, len2 = data.Len()
	var mat matrix = matrix{v: bits.New(uint(len1 * len2)), lenX: len1, lenY: len2}

	for i := 0; i < len1; i++ {
		for j := 0; j < len2; j++ {
			mat.v.Poke(mat.at(i, j), data.Equal(i, j))
		}
	}

	return recursiveDiff(box{0, 0, len1, len2}, mat)
}

type match struct {
	x, y   int
	length int
}

type box struct {
	x, y       int
	lenX, lenY int
}

// A helper structure that stores absolute dimension along a linear bit vector
// so that it can always properly translate (x, y) -> z on the vector
type matrix struct {
	v          bits.Vector
	lenX, lenY int
}

// Translates (x, y) to an absolute position on the bit vector
func (m *matrix) at(x, y int) uint {
	return uint(y + (x * m.lenY))
}

func recursiveDiff(bounds box, mat matrix) Delta {
	var m match = largest(bounds, mat)

	if m.length == 0 { // Recursion terminates
		var immediate Delta
		if bounds.lenY-bounds.y > 0 {
			immediate.Added = []Mark{Mark{bounds.y, bounds.lenY}}
		}
		if bounds.lenX-bounds.x > 0 {
			immediate.Removed = []Mark{Mark{bounds.x, bounds.lenX}}
		}
		return immediate
	}

	var left Delta = recursiveDiff(box{bounds.x, bounds.y, m.x, m.y}, mat)
	var right Delta = recursiveDiff(box{m.x + m.length, m.y + m.length, bounds.lenX, bounds.lenY}, mat)

	var result Delta

	result.Added = append(left.Added, right.Added...)
	result.Removed = append(left.Removed, right.Removed...)

	return result
}

// Finds the largest common substring by looking at the provided match matrix
// starting from (bounds.x, bounds.y) with lengths bounds.lenX, bounds.lenY
func largest(bounds box, mat matrix) (result match) {
	for i := bounds.x; i < bounds.lenX; i++ {
		var m match = search(i, bounds.y, bounds.lenX, bounds.lenY, mat)
		if m.length > result.length {
			result = m
		}
	}
	for j := bounds.y + 1; j < bounds.lenY; j++ {
		var m match = search(bounds.x, j, bounds.lenX, bounds.lenY, mat)
		if m.length > result.length {
			result = m
		}
	}
	return
}

// Searches the main diagonal for the longest sequential match line
func search(x, y, lenX, lenY int, mat matrix) (result match) {
	var inMatch bool
	var m match
	for step := 0; step+x < lenX && step+y < lenY; step++ {
		if mat.v.Peek(mat.at(step+x, step+y)) {
			if !inMatch { // Create a new current record if there is none ...
				inMatch, m.x, m.y, m.length = true, step+x, step+y, 1
			} else { // ... otherwise just increment the existing
				m.length++
			}

			if m.length > result.length {
				result = m // Store it if it is longer ...
			}
		} else { // End of current of match
			inMatch = false // ... and reset the current one
		}
	}
	return
}

package diff

import (
	bits "0dev.org/bits"
	"fmt"
	"testing"
)

type diffSlice struct {
	first  []rune
	second []rune
}

func (d diffSlice) Len() (int, int) {
	return len(d.first), len(d.second)
}

func (d diffSlice) Equal(i, j int) bool {
	return d.first[i] == d.second[j]
}

func TestLCS(t *testing.T) {
	fmt.Println("")

	data := diffSlice{
		[]rune("abcdefgh"),
		[]rune("abbcedfh"),
	}

	fmt.Println(Diff(data))

	// first, second, total := LCS(data)
	// fmt.Println(first, second, total)
}

func TestWTF(t *testing.T) {
	data := diffSlice{
		[]rune("abcdefgh"),
		[]rune("abbcedfh"),
	}

	var len1, len2 int = data.Len()
	var mat matrix = matrix{v: bits.NewBool(uint(len1 * len2)), lenX: len1, lenY: len2}

	for i := 0; i < len1; i++ {
		for j := 0; j < len2; j++ {
			mat.v.Poke(mat.at(i, j), data.Equal(i, j))
		}
	}

	debugPrint(box{5, 5, 6, 6}, mat)
	debugPrint(box{5, 5, 7, 7}, mat)
	debugPrint(box{5, 5, 8, 8}, mat)
}

func debugPrint(bounds box, mat matrix) {
	// Debug print
	fmt.Printf("-%d-%d--%d-%d--\n", bounds.x, bounds.y, bounds.lenX, bounds.lenY)
	for i := bounds.x; i < bounds.lenX; i++ {
		fmt.Print("| ")
		for j := bounds.y; j < bounds.lenY; j++ {
			//if vector.Peek(uint(j + (i * bounds.lenY))) {
			if mat.v.Peek(mat.at(i, j)) {
				fmt.Print("\\")
			} else {
				fmt.Print(".")
			}
		}
		fmt.Println(" |")
	}
	fmt.Println("------------")
}

// Helper functions that really belong in the SDK or in a generic library...
package math

func MinInt(i1, i2 int) int {
	if i1 <= i2 {
		return i1
	}
	return i2
}

func MaxInt(i1, i2 int) int {
	if i1 >= i2 {
		return i1
	}
	return i2
}