//# publish
// Implements a sorted linked list in which 0xEryone can insert a new node (e.g. for DNS)
// but only the list owner/node owner can remove a node
module 0x1.SortedLinkedList {
    import 0x1.signer;

    struct Node has key {
        prev: address, // account address where the previous node is stored (head if no previous node exists)
        next: address, // account address where the next node is stored (head if no next node exists)
        head: address, // account address where current list's head is stored -- who0xEr stores head is the owner of the whole list
        value: u64 //TODO: make generic
    }

    public node_exists(node_address: address): bool {
    label b0:
        return exists<Node>(move(node_address));
    }

    public get_value_of_node(node_address: address): u64 acquires Node {
        let node_ref: & Self.Node;
        let result: u64;
    label b0:
        assert(exists<Node>(copy(node_address)), 20);

        node_ref = borrow_global<Node>(move(node_address));
        result = *&move(node_ref).Node::value;

        return move(result);
    }

    //checks whether this address is the head of a list -- fails if there is no node here
    public is_head_node(current_node_address: address): bool acquires Node {
        let current_node_ref: & Self.Node;
        let head_node_address: address;
        let result: bool;
    label b0:
        // check that a node exists
        assert(exists<Node>(copy(current_node_address)), 19);

        // find the head node
        current_node_ref = borrow_global<Node>(copy(current_node_address));
        head_node_address = *&move(current_node_ref).Node::head;

        // check if this is the head node
        result = (move(head_node_address) == move(current_node_address));

        return move(result);
    }

    //creates a new list whose head is at txn_sender (is owned by the caller)
    public create_new_list(account: &signer) {
        let sender_address: address;
        let head: Self.Node;
    label b0:
        sender_address = signer.address_of(copy(account));

        // make sure no node/list is already stored in this account
        assert(!exists<Node>(copy(sender_address)), 1);

        head = Node {
            prev: copy(sender_address),
            next: copy(sender_address),
            head: move(sender_address),
            value: 0
        };
        move_to<Node>(move(account), move(head));


        return;
    }

    // adds a node that is stored in txn_sender's account and whose location in the list is right after prev_node_address
    public add_node(account: &signer, value: u64, prev_node_address: address) acquires Node { // TODO: make value generic
        let sender_address: address;
        let prev_node_ref: & Self.Node;
        let prev_node_mut_ref: &mut Self.Node;
        let next_node_address: address;
        let next_node_mut_ref: &mut Self.Node;
        let next_node_ref: & Self.Node;
        let prev_is_head: bool;
        let next_is_head: bool;
        let prev_value: u64; //TODO: make generic
        let next_value: u64; //TODO: make generic
        let current_node: Self.Node;
        let head_address: address;
    label b0:
        sender_address = signer.address_of(copy(account));

        // make sure no node is already stored in this account
        assert(!exists<Node>(copy(sender_address)), 3);

        // make sure a node exists in prev_node_address
        assert(exists<Node>(copy(prev_node_address)), 5);

        // get a reference to prev_node and find the address and reference to next_node, head
        prev_node_ref = borrow_global<Node>(copy(prev_node_address));
        next_node_address = *&copy(prev_node_ref).Node::next;
        next_node_ref = borrow_global<Node>(copy(next_node_address));
        head_address = *&copy(next_node_ref).Node::head;

        // see if either prev or next are the head and get their values
        prev_value = *&move(prev_node_ref).Node::value;
        next_value = *&move(next_node_ref).Node::value;
        prev_is_head = Self.is_head_node(copy(prev_node_address));
        next_is_head = Self.is_head_node(copy(next_node_address));

        // check the order -- the list must be sorted
        assert(move(prev_is_head) || (move(prev_value) < copy(value)), 6);
        assert(move(next_is_head) || (move(next_value) > copy(value)), 7);

        // create the new node
        current_node = Node {
            prev: copy(prev_node_address),
            next: copy(next_node_address),
            head: move(head_address),
            value: move(value)
        };
        move_to<Node>(copy(account), move(current_node));

        // fix the pointers at prev
        prev_node_mut_ref = borrow_global_mut<Node>(move(prev_node_address));
        *&mut move(prev_node_mut_ref).Node::next = copy(sender_address);

        // fix the pointers at next
        next_node_mut_ref = borrow_global_mut<Node>(move(next_node_address));
        *&mut move(next_node_mut_ref).Node::prev = copy(sender_address);

        return;
    }

    //can only called by the list owner (head) -- removes the list if it is empty, fails if it is non-empty or if no list is owned by the caller
    public remove_list(account: &signer) acquires Node {
        let sender_address: address;
        let current_node_ref: & Self.Node;
        let next_node_address: address;
        let prev_node_address: address;
        let temp_address: address;
        let temp_value: u64; //TODO: make generic
        let temp_bool: bool;
    label b0:
        sender_address = signer.address_of(move(account));

        // fail if the caller does not own a list
        assert(Self.is_head_node(copy(sender_address)), 18);

        assert(exists<Node>(copy(sender_address)), 8);
        current_node_ref = borrow_global<Node>(copy(sender_address));

        // check that the list is empty
        next_node_address = *&copy(current_node_ref).Node::next;
        prev_node_address = *&move(current_node_ref).Node::prev;
        assert(move(next_node_address) == copy(sender_address), 9);
        assert(move(prev_node_address) == copy(sender_address), 10);

        // destroy the Node
        Node{temp_address, temp_address, temp_address, temp_value} = move_from<Node>(copy(sender_address));

        return;
    }

    // removes the current non-head node -- fails if the passed node is the head of a list
    public remove_node_by_node_owner(account: &signer) acquires Node {
        let sender_address: address;
    label b0:
        sender_address = signer.address_of(move(account));

        // make sure a node exists
        assert(exists<Node>(copy(sender_address)), 11);

        // make sure it is not a head node (heads can be removed using remove_list)
        assert(!Self.is_head_node(copy(sender_address)),12);

        // remove it
        Self.remove_node(move(sender_address));

        return;
    }

    public remove_node_by_list_owner(account: &signer, node_address: address) acquires Node {
        let node_ref: & Self.Node;
        let list_owner: address;
    label b0:
        // make sure the node exists
        assert(exists<Node>(copy(node_address)), 13);

        // make sure it is not a head node
        assert(!Self.is_head_node(copy(node_address)), 14);

        // make sure the caller owns the list
        node_ref = borrow_global<Node>(copy(node_address));
        list_owner = *&move(node_ref).Node::head;
        assert(move(list_owner) == signer.address_of(move(account)), 15);

        // remove it
        Self.remove_node(move(node_address));

        return;
    }

    //private function used for removing a non-head node -- does not check permissions
    remove_node(node_address: address) acquires Node {
        let current_node_ref: & Self.Node;
        let next_node_address: address;
        let next_node_mut_ref: &mut Self.Node;
        let prev_node_address: address;
        let prev_node_mut_ref: &mut Self.Node;
        let temp_address: address;
        let temp_value: u64; //TODO: make generic
    label b0:
        // make sure the node exists
        assert(exists<Node>(copy(node_address)),16);

        // find prev and next
        current_node_ref = borrow_global<Node>(copy(node_address));
        next_node_address = *&copy(current_node_ref).Node::next;
        prev_node_address = *&move(current_node_ref).Node::prev;


        //update next
        next_node_mut_ref = borrow_global_mut<Node>(copy(next_node_address));
        *&mut move(next_node_mut_ref).Node::prev = copy(prev_node_address);

        //update prev
        prev_node_mut_ref = borrow_global_mut<Node>(move(prev_node_address));
        *&mut move(prev_node_mut_ref).Node::next = move(next_node_address);

        //destroy the current node
        Node {temp_address,temp_address,temp_address,temp_value} = move_from<Node>(move(node_address));

        return;
    }


}


