Re: Neat and tidy solution to following problem?

["Robert I. Eachus" <rieachus@attbi.com>]

chris.danx wrote:

  
> In this case the length of the strings per line in the file is left
> unspecified, and also the size of the document.  If it's large then there'd
> probably be a problem with a recursive solution unless the recursion
> operates in more or less constant space (can't remember what this is called,
> but iirc it's doable for a variety of problems).


Actually, in this case there is an extremely elegant Ada pattern that 
works for general problems of this type. And I assume that anyone who 
had this as a homework assignment has turned it in.

For example, in KWIC (key word in context) indexing programs, you want 
to find all instances of every token without "losing" the context, so an 
index into the original source is a very useful representation.

You want to create a data structure Token_List of the form:

type Token is record First, Last: Natural; end record;
type Token_Array is array (Integer range <>) of Token;
type Token_List(Length: Integer) is record
   Source: Ada.Strings.Unbounded.Unbounded_String;
   Tokens: Token_Array(1..Length);
end record;

And have a function which returns one object of the type properly 
populated.  Notice that there is no default for the Index, so this is 
not what Alsys called a mutable object.  Also if you felt like it, you 
could replace the Unbounded_String by a String, with another discriminant.

The code looks like this.  I have dressed it up as a generic only as a 
way of leaving the procedure Next_Token undefined.

generic
   Input: String;
   with procedure Next_Token(Start: in Integer;
                             Found: out Boolean;
                             First_Position, Last_Position: out Integer);
function Find_Tokens return Token_List;

function Find_Tokens return Token_List is
   type Token_List_Access is access all Token_List;
   TLA: Token_List_Access;

   procedure Recur(Starting_Place, Index: in Natural) is
     More: Boolean;
     First, Last: Natural;
   begin
     Next_Token(Starting_Place, More, First, Last);
     if More
     then
       Recur(Last+1, Index+1);
       TLA.Tokens(Index).First := First;
       TLA.Tokens(Index).Last := Last;
     else
       TLA := new Token_List(Index - 1);
       TLA.Source := Ada.Strings.Unbounded.To_Unbounded_String(Input);
     end if;
    end Recur;

  begin Recur(1,1); return TLA.all; end Find_Tokens;

This code compiles, if it is suitably packaged. Of course proper 
functioning depends on the definition of Next_Token, and whether it 
meets your definition of proper functioning. Notice that the scope of 
the access type is left when you return from Find_Tokens, so there is no 
question of storage leaks, and only one object of the type is created 
anyway...