(*

  BTS: bubble top stack

  if you push an element onto the stack, and the element is already
  in the stack, that element "bubbles" to the top of the stack

*)

datatype BTS = 
   New  
   | push of BTS * int ;

fun mem (New,i) = false
  | mem (push(B,i),j) = if i=j
                        then true
                        else mem(B,j) ;

fun size (New) = 0
  | size (push(B,i)) = if mem(B,i)
                        then size(B)
                        else size(B)+1 ;

exception topEmptyStack;

fun top (New) = raise topEmptyStack 
  | top (push(B,i)) = i ;

fun pop (New) = New
  | pop (push(B,i)) = if not(mem(B,i))
                       then B
                       else if top(B)=i 
                             then pop(B)
                             else push( pop( push(pop(B),i) ), top(B) ) ;

fun empty (New) = true
  | empty (B) = size(B)=0 ;


val b1 = push(New,1);
val b2 = push(b1,2);
val b3 = push(b2,2);
val b4 = push(b3,2);
val b5 = push(b4,2);
val b6 = push(b5,2);

val s1 = push(push(push(pop(push(b6,100)),41),31),21) ;