Changeset fd54fef for tests/avltree


Ignore:
Timestamp:
Jan 19, 2021, 8:44:29 PM (5 years ago)
Author:
Michael Brooks <mlbrooks@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
dafbde8
Parents:
2f47ea4
Message:

Converting the project to use the new syntax for otype, dtype and ttytpe.

Changed prelude (gen), libcfa and test suite to use it. Added a simple deprecation rule of the old syntax to the parser; we might wish to support both syntaxes "officially," like with an extra CLI switch, but this measure should serve as a simple reminder for our team to try the new syntax.

Location:
tests/avltree
Files:
8 edited

Legend:

Unmodified
Added
Removed

  • tests/avltree/avl-private.cfa

    r2f47ea4 rfd54fef  
    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)){

  • tests/avltree/avl-private.h

    r2f47ea4 rfd54fef  
    55
    66// attempt to fix the tree, if necessary
    7 forall(otype K | Comparable(K), otype V)
     7forall(K | Comparable(K), V)
    88tree(K, V) * tryFix(tree(K, V) * t);
    99
    1010// sets parent field of c to be p
    11 forall(otype K | Comparable(K), otype V)
     11forall(K | Comparable(K), V)
    1212void setParent(tree(K, V) * c, tree(K, V) * p);
    1313
    14 forall(otype K | Comparable(K), otype V)
     14forall(K | Comparable(K), V)
    1515int height(tree(K, V) * t);

  • tests/avltree/avl.h

    r2f47ea4 rfd54fef  
    99// #include <lib.h>
    1010
    11 trait Comparable(otype T) {
     11trait Comparable(T) {
    1212  int ?<?(T, T);
    1313};
    1414
    15 forall(otype T | Comparable(T))
     15forall(T | Comparable(T))
    1616int ?==?(T t1, T t2);
    1717
    18 forall(otype T | Comparable(T))
     18forall(T | Comparable(T))
    1919int ?>?(T t1, T t2);
    2020
    … …  
    4141
    4242// temporary: need forward decl to get around typedef problem
    43 forall(otype K | Comparable(K), otype V)
     43forall(K | Comparable(K), V)
    4444struct tree;
    4545
    46 forall(otype K | Comparable(K), otype V)
     46forall(K | Comparable(K), V)
    4747struct tree {
    4848  K key;
    … …  
    5454};
    5555
    56 forall(otype K | Comparable(K), otype V)
     56forall(K | Comparable(K), V)
    5757void ?{}(tree(K, V) &t, K key, V value);
    5858
    59 forall(otype K | Comparable(K), otype V)
     59forall(K | Comparable(K), V)
    6060void ^?{}(tree(K, V) & t);
    6161
    62 forall(otype K | Comparable(K), otype V)
     62forall(K | Comparable(K), V)
    6363tree(K, V) * create(K key, V value);
    6464
    65 forall(otype K | Comparable(K), otype V)
     65forall(K | Comparable(K), V)
    6666V * find(tree(K, V) * t, K key);
    6767
    68 forall(otype K | Comparable(K), otype V)
     68forall(K | Comparable(K), V)
    6969int empty(tree(K, V) * t);
    7070
    7171// returns the root of the tree
    72 forall(otype K | Comparable(K), otype V)
     72forall(K | Comparable(K), V)
    7373int insert(tree(K, V) ** t, K key, V value);
    7474
    75 forall(otype K | Comparable(K), otype V)
     75forall(K | Comparable(K), V)
    7676int remove(tree(K, V) ** t, K key);
    7777
    78 forall(otype K | Comparable(K), otype V)
     78forall(K | Comparable(K), V)
    7979void copy(tree(K, V) * src, tree(K, V) ** ret);
    8080
    81 forall(otype K | Comparable(K), otype V)
     81forall(K | Comparable(K), V)
    8282void for_each(tree(K, V) * t, void (*func)(V));
    8383

  • tests/avltree/avl0.cfa

    r2f47ea4 rfd54fef  
    11#include "avl.h"
    22
    3 forall(otype T | Comparable(T))
     3forall(T | Comparable(T))
    44int ?==?(T t1, T t2) {
    55  return !(t1 < t2) && !(t2 < t1);
    66}
    77
    8 forall(otype T | Comparable(T))
     8forall(T | Comparable(T))
    99int ?>?(T t1, T t2) {
    1010  return t2 < t1;

  • tests/avltree/avl1.cfa

    r2f47ea4 rfd54fef  
    33#include <stdlib.hfa>
    44
    5 forall(otype K | Comparable(K), otype V)
     5forall(K | Comparable(K), V)
    66void ?{}(tree(K, V) &t, K key, V value){
    77  (t.key) { key };
    … …  
    1313}
    1414
    15 forall(otype K| Comparable(K), otype V)
     15forall(K| Comparable(K), V)
    1616void ^?{}(tree(K, V) & t){
    1717  delete(t.left);
    … …  
    2121}
    2222
    23 forall(otype K | Comparable(K), otype V)
     23forall(K | Comparable(K), V)
    2424tree(K, V) * create(K key, V value) {
    2525  // infinite loop trying to resolve ... t = malloc();

  • tests/avltree/avl2.cfa

    r2f47ea4 rfd54fef  
    22#include "avl-private.h"
    33
    4 forall(otype K | Comparable(K), otype V)
     4forall(K | Comparable(K), V)
    55V * find(tree(K, V) * t, K key){
    66  if (empty(t)){
    … …  
    1818}
    1919
    20 forall(otype K | Comparable(K), otype V)
     20forall(K | Comparable(K), V)
    2121int empty(tree(K, V) * t){
    2222  return t == NULL;
    … …  
    2424
    2525// returns the root of the tree
    26 forall(otype K | Comparable(K), otype V)
     26forall(K | Comparable(K), V)
    2727int insert(tree(K, V) ** t, K key, V value) {
    2828  // handles a non-empty tree

  • tests/avltree/avl3.cfa

    r2f47ea4 rfd54fef  
    44
    55// swaps the data within two tree nodes
    6 forall(otype K | Comparable(K), otype V)
     6forall(K | Comparable(K), V)
    77void node_swap(tree(K, V) * t, tree(K, V) * t2){
    88        swap( t->key,  t2->key);
    … …  
    1111
    1212// go left as deep as possible from within the right subtree
    13 forall(otype K | Comparable(K), otype V)
     13forall(K | Comparable(K), V)
    1414tree(K, V) * find_successor(tree(K, V) * t){
    1515        tree(K, V) * find_successor_helper(tree(K, V) * t){
    … …  
    2525
    2626// cleanup - don't want to deep delete, so set children to NULL first.
    27 forall(otype K | Comparable(K), otype V)
     27forall(K | Comparable(K), V)
    2828void deleteSingleNode(tree(K, V) * t) {
    2929        t->left = NULL;
    … …  
    3333
    3434// does the actual remove operation once we've found the node in question
    35 forall(otype K | Comparable(K), otype V)
     35forall(K | Comparable(K), V)
    3636tree(K, V) * remove_node(tree(K, V) * t){
    3737        // is the node a leaf?
    … …  
    8585
    8686// finds the node that needs to be removed
    87 forall(otype K | Comparable(K), otype V)
     87forall(K | Comparable(K), V)
    8888tree(K, V) * remove_helper(tree(K, V) * t, K key, int * worked){
    8989        if (empty(t)){
    … …  
    106106}
    107107
    108 forall(otype K | Comparable(K), otype V)
     108forall(K | Comparable(K), V)
    109109int remove(tree(K, V) ** t, K key){
    110110        int worked = 0;

  • tests/avltree/avl4.cfa

    r2f47ea4 rfd54fef  
    44// Perform a shallow copy of src, return the
    55// new tree in ret
    6 forall(otype K | Comparable(K), otype V)
     6forall(K | Comparable(K), V)
    77int copy(tree(K, V) * src, tree(K, V) ** ret){
    88  tree(K, V) * helper(tree(K, V) * t, int * worked){
    … …  
    3535
    3636// Apply func to every value element in t, using an in order traversal
    37 forall(otype K | Comparable(K), otype V)
     37forall(K | Comparable(K), V)
    3838void for_each(tree(K, V) * t, int (*func)(V)) {
    3939  if (t == NULL) {
Note: See TracChangeset for help on using the changeset viewer.