#!/afs/cats.ucsc.edu/courses/cmps112-wm/usr/smalltalk/bin/gst -f
"$Id: tree.st,v 1.10 2012-02-23 18:57:51-08 - - $"

nl := Character nl.




"------------------------------------------------------------"
Object subclass: OutBits [
   |bitIndex currentByte myStream|
   OutBits class >> new [
      self shouldNotImplement.
   ]
   OutBits class >> new: fileStream [
      |result|
      result := super new.
      result init: fileStream.
      ^result
   ]
   clearByte [
      bitIndex := 8.
      currentByte := 0.
   ]
   init: fileStream [
      myStream := fileStream.
      self clearByte.
   ]
   flushByte [
      bitIndex = 8 ifFalse: [
         myStream nextPutByte: currentByte.
         self clearByte.
      ]
   ]
   writeBit: bit [
      currentByte := currentByte bitAt: bitIndex put: bit.
      stdout << (currentByte bitAt: bitIndex).
      bitIndex := bitIndex - 1.
      bitIndex = 0 ifTrue: [self flushByte].
   ]
]


"----------------------------------------------------------"
Object subclass: Leaf [
   |char count|
   char [ ^ char ]
   count [ ^ count ]

   Leaf class >> new [
      self shouldNotImplement
   ]

   Leaf class >> new: aChar count: aCount [
      |result|
      result := super new.
      result setChar: aChar andCount: aCount.
      ^result
   ]

   setChar: aChar andCount: aCount [
      char := aChar.
      count := aCount.
   ]

   <= other [
      ^ (count < other count)
      | ((count = other count) & (char <= other char))
   ]

   printBase: aStream [
      ^ aStream << self class << '(' << char << ',' << count
   ]

   printOn: aStream [
      (self printBase: aStream) << ')'.
   ]

   inorder: visitor prefix: string [
      visitor value: char value: string.
   ]


   treeAsBit: visitor sum: qlength queue: stackq [
      stdout<< '1'.
      stackq nextPut: 1.

      stackq nextPut: ((char asInteger) bitAt: 8).
      stackq nextPut: ((char asInteger) bitAt: 7).
      stackq nextPut: ((char asInteger) bitAt: 6).
      stackq nextPut: ((char asInteger) bitAt: 5).
      stackq nextPut: ((char asInteger) bitAt: 4).
      stackq nextPut: ((char asInteger) bitAt: 3).
      stackq nextPut: ((char asInteger) bitAt: 2).
      stackq nextPut: ((char asInteger) bitAt: 1).

      stdout << ((char asInteger) bitAt: 8).
      stdout << ((char asInteger) bitAt: 7).
      stdout << ((char asInteger) bitAt: 6).
      stdout << ((char asInteger) bitAt: 5).
      stdout << ((char asInteger) bitAt: 4).
      stdout << ((char asInteger) bitAt: 3).
      stdout << ((char asInteger) bitAt: 2).
      stdout << ((char asInteger) bitAt: 1).
      ^ 9.

   ]
]


Leaf subclass: Tree [
   |left right|

   Tree class >> new: aChar count: aCount [
      self shouldNotImplement
   ]

   Tree class >> new: aChar count: aCount left: aLeft right: aRight [
      |result|
      result := super new: aChar count: aCount.
      result setLeft: aLeft andRight: aRight.
      ^ result
   ]

   setLeft: aLeft andRight: aRight [
      left := aLeft.
      right := aRight.
   ]

   printOn: aStream [
      (self printBase: aStream) << ',' << left << ',' << right << ')'.
   ]

   inorder: visitor prefix: string [
      left inorder: visitor prefix: string, '0'.
      right inorder: visitor prefix: string, '1'.
   ]

   treeAsBit: visitor sum: qlength queue: stackq[
      |sum1 sum2 sum |
      sum1 := left treeAsBit: visitor sum: qlength queue: stackq.
      sum2 := right treeAsBit: visitor sum: qlength queue: stackq.
      sum := sum1 + sum2.
      sum := sum + 1.
      stackq nextPut: 0.
      stdout << '0'.
      ^ sum
   ]

]


"----------------------------------------------------------------------"

Character extend [
   isPrint [
      ^ (Character space <= self) & (self <= $~)
   ]
   visible [
      self isPrint ifTrue: [^ '$', self asString]
                   ifFalse: [^ self asInteger printStringRadix: 8]
   ]
]

Object subclass: ZeroArray [
   |theArray|

   ZeroArray class >> new [
      self shouldNotImplement.
   ]

   ZeroArray class >> new: size [
      |result|
      result := super new.
      result init: size.
      ^ result
   ]

   init: size [
      theArray := Array new: size.
   ]

   size [
      ^ theArray size.
   ]

   at: index [
      ^ theArray at: index + 1.
   ]

   at: index put: value [
      ^ theArray at: index + 1 put: value.
   ]

   incr: index [
      (self at: index) isNil
         ifTrue: [ self at: index put: 0].
      self at: index put: (self at: index) + 1.
   ]

   keysAndValuesDo: aBlock [
      (0 to: (self size) - 1) do: [:index |
         aBlock value: index value: (self at: index).
      ]
   ]



]

"-------------------------------------------------------------------"





freqtable := ZeroArray new: 256.

