space system
{
   class tree
   {
       header
       nodes
       iterator
       datatype

       tree()
       {
          header = node()
          nodes = 0
       }

       left_most
       {
           get
           {
               return header.left
           }
           set
           {
               header.left = value
           }
       }

       right_most
       {
           get
           {
               return header.right
           }
           set
           {
               header.right = value
           }
       }

      root
      {
           get
           {
               return header.parent
           }
           set
           {
               header.parent = value
           }
       }

       empty
       {
           get
           {
               return nodes == 0
           }
       }


       iterate() { iterator = header  }

       next() {iterator = iterator.next() return iterator.halt }

       begin { get { return header.left } }

       end { get { return header } }

       validate()
       {
           if header.parent.null()
           {
               if header.left != header  throw "invalid header node" 
               if header.right != header  throw "invalid header node"
           }

           validate(header.parent)
      }

      validate(n)
      {
          if n.null() return null

          if !n.left.null()
          {
              left = n.left

              if ! (left.data < n.data)
                  throw "out of key order at " + (string)left.data + " and " + (string)n.data

              if left.parent != n
                 throw "invalid parent for " +  (string)left.data

              validate(n.left)
          }

          if !n.right.null()
          {
              right = n.right

              if right.data < n.data
                  throw "out of key order"  + (string)right.data + " and " + (string)n.data

              if right.parent != n
                 throw "invalid parent for " +  (string)right.data

              validate(n.right)
          }

          depth_left = 0
          if !n.left.null() depth_left = n.left.depth

          depth_right = 0
          if !n.right.null() depth_right = n.right.depth

          if depth_left > depth_right
          {
               if depth_left - depth_right > 2
                   throw "tree out of balance at " + (string)n.data + " depth left: " + (string)depth_left + " depth right: " + (string)depth_right
               if n.balance != state.left_high
                   throw "tree balance factor error at " + (string)n.data + " depth left: " + (string)depth_left + " depth right: " + (string)depth_right + " balance factor " + n.balance
          }
      
          if depth_left < depth_right
          {
              if depth_right - depth_left > 2
                  throw "tree out of balance at " + (string)n.data + " depth left: " + (string)depth_left + " depth right: " + (string)depth_right
              if n.balance != state.right_high
                   throw "tree balance factor error at " + (string)n.data + " depth left: " + (string)depth_left + " depth right: " + (string)depth_right + " balance factor " + n.balance
          }
        } 

       operator<<(data)
       {
           if header.parent.null()
           {
                root = node(header data)
                left_most = root
                right_most = root
                datatype = data.type()
                nodes++
            }
            else
            {
                n = root
 
                repeat
                {
                    less = data < n.data
                    greater = n.data < data
                    if less
                    {
                        if !n.left.null()
                            n = n.left
                        else
                        {
                          new_node = node(n data)
                          n.left = new_node
                          if left_most == n left_most = new_node
                          balance_tree(n direction.from_left)
                          nodes++
                          break    
                       } 
                   }
                   else if greater
                   {
                       if !n.right.null()
                           n = n.right
                       else
                       {
                          new_node = node(n data)
                          n.right = new_node
                          if right_most == n right_most = new_node
                          balance_tree(n direction.from_right)
                          nodes++ 
                          break      
                      }
                    }
                    else // item already exists
                    {
                        n.data = data
                        break
                    }
               }
           }

           return this
       }

       operator>>(data)
       {
           from = direction.from_left

           n = root

           repeat
           {
               if n.null() throw "entry " + (string)data + " not found"

               less = data < n.data
               greater = n.data < data

               if less
                   n = n.left
               else if greater
                   n = n.right
               else // item found
               {
                   if !n.left.null() && !n.right.null()
                   {
                      replace = n.left
                      while !replace.right.null() replace = replace.right
                      temp = n.data
                      n.data = replace.data
                      replace.data = temp
                      n = replace
                   }
                  
                   if left_most == n
                   {
                       next = n
                       next = next.next()
                       
                       if header == next
                       {
                           left_most = header
                           right_most = header
                       }
                       else
                           left_most = next
                   }
 
                   if right_most == n
                   {
                       previous = n
                       previous = previous.previous()
                    
                       if header == previous
                       {
                           left_most = header
                           right_most = header
                       }
                       else
                           right_most = previous
                   }

                   from = direction.from_left
                   if n.parent.left != n from = direction.from_right

                   if n.left.null()
                   {
                       if n.parent == header
                       {
                           root = n.right
                       }
                       else
                       {
                           if n.parent.left == n
                           {
                               n.parent.left = n.right
                           }
                           else
                           {
                               n.parent.right = n.right
                           }
                       }

                       if !n.right.null() n.right.parent = n.parent
                   }
                   else
                   {
                       if n.parent == header
                       {
                           root = n.left
                       }
                       else
                       {
                           if n.parent.left == n
                           {
                               n.parent.left = n.left
                           }
                           else
                           {
                               n.parent.right = n.left
                           }
                        }

                        if !n.left.null() n.left.parent = n.parent
                   }

                   balance_tree_remove(n.parent from)
                   break  
               }
           }
           nodes--
           return this
       }

        rotate_left(node)
        {
            parent = node.parent
            x = node.right

            node.parent = x
            x.parent = parent
            if !x.left.null() x.left.parent = node

            node.right = x.left
            x.left = node
           
            return  x
        }

        rotate_right(node)
        {
            parent = node.parent
            x = node.left

            node.parent = x
            x.parent = parent
            if !x.right.null() x.right.parent = node

            node.left = x.right
            x.right = node

            return  x
        }
        
        balance_left(node)
        {
            left = node.left

            select left.balance
            {
                left_high
                {
                    node.balance = state.balanced
                    left.balance = state.balanced
                    return rotate_right(node)
                }
    
                right_high
                {
                    subright = left.right
                    select subright.balance
                    {
                       balanced
                       {
                           node.balance = state.balanced

                           left.balance = state.balanced
                       }

                       right_high
                       {
                           node.balance = state.balanced
                           left.balance = state.left_high
                       }

                       left_high
                       {
                           node.balance = state.right_high
                           left.balance = state.balanced
                       }
                   }
                   subright.balance = state.balanced
                   left = rotate_left(left)
                   node.left = left
                   return rotate_right(node)
              }
      
                balanced
                {
                   node.balance = state.left_high
                   left.balance = state.right_high
                   return rotate_right(node)
                }
            }
            
            return node
        }

        balance_right(node)
        {
            right = node.right

            select right.balance
            {
                right_high
                {
                    node.balance = state.balanced
                    right.balance = state.balanced
                    node = rotate_left(node)
                }

                left_high
                {
                   subleft = right.left // left Subtree of right
                   select subleft.balance
                   {
                       balanced
                       {
                           node.balance = state.balanced
                           right.balance = state.balanced
                       }

                       left_high
                       {
                           node.balance = state.balanced
                           right.balance = state.right_high
                       }

                       right_high
                       {
                         node.balance = state.left_high
                         right.balance = state.balanced
 
                        }
                    
                  }
                  subleft.balance = state.balanced
                  right = rotate_right(right)
                  node.right = right
                  node = rotate_left(node)
             }
            
             balanced
             {
                    node.balance = state.right_high
                    right.balance = state.left_high
                    node = rotate_left(node)
             }
           }
         
           return node
        }

        balance_tree(node from)
        {
            taller = true

            while taller
            {
                parent = node.parent

                if parent.left == node
                    next_from = direction.from_left
                else
                    next_from =  direction.from_right

                if from == direction.from_left
                {
                    select node.balance
                    {
                        left_high
                        {
                            if parent.is_header
                                parent.parent = balance_left(parent.parent)
                            else if parent.left == node
                                parent.left = balance_left(parent.left)
                            else
                                parent.right = balance_left(parent.right)
                            taller = false
                        }
       
                        balanced
                        {
                            node.balance = state.left_high
                            taller = true
                        }

                        right_high
                        {
                            node.balance = state.balanced
                            taller = false
                        }
                    }
                }
                else
                {
                   select node.balance
                    {
                        left_high
                        {
                            node.balance = state.balanced
                            taller = false
                        }

                        balanced
                        {
                            node.balance = state.right_high
                            taller = true
                        }

                        right_high
                        {
                            if parent.is_header
                                parent.parent = balance_right(parent.parent)
                            else if (parent.left == node)
                                parent.left = balance_right(parent.left)
                            else
                                parent.right = balance_right(parent.right)
                            taller = false
                        }
                    }
                }

                if taller // skip up a level
                {
                    if node.parent.is_header
                        taller = false
                    else
                    {
                        node = parent
                        from = next_from
                    }
                }
            }
        }    
        
        balance_tree_remove(node from)
        {
            if node.is_header return null

            shorter = true

            while shorter
            {
                parent = node.parent
                if parent.left == node next_from = direction.from_left else next_from = direction.from_right

                if from == direction.from_left
                {
                    select node.balance
                    {
                        left_high
                        {
                            node.balance = state.balanced
                            shorter = true
                        }

                        balanced
                        {
                            node.balance = state.right_high
                            shorter = false
                        }

                        right_high
                        {
                            if node.right.balance == state.balanced
                                shorter = false
                            else
                                shorter = true
                            if parent.is_header
                                parent.parent = balance_right(parent.parent)
                            else if (parent.left == node)
                                parent.left = balance_right(parent.left)
                            else
                                parent.right = balance_right(parent.right)
                        }
                    }
                }
                else
                {
                    select node.balance
                    {
                        right_high
                        {
                            node.balance = state.balanced
                            shorter = true
                        }

                        balanced
                        {
                            node.balance = state.left_high
                            shorter = false
                        }

                        left_high
                        {
                            if node.left.balance == state.balanced
                                shorter = false
                            else
                                shorter = true
                            if parent.is_header
                                parent.parent = balance_left(parent.parent)
                            else if parent.left == node
                                parent.left = balance_left(parent.left)
                            else
                                parent.right = balance_left(parent.right)
                         }
                    }
                }

                if shorter
                {
                    if node.parent.is_header
                        shorter = false
                    else
                    {
                        from = next_from
                        node = parent
                    }
                }
            }
        }

       operator[key]
       {
           get
           {
               if empty
                  throw "entry not found exception"
               else
               {
                   n = root
 
                   repeat
                   {
                       if key < n.data
                       {
                           if !n.left.null()
                               n = n.left
                           else
                               throw "entry not found exception"
                       } 
                       else
                       {
                           if key == n.data
                               return n.data
                           else
                           {
                               if !n.right.null()
                                   n = n.right
                               else
                                   throw "entry not found exception"
                           }
                       }
                   }
               }
           }   
       }

       contains(data)
       {
           if empty
           {
               return false
           }
           else
           {
               n = root
 
               repeat
               {
                   less = data < n.data
                   greater = n.data < data

                   if less
                   {
                       if !n.left.null()
                           n = n.left
                       else
                           return false
                   }
                   else if greater
                   {
                      if !n.right.null()
                         n = n.right
                      else
                         return false
                   }
                   else // item exists
                      return true
               }
           }
       }

       get(data)
       {
           if empty throw "empty collection"

           n = root
 
           repeat
           {
               less = data < n.data
               greater = n.data < data
               if less
               {
                  if !n.left.null()
                     n = n.left
                  else
                     throw "item: " + (string)data + " not found in collection"
               }
               else if greater
               {
                   if !n.right.null()
                       n = n.right
                    else
                      throw "item: " + (string)data + " not found in collection"
               }
               else // item exists
                   return n.data
            }
       }

       last
       {
           get
           {
               if empty
                  throw "empty set"
               else
                  return header.right.data
           }
       }

       count
       {
           get
           {
               return nodes
           }
       }

       depth
       {
          get
          {
             return root.depth
          }
       }

       operator==(compare)
       {
          if this < compare return false
          if compare < this return false
          return true
       }

       operator!=(compare)
       {
           if this < compare return true
           if compare < this return true
           return false
       }  

        operator<(c)
        {
         first1 = begin
         last1 = end
         first2 = c.begin
         last2 = c.end

         while first1 != last1 && first2 != last2
         {
           less = first1.data < first2.data
            if !less
            {
                first1 = first1.next()
                first2 = first2.next()
            }
            else return true
         }
         a = count
         b = c.count
         return a < b
      }

      operator string()
      {
          out = "{"
          first1 = begin
          last1 = end
          while first1 != last1 
          {
              out = out + (string)first1.data
              first1 = first1.next()
              if first1 != last1 out = out + ","
          }
          out = out + "}"
          return out
      }

       operator|(b)
       {
           r = new tree()

           first1 = begin
           last1 = end
           first2 = b.begin
           last2 = b.end

            while first1 != last1 && first2 != last2
            {
                less = first1.data < first2.data
                greater = first2.data < first1.data
  
                if less
                {
                    r << first1.data
                    first1 = first1.next()
                }

                else if greater
                {
                    r << first2.data
                    first2 = first2.next()
                }

                else
                {

                    r << first1.data
                    first1 = first1.next()
                    first2 = first2.next()
                }
            }
 
            while first1 != last1
            {
                r << first1.data
                first1 = first1.next()
            }
            while first2 != last2
            {
                r << first2.data
                first2 = first2.next()
            }
            return r
       }

       operator&(b)
       {
           r = new tree()

           first1 = begin
           last1 = end
           first2 = b.begin
           last2 = b.end

            while first1 != last1 && first2 != last2
            {
                less = first1.data < first2.data
                greater = first2.data < first1.data

                if less
                {
                   first1 = first1.next()
                }

                else if greater
                {
                   first2 = first2.next()
                }

                else
                {
                   r << first1.data
                   first1 = first1.next()
                   first2 = first2.next()
                }
            }
 
            return r
       }

       operator^(b)
       {
           r = new tree()

           first1 = begin
           last1 = end
           first2 = b.begin
           last2 = b.end

            while first1 != last1 && first2 != last2
            {
                less = first1.data < first2.data
                greater = first2.data < first1.data

                if less
                {
                   r << first1.data
                   first1 = first1.next()
                }

                else if greater
                {
                   r << first2.data
                   first2 = first2.next()
                }

                else
                {
                   first1 = first1.next()
                   first2 = first2.next()
                }
            }
 
            while first1 != last1
            {
                r << first1.data
                first1 = first1.next()
            }
            while first2 != last2
            {
                r << first2.data
                first2 = first2.next()
            }
            return r
       }

       operator-(b)
       {
           r = new tree()

           first1 = begin
           last1 = end
           first2 = b.begin
           last2 = b.end

            while first1 != last1 && first2 != last2
            {
                less = first1.data < first2.data
                greater = first2.data < first1.data

                if less
                {
                   r << first1.data
                   first1 = first1.next()
                }

                else if greater
                {
                   r << first2.data
                   first1 = first1.next()
                   first2 = first2.next()
                }

                else
                {
                   first1 = first1.next()
                   first2 = first2.next()
                }
            }
 
            while first1 != last1
            {
                r << first1.data
                first1 = first1.next()
            }
            return r
       }

       serialize(oarchive)
       {
         oarchive << count
         oarchive << datatype
         b = begin
         e = end
         while b != e
         {
           oarchive << b.data
           b = b.next()
         }
       }

       deserialize(iarchive)
       {
           c = 0           
           iarchive >> c
           type_string = ""
           iarchive >> type_string
           i = 0
           while i < c 
           {
               data = create_class(type_string)
               d = data.refresh()
               iarchive >> d
               this << d
               i++
           } 
       }

       contains_for_array(key)
       {
           if empty
           {
               return false
           }
           else
           {
               n = root
 
               repeat
               {
                   less = key < n.data.key
                   greater = n.data.key < key

                   if less
                   {
                       if !n.left.null()
                           n = n.left
                       else
                           return false
                   }
                   else if greater
                   {
                      if !n.right.null()
                         n = n.right
                      else
                         return false
                   }
                   else // item exists
                      return true
               }
           }
       }

    }
}