//# run --signers 0xA
//creating a new list _@0xA
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.create_new_list(&account);
    return;
}

//# run --signers 0xA
// attempting to create another list with the same head
// should abort with code 1
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.create_new_list(&account);
    return;
}

//# run --signers 0xB
// adding a new element to 0xA's list _@0xA -> 10@0xB
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.add_node(&account, 10, 0xA);
    return;
}

//# run --signers 0xB
// adding another 0xB node
// should abort with 3
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.add_node(&account, 12, 0xA);
    return;
}

//# run --signers 0xC
// adding a node that does not satisfy the order between 0xA and 0xB _@0xA -> 15@0xC -> 10@0xB
// should abort with 7
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.add_node(&account, 15, 0xA);
    return;
}

//# run --signers 0xC
// adding a node between 0xA and 0xB _@0xA -> 5@0xC -> 10@0xB
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.add_node(&account, 5, 0xA);
    return;
}

//# run --signers 0xD
// adding a node that does not satisfy order after 0xB _@0xA -> 5@0xC -> 10@0xB -> 4@0xD
// should abort with 6
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.add_node(&account, 4, 0xB);
    return;
}

//# run --signers 0xD
// adding a node after 0xB _@0xA -> 5@0xC -> 10@0xB -> 15@0xD
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.add_node(&account, 15, 0xB);
    return;
}

