-- Ada implementation of red-black trees as described in
--   Alternatives to Two Classic Data Structures
--   Chris Okasaki
--   SIGCSE 2005
--
-- Implements a set of integers.  Can easily be adapted to other
-- key types, or to other abstractions such as bags/dictionaries/etc.

PACKAGE Red_Black IS

   TYPE Set_Type IS PRIVATE;

   PROCEDURE Insert(Key : Integer; Set : IN OUT Set_Type);
   FUNCTION Member(Key : Integer; Set : Set_Type) RETURN Boolean;
   
PRIVATE

   TYPE Color_Type IS (Red, Black);

   TYPE Tree_Node;
   TYPE Tree_Ptr IS ACCESS Tree_Node;
   TYPE Tree_Node IS RECORD
      Key : Integer;
      Color : Color_Type;
      Left, Right : Tree_Ptr;
   END RECORD;

   TYPE Set_Type IS RECORD
      Root : Tree_Ptr := null;
   END RECORD;

END Red_Black;