class GBN_HEAP [ G->COMPARABLE ]
	-- Keys are stored in objects of type GBN_HEAP_PLACE.
	-- This allows keys to be accessed directly
	-- through their place.  Indexes into the data array,
	-- which are changeable, are kept private.

creation
  make, build_heap

feature

count : INTEGER

is_empty : BOOLEAN is
  do
    Result := count = 0
  end

min : G is
  require
    nonempty : not is_empty
  do
    Result := data . item (1) . key
  end

has_place ( p : GBN_HEAP_PLACE [G] ) : BOOLEAN is
  local
    i : INTEGER
  do
    if p /= void then
      i := p . index
      Result :=
        i >= 1 and then
        i <= count and then
        data . item ( i ) = p
    end
  end

delete_min is
  require
    nonempty : not is_empty
  local
    p : GBN_HEAP_PLACE [G]
  do
    p := data . item ( 1 )
    data . put ( data . item ( count ), 1 )
    data . item (1) . set_index (1)
    count := count - 1
    sift_down ( 1 )
    p . set_index ( -1 )
  ensure
    one_gone : count = old count - 1
  end

remove ( p : GBN_HEAP_PLACE [G] ) is
  require
    has_place : has_place ( p )
  local
    i : INTEGER
  do
    i := p . index
    data . put ( data . item ( count ), i )
    data . item ( i ) . set_index ( i )
    count := count - 1
    if  i > 1 and then 
        data . item ( i ) . key
    	  < data . item ( i // 2 ) . key
    then
      sift_up ( i )
    else
      sift_down ( i )
    end
    p . set_index ( -1 )
  ensure
    p_gone : not has_place ( p )
    reduced : count = old count - 1
  end

add ( k : G; stored_at : GBN_BOX [ GBN_HEAP_PLACE [G] ] ) is
  local
    p : GBN_HEAP_PLACE [G]
  do
    !! p . make ( k )
    count := count + 1
    p . set_index ( count )
    data . force ( p , count )
    sift_up ( count )
    if stored_at /= Void then
      stored_at . put ( p )
    end
  ensure
    enlarged : count = old count + 1
    returned : stored_at /= Void implies not stored_at . is_empty
  end

feature { NONE }

make is
  do
    !! data . make ( 1, 1000 )
  end

build_heap ( keys : ARRAY [ G ] ) is
  local
    p : GBN_HEAP_PLACE [G]
    i : INTEGER
  do
    count := 1 + keys.upper - keys.lower
    !! data . make ( 1, count )
    from
      i := 1
    until
      i > count
    loop
      !! p . make ( keys.item (i) )
      data . put ( p , i )
      p . set_index ( i )
      i := i + 1
    end

    from
      i := count // 2
    until
      i = 0
    loop
      sift_down ( i )
      i := i - 1
    end
  end

data : ARRAY [ GBN_HEAP_PLACE [G] ]

sift_up ( i : INTEGER ) is
  local
    j, k : INTEGER
    temp : GBN_HEAP_PLACE [G]
  do
    from
      k := i
      temp := data . item ( i )
    until
      k = 0
    loop
      j := k // 2
      if j = 0 or else
         data . item ( j ) . key <=
	 temp . key
      then
        data . put ( temp, k )
	temp . set_index ( k )
	k := 0
      else
        data . put ( data . item ( j ), k )
	data . item ( k ) . set_index ( k )
	k := j
      end
    end
  end

sift_down ( i : INTEGER ) is
  local
    j, k : INTEGER
    temp : GBN_HEAP_PLACE [G]
  do 
    from
      j := i
      temp := data . item ( i )
    until
      j > count
    loop
      k := 2 * j
      if k < count and then
         data . item ( k + 1 ) . key
	 < data . item ( k ) . key
      then
        k := k + 1
      end

      if k > count or else
         data . item ( k ) . key
	   >= temp . key
      then
        data . put ( temp, j )
	temp . set_index ( j )
	j := count + 1
      else
        data . put ( data . item ( k ) , j )
	data . item ( j ) . set_index ( j )
	j := k
      end
    end
  end

end -- class GBN_HEAP