##  Copyright (C) 2015  Daniel Kraft <address@hidden>
##  GNU Octave datastructure package.
##
##  This program is free software: you can redistribute it and/or modify
##  it under the terms of the GNU General Public License as published by
##  the Free Software Foundation, either version 3 of the License, or
##  (at your option) any later version.
##
##  This program is distributed in the hope that it will be useful,
##  but WITHOUT ANY WARRANTY; without even the implied warranty of
##  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
##  GNU General Public License for more details.
##
##  You should have received a copy of the GNU General Public License
##  along with this program.  If not, see <http://www.gnu.org/licenses/>.

## -*- texinfo -*-
## @deftypefn {Function File} address@hidden =} stack ()
## @deftypefnx {Function File} address@hidden =} stack (@var{values})
##
## Construct a new object @var{s} of the @code{stack} class.  If called
## with the argument @var{values}, the initial content of the stack
## can be set from a scalar, vector or cell array.
##
## Stack is a datastructure that allows efficient appending and removing
## of elements from the end.  This is achieved by overallocating a cell array,
## such that addition of elements to the end is amortized constant in time.
## Removing elements is guaranteed to be constant.
##
## Note that the stack is implemented in m-file code, so that operations
## carry some overhead for interpretation.  This class is most useful
## if large elements have to be stored and the maximum size of the array
## is not known a-priori.

% FIXME: Add documentation for the individual functions, although it is
% seemingly currently not displayed at all by Octave.

classdef stack < handle

  % Define constants that determine the resizing behaviour.
  properties (Access = private, Constant = true)
    minSize = 16;
    resizeFactor = 2;
  endproperties

  properties (Access = private)
    values = {};
    sz = 0;
  endproperties

  methods

    function s = stack (initial)
      if (nargin > 0)
        s.set (initial);
      else
        s.values = cell (s.minSize, 1);
        s.sz = 0;
      endif
    endfunction

    function res = isempty (this)
      res = (this.sz == 0);
    endfunction

    function [real, reserved] = size (this)
      real = this.sz;
      reserved = length (this.values);
    endfunction

    function display (this)
      fprintf ("%s = stack: size %u, allocated %u\n", ...
               inputname(1), this.sz, length (this.values));
    endfunction

    function v = top (this)
      if (this.isempty ())
        error ("the stack is empty");
      endif
      v = this.values{this.sz};
    endfunction

    function push (this, val)
      inds = struct ("type", "()", "subs", {{this.sz+1}});
      this.subsasgn (inds, val);
    endfunction

    function v = pop (this)
      if (this.isempty ())
        error ("the stack is empty");
      endif
      if (nargout > 0)
        v = this.values{this.sz};
      endif

      % Set the 'deleted' entry to a small value.  If the entry was something
      % like a large array, this allows to immediately free the memory instead
      % of keeping it around.
      this.values{this.sz} = {};

      --this.sz;
    endfunction

    function clear (this)
      this.sz = 0;
    endfunction

    function reserve (this, sz, tighten = false)
      sz = max (sz, this.sz);
      if (sz == length (this.values))
        return;
      endif
      if (sz < length (this.values) && !tighten)
        return;
      endif

      assert (sz >= this.sz);
      this.values = resize (this.values, [sz, 1]);
    endfunction

    % Define functions related to indexing.  They do the main work.

    function r = end (this, indexPos, numInd)
      if (numInd != 1)
        error ("stack can only have one index");
      endif
      assert (indexPos, 1);
      r = this.sz;
    endfunction

    function v = subsref (this, ind)
      % FIXME: Somehow make this not fail when trying to call
      % methods via the dot notation!

      if (!strcmp (ind.type, "()"))
        error ("invalid indexing of stack");
      endif
      inds = ind.subs;
      if (numel (inds) != 1)
        error ("stack can only have one index");
      endif

      if (strcmp (inds, ":"))
        v = this.values(1 : this.sz);
      else
        inds = cell2mat (inds);
        if (any (inds < 1 | inds > this.sz))
          error ("stack index out of bounds");
        endif

        if (isscalar (inds))
          v = this.values{inds};
        else
          v = this.values(inds);
        endif
      endif
    endfunction

    function this = subsasgn (this, ind, rhs)
      if (!strcmp (ind.type, "()"))
        error ("invalid indexing of stack");
      endif
      inds = ind.subs;
      if (numel (inds) != 1)
        error ("stack can only have one index");
      endif

      if (strcmp (inds, ":"))
        this.set (rhs);
      else
        inds = cell2mat (inds);
        if (any (inds < 1))
          error ("stack index out of bounds");
        endif

        % Resize if necessary.
        alloc = length (this.values);
        if (alloc < max (inds))
          alloc = max (max (inds), this.resizeFactor * alloc);
          this.values = resize (this.values, [alloc, 1]);
        endif
        assert (max (inds) <= length (this.values));

        % Assign a scalar as-is but translate the RHS to a cell array
        % (i. e., allow using a vector) if we do range assignment.
        if (isscalar (inds))
          this.values{inds} = rhs;
        else
          this.values(inds) = this.rhsToCell (rhs);
        endif
        this.sz = max ([this.sz, inds]);
      endif
    endfunction

  endmethods

  methods (Access = private)

    function set (this, rhs)
      % Make sure that we have at least the minimum initial size.
      this.sz = length (rhs);
      alloc = max (this.minSize, this.sz);
      this.values = cell (alloc, 1);
      this.values(1 : this.sz) = this.rhsToCell (rhs);
    endfunction

  endmethods

  methods (Access = private, Static = true)

    function rhs = rhsToCell (rhs)
      n = numel (rhs);
      if (n > 0 && !isvector (rhs))
        error ("invalid stack assignment right-hand side");
      endif
      if (!isscalar (rhs) && !strcmp (class (rhs), "cell"))
        rhs = reshape (rhs, [n, 1]);
        rhs = mat2cell (rhs, ones (n, 1));
      endif
    endfunction

  endmethods

