unit stack;
{
   Implements a stack as round list.
   Pop from empty stack returns 0
   Push to full stack deletes the last most value

   Author:  Vesa Lappalainen
   Date:    25.4.1998
   Changes: 13.7.2001/vl
    + the implementation of stack changed to dynamic array
      instead of round list.
    + stack will never be full

}

interface
type
  TaStack = class
  private
    fi:integer;
    fmax:integer;
    function GetOneAsString(i:integer):string; virtual;
    function GetCount: integer;
  protected
    function PushI:boolean; virtual;
    function PopI:boolean;  virtual;
    procedure IncMax; virtual;
  public
    constructor Create(amax:integer); virtual;
    destructor Destroy; override;
    function  GetEmpty : boolean; virtual;
    function  GetFull : BooleaN; virtual;
    procedure Clear; virtual;
    function AsString(const sep:string):string; virtual;
    function GetIndex(n:integer):integer; virtual; // index n step from top
  published
    property Empty : boolean read GetEmpty;
    property Full : BooleaN read GetFull;
    property i : integer read fi;
    property Count : integer read GetCount;
  end;


  TIntStack = class(TaStack)
  private
    values : array of integer;
    function GetOneAsString(i:integer):string; override;
  public
    constructor Create(amax:integer); override;
    destructor Destroy; override;
    function Push(value:integer):boolean; virtual;
    function Pop : integer;           virtual;
  end;

  TDoubleStack = class(TaStack)
  private
    values : array of double;
    function GetOneAsString(i:integer):string; override;
    procedure SetValue(j: integer; d: double);
  public
    constructor Create(amax:integer); override;
    destructor Destroy; override;
    function Push(value:double):boolean; virtual;
    function Pop : double;           virtual;
    function Peek(j:integer=0) : double;           virtual;
    function Rotate(n:integer) : double;           virtual;
    property Value[j:integer] : double read Peek write SetValue;
  end;

implementation
uses SysUtils,kdouble;

//-----------------------------------------------------------------------------
procedure TaStack.Clear; // virtual;
begin
  fi := 0;
end;


//-----------------------------------------------------------------------------
function  TaStack.GetEmpty : boolean; //  virtual;
begin
  Result := fi = 0;
end;


//-----------------------------------------------------------------------------
function  TaStack.GetFull : BooleaN; //  virtual;
begin
  Result := false;
end;


//-----------------------------------------------------------------------------
constructor TaStack.Create(amax:integer); //  virtual;
begin
  inherited Create;
  fmax := amax;
  Clear;
end;

//-----------------------------------------------------------------------------
destructor TaStack.Destroy; //  override;
begin
  FMax := 0;
  inherited;
end;

//-----------------------------------------------------------------------------
function TaStack.GetCount: integer;
begin
  Result := fi;
end;

//-----------------------------------------------------------------------------
procedure TaStack.IncMax;
begin
  if ( fmax < 2 ) then begin fmax := 4; exit; end;
  if ( fmax < 8 ) then begin fmax := 2*fmax; exit; end;
  fmax := 3 * fmax div 2;
end;

//-----------------------------------------------------------------------------
function TaStack.PushI:boolean;
begin
  Result := true;
  fi := fi + 1;
end;


//-----------------------------------------------------------------------------
function TaStack.PopI:boolean;
begin
  Result := false;
  if ( fi = 0 ) then exit;
  dec(fi); if ( fi < 0 ) then fi := fmax-1;
  Result := true;
end;

//-----------------------------------------------------------------------------
function TaStack.GetIndex(n: integer): integer;
begin
  if ( n >= Count ) then begin Result := 0; exit; end;
  Result := i - n - 1;
  while ( Result < 0 ) do Result := Result + fmax;
end;

//-----------------------------------------------------------------------------
function TaStack.AsString(const sep:string):string; //  virtual;
var ii:integer; s:string;
begin
  Result := '';
  s := '';
  for ii:=0 to Count-1 do begin
    Result := Result + s + GetOneAsString(ii);
    s := sep;
  end;
end;


//-----------------------------------------------------------------------------
constructor TIntStack.Create(amax:integer); //  override;
begin
  inherited;
  SetLength(values,fmax);
end;


//-----------------------------------------------------------------------------
destructor TIntStack.Destroy; //  override;
begin
  values := nil;
  inherited;
end;


//-----------------------------------------------------------------------------
function TIntStack.Push(value:integer):boolean; //  virtual;
begin
  if ( i >= fmax ) then begin IncMax; SetLength(values,fmax); end;
  values[i] := value;
  Result := PushI;
end;


//-----------------------------------------------------------------------------
function TIntStack.Pop : integer; //            virtual;
begin
  PopI;
  Result := values[i];
end;


//-----------------------------------------------------------------------------
constructor TDoubleStack.Create(amax:integer); //  override;
begin
  inherited;
  SetLength(values,amax);
end;


//-----------------------------------------------------------------------------
destructor TDoubleStack.Destroy; //  override;
begin
  values := nil;
  inherited;
end;


//-----------------------------------------------------------------------------
function TDoubleStack.Push(value:double):boolean; //  virtual;
begin
  if ( i >= fmax ) then begin IncMax; SetLength(values,fmax); end;
  values[i] := value;
  Result := PushI;
end;


//-----------------------------------------------------------------------------
function TDoubleStack.Pop : double; //            virtual;
begin
  PopI;
  Result := values[i];
end;

//-----------------------------------------------------------------------------
function TDoubleStack.Peek(j:integer): double;
begin
  Result := Value[j];
end;

//-----------------------------------------------------------------------------
procedure TDoubleStack.SetValue(j:integer;d:double);
begin
  Value[j] := d;
end;

//-----------------------------------------------------------------------------
function TDoubleStack.Rotate(n: integer): double;
var j,m:integer; d : double;
begin
  Result := 0;
  m := Abs(n);
  if ( m >= Count ) then m := Count;
  if ( m = 0 ) then exit;


  if ( n < 0 ) then begin  // Rotate downwards
    d := Peek(m-1);
    for j:=m-1 downto 1 do
      Value[j] := Value[j-1];
    Value[0] := d;
    Result := Peek;
    Exit;
  end;

  d := Value[0];          // Rotate upwards
  for j := 0 to m-2 do
    Value[j] := Value[j+1];
  Value[m-1] := d;

  Result := Peek;
end;


//-----------------------------------------------------------------------------
function TaStack.GetOneAsString(i:integer):string; //  virtual;
begin
  Result := '';
end;


//-----------------------------------------------------------------------------
function TIntStack.GetOneAsString(i:integer):string; //  virtual;
begin
  Result := IntToStr(values[i]);
end;


//-----------------------------------------------------------------------------
function TDoubleStack.GetOneAsString(i:integer):string; //  virtual;
begin
  Result := DoubleToIniStr(values[i],4);
end;


end.