infile := FileStream open: (Smalltalk arguments at: 2)
                     mode: FileStream read.


[infile atEnd not] whileTrue: [
   |ordChar|
   ordChar := infile next asInteger.
   freqtable incr: ordChar.
].

infile close.

d := 0.
t := 0.
c := 0.
u := 0.

stdout << 'file: ' <<(Smalltalk arguments at: 2) << nl.

Smalltalk arguments: '-d -t -c -u'
do: [:opt :arg |
   opt = $d ifTrue: [stdout << 'option d' <<nl.
                      d :=1. ].
   opt = $t ifTrue: [stdout << 'option t' <<nl.
                      t :=1. ].
   opt = $c ifTrue: [stdout << 'option c' <<nl.
                      c :=1. ].
   opt = $u ifTrue: [stdout << 'option u' <<nl.
                      u :=1. ].
]
ifError: [
   'Error: invalid option' displayNl.
].




sortcol := SortedCollection new.
q := SharedQueue new.
chars_in_file := SortedCollection new.

freqtable keysAndValuesDo: [:key :value |
   (value notNil and: [value > 0]) ifTrue: [
      val := Leaf new: key asCharacter count: value.
      sortcol add: val.
      chars_in_file add: key
   ]
].

encode_table := ZeroArray new: 256.


[sortcol size > 1] whileTrue: [
   |first second t|
   first := sortcol removeFirst.
   second := sortcol removeFirst.

   t := Tree new: (second char) count: (first count + second count) left: first right: second.
   sortcol add: t.
].


t := sortcol removeFirst.

t inorder: [:char :string |
   encode_table at: char asInteger put: string.
] prefix: ''.

formatOutput := [:let :freq :bits|
         let asString size to: 3 do: [:skip| stdout << ' '].
         stdout << let.
         freq asString size to: 5 do: [:skip| stdout << ' '].
         stdout << freq << '   ' << bits << nl.
].


arraylen := 0.

encode_table keysAndValuesDo: [:key :value |
   (value notNil and: [value > 0]) ifTrue: [
      formatOutput value: (key asCharacter visible) value: (freqtable at: key) value: value.
      arraylen := arraylen + ((freqtable at: key)*(value size)).
   ]
].





stackq := SharedQueue new.
qlength := 0.
stdout<<nl.
qlength := t treeAsBit: [:char :string ] sum: qlength queue: stackq.
stdout<<0.
qlength := qlength + 1.
stackq nextPut: 0.
stdout<<nl.


stdout << qlength<< nl.


extra:= 0.
stdout << ((arraylen+qlength) \\ 8) << nl << nl << nl.
((arraylen+qlength) // 8 = 0) ifFalse: [
   extra := 8 - (arraylen+qlength) \\ 8 ].

bitArray := Array new: (arraylen+qlength)+extra.
stdout << bitArray size << nl << nl.

index := 1.


[stackq isEmpty not] whileTrue: [
   |bit|
   bit := stackq next.
   bitArray at: index put: bit.
   index := index + 1.
].

stdout << nl << nl.



infile := FileStream open: (Smalltalk arguments at: 2)
                     mode: FileStream read.



stdout << 'second part of bitarray' <<nl.

[infile atEnd not] whileTrue: [
   |ordChar|
   ordChar := infile next asInteger.

   index to: (index+((encode_table at: ordChar) size))-1  do:
      [ :x |
      bit := 0.
      (((encode_table at: ordChar) at: ((x-index)+1)) = $1) ifTrue: [bit:= 1.].
      bitArray at: x put: bit.
      stdout << (bitArray at: x put: bit).
      ].

   index := (index+((encode_table at: ordChar) size)).
].

index to: ((arraylen+qlength)+extra) do: [
   :x |
   (bitArray at: x put: 0).
].

stdout << nl << nl << nl.
bitArray do: [:bit | stdout << bit. ].
stdout << nl.

infile close.


writeBitArray := [:outfile|
   |outBytes|
   outBytes := OutBits new: outfile.
   stdout << 'writing to outfile:'<<nl.
   bitArray do: [:bit| outBytes writeBit: bit.].
   stdout << nl << 'done writing to outfile'<<nl.
   outBytes flushByte.
   stdout<<nl.
].

Smalltalk arguments size = 2
   ifTrue: [writeBitArray value: stdout]
   ifFalse: [
      |outfilename|
      outfilename := Smalltalk arguments at: 3.
      [  |outfile|
         outfile := FileStream open: outfilename mode: FileStream write.
         writeBitArray value: outfile.
         outfile close.
      ] on: SystemExceptions.FileError do: [:signal |
         |errno|
         errno := File errno.
         stdout flush.
         stderr << execname << ': ' << filename << ': '
                << signal messageText << nl.
         stderr flush.
      ]
   ].

bitArray do: [:bit | stdout << bit. ].
stdout << nl.
stdout << nl.

"
infile := FileStream open: (Smalltalk arguments at: 2)
                     mode: FileStream read.

Smalltalk arguments size = 2
   ifTrue: [
      [infile atEnd not] whileTrue: [
         |ordChar|
         ordChar := infile next asInteger.
         stdout << (encode_table at: ordChar)
      ].
      ]
   ifFalse: [stdout << 'hi' << nl.].

infile close."