#!/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.
      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.

   ]

   isLeaf [
      ^1
   ]
]


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.
   ]

   left [
      ^ left
   ]

   right [
      ^ right
   ]

   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
   ]


   isLeaf [
      ^0
   ]

]


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

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.
].


c = 1 ifTrue: [
   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.
   stdout << 'hi this is our encrypted tree: \n'.
   t inspect.

   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.
      bitArray do: [:bit| outBytes writeBit: bit.].
      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.
].






"-----------------------------------------------------------------"
"decompression----------------------------------------------------"

   FileStream extend [
      |bitIndex currentChar|

      nextBit [
         |bit|
         bitIndex isNil ifTrue: [bitIndex := 0].
         bitIndex = 0 ifTrue: [
            bitIndex := 8.
            currentChar := self next.
         ].
         bit := currentChar value bitAt: bitIndex.
         bitIndex := bitIndex - 1.
         ^ bit
      ]

      atBitEnd [
         ^ (bitIndex isNil | (bitIndex = 0)) & self atEnd
      ]

   ]


   treeq := SortedCollection new.



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


   stdout <<'contents of file:'<<nl.
   [infile atBitEnd not] whileTrue: [
      | bit |
      bit := infile nextBit.
      stdout << bit.
   ].
   stdout << nl.
   infile close.


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

   treeq := OrderedCollection new.
   priority := 1000.
   endOfTree := 1.

   [endOfTree = 1] whileTrue: [
      | bit |
      bit := infile nextBit.

      bit = 1 ifTrue: [
         | char  count |
         char := 255.
         count := 8.
         [count > 0 ] whileTrue: [
            count := count - 1.
            infile nextBit = 0 ifTrue: [
               num := 2 raisedTo: count.
               char := char - num.
            ]
         ].
         val := Leaf new: char asCharacter count: priority. "we do this because don't know freq"
         stdout <<'is this a leaf---------------------------------'<< (val isLeaf) << nl.
         priority := priority - 10.
         treeq addFirst: val.
         stdout << val <<nl.
      ]
      ifFalse: [ "for when we see a zero"
         treeq size = 1
         ifTrue: [
            endOfTree := 0. ]
         ifFalse: [
            |first second t|
            first := treeq removeFirst.
            second := treeq removeFirst.

            t := Tree new: (first char) count: priority left: second right: first.
            priority := priority - 10.
            treeq addFirst: t.
         ].

      ].

   ].

   t := treeq removeFirst.
   encode_table := ZeroArray new: 256.


   "creating an encoding table based of tree we created above ^"
   t inorder: [:char :string |
      encode_table at: char asInteger put: string.
      stdout << char << ' ' << string <<nl.
   ] prefix: ''.

   tR := t right.
   stdout << tR isLeaf << nl.
   stdout << tR char <<nl.


   t_current := t.
   result := OrderedCollection new.

   [infile atBitEnd not] whileTrue: [
      | bit |

      t_current isLeaf = 1
      ifTrue: [
         result addLast: t_current char.
         stdout << t_current char.
         t_current := t.
      ]
      ifFalse: [
         bit := infile nextBit.
         bit = 1 ifTrue: [
            t_current := t_current right.
         ]
         ifFalse: [
            t_current := t_current left.
         ].
      ].

   ].

   infile close.

   writeOutFile := [:outfile|
      [(result size = 1) not] whileTrue: [
         |letter|
         letter := result removeFirst.
         outfile nextPut: letter.
         ].
   ].

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





"

   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.
"


 "  createLeaf := [:infile|
      | char  count |
      char = 255.
      count = 8.
      [count > 0 ] whileTrue: [
         count := count - 1.
         nextbit = 0 ifTrue: [
            char := char - (2 raisedTo count).
         ].
         val :=  Leaf new: char asCharacter count: -1. we do this because don't know freq
         treeq nextPut val.
      ].
      b0 := infile nextBit.


   ]."