endclassdef

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Demo.

% Demonstrate how pushing to the stack is algorithmically better
% than using an ordinary array "naively".
%!demo
%!  k = 100;
%!  ns = round (logspace (log10 (10), log10 (500), 10));
%!
%!  timesStack = NA (size (ns));
%!  timesArray = NA (size (ns));
%!  for i = 1 : length (ns)
%!
%!    t1 = cputime ();
%!    s = stack ();
%!    for j = 1 : ns(i)
%!      push (s, rand (k, k));
%!    endfor
%!    t2 = cputime ();
%!    timesStack(i) = t2 - t1;
%!
%!    t1 = cputime ();
%!    s = [];
%!    for j = 1 : ns(i)
%!      s(1 : k, 1 : k, end + 1) = rand (k, k);
%!    endfor
%!    t2 = cputime ();
%!    timesArray(i) = t2 - t1;
%!
%!    printf ("Times for n = %3d: stack %6.3f, array %6.3f\n", ...
%!            ns(i), timesStack(i), timesArray(i));
%!  endfor
%!
%!  loglog (ns, timesStack, "bo", ns, timesArray, "ro");
%!  legend ("Stack", "Array");

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Tests.

% Test basic stack operations.
%!test
%!  s = stack ();
%!  assert (size (s), 0);
%!  assert (isempty (s));
%!  toPush = {42, "foobar", {}, [], rand(2, 2), 1:5};
%!
%!  for i = 1 : length (toPush)
%!    push (s, toPush{i});
%!    assert (size (s), i);
%!    assert (!isempty (s));
%!    assert (top (s), toPush{i});
%!  endfor
%!
%!  for i = length (toPush) : -1 : 1
%!    assert (size (s), i);
%!    assert (!isempty (s));
%!    val = pop (s);
%!    assert (val, toPush{i});
%!  endfor
%!
%!  assert (size (s), 0);
%!  assert (isempty (s));
%!error<the stack is empty>
%!  s = stack ();
%!  top (s);
%!error<the stack is empty>
%!  s = stack ();
%!  pop (s);

