cekla.h

Ugrás a fájl dokumentációjához.

/* -*- c++ -*- $Revision: 320 $
 *
 *  Copyright (C) 2011, BME Declarative Programming Course
 *
 *  List functions for Cekla. Released under GPL.
 */

#ifndef CEKLA_H
#define CEKLA_H

#include <stdexcept>
#include <string>
#include <iomanip>
#include <sstream>
#include <iostream>
#include <cassert>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <new>
#ifdef ENABLE_INITIALIZER_LIST // __GXX_EXPERIMENTAL_CXX0X__
#  include <initializer_list>
#endif

// Uncomment to disable debugging info in write and writeln
//#define NDEBUG

// Uncomment to enable garbage collection.
// WARNING: defining this macro will cause memory leaks!!!
//#define ENABLE_SHARED_PTR

class list {

public:

    list(const char *S) throw (std::logic_error);

#ifdef ENABLE_INITIALIZER_LIST

    list(std::initializer_list<int> S);
#endif

    bool operator==(const list & Rhs) const;
    bool operator!=(const list & Rhs) const;

#ifdef ENABLE_SHARED_PTR
    ~list();
#endif

    // for cons, hd, tl, because couldn't convince Doxygen
    // to omit friend declarations
    list(int, const list);
    int head() const;
    list tail() const;
private:
    // BFF
//    friend list cons(int Head, const list Tail);
//    friend int hd(const list L);
//    friend list tl(const list L);

    struct elem;

#ifndef ENABLE_SHARED_PTR
    // C pointer, causes memory leak
    typedef const elem * shared_ptr;
#else
    // our replacement of TR1 shared_ptr for reference counting
    // because need to do nasty things in ~list(), need a public counter
    struct shared_ptr {
        const elem * p;
        void inc() { if (p) p->refcount++; }
        void dec() { if (p) if (0 == --(p->refcount)) delete p; }
        shared_ptr(const elem *p = NULL) : p(p) { inc(); }
        shared_ptr(const shared_ptr & o) : p(NULL) { *this = o; }
        shared_ptr & operator=(const shared_ptr & o) { dec(); p = o.p; inc(); return *this; }
        const elem* operator->() const { return p; }
        operator const elem* const & () const { return p; }
        //const elem operator*() const { //TODO }
        ~shared_ptr() { dec(); }
    };
#endif

    struct elem {
        // Underlying data
        int data;
        // The rest of the list
        shared_ptr next;

        elem(int data, shared_ptr next = 0) : data(data), next(next)
#ifdef ENABLE_SHARED_PTR
        , refcount(0)
#endif
        {}

#ifdef ENABLE_SHARED_PTR
        // for smart pointer
        mutable int refcount;
    private:
        void operator=(const elem&);
        elem(const elem&);
#endif
    };

    // The first (head) element of the list
    shared_ptr first;

};

list cons(int Head, const list Tail);

int hd(const list L);

list tl(const list L);

extern const list nil;

// ------------------- Other improvements ----------------------

template <typename any_type>
void write(const any_type & X);

#ifdef NDEBUG

template <typename any_type>
void writeln(const any_type & X);
#else

#define writeln(X) detail::_writeln(X, __FILE__, __LINE__)
#endif

list l() { return nil; }
list l(int E) { return cons(E, nil); }
list l(int E1,int E2) { return cons(E1,l(E2)); }
list l(int E1,int E2,int E3) { return cons(E1,l(E2,E3)); }
list l(int E1,int E2,int E3,int E4) { return cons(E1,l(E2,E3,E4)); }
list l(int E1,int E2,int E3,int E4,int E5) { return cons(E1,l(E2,E3,E4,E5)); }
list l(int E1,int E2,int E3,int E4,int E5,int E6) { return cons(E1,l(E2,E3,E4,E5,E6)); }
list l(int E1,int E2,int E3,int E4,int E5,int E6,int E7) { return cons(E1,l(E2,E3,E4,E5,E6,E7)); }
list l(int E1,int E2,int E3,int E4,int E5,int E6,int E7,int E8) { return cons(E1,l(E2,E3,E4,E5,E6,E7,E8)); }
list l(int E1,int E2,int E3,int E4,int E5,int E6,int E7,int E8,int E9) { return cons(E1,l(E2,E3,E4,E5,E6,E7,E8,E9)); }
list l(int E1,int E2,int E3,int E4,int E5,int E6,int E7,int E8,int E9,int E10) { return cons(E1,l(E2,E3,E4,E5,E6,E7,E8,E9,E10)); }

typedef int (*fun1)(int);
typedef int (*fun2)(int, int);

// -------------- Details, not important to a regular user -----------

