unit huffman_trees;

{$M+}
{$MODE OBJFPC}
{$ASSERTIONS ON}

interface
uses bitstreams, type_fixes, classes;

type
  TBinaryTreeStorage = array of TByte;

type
  TBinaryTree = class(TComponent)
  private
    fStorage : TBinaryTreeStorage;
  protected
    function GetItem(aID : Integer) : TByte;
    procedure SetItem(aID : Integer; aValue : TByte);
    function GetLeftChild(aID : Integer) : Integer;
    function GetRightChild(aID : Integer) : Integer;
  published
    constructor Create(aOwner : TComponent; aLevelCount : Integer); reintroduce;
  public
    property Item[ID : Integer] : TByte read GetItem write SetItem;
    property LeftChild[ID : Integer] : Integer read GetLeftChild;
    property RightChild[ID : Integer] : Integer read GetRightChild;
  end;

  THuffmanTree = class(TBinaryTree)
    constructor LoadFromJFIF(aOwner : TComponent; aStream : TStream);
    procedure LoadLevelFromJFIF(aStream : TStream; aLevel : TByte; aCount : Cardinal);  // level: 0-based.
´   class procedure SkipFromJFIF(aStream : TStream);
  end;

implementation

{
binary tree:
Node index i, starting at 0.
Then the parent is at (i - 1) // 2.
The left child is at 2 * i + 1.
The right child is at 2 * i + 2.
}

function TBinaryTree.GetItem(aID : Integer) : TByte;
begin
  assert(Length(fStorage) > aID);
  Result := fStorage[aID];
end;

procedure TBinaryTree.SetItem(aID : Integer; aValue : TByte);
begin
  assert(Length(fStorage) > aID);
  fStorage[aID] := aValue;
end;

function TBinaryTree.GetLeftChild(aID : Integer) : Integer; inline;
begin
  Result := 2 * aID + 1;
end;

function TBinaryTree.GetRightChild(aID : Integer) : Integer; inline;
begin
  Result := 2 * aID + 2;
end;

constructor TBinaryTree.Create(aOwner : TComponent; aLevelCount : Integer);
begin
  inherited Create(aOwner);
  SetLength(fStorage, 1 shl (aLevelCount + 1));
end;

procedure THuffmanTree.LoadLevelFromJFIF(aStream : TStream; aLevel : TByte; aCount : Cardinal); 
var
  i : Integer;
  maxCount : Integer;
  count : Integer;
begin
  maxCount := 1 shl aLevel;
  count := aCount;
  assert(count <= maxCount);
  i := 0;
  while aLevel > 0 do begin
    i := 2 * i + 1;
    Dec(aLevel);
  end;
  assert(i + count <= Length(fStorage));
  aStream.ReadBuffer(fStorage[i], Sizeof(TByte) * count);
end;

constructor THuffmanTree.LoadFromJFIF(aOwner : TComponent; aStream : TStream);
var
  counts : packed array[1..16] of TByte; // index=bit count.
  i : Integer;
begin
  Create(aOwner, 16);
  aStream.ReadBuffer(counts, 16);
  for i := Low(counts) to High(counts) do 
    LoadLevelFromJFIF(aStream, i-1, counts[i]);
end;

class procedure THuffmanTree.SkipFromJFIF(aStream : TStream);
begin
var
  counts : packed array[1..16] of TByte; // index=bit count.
  i : Integer;
  count : Integer;
begin
  aStream.ReadBuffer(counts, 16);
  count := 0;
  for i := Low(counts) to High(counts) do
    Inc(count, counts[i]);
  SkipJunk(aStream, count);
end;

end.