Thursday 4 May 2017

NoITAB – A Stack

Internal Tables


ABAP’s internal tables are dynamic data objects that allow to process large quantities of data with the same structure, thereby taking care of dynamic memory management. So they are good at storing database table data and this makes them ubiquitous.

There seems to be no alternative. Complex data structure are usually mapped to internal table to avoid additional effort to implement a special data structure that will probably have poor performance anyway.

But I see a problem here: efficient algorithms often use a dedicated data structure that helps describe design concepts in simple but correct language. Without alternative, the communication and the design discussion suffer. Expressing a problem in a well understood data structure would help reduce the intellectual challenge of programming.

With this in mind, my aim is to showcase ABAP solutions that do not rely on internal tables. Given a problem to solve, the game will be to look beyond the obvious internal table structure, going back to the basics if needed, and find a design that works and is worth the additional effort.

I call this effort NoITAB, pronounced not only internal tables, as in NoSQL that is not only SQL.

A Stack


A stack is an abstract data type providing access to a Last In First Out collection using 2 operations, PUSH( ) and POP( ).

SAP ABAP Tutorials, SAP ABAP Guide, SAP ABAP Certifications

You will use a stack (or recursion) to fill a tree-like data structure like the ABAP tree view control. In ABAP, prefer a custom stack because the call stack implicitly used by recursion is more limited than the heap.

A stack is really not difficult to implement. Not at all. The enjoy transactions for purchasing documents (ME53N, ME23N and others) manage screens and subscreens using a stack in include LMEVIEWSF01:

FORM push_call_view.
  APPEND call_view TO call_view_stack.
ENDFORM.

FORM pop_call_view.
  IF NOT call_view_stack[] IS INITIAL.
    DATA: last TYPE sy-tabix.
    DESCRIBE TABLE call_view_stack LINES last.
    READ TABLE call_view_stack INTO call_view INDEX last.
    DELETE call_view_stack INDEX last.
  ENDIF.
ENDFORM.
  • The PUSH( ) operation is translated to an APPEND to add a view at the end of the internal table.
  • The POP( ) operation reads the last entry in the internal table and then delete this entry from the table.

If you feel like me, that the POP( ) implementation is not expressing its intent naturally in terms of internal table operations. That may tempt you to strike a new path and DIY – A NoITAB stack implementation using a linked list where we only insert and delete at the top:

DEFINE new_stack.
CLASS &1 DEFINITION.
  PUBLIC SECTION.
    METHODS push IMPORTING iv_key TYPE &2.
    METHODS pop RETURNING VALUE(rv_key) TYPE &2.
    METHODS empty RETURNING VALUE(rv_flag) TYPE xsdboolean.
  PROTECTED SECTION.
    TYPES: BEGIN OF ts_node,
             key  TYPE &2,
             next TYPE REF TO data,
           END OF ts_node.

    DATA mr_top TYPE REF TO ts_node.
ENDCLASS.

CLASS &1 IMPLEMENTATION.

  METHOD push.
    mr_top = NEW ts_node( key = iv_key
                          next = mr_top ).
  ENDMETHOD.

  METHOD pop.
    CLEAR rv_key.
    CHECK empty( ) EQ abap_false.
    rv_key = mr_top->key.
    mr_top ?= mr_top->next.
  ENDMETHOD.

  METHOD empty.
    rv_flag = xsdbool( mr_top IS NOT BOUND ).
  ENDMETHOD.

ENDCLASS.
END-OF-DEFINITION.

  • Is it easy to use?


The generic implementation as a macro makes it flexible and lightweight. Parameter &2 in the macro defines the type of the elements in the stack. With this, I can create a stack of any type, i.e. a stack of strings:

new_stack lcl_stack_string string.

START-OF-SELECTION.
  WRITE: / 'Stack of strings'. 
  DATA(lo_stack2) = NEW lcl_stack_string( ).
  lo_stack2->push( `Hello World` ).  
  WRITE: lo_stack2->pop( ), 
         lo_stack2->pop( ).

  • Does this scale?


The implementation has fixed costs for PUSH( ) and POP( ) operation no matter the number of elements in the stack, i.e. in theory the best possible behavior. The only issue I could think of is the garbage collector that would kick off at unexpected times to reclaim freed memory, which could hurt performance.

I have used this stack often and never bother to measure performance. If you do, please report here.

Outlook


There is nothing wrong with internal table, but in some cases, we know about better data structures for our collection of data. The simplest case is a stack, where a linked list implementation is efficient and easy to use.

Compared to an internal table, a custom linked list is efficient when we only insert/delete at the beginning or at the end of the list. A custom dynamic array can be efficient if it is fixed-sized, so we can use the ASSIGN with INCREMENT and RANGE command (or the obsolete DO VARYING / WHILE VARY commands) for random access.

Trying to generalize, we could provide functional interfaces to more abstract data types. I like to use an internal table base iterator object to handle the selected entries of an ALV Grid. The benefit here is not performance, but abstraction (Not Only ITAB). I have proposed the same approach for a priority queue.

No comments:

Post a Comment