AvlTree.borg

AvlTree.borg


`*----------------------------------------------------------------------------
`* Avl Trees
`*----------------------------------------------------------------------------
`* author: Borg: Werner Van Belle nov 01
`*            C: Werner Van Belle aug 95
`*----------------------------------------------------------------------------
{
MakeAvlTree(COMPARE, PRINT)::
  {
  ` --------------
  ` node type
  ` --------------
  RIGHT::POSITIVE::1;
  LEFT::NEGATIVE::-1;
  ROOTNODE:NULLNODE::void;
  ZERO::0;
  NewNode(w)::[NULLNODE,NULLNODE,0,w];
  IsNullNode(x)::is_void(x);
  Flag(x,val)::x[3] = val;
  SetFlag(x,val)::x[3] := val;
  Node(x,w)::x[(w+3)//2];
  SetNode(x,w,v)::x[(w+3)//2]:=v;
  inv_Flag(x,val)::Flag(x,-val);
  inv_SetFlag(x,val)::SetFlag(x,-val);
  inv_Node(x,w)::Node(x,-w);
  inv_SetNode(x,w,v)::SetNode(x,-w,v);
  COMPARE_ADD_DATA(w1,w2)::COMPARE(w1[4],w2[4]);
  COMPARE_SEARCH_DATA(w,key)::COMPARE(w[4],key);
  ` --------------
  ` internals
  ` --------------
  SearchAvlNode(root, watte)::
    ` geeft het resultaat van het zoeken weer, NULLNODE indien niet gevonden */
    if (IsNullNode(root), root,
    if ((CompareResult:COMPARE_SEARCH_DATA(root,watte))=0, root,
    if (CompareResult=1, SearchAvlNode(Node(root,LEFT),watte),
    SearchAvlNode(Node(root,RIGHT),watte))));
  Rotate(root, depthchanged, Node, SetNode, Flag, SetFlag)::
    {
    sec:Node(root,RIGHT);
    if (!Flag(sec,NEGATIVE),
      {
      SetNode(root,RIGHT,Node(sec,LEFT));
      SetNode(sec,LEFT,root);
      if (Flag(sec,POSITIVE),
        {
        SetFlag(root,ZERO);
    SetFlag(sec, ZERO);
    depthchanged[1]:=true
        },
        {
        SetFlag(root,POSITIVE);
    SetFlag(sec,NEGATIVE)
        });
      sec
      },
      {
      third:Node(sec,LEFT);
      SetNode(sec,LEFT,Node(third,RIGHT));
      SetNode(root,RIGHT,Node(third,LEFT));
      SetNode(third,RIGHT,sec);
      SetNode(third,LEFT,root);
      depthchanged[1]:=true;
      if (Flag(third,NEGATIVE),
        {
        SetFlag(sec,POSITIVE);
    SetFlag(root,ZERO)
        },
      if (Flag(third,ZERO),
    {
        SetFlag(sec,ZERO);
    SetFlag(root,ZERO)
        },
        {
        SetFlag(sec,ZERO);
        SetFlag(root,NEGATIVE)
        }));
      SetFlag(third,ZERO);
      third})
    };
  RotateLeft(root, depthchanged)::Rotate(root, depthchanged, Node,SetNode,Flag,SetFlag);
  RotateRight(root,depthchanged)::Rotate(root, depthchanged, inv_Node,inv_SetNode,inv_Flag,inv_SetFlag);
  AddAvlNode_aux(root, who, depthchanged)::
    {
    ` functie die iets links of rechts hangt, afhankelijk van de situatie
    Hang(rotation, Node, SetNode, Flag, SetFlag)::
      {
      SetNode(root,LEFT,AddAvlNode_aux(Node(root,LEFT),who,heightchanged));
      if (heightchanged[1],
        if (Flag(root,ZERO),
          {
          SetFlag(root,NEGATIVE);
          depthchanged[1]:=true
          },
        if (Flag(root,POSITIVE),
          SetFlag(root,ZERO),
          {
          heightchanged[1]:=false;
          root:=rotation(root,heightchanged);
          ` als heightchanged verandert is; is root kleiner geworden
          if (!heightchanged[1], depthchanged[1]:=true)
          })));
      root
      };
    HangLeft()::Hang(RotateRight, Node, SetNode, Flag, SetFlag);
    HangRight()::Hang(RotateLeft, inv_Node, inv_SetNode, inv_Flag, inv_SetFlag);
    heightchanged:[false];
    if (IsNullNode(who),root,
      {
      SetNode(who,LEFT,NULLNODE);
      SetNode(who,RIGHT,NULLNODE);
      SetFlag(who,ZERO);
      if (IsNullNode(root),
      {
          depthchanged[1]:=true;
      who
          },
      {
      CompareResult:COMPARE_ADD_DATA(root,who);
      if (CompareResult=0, error("No duplicates please"),
      if (CompareResult=1, HangLeft(), HangRight()))
      })})};
  DeleteAvlNode_naardelete(root, wie, heightchanged)::
    {
    freedom:void;
    Freedom_aux(cur, heightchanged, FreedomAux, Rotate,Node,SetNode,Flag,SetFlag)::
        if (IsNullNode(Node(cur,RIGHT)),
          {
          freedom:=cur;
          heightchanged[1]:=true;
          if (IsNullNode(Node(cur,LEFT)),
            NULLNODE,
            Node(cur,LEFT))
          },
          {
          takverkleind:[false];
          SetNode(cur,RIGHT,FreedomAux(Node(cur,RIGHT),takverkleind));
          if (takverkleind[1],
            if (Flag(cur,NEGATIVE), Rotate(cur,heightchanged),
            if (Flag(cur,POSITIVE),
              {
               SetFlag(cur,ZERO);
               heightchanged[1]:=true;
               cur
              },
              {
              SetFlag(cur,NEGATIVE);
              cur})),
            cur)
        });
    LeftFreedom_aux(c,heightchanged)::Freedom_aux(c,heightchanged,LeftFreedom_aux,RotateRight,Node,SetNode,Flag,SetFlag);
    RightFreedom_aux(c,heightchanged)::Freedom_aux(c,heightchanged,RightFreedom_aux,RotateLeft,inv_Node,inv_SetNode,inv_Flag,inv_SetFlag);
    GetFreedom(heightchanged, FreedomAux, Node)::
      {
      nname:Node(root,LEFT);
      if (!IsNullNode(Node(nname,RIGHT)),
      FreedomAux(nname,heightchanged),
        {
      heightchanged[1]:=true;
    freedom:=nname;
    Node(nname,LEFT)
        })
      };
    GetLeftFreedom(heightchanged)::GetFreedom(heightchanged,LeftFreedom_aux,Node);
    GetRightFreedom(heightchanged)::GetFreedom(heightchanged,RightFreedom_aux,inv_Node);

    takkleiner:[false];
    Zak(Rotate, Node, SetNode,Flag,SetFlag)::
      {
      SetNode(root,LEFT,DeleteAvlNode_naardelete(Node(root,LEFT),wie,takkleiner));
      if (takkleiner[1],
        {
    if (Flag(root,NEGATIVE),
      {
      SetFlag(root,ZERO);
      heightchanged[1]:=true;
      root
      },
    if (Flag(root,ZERO),
      {
      SetFlag(root,POSITIVE);
      root
      },
        Rotate(root,heightchanged)))
        }, root)
      };
    ZakLeft()::Zak(RotateLeft,Node,SetNode,Flag,SetFlag);
    ZakRight()::Zak(RotateRight,inv_Node,inv_SetNode,inv_Flag,inv_SetFlag);
    if (IsNullNode(root), root,
      {
      CompareResult:COMPARE_SEARCH_DATA(root,wie);
      if (CompareResult = -1, ZakRight(), ` root
      if (CompareResult = 1, ZakLeft(), ` root>wie
      if (IsNullNode(Node(root,LEFT)) & IsNullNode(Node(root,RIGHT)),
     {
     heightchanged[1]:=true;
     NULLNODE
     },
      if (IsNullNode(Node(root,LEFT)),
     {
     rechter:Node(root,RIGHT);
     heightchanged[1]:=true;
         rechter
     },
      if (IsNullNode(Node(root,RIGHT)),
     {
     linker:Node(root,LEFT);
     heightchanged[1]:=true;
     linker
     },
      if (Flag(root,POSITIVE),
     {
     SetNode(root,RIGHT,GetRightFreedom(heightchanged));
     SetNode(freedom,LEFT,Node(root,LEFT));
         SetNode(freedom,RIGHT,Node(root,RIGHT));
     if (heightchanged[1],SetFlag(freedom,ZERO),SetFlag(freedom,POSITIVE));
         freedom
     },
      if (Flag(root,NEGATIVE),
     {
     SetNode(root,LEFT,GetLeftFreedom(heightchanged));
     SetNode(freedom,LEFT,Node(root,LEFT));
     SetNode(freedom,RIGHT,Node(root,RIGHT));
     if (heightchanged[1], SetFlag(freedom,ZERO), SetFlag(freedom,NEGATIVE));
     freedom
     },
      if (Flag(root,ZERO),
     {
     takverkleind:[false];
     SetNode(root,LEFT,GetLeftFreedom(takverkleind));
     SetNode(freedom,LEFT,Node(root,LEFT));
     SetNode(freedom,RIGHT,Node(root,RIGHT));
     if (takverkleind[1], SetFlag(freedom,POSITIVE), SetFlag(freedom,ZERO));
     freedom
     },
      error("exit(57)")))))))))})
    };
  AvlDepth(root)::
    if (IsNullNode(root), 0,
      {
      l:AvlDepth(Node(root,LEFT));
      r:AvlDepth(Node(root,RIGHT));
      if (l>r, l+1, r+1)
      });
  ValidAvlTree(root)::
    if (IsNullNode(root), true,
    if (!ValidAvlTree(Node(root,LEFT)), false,
    if (!ValidAvlTree(Node(root,RIGHT)), false,
    if (Flag(root,POSITIVE), AvlDepth(Node(root,LEFT))=(AvlDepth(Node(root,RIGHT))-1),
    if (Flag(root,NEGATIVE), AvlDepth(Node(root,LEFT))=(AvlDepth(Node(root,RIGHT))+1),
    AvlDepth(Node(root,LEFT))=AvlDepth(Node(root,RIGHT)))))));
  AvlTreeCount(cell)::
    if (IsNullNode(cell),0,
      1+AvlTreeCount(Node(cell,LEFT))
       +AvlTreeCount(Node(cell,RIGHT)));
  PrintAvlTree(root, diepte)::
    if (!IsNullNode(root),
      {
      PrintAvlTree(Node(root,RIGHT),diepte+".");
      display(diepte);
      display(if(root[3]=1, "+ ", if (root[3]= -1, "- ", "0 ")) + PRINT(root[4]));
      l:AvlDepth(Node(root,LEFT));
      r:AvlDepth(Node(root,RIGHT));
      display(" left="+text(l)+" right="+text(r)+" count="+text(AvlTreeCount(root)));
      if ((abs(l-r)>1) |
      ((lr) & !Flag(root,NEGATIVE)) |
      ((l=r) & !Flag(root,ZERO)), display("**********"));
      display(eoln);
      PrintAvlTree(Node(root,LEFT),diepte+".")
     });
  ForeachAvlTree(root, lambda)::
    if (!IsNullNode(root),
      {
      ForeachAvlTree(Node(root,LEFT),lambda);
      lambda(root[4]);
      ForeachAvlTree(Node(root,RIGHT),lambda)
      });
  ` --------------
  ` user functions
  ` --------------
  Add(data):: ` O(log2n)
    ROOTNODE:=AddAvlNode_aux(ROOTNODE,NewNode(data),[false]);
  Search(key):: ` O(
    {
    node:SearchAvlNode(ROOTNODE,key);
    if (IsNullNode(node),void,node[4])
    };
  Delete(key):: ` O(log2n)
    ROOTNODE:=DeleteAvlNode_naardelete(ROOTNODE,key,[false]);
  Foreach(lambda)::
    ForeachAvlTree(ROOTNODE,lambda);
  Print()::
    PrintAvlTree(ROOTNODE,"");
  Count()::
    AvlTreeCount(ROOTNODE);
  SetRoot(n)::
    ROOTNODE:=n;
  GetRoot()::
    ROOTNODE;
  Exist(name)::
    !IsNullNode(SearchAvlNode(ROOTNODE,name));
  clone()
  };

AddAndDel()::
  {
  compareword(w1,w2)::if (w1>w2, 1, if(w1=w2, 0, -1));
  printword(w)::display(w);
  a:MakeAvlTree(compareword,printword);
  i:100;
  while(i>0,
    {
    a.Add("text"+text(i)+" ");
    i:=i-1
    });
  a.Print();
  i:100;
  display("========================"+eoln);
  while(i>0,
    {
    a.Delete("text"+text(i)+" ");
    i:=i-2
    });
  a.Print();
  i:99;
  display("========================"+eoln);
  while(i>0,
    {
    a.Delete("text"+text(i)+" ");
    i:=i-2
    });
  a.Print()
  };
"AddAndDel()"
}