namespace detail {

// how much chars are already printed to this line
extern volatile int Tab;

// prints X, the current source_file:source_line and a newline (for debugging)
template <typename any_type>
void _writeln(const any_type & X, const char * Source_file, int Source_line);

// error handling
void error(const char *Errmsg) throw (std::logic_error);

// list printing.
std::ostream & operator<<(std::ostream & Os, const list & L);

}

// -------------- Implementation, not important to a regular user -----------
// -------------- WARNING! --------------
// Causes linker error in case of multiple source files:
// "multiple definition of ..."
// Could be put into a source file (and a lib) but it's easier to deploy in IDEs

const list nil = "";

template <typename any_type>
void write(const any_type & X) {
    using namespace detail;
    std::stringstream S;
    S << X;
    detail::Tab += (int)S.str().length();
    std::cout << X;
}

#ifdef NDEBUG
template <typename any_type>
void writeln(const any_type & X) {
    write(X);
    std::cout << std::endl;
}
#else
namespace detail {
template <typename any_type>
void _writeln(const any_type & X, const char * Source_file, int Source_line) {
    write(X);
    using namespace std;
    cout << setw(60 - Tab) << ' ' << setw(0);
    cout << " // " << Source_file << ":" << Source_line;
    Tab = 0;
    cout << endl;
}
}
#endif

list::list(const char *S) throw (std::logic_error) : first() {
    if (!S) detail::error("ERROR in list(char*): null pointer given");
    *this = nil;
    for (const char * P = S + strlen(S) - 1; P >= S; P--)
        *this = cons(*P, *this);
}

#ifdef ENABLE_INITIALIZER_LIST
list::list(std::initializer_list<int> S) : first() {
    for (auto P = S.begin(); P != S.end(); ++P)
        *this = cons(*P, *this);
}
#endif

bool list::operator==(const list & Rhs) const {
    shared_ptr p1, p2;
    for (p1 = first, p2 = Rhs.first; p1 && p2; p1 = p1->next, p2 = p2->next)
        if (p1->data != p2->data)
            return false;
    return !p1 && !p2;
}

bool list::operator!=(const list & Rhs) const {
    return ! (*this == Rhs);
}

#ifdef ENABLE_SHARED_PTR
list::~list() {
    // Non-recursive deletion of linked elements
    // The builtin desctruction would cause stack overflow for big lists:
    // ~list() calls ~shared_ptr calls delete calls ~shared_ptr ...
    // So we delete elements with refcount==1
    for (const elem * p = first; p && p->refcount == 1; p = first) {
        first.p = NULL; // disable delete
        first = p->next;
        delete p;
    }
}
#endif

inline
list::list(int Head, const list Tail) : first() {
    first = new list::elem(Head, Tail.first);
}

list cons(int Head, const list Tail) {
    return list(Head, Tail);
}

inline
int list::head() const {
    if (first==NULL)
        detail::error("ERROR in head(): list is empty");
    return first->data;
}

int hd(const list L) {
    return L.head();
}

inline
list list::tail() const {
    if (first==NULL)
        detail::error("ERROR in tail(): list is empty");
    list L0 = nil;
    L0.first = first->next;
    return L0;
}

list tl(const list L) {
    // // prevents a function from being considered for inlining
    // __attribute__((noinline))
    // // From the GCC Manual: To keep such calls from being optimized away,
    // // put in the called function, to serve as a special side-effect.
    // asm ("");
    return L.tail();
}

namespace detail {

void memory_error() {
    std::cerr << "ERROR: out of memory" << std::endl;
    throw std::bad_alloc();
}

// to start automatically before main()
struct bootstrap {
    bootstrap() {
        std::set_new_handler(memory_error);
    }
} _startup;

volatile int Tab = 0;

void error(const char *errmsg) throw (std::logic_error) {
    std::logic_error e(errmsg);
    std::cerr << e.what() << std::endl;
    throw e;
}

std::ostream & operator<<(std::ostream & Os, const list & L) {
    bool Is_szoveg = true;
    for (list L0 = L; L0 != nil; L0 = tl(L0)) {
        if (hd(L0) < 32 || 126 < hd(L0)) {
            Is_szoveg = false;
            break;
        }
    }
    if (Is_szoveg && L != nil) {
        //  os << '"';
        for (list L0 = L; L0 != nil; L0 = tl(L0))
            Os << (char) hd(L0);
        //  os << '"';
    }
    else {
        Os << "[";
        bool First = true;
        for (list L0 = L; L0 != nil; L0 = tl(L0)) {
            if (!First) Os << ",";
            Os << hd(L0);
            First = false;
        }
        Os << "]";
    }
    return Os;
}

}

#endif /* CEKLA_H */