% Initialisation and retrieval with (:) indexing.
%!test
%!  s = stack (5);
%!  assert (s(:), {5});
%!
%!  s = stack ([1, 2, 3]);
%!  assert (s(:), {1; 2; 3});
%!
%!  R = rand (2, 2);
%!  s = stack ({"abc", {}, R});
%!  assert (s(:), {"abc"; {}; R});
%!
%!  s(:) = 5;
%!  assert (s(:), {5});
%!
%!  s(:) = {"abc"; 42};
%!  assert (s(:), {"abc"; 42});
%!
%!  s(:) = {};
%!  assert (isempty (s));
%!error<invalid stack assignment right-hand side>
%!  stack (rand (2, 2));
%!error<invalid stack assignment right-hand side>
%!  s = stack ();
%!  s(:) = [1, 2; 3, 4];

% Indexing by single entries and ranges, including end.
%!test
%!  s = stack (1 : 10);
%!  push (s, {});
%!  assert (size (s), 11);
%!  for i = 1 : 10
%!    assert (s(i), i);
%!  endfor
%!  assert (s(3 : 5), {3; 4; 5});
%!  assert (s(end), {});
%!  assert (s(end - 2 : end - 1), {9; 10});
%!error<stack index out of bounds>
%!  s = stack (1 : 10);
%!  s(0);
%!error<stack index out of bounds>
%!  s = stack (1 : 10);
%!  s(end + 1);
%!error<subscript indices must be>
%!  s = stack (1 : 10);
%!  s(1.5);
%!error<stack can only have one index>
%!  s = stack (1 : 10);
%!  s(1, 2);
%!error<stack can only have one index>
%!  s = stack (1 : 10);
%!  s();
%!error<invalid indexing of stack>
%!  s = stack (1 : 10);
%!  s{5};

% Assigning to entries and ranges, including after the end.
%!test
%!  s = stack (1 : 3);
%!  s(2) = {"abc"};
%!  assert (s(:), {1; {"abc"}; 3});
%!  s(1 : 2) = {"abc"};
%!  assert (s(:), {"abc"; "abc"; 3});
%!  s(end : end + 2) = 42;
%!  assert (s(:), {"abc"; "abc"; 42; 42; 42});
%!
%!  s = stack ();
%!  s(10) = 1;
%!  assert (size (s), 10);
%!  assert (s(10), 1);
%!error<stack index out of bounds>
%!  s = stack ();
%!  s(0) = 5;
%!error<stack can only have one index>
%!  s = stack ();
%!  s(1, 2) = 5;
%!error<invalid indexing of stack>
%!  s = stack ();
%!  s{1} = 5;
%!error<must have the same size>
%!  s = stack ();
%!  s(1 : 5) = 1 : 6;
%!error<invalid stack assignment right-hand side>
%!  s = stack ();
%!  s(1 : 5) = rand (2, 2);

% Tests for reserve and the expected reserving in general.
%!test
%!  minSize = 16;
%!  sizingFactor = 2;
%!
%!  s = stack (42);
%!  [a, b] = size (s);
%!  assert ([a, b], [1, minSize]);
%!
%!  s(minSize) = 5;
%!  [a, b] = size (s);
%!  assert ([a, b], [minSize, minSize]);
%!
%!  push (s, 1);
%!  [a, b] = size (s);
%!  assert ([a, b], [minSize+1, sizingFactor*minSize]);
%!
%!  s(:) = 1 : 5;
%!  [a, b] = size (s);
%!  assert ([a, b], [5, minSize]);
%!
%!  reserve (s, 3);
%!  assert (s(:), {1; 2; 3; 4; 5});
%!  [a, b] = size (s);
%!  assert ([a, b], [5, minSize]);
%!
%!  reserve (s, 3, true);
%!  assert (s(:), {1; 2; 3; 4; 5});
%!  [a, b] = size (s);
%!  assert ([a, b], [5, 5]);
%!
%!  reserve (s, 100);
%!  assert (s(:), {1; 2; 3; 4; 5});
%!  [a, b] = size (s);
%!  assert ([a, b], [5, 100]);