signature UpperFlexARRAY =
sig
  type 'a t 
  exception Subscript
  val empty: 'a t
  val null: 'a t -> bool
  val length: 'a t -> int
  val lookup: 'a t * int -> 'a
  val update: 'a t * int * 'a -> 'a t
  val shrink: 'a t -> 'a t
end ;

structure TreeArrayMod =
struct
  abstype 'a t = O | V of 'a * 'a t * 'a t with

  exception Subscript ;

  val empty = O ;

  fun null O = true
    | null _ = false ;

  fun lookup( V(v,tl,tr) , k )
        = if k = 1 then v 
          else if k mod 2 = 0 
               then lookup( tl , k div 2 )
               else lookup( tr , k div 2 ) 
    | lookup( O , _ )   
        = raise Subscript ;

  fun update( O , k , v ) 
        = if k = 1 then ( V(v,O,O) , 1 )
          else raise Subscript 
    | update( V(x,tl,tr) , k , v )
        = if k = 1 then ( V(v,tl,tr) , 0 )
          else if k mod 2 = 0 
               then let 
                 val (t,i) 
                   = update(tl,k div 2,v) 
               in  ( V(x,t,tr) , i )  end 
               else let 
                 val (t,i) 
                   = update(tr,k div 2,v) 
               in  ( V(x,tl,t) , i )  end ;

  fun delete( O , n ) 
    = raise Subscript
    | delete( V(v,tl,tr) , n )
      = if n = 1 then O
        else if n mod 2 = 0
             then V( v , delete(tl,n div 2) , tr )
             else V( v , tl , delete(tr,n div 2) ) ;
  end ;
end ;  

structure TreeArray : UpperFlexARRAY =
struct
  abstype 'a t = A of int * 'a TreeArrayMod.t with

  exception Subscript ;

  val empty = A( 0 , TreeArrayMod.empty ) ;

  fun null( A(l,_) ) = l = 0 ;

  fun length( A(l,_) ) = l ;

  fun lookup( A(l,t) , k ) 
    = if l = 0 orelse ( k < 1 andalso k > l )
      then raise Subscript
      else TreeArrayMod.lookup(t,k) ;
       
  fun update( A(l,t) , k , v )
    = if 1 <= k andalso k <= l+1
      then let 
             val (u,i) = TreeArrayMod.update( t , k , v ) 
           in 
             A( l+i , u ) 
           end 
      else raise Subscript ;

  fun shrink( A(l,t) ) 
    = if l = 0 then empty
      else A( l-1 , TreeArrayMod.delete(t,l) ) ;

  end ;
end ;

open TreeArray;

val a1 = update(update(update(empty,1,10),2,20),1,30) ;
length a1 ;
lookup(a1,1) ;
lookup(a1,2) ;

val a2 = update(a1,3,40);
length a2 ;
val a3 = update(update(a2,3,50),2,200);
length a3 ;
lookup(a3,1) ;
lookup(a3,2) ;