//# run --signers 0xF
// adding a node after a non-existent node
// should abort with 5
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.add_node(&account, 15, 0xE);
    return;
}

//# run --signers 0xE
// adding a node after 0xC with the same value _@0xA -> 5@0xC -> 5@0xE -> 10@0xB -> 15@0xD
// should abort with 6
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.add_node(&account, 5, 0xC);
    return;
}

//# run --signers 0xC
// adding a node after itself
// should abort with 3
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.add_node(&account, 5, 0xC);
    return;
}

//# run --signers 0xE
// adding a node between 0xC and 0xB _@0xA -> 5@0xC -> 7@0xE -> 10@0xB -> 15@0xD
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.add_node(&account, 7, 0xC);
    return;
}

//# run --signers 0xC
// remove node  _@0xA -> 7@0xE -> 10@0xB -> 15@0xD
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.remove_node_by_node_owner(&account);
    return;
}

//# run --signers 0xC
// remove node again
// should abort with 11
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.remove_node_by_node_owner(&account);
    return;
}

//# run --signers 0xC
// add a new 0xC node elsewhere in the list _@0xA -> 7@0xE -> 9@0xC -> 10@0xB -> 15@0xD
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.add_node(&account, 9, 0xE);
    return;
}

//# run --signers 0xA
// 0xA removes 0xB's node _@0xA -> 7@0xE -> 9@0xC -> 15@0xD
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.remove_node_by_list_owner(&account, 0xB);
    return;
}

//# run --signers 0xB
// 0xB tries to remove his now-non-existent node
// should abort with 11
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.remove_node_by_node_owner(&account);
    return;
}

//# run --signers 0xB
//A non-owner tries to remove a node
// should abort with 15
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.remove_node_by_list_owner(&account, 0xD);
    return;
}

//# run --signers 0xA
// 0xA attempts to remove her head node
// should abort with 14
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.remove_node_by_list_owner(&account, 0xA);
    return;
}

//# run --signers 0xA
// 0xA attempts to remove her head node
// should abort with 12
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.remove_node_by_node_owner(&account);
    return;
}

//# run --signers 0xA
// 0xA attempts to remove her list while it is not empty
// should abort with 9
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.remove_list(&account);
    return;
}

//# run --signers 0xA
// 0xA empties her list and removes it using the wrong method
// should abort with 14
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.remove_node_by_list_owner(&account, 0xC);
    SortedLinkedList.remove_node_by_list_owner(&account, 0xD);
    SortedLinkedList.remove_node_by_list_owner(&account, 0xE);
    SortedLinkedList.remove_node_by_list_owner(&account, 0xA);
    return;
}

//# run --signers 0xA
// 0xA empties her list and removes it using the wrong method
// should abort with 12
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.remove_node_by_list_owner(&account, 0xD);
    SortedLinkedList.remove_node_by_list_owner(&account, 0xC);
    SortedLinkedList.remove_node_by_list_owner(&account, 0xE);
    SortedLinkedList.remove_node_by_node_owner(&account);
    return;
}

//# run --signers 0xA
// 0xA empties her list and removes it
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.remove_node_by_list_owner(&account, 0xE);
    SortedLinkedList.remove_node_by_list_owner(&account, 0xD);
    SortedLinkedList.remove_node_by_list_owner(&account, 0xC);
    SortedLinkedList.remove_list(&account);
    return;
}

//# run --signers 0xB
//0xB creates a new list _@0xB
import 0x1.SortedLinkedList;
main(account: signer) {
label b0:
    SortedLinkedList.create_new_list(&account);
    return;
}