// Copyright 2015 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// This file implements multi-precision decimal numbers.
// The implementation is for float to decimal conversion only;
// not general purpose use.
// The only operations are precise conversion from binary to
// decimal and rounding.
//
// The key observation and some code (shr) is borrowed from
// strconv/decimal.go: conversion of binary fractional values can be done
// precisely in multi-precision decimal because 2 divides 10 (required for
// >> of mantissa); but conversion of decimal floating-point values cannot
// be done precisely in binary representation.
//
// In contrast to strconv/decimal.go, only right shift is implemented in
// decimal format - left shift can be done precisely in binary format.

package big

// A decimal represents an unsigned floating-point number in decimal representation.
// The value of a non-zero decimal d is d.mant * 10**d.exp with 0.1 <= d.mant < 1,
// with the most-significant mantissa digit at index 0. For the zero decimal, the
// mantissa length and exponent are 0.
// The zero value for decimal represents a ready-to-use 0.0.
type decimal struct {
	mant []byte // mantissa ASCII digits, big-endian
	exp  int    // exponent
}

// at returns the i'th mantissa digit, starting with the most significant digit at 0.
func ( *decimal) ( int) byte {
	if 0 <=  &&  < len(.mant) {
		return .mant[]
	}
	return '0'
}

// Maximum shift amount that can be done in one pass without overflow.
// A Word has _W bits and (1<<maxShift - 1)*10 + 9 must fit into Word.
const maxShift = _W - 4

// TODO(gri) Since we know the desired decimal precision when converting
// a floating-point number, we may be able to limit the number of decimal
// digits that need to be computed by init by providing an additional
// precision argument and keeping track of when a number was truncated early
// (equivalent of "sticky bit" in binary rounding).

// TODO(gri) Along the same lines, enforce some limit to shift magnitudes
// to avoid "infinitely" long running conversions (until we run out of space).

// Init initializes x to the decimal representation of m << shift (for
// shift >= 0), or m >> -shift (for shift < 0).
func ( *decimal) ( nat,  int) {
	// special case 0
	if len() == 0 {
		.mant = .mant[:0]
		.exp = 0
		return
	}

	// Optimization: If we need to shift right, first remove any trailing
	// zero bits from m to reduce shift amount that needs to be done in
	// decimal format (since that is likely slower).
	if  < 0 {
		 := .trailingZeroBits()
		 := uint(-)
		if  >=  {
			 =  // shift at most ntz bits
		}
		 = nat(nil).shr(, )
		 += int()
	}

	// Do any shift left in binary representation.
	if  > 0 {
		 = nat(nil).shl(, uint())
		 = 0
	}

	// Convert mantissa into decimal representation.
	 := .utoa(10)
	 := len()
	.exp = 
	// Trim trailing zeros; instead the exponent is tracking
	// the decimal point independent of the number of digits.
	for  > 0 && [-1] == '0' {
		--
	}
	.mant = append(.mant[:0], [:]...)

	// Do any (remaining) shift right in decimal representation.
	if  < 0 {
		for  < -maxShift {
			shr(, maxShift)
			 += maxShift
		}
		shr(, uint(-))
	}
}

// shr implements x >> s, for s <= maxShift.
func shr( *decimal,  uint) {
	// Division by 1<<s using shift-and-subtract algorithm.

	// pick up enough leading digits to cover first shift
	 := 0 // read index
	var  Word
	for >> == 0 &&  < len(.mant) {
		 := Word(.mant[])
		++
		 = *10 +  - '0'
	}
	if  == 0 {
		// x == 0; shouldn't get here, but handle anyway
		.mant = .mant[:0]
		return
	}
	for >> == 0 {
		++
		 *= 10
	}
	.exp += 1 - 

	// read a digit, write a digit
	 := 0 // write index
	 := Word(1)<< - 1
	for  < len(.mant) {
		 := Word(.mant[])
		++
		 :=  >> 
		 &=  // n -= d << s
		.mant[] = byte( + '0')
		++
		 = *10 +  - '0'
	}

	// write extra digits that still fit
	for  > 0 &&  < len(.mant) {
		 :=  >> 
		 &= 
		.mant[] = byte( + '0')
		++
		 =  * 10
	}
	.mant = .mant[:] // the number may be shorter (e.g. 1024 >> 10)

	// append additional digits that didn't fit
	for  > 0 {
		 :=  >> 
		 &= 
		.mant = append(.mant, byte(+'0'))
		 =  * 10
	}

	trim()
}

func ( *decimal) () string {
	if len(.mant) == 0 {
		return "0"
	}

	var  []byte
	switch {
	case .exp <= 0:
		// 0.00ddd
		 = make([]byte, 0, 2+(-.exp)+len(.mant))
		 = append(, "0."...)
		 = appendZeros(, -.exp)
		 = append(, .mant...)

	case /* 0 < */ .exp < len(.mant):
		// dd.ddd
		 = make([]byte, 0, 1+len(.mant))
		 = append(, .mant[:.exp]...)
		 = append(, '.')
		 = append(, .mant[.exp:]...)

	default: // len(x.mant) <= x.exp
		// ddd00
		 = make([]byte, 0, .exp)
		 = append(, .mant...)
		 = appendZeros(, .exp-len(.mant))
	}

	return string()
}

// appendZeros appends n 0 digits to buf and returns buf.
func appendZeros( []byte,  int) []byte {
	for ;  > 0; -- {
		 = append(, '0')
	}
	return 
}

// shouldRoundUp reports if x should be rounded up
// if shortened to n digits. n must be a valid index
// for x.mant.
func shouldRoundUp( *decimal,  int) bool {
	if .mant[] == '5' && +1 == len(.mant) {
		// exactly halfway - round to even
		return  > 0 && (.mant[-1]-'0')&1 != 0
	}
	// not halfway - digit tells all (x.mant has no trailing zeros)
	return .mant[] >= '5'
}

// round sets x to (at most) n mantissa digits by rounding it
// to the nearest even value with n (or fever) mantissa digits.
// If n < 0, x remains unchanged.
func ( *decimal) ( int) {
	if  < 0 ||  >= len(.mant) {
		return // nothing to do
	}

	if shouldRoundUp(, ) {
		.roundUp()
	} else {
		.roundDown()
	}
}

func ( *decimal) ( int) {
	if  < 0 ||  >= len(.mant) {
		return // nothing to do
	}
	// 0 <= n < len(x.mant)

	// find first digit < '9'
	for  > 0 && .mant[-1] >= '9' {
		--
	}

	if  == 0 {
		// all digits are '9's => round up to '1' and update exponent
		.mant[0] = '1' // ok since len(x.mant) > n
		.mant = .mant[:1]
		.exp++
		return
	}

	// n > 0 && x.mant[n-1] < '9'
	.mant[-1]++
	.mant = .mant[:]
	// x already trimmed
}

func ( *decimal) ( int) {
	if  < 0 ||  >= len(.mant) {
		return // nothing to do
	}
	.mant = .mant[:]
	trim()
}

// trim cuts off any trailing zeros from x's mantissa;
// they are meaningless for the value of x.
func trim( *decimal) {
	 := len(.mant)
	for  > 0 && .mant[-1] == '0' {
		--
	}
	.mant = .mant[:]
	if  == 0 {
		.exp = 0
	}
}