declare -r MAX_TERMS=101
declare -r MAX_POLY=11
declare -r MAX_COEF=10

declare coef=()
declare expon=()

declare avail=0

function compare()
{
  local a=$1
  local b=$2
  [ $a -gt $b ] && echo ">"
  [ $a -eq $b ] && echo "="
  [ $a -lt $b ] && echo "<"
  return 0
}

function attach()
{
  local coef_val=$1
  local expon_val=$2
  if [ $avail -ge $MAX_TERMS ]; then
    echo "Too many entries."
    return -1
  fi
  coef[$avail]=$coef_val
  expon[$avail]=$expon_val
  ((avail++))
  return 0
}

function poly_add2()
{
  local As=$1
  local Ae=$2
  local Bs=$3
  local Be=$4
  local Cs_p=$5
  local Ce_p=$6
  local tempcoef

  eval ${Cs_p}=$avail

  while [ $As -le $Ae -a $Bs -le $Be ]; do
    local r=$(compare ${expon[$As]} ${expon[$Bs]})
    case $r in
    ">" )
      attach ${coef[$As]} ${expon[$As]}
      ((As++))
      ;;
    "=" )
      let tempcoef=${coef[$As]}+${coef[$Bs]}
      [ $tempcoef -ne 0 ] && attach $tempcoef ${expon[$Bs]}
      ((As++))
      ((Bs++))
      ;;
    "<" )
      attach ${coef[$Bs]} ${expon[$Bs]}
      ((Bs++))
      ;;
    esac
  done
  while [ $As -le $Ae ]; do
    attach ${coef[$As]} ${expon[$As]}
    ((As++))
  done
  while [ $Bs -le $Be ]; do
    attach ${coef[$Bs]} ${expon[$Bs]}
    ((Bs++))
  done

  eval let ${Ce_p}=$avail-1

  return 0
}

function is_num()
{
  local num=$1
  local len=${#num}
  local i=0
  local c
  while [ $i -lt $len ]
  do
    c=${num:$i:1}
    [ -n "${c/[0-9]/}" ] && return $FALSE
    let i=$i+1
  done
  return $TRUE
}

function get_num()
{
  local min=$1
  local max=$2
  local num
  read num
  is_num $num || return $FALSE
  [ ${num} -lt ${min} -o ${num} -gt ${max} ] && return -1
  echo $num
  return 0
}

function inputPolyNum()
{
  local num=-1
  while [ true ]
  do
    echo -n "Number of $1: "
    num=$(get_num 1 $MAX_POLY)
    [ $? -eq 0 ] && break
    echo "Out of range(1~$MAX_POLY). Retry!"
  done
  return $num
}

function makeRandomPoly()
{
  local As_p=$1
  local Ae_p=$2
  local Bs_p=$3
  local Be_p=$4
  local An=$5
  local Bn=$6

  local tmp_array=()
  local pos
  local count
  local exp
  local sign
  local i

  eval let ${As_p}=$avail
  eval let ${Ae_p}=${!As_p}+$An-1
  eval let ${Bs_p}=${!Ae_p}+1
  eval let ${Be_p}=${!Bs_p}+$Bn-1

  let coef_mod=${MAX_COEF}
  let pos_mod=${MAX_POLY}

  # poly A
  pos=0
  while (($pos < $MAX_POLY)); do
    tmp_array[$pos]=0
    ((pos++))
  done

  count=0
  while (($count < $An)); do
    let pos=$RANDOM%${pos_mod}
    [ ${tmp_array[$pos]} -ne 0 ] && continue
    let i=($RANDOM%${coef_mod})+1
    let sign=$RANDOM%2
    [ $sign -eq 1 ] && sign="-" || sign=""
    tmp_array[$pos]=${sign}${i}
    ((count++))
  done
  
  i=0
  while (($i < $MAX_POLY)); do
    pos=$i
    ((i++))
    [ ${tmp_array[$pos]} -eq 0 ] && continue
    let exp=${MAX_POLY}-${pos}-1
    attach ${tmp_array[$pos]} $exp
  done

  # poly B
  pos=0
  while (($pos < $MAX_POLY)); do
    tmp_array[$pos]=0
    ((pos++))
  done

  count=0
  while (($count < $Bn)); do
    let pos=$RANDOM%${pos_mod}
    [ ${tmp_array[$pos]} -ne 0 ] && continue
    let i=($RANDOM%${coef_mod})+1
    let sign=$RANDOM%2
    [ $sign -eq 1 ] && sign="-" || sign=""
    tmp_array[$pos]=${sign}${i}
    ((count++))
  done
  
  i=0
  while (($i < $MAX_POLY)); do
    pos=$i
    ((i++))
    [ ${tmp_array[$pos]} -eq 0 ] && continue
    let exp=${MAX_POLY}-${pos}-1
    attach ${tmp_array[$pos]} $exp
  done

  return 0
}

function printPoly()
{
  local S=$1
  local E=$2
  while (($S <= $E)); do
    printf "%3dX^%-2d " "${coef[$S]}" "${expon[$S]}"
    ((S++))
  done
  printf "\n"
  return 0
}

function main()
{
  local An=0
  local Bn=0
  local As=0
  local Ae=0
  local Bs=0
  local Be=0
  local Cs=0
  local Ce=0

  inputPolyNum "A"
  An=$?

  inputPolyNum "B"
  Bn=$?

  makeRandomPoly As Ae Bs Be $An $Bn

  printf "A      : "
  printPoly $As $Ae

  printf "B      : "
  printPoly $Bs $Be

  poly_add2 $As $Ae $Bs $Be Cs Ce

  printf "C=(A+B): "
  printPoly $Cs $Ce
  
}

main ${@}