Ignore:
Timestamp:
Jan 20, 2021, 4:49:40 PM (9 months ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
arm-eh, jacob/cs343-translation, master, new-ast-unique-expr
Children:
454f478
Parents:
92bfda0 (diff), fd54fef (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:
1 edited

Legend:

Unmodified
Added
Removed
  • tests/avltree/avl-private.cfa

    r92bfda0 rdafbde8  
    1111// an AVL tree's height is easy to compute
    1212// just follow path with the larger balance
    13 forall(otype K | Comparable(K), otype V)
     13forall(K | Comparable(K), V)
    1414int height(tree(K, V) * t){
    1515  int helper(tree(K, V) * t, int ht){
     
    2727}
    2828
    29 forall(otype K | Comparable(K), otype V)
     29forall(K | Comparable(K), V)
    3030int calcBalance(tree(K, V) * t){
    3131  int l = height(t->left);
     
    3636
    3737// re-establish the link between parent and child
    38 forall(otype K | Comparable(K), otype V)
     38forall(K | Comparable(K), V)
    3939void relinkToParent(tree(K, V) * t){
    4040  tree(K, V) * parent = t->parent; // FIX ME!!
     
    4949
    5050// rotate left from t
    51 forall(otype K | Comparable(K), otype V)
     51forall(K | Comparable(K), V)
    5252tree(K, V) * rotateLeft(tree(K, V) * t){
    5353  tree(K, V) * newRoot = t->right;
     
    6868
    6969// rotate right from t
    70 forall(otype K | Comparable(K), otype V)
     70forall(K | Comparable(K), V)
    7171tree(K, V) * rotateRight(tree(K, V) * t){
    7272  tree(K, V) * newRoot = t->left;
     
    8787
    8888// balances a node that has balance factor -2 or 2
    89 forall(otype K | Comparable(K), otype V)
     89forall(K | Comparable(K), V)
    9090tree(K, V) * fix(tree(K, V) * t){
    9191  // ensure that t's balance factor is one of
     
    113113
    114114// attempt to fix the tree, if necessary
    115 forall(otype K | Comparable(K), otype V)
     115forall(K | Comparable(K), V)
    116116tree(K, V) * tryFix(tree(K, V) * t){
    117117  int b = calcBalance(t);
     
    126126
    127127// sets parent field of c to be p
    128 forall(otype K | Comparable(K), otype V)
     128forall(K | Comparable(K), V)
    129129void setParent(tree(K, V) * c, tree(K, V) * p){
    130130  if (! empty(c)){
Note: See TracChangeset for help on using the changeset viewer.