home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / sa104os2.zip / SATHR104.ZIP / SATHER / LIBRARY / FLIST.SA < prev    next >
Text File  |  1995-02-05  |  11KB  |  269 lines
  1. -- Copyright (C) International Computer Science Institute, 1994.  COPYRIGHT  --
  2. -- NOTICE: This code is provided "AS IS" WITHOUT ANY WARRANTY and is subject --
  3. -- to the terms of the SATHER LIBRARY GENERAL PUBLIC LICENSE contained in    --
  4. -- the file "Doc/License" of the Sather distribution.  The license is also   --
  5. -- available from ICSI, 1947 Center St., Suite 600, Berkeley CA 94704, USA.  --
  6. --------> Please email comments to "sather-bugs@icsi.berkeley.edu". <----------
  7.  
  8. -- flist.sa: Array-based lists of elements of type T.
  9. -------------------------------------------------------------------
  10. class FLIST{T} is
  11.    -- Array-based lists of elements of type T.
  12.    -- These are extensible stacks based on amortized doubling.
  13.    -- They may often be used as replacements for linked lists.
  14.    -- Like linked lists (which are widely used as containers in
  15.    -- languages like Lisp), they serve as general container
  16.    -- objects for holding collections of other objects. They are
  17.    -- often a more efficient abstraction, however, because less
  18.    -- allocation and deallocation must occur, because they keep
  19.    -- successive elements in successive memory locations, because
  20.    -- they don't require storage for the links in a linked list,
  21.    -- and they support efficient access by array index.  Linked
  22.    -- lists also support insertion and deletion into the middle
  23.    -- of the list. A variant of FLIST{T} named GLIST{T} will often
  24.    -- be useful in applications which require these operations. 
  25.    -- AQUEUE{T} is a similar structure supporting queue ops. The
  26.    -- set operations `union', `intersection', `difference', and
  27.    -- `sym_difference' and the searching operation `index_of' are
  28.    -- implemented by brute force search. If extensive use is made
  29.    -- of these operations, one should consider the use of other
  30.    -- data structures such as BITVEC or FSET{T}.
  31.  
  32.    private include AREF{T} aget->private aref_aget, 
  33.       aset->private aref_aset;    -- Storage for the stack elements.
  34.  
  35.    private attr loc:INT;    -- The index to insert the next element.
  36.  
  37.    elt_eq(e1,e2:T):BOOL is
  38.       -- The test for element equality used by the following routines.
  39.       -- Uses object equality by default. May be redefined in descendants.
  40.       typecase e1
  41.       when $IS_EQ{T} then return e1.is_eq(e2)
  42. --    else return SYS::ob_eq(e1,e2) end end;                                    -- NLP
  43.       else; end; return SYS::ob_eq(e1,e2); end;                                 -- NLP
  44.  
  45.    invariant:BOOL is        
  46.       -- Illegal state if false.
  47.       if void(self) then return true end;
  48.       return loc.is_bet(0,asize) and asize>0 end;
  49.    
  50.    size:INT is
  51.       -- The current size. Self may be void.
  52. --    if void(self) then return 0 else return loc end end;                      -- NLP
  53.       if void(self) then return 0; end; return loc; end;                        -- NLP
  54.    
  55.    create:SAME is return void; end;
  56.  
  57.    create(n:INT):SAME
  58.       -- A new empty FLIST capable of storing `n' elements without extra
  59.       -- space allocation.
  60.       pre n>=1 is 
  61.       return new(n) end;
  62.  
  63.    copy:SAME is
  64.       -- A copy of self.
  65.       if void(self) then return void end;
  66.       r::=new(asize); loop r:=r.push(elt!) end; return r end;
  67.    
  68.    aget(ind:INT):T            
  69.       -- The element of self with index `ind'. Self may not be void.
  70.       pre ~void(self) and ind.is_bet(0,loc-1) is
  71.       return aref_aget(ind) end;
  72.  
  73.    aset(ind:INT,val:T)
  74.       -- Set the element of self with index `ind' to `val'. Self may
  75.       -- not be void. 
  76.       pre ~void(self) and ind.is_bet(0,loc-1) is 
  77.       aref_aset(ind,val) end;
  78.    
  79.    push(e:T):SAME is
  80.       -- Add a new element to the end of the list and return the list.
  81.       -- If self is void, create a new list. Usage: `l:=l.push(e)'.
  82.       r:SAME;
  83.       if void(self) then r:=new(5)
  84.       elsif loc<asize then r:=self
  85.       else r:=new(2*asize); r.loc:=loc; 
  86.      loop r.aset!(elt!) end;
  87.      clear; end;
  88.       r.loc:=r.loc+1; r[r.loc-1]:=e; return r end;
  89.  
  90.    pop:T is
  91.       -- Return the top element and shrink the list.
  92.       -- Void if the list is empty or void.
  93.       if size=0 then return void end;
  94.       r::=[loc-1]; [loc-1]:=void; loc:=loc-1; return r end;
  95.  
  96.    top:T is
  97.       -- The value of the top of the list.
  98.       -- Void if the list is empty or void.
  99.       if size=0 then return void end;      
  100.       return [loc-1] end;
  101.  
  102.    is_eq(l:SAME):BOOL is
  103.       -- True if self and `l' have the same number of elements and each
  104.       -- element of self is equal to the corresponding element of `l'.
  105.       -- Self may be void.
  106.       if void(self) then return l.size=0
  107.       elsif void(l) then return loc=0
  108.       elsif loc/=l.loc then return false
  109.       else
  110.      loop if ~elt_eq(elt!,l.elt!) then return false end end end;
  111.       return true end;
  112.    
  113.    is_empty:BOOL is    
  114.       -- True if the list is empty or void.
  115.       return size=0 end;
  116.  
  117.    clear is            
  118.       -- Clear the list. Self may be void.
  119.       if is_empty then return else aclear; loc:=0 end end;
  120.    
  121.    array:ARRAY{T} is        
  122.       -- An array containing the elements of self. Void if self is void.
  123.       if void(self) then return void end;
  124.       r::=#ARRAY{T}(loc); 
  125.       loop r.set!(elt!) end; return r end;
  126.    
  127.    elt!:T is
  128.       -- Yield the elements of self in order. Self may be void.
  129.       -- Don't insert elements while calling this.
  130.       if ~void(self) then 
  131.      loop yield aelt!(0,loc) end end end;
  132.  
  133.    elt!(beg:INT):T
  134.       -- Yield the elements of self starting at `beg'.
  135.       -- Don't insert elements while calling this.   
  136.       pre ~void(self) and beg.is_bet(0,loc-1) is
  137.       loop yield aelt!(beg,loc-beg) end end;     
  138.    
  139.    elt!(beg, num:INT):T
  140.       -- Yield `num' successive elements starting at index `beg'.
  141.       -- Don't insert elements while calling this.      
  142.       pre ~void(self) and beg.is_bet(0,loc-1) and 
  143.          num.is_bet(0,loc-beg) is
  144.       loop yield aelt!(beg,num) end end;
  145.  
  146.    private is_legal_elts_arg(beg,num,step:INT):BOOL is
  147.       -- True if the arguments are legal values for `elts'.
  148.       if ~beg.is_bet(0,loc-1) then return false end;
  149.       if step>0 then return num.is_bet(0,(loc-beg+step-1)/step);
  150.       elsif step<0 then return num.is_bet(0,(beg-step)/-step);
  151. --    else return false end end;                                                -- NLP
  152.       end; return false; end;                                                   -- NLP
  153.    
  154.    elt!(beg, num, step:INT):T
  155.       -- Yield `num' elements starting at `beg' stepping by `step'.
  156.       pre ~void(self) and is_legal_elts_arg(beg,num,step) is
  157.       loop yield aelt!(beg,num,step) end end;
  158.    
  159.    ind!:INT is        
  160.       -- Yield the indices of the list. Self may be void.
  161.       if ~void(self) then      
  162.      loop yield 0.upto!(loc-1) end end end;
  163.    
  164.    index_of(e:T):INT is
  165.       -- The list index of `e'. -1 if the list is void or the
  166.       -- element is not present (not fast). Consider using FSET{T}.
  167.       if ~void(self) then
  168.      loop r::=ind!; if elt_eq(e,[r]) then return r end end end;
  169.       return -1 end;   
  170.  
  171.    contains(e:T):BOOL is
  172.       -- True if `e' is contained in self.
  173.       loop if elt_eq(e,elt!) then return true end end;
  174.       return false end;
  175.    
  176.    push_if_new(e:T):SAME is
  177.       -- Push `e' if it is not already present in the list.
  178.       -- Self may be void. 
  179.       -- Usage is: `l:=l.push_if_new(e)'. Consider using FSET{T}.
  180. --    if contains(e) then return self else return push(e) end end;              -- NLP
  181.       if contains(e) then return self; end; return push(e); end;                -- NLP
  182.  
  183.    append(l:SAME):SAME 
  184.       -- Append `l' to the end of self and return the result.
  185.       -- Self may be void. `l' mustn't equal self unless void.
  186.       pre ~SYS::ob_eq(l,self) or void(self) is 
  187.       r::=copy; loop r:=r.push(l.elt!) end; return r end;
  188.  
  189.    concat(l:SAME):SAME
  190.       -- Append 'l' destructively.  'l' mustn't equal self
  191.       -- unless void.
  192.       pre ~SYS::ob_eq(l,self) or void(self) is
  193.       res::=self;
  194.       if ~void(l) then loop res:=res.push(l.elt!) end end;
  195.       return (res);
  196.    end;
  197.  
  198.    union(l:SAME):SAME is
  199.       -- A new list containing the elements in self unioned with
  200.       -- those in `l'. Doesn't modify self or `l'. Self may be void.
  201.       -- Consider using FSET{T} for better performance.
  202.       r::=copy; loop r:=r.push_if_new(l.elt!) end; return r end;
  203.    
  204.    intersect(l:SAME):SAME is
  205.       -- A new list containing the elements in both self and `l'.
  206.       -- Doesn't modify self or `l'. Consider FSET{T} for better 
  207.       -- performance. Self may be void.
  208.       r:SAME;
  209.       loop e::=elt!; if l.contains(e) then r:=r.push(e) end end;
  210.       return r end;
  211.    
  212.    difference(l:SAME):SAME is
  213.       -- A new list containing the elements of self not in `l'.
  214.       -- Doesn't modify self or `l'. Consider FSET{T} for better
  215.       -- performance. Self may be void.
  216.       r:SAME;
  217.       loop e::=elt!; if ~l.contains(e) then r:=r.push(e) end end;
  218.       return r end;
  219.  
  220.    sym_difference(l:SAME):SAME is
  221.       -- A new list containing the elements in self or `l' but
  222.       -- not both. Doesn't modify self or `l'. Consider FSET{T} for
  223.       -- better performance. Self may be void.
  224.       r:SAME; 
  225.       loop e::=elt!; if ~l.contains(e) then r:=r.push(e) end end;
  226.       loop e::=l.elt!; if ~contains(e) then r:=r.push(e) end end;
  227.       return r end;
  228.  
  229.    sublist(beg,num:INT):SAME 
  230.       -- A new list with `num' entries copied from self starting
  231.       -- at `beg'. Self may not be void.
  232.       pre ~void(self) and
  233.          beg.is_bet(0,loc-1) and num.is_bet(0,loc-beg) is
  234.       r::=new(num+5); r.loc:=num; r.acopy(0,num,beg,self); return r end;
  235.  
  236.    to_reverse is
  237.       -- Reverse the order of the elements in self. Self may be void.
  238.       if void(self) then return end;
  239.       loop i::=(loc/2).times!; 
  240.      u::=loc-i-1; t::=[i]; [i]:=[u]; [u]:=t end end; 
  241.    
  242.    delete(ind:INT) 
  243.       -- Delete the element with index `ind' and move the last element
  244.       -- in its place. Self may not be void.
  245.       pre ~void(self) and ind.is_bet(0,loc-1) is
  246.       loc:=loc-1; [ind]:=[loc]; v:T; [loc]:=v end;
  247.  
  248.    map(map:FMAP{T,T}):SAME is
  249.       -- If an element of self is a key in FMAP
  250.       -- it is replaced with the corresponding
  251.       -- target. Self may be void.
  252.       if void(self) then
  253.          return void;
  254. --    else                                                                      -- NLP
  255.       end;                                                                      -- NLP
  256.          res::=copy;
  257.          loop
  258.             i::=0.upto!(loc-1);
  259.             if map.test(res[i]) then
  260.                res[i]:=map.get(res[i]);
  261.             end;
  262.          end;
  263. --       return res end end;                                                    -- NLP
  264.          return res; end;                                                       -- NLP
  265.  
  266. end; -- class FLIST{T}
  267.  
  268. -------------------------------------------------------------------
  269.