// S : tags   sym c++  $TAGS
// S : expect --result valid
// S : cc     -o test.bc  $CC_OPT $file
// S : verify --symbolic $V_OPT test.bc

// N : V    : CC_OPT : V_OPT : TAGS : RESULT
// V : v.O2 : -O2    :       :      : valid
// V : v.O1 : -O1    :       :      : valid
// V : v.Os : -Os    :       :      : valid
// V : v.O0 : -O0    :       : min  : valid

#include <sys/lamp.h>
#include <cstdint>
#include <cassert>

struct Node {
    int64_t val;
    Node * next = nullptr;

};

struct List {
    Node * head = nullptr;

    void insert( Node * node ) {
        if ( !head ) {
            head = node;
        } else if ( node->val < head->val ) {
            node->next = head;
            head = node;
        } else {
            auto curr = head;
            while ( curr->next && curr->next->val < node->val )
                curr = curr->next;
            node->next = curr->next;
            curr->next = node;
        }
    }

    bool isSorted() {
        Node * curr = head;
        while ( curr ) {
            auto next = curr->next;
            if ( next && curr->val > next->val )
                return false;
            curr = curr->next;
        }
        return true;
    }
};

void init_node( Node * node ) {
    int x = __lamp_any_i32();
    node->val = x;
}

int main() {
    Node n1, n2, n3;
    init_node( &n1 );
    init_node( &n2 );
    init_node( &n3 );

    List list;
    list.insert( &n1 );
    list.insert( &n2 );
    list.insert( &n3 );

    assert( list.isSorted() );
}