// Package provides a shifted, reversed fibonacci encoding of unsigned integers.
// Package provides a shifted fibonacci encoding of unsigned integers.
//
// http://en.wikipedia.org/wiki/Fibonacci_coding maps positive integers as
// 1 - 11, 2 - 011, 3 - 0011, 4 - 1011, 5 - 00011
//
// Incrementing input by one to allow for zero gives
// 0 - 11, 1 - 011, 2 - 0011, 3 - 1011, 4 - 00011
//
// The codes are then reversed so that they are easily stored in uints
// 0 - 11, 1 - 110, 2 - 1100, 3 - 1101, 4 - 11000
// (so that they are always comparable with each other as there is no need to
//  store the leading number of zeroes which are otherwise required)
package fibonacci

import (
	_ "fmt"
	"io"
)

type Numbers []uint64

// Returns a slice with fibonacci numbers up to the given length
func New(size int) Numbers {
	var fibs Numbers = make(Numbers, size)
	copy(fibs, []uint64{1, 1})
	for i := 2; i < size; i++ {
		fibs[i] = fibs[i-1] + fibs[i-2]
	}
	return fibs
}

// Returns a fibonacci code for an integer as specified in the package's doc.
func (f Numbers) Code(value uint64) (result uint64) {
func (f Numbers) Code(value uint64) (result uint64, length byte) {
	// Increment to encode zero as one
	value++

	// Find the nearest fibonacci number
	i := 0
	for f[i+1] <= value {
		i++
	for f[length] <= value {
		length++
	}

	// Leading bit that signals the start of a fibonacci-encoded integer
	result |= 1

	// Find the Zeckendorf's representation by raising a bit for each
	// fibonacci number that is less or equal to the difference
	// between the value and the previous such number
	for ; i >= 1; i-- {
	for i := length - 1; i >= 1; i-- {
		result <<= 1
		if f[i] <= value {
			result |= 1
			value -= f[i]
		}
	}
	return
}

// Returns an integer from a fibonacci code as specified in the package's doc.
func (f Numbers) Decode(value uint64) (result uint64) {
	i := 1
func (f Numbers) Decode(value uint64) (result uint64, length byte) {
	length = 1
	// Loop until the lowest two bits are both raised
	for (value & 3) != 3 {
		// Add the fibonacci number for the current bit if it is raised
		if (value & 1) == 1 {
			result += f[i]
			result += f[length]

			// We know that the next bit cannot be raised by Zeckendorf's theorem
			value >>= 2
			i += 2
			length += 2
			continue
		}

		value >>= 1
		i++
		length++
	}
	result += f[i] - 1
	result += f[length] - 1
	return
}

func Writer(target io.Writer) io.Writer {
	var enc encoder
	enc.Numbers = New(16)
	enc.target = target
	enc.buffer = enc.backing[:0:len(enc.backing)]
	return &enc
}

type encoder struct {
	Numbers
	target    io.Writer
	backing   [3]byte // TODO - verify that this can be reduced to 2 bytes
	buffer    []byte
	remaining byte
	length    byte
}

func (e *encoder) Write(input []byte) (int, error) {
	var (
		total int
		err   error
	)

	// Flush on a nil slice
	if input == nil {
		e.backing[0] = byte(e.remaining)
		_, err = e.target.Write(e.buffer[:1])
		return 0, err
	}

	for _, currentByte := range input {
		// Get the fibonacci code and bit length for the current byte
		enc, len := e.Code(uint64(currentByte))

		// Add current bits to higher positions
		e.remaining |= byte(enc << e.length)

		// maximum length of added bits to e.remaining
		added := 8 - e.length

		// Shift the the encoded value and account for its length
		enc >>= added
		e.length += len
		len -= added

		// Not enough bits to write
		if e.length < 8 {
			continue
		}

		// Clearing e.length is not necessary as it will be overwritten later

		// Stage the complete byte for writing
		e.buffer = append(e.buffer, byte(e.remaining))

		// Stage every full byte from the encoded value for writing
		for enc > 128 {
			e.buffer = append(e.buffer, byte(enc))
			enc >>= 8
			len -= 8
		}

		// Store the remaining bits
		e.remaining, e.length = byte(enc), len

		// Write the staged bytes
		_, err = e.target.Write(e.buffer)

		// Abort write on error
		if err != nil {
			break
		}

		// Account for the just-written byte
		total++

		// Clear the buffer
		e.buffer = e.buffer[:0]
	}
	return total, err
}

// func Reader(source io.Reader) io.Reader {
// 	var dec decoder
// 	dec.Numbers = New(16)
// 	dec.source = source
// 	return &dec
// }

// type decoder struct {
// 	Numbers
// 	source io.Reader
// 	buffer uint64
// 	at     byte
// }

// func (d *decoder) Read(output []byte) (int, error) {
// 	return 0, nil
// }

package fibonacci

import (
	"bytes"
	"fmt"
	"io"
	"testing"
)

func TestNumbers(t *testing.T) {
	n := New(32)

	expected := []uint64{1, 1, 2, 3, 5, 8, 13, 21}

	for i, v := range expected {

		if f := n[i]; f != v {
			t.Error("Unexpected value for", i, f, "expected", v)
		}
	}
}

func TestCoding(t *testing.T) {
	n := New(32)

	for i := uint64(0); i < 1024; i++ {
		enc := n.Code(i)
		dec := n.Decode(enc)
	for i := uint64(0); i < 4096; i++ {
		enc, _ := n.Code(i)
		//fmt.Printf("%d - %b, %d\n", i, enc, len)
		dec, _ := n.Decode(enc)
		if i != dec {
			t.Errorf("Unexpected value for %d - enc is %b, dec is %d\n", i, enc, dec)
		}
	}
}

func TestWriter0(t *testing.T) {
	var buf bytes.Buffer
	var w io.Writer = Writer(&buf)

	w.Write([]byte{0})
	w.Write(nil)
	for _, v := range buf.Bytes() {
		fmt.Printf("%s-", b2s(v))
	}
	fmt.Println()
}

func TestWriter1(t *testing.T) {
	var buf bytes.Buffer
	var w io.Writer = Writer(&buf)

	w.Write([]byte{0, 1})
	w.Write(nil)
	for _, v := range buf.Bytes() {
		fmt.Printf("%s-", b2s(v))
	}
	fmt.Println()
}

func TestWriter2(t *testing.T) {
	var buf bytes.Buffer
	var w io.Writer = Writer(&buf)

	w.Write([]byte{0, 1, 2})
	w.Write(nil)
	for _, v := range buf.Bytes() {
		fmt.Printf("%s-", b2s(v))
	}
	fmt.Println()
}

func TestWriter3(t *testing.T) {
	var buf bytes.Buffer
	var w io.Writer = Writer(&buf)

	var input []byte = make([]byte, 256)
	for i := 0; i < 256; i++ {
		input[i] = byte(i)
	}

	w.Write(input)
	w.Write(nil)
	for _, v := range buf.Bytes() {
		fmt.Printf("%s-", b2s(v))
	}
	fmt.Println()
}

func b2s(b byte) (result string) {
	for i := 0; i < 8; i++ {
		if b&1 > 0 {
			result += "1"
		} else {
			result += "0"
		}
		b >>= 1
	}
	return
}