dlist.h

Go to the documentation of this file.

// ----------------------------------------------------------------------------
// SOSpin Library
// Copyright (C) 2015 SOSpin Project
//
//   Authors:
//
//     Nuno Cardoso (nuno.cardoso@tecnico.ulisboa.pt)
//     David Emmanuel-Costa (david.costa@tecnico.ulisboa.pt)
//     Nuno Gonçalves (nunogon@deec.uc.pt)
//     Catarina Simoes (csimoes@ulg.ac.be)
//
// ----------------------------------------------------------------------------
// This file is part of SOSpin Library.
//
// SOSpin Library is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or any
// later version.
//
// SOSpin Library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with SOSpin Library.  If not, see <http://www.gnu.org/licenses/>.
// ----------------------------------------------------------------------------

//       dllist.h created on 27/02/2015
//
//      This file contains the functions necessary to do things
//   in the SOSpin Library.
//
//      Revision 1.1 28/02/2015 23:19:29 david
//      Revision 1.2 29/04/2015 17:27:00 nunogon
//      Revision 1.3 26/05/2015 00:04:00 nunogon
//      License updated
//

#ifndef CLASS_DList_H
#define CLASS_DList_H

#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include <list>



using namespace std;


namespace sospin {

    enum Elem {
        b = 0, 
        bt = 1, 
        delta = 2, 
        ct = 3 
    };

    struct elemType {
        //Type - 3 bits
        //Sign - 1 bit
        //id.x - 10 bits
        //id.y - 10 bits
        //Free bits - 8 bits
        //Total - 32 bits
        unsigned int dataField;

        unsigned int getType() {
            unsigned int type_out;
            type_out = dataField >> 29;
            return type_out;
        }

        bool getSign() {
            unsigned int bool_out;
            bool_out = dataField & 0x10000000;
            bool_out = bool_out >> 28;
            return bool_out;
        }

        unsigned int getIdx1() {
            unsigned int idx1_out;
            idx1_out = dataField & 0x0FFC0000;
            idx1_out = idx1_out >> 18;
            return idx1_out;
        }

        unsigned int getIdx2() {
            unsigned int idx2_out;
            idx2_out = dataField & 0x0003FF00;
            idx2_out = idx2_out >> 8;
            return idx2_out;
        }

        static elemType make_elem(int type, int data) {
            if (type == 2) {
                cout << "Cannot make a delta elemType with only one index" << endl;
                exit(0);
            } // returns error if data.type = 2 (delta)
            elemType elem;
            elem.setType(type);
            elem.setIdx1(data);
            elem.setIdx2(0);
            return elem;
        }

        static elemType make_elem(int type, int data1, int data2) {
            elemType elem;
            elem.setType(type);
            elem.setIdx1(data1);
            elem.setIdx2(data2);
            return elem;
        }

        static elemType make_delta(elemType data1, elemType data2) {
            elemType elem;
            elem.setType(2);
            elem.setIdx1(data1.getIdx1());
            elem.setIdx2(data2.getIdx1());
            return elem;
        }

        void setType(unsigned int typ) {

            //Clean 3-bits of type
            dataField = dataField & 0x1FFFFFFF;

            //Set type
            //b
            if (typ == 0) dataField = dataField | 0x00000000;
            //b^\dagger
            if (typ == 1) dataField = dataField | 0x20000000;
            //delta
            if (typ == 2) dataField = dataField | 0x40000000;
            //constant
            if (typ == 3) dataField = dataField | 0x60000000;
            // For all other types (not used)
            if (typ > 3) dataField = dataField | 0x80000000;

        }

        void setSign(bool sign) {
            //Clean bit of sign
            dataField = dataField & 0xEFFFFFFF;

            //Set sign (only if sign is true)
            if (sign == 1) dataField = dataField | 0x10000000;

        }

        void setIdx1(unsigned int idx) {
            unsigned int in;

            //Clean bits of data1 field
            dataField = dataField & 0xF003FFFF;

            //Format in to accommodate 10 bits from the input
            in = idx & 0x000003FF;

            //Shift to match filled bits
            in = in << 18;

            //Set data1 field
            dataField = dataField | in;
        }

        void setIdx2(unsigned int idx) {
            unsigned int in;

            //Clean bits of data2 field
            dataField = dataField & 0xFFFC00FF;

            //Format in to accommodate 10 bits from the input
            in = idx & 0x000003FF;

            //Shift to match filled bits
            in = in << 8;

            //Set data2 field
            dataField = dataField | in;
        }

        elemType& operator=(const elemType &elem) {
            elemType aux=elem;
            setType(aux.getType());
            setIdx1(aux.getIdx1());
            setIdx2(aux.getIdx2());
            return *this;
        }

    };

    struct noList {
        elemType data;
        noList *prv;
        noList *nxt;
    };

    class DList {
        noList *begin;
        noList *end;
        noList *actual;
        int sign;


    public:
        //Constructors and destructor

        DList(void);

        DList(int tp, int i);

        DList(int tp, int i, int j);

        DList(const DList &L);

        ~DList(void);


        //Changing, writing and updating

        void clear();

        void negate() {
            sign *= -1;
        }


        void add(elemType);

        void add_begin(elemType);

        void add_end(elemType);


        void set(elemType i) {
            actual->data = i;
        }

        void set_begin() {
            actual = begin;
        }

        void set_end() {
            actual = end;
        }

        void set_sign(int ii) {
            sign = ii;
        }


        void join(DList& L);

        void loop_right() {
            if (actual == 0 || actual->nxt == 0) actual = begin;
            else actual = actual->nxt;
        }

        void loop_left() {
            actual = actual -> prv;
            if (actual == 0) actual = end;
        }

        DList rearrange();

        void remove(unsigned int type);

        void remove_actual();

        void shift_right() {
            if (actual == 0 || actual->nxt == 0) actual = end;
            else actual = actual->nxt;
        }

        void shift_left() {
            actual = actual -> prv;
            if (actual == 0) actual = begin;
        }

        void swap_next();


        //Reading and accessing data

        elemType get() {
            return actual->data;
        }

        int getSign() {
            return sign;
        }

        vector<int> getIds();

        void getBandBdaggerIds(bool &BandBdagger, vector<string> &id0, vector<string> &id1, int &sign);

        void getDeltaIds(bool &AllDeltas, vector<string> &id0, vector<string> &id1, int &sign);

        void getBandBdaggerAndDeltasIds(vector<string> &id0, vector<string> &id1, vector<string> &id2, vector<string> &id3, int &sign);

        int numDeltas();

        int numBs();


        bool search_last(unsigned int type1);

        bool search_first(unsigned int type1);

        bool search_first(unsigned int type0, unsigned int type1);

        bool search_elem(unsigned int type1);


        //Querying and booleans

        bool check();

        bool checkDeltaIndex();

        bool check_num();

        bool check_same_num();

        bool isActualLast() {
            return (actual == end) ? true : false;
        }

        bool isEmpty() {
            bool epty = true;
            if (begin != 0) epty = false;
            return epty;
        }

        bool hasNoDeltas();

        bool hasOnlyDeltas();

        bool hasRepeatedIndex();


        //Operators

        DList& operator=(const DList& L);

        const DList operator-()const;


        //Friends

        friend DList* copy(DList *L);

        friend DList contract_deltas(DList &L, bool braketmode);

        friend DList ordering(DList &L, bool braketmode);


        friend string printDeltas(DList &L);


        friend DList& operator*(DList& L, elemType j);

        friend DList operator*(const DList& L, const DList &M);

        friend DList& operator-(DList& L, elemType j);

        friend DList& operator,(DList& L, elemType j);

        friend ostream& operator<<(ostream& out, DList &L);

        friend ostream& operator<<(ostream& out, DList *L);

        //same as operator* and operator,
        friend DList& operator<<(DList &L, elemType j);

        friend DList& operator<<(DList &L, DList &M);

        friend bool operator==(DList &L, DList &M);

    };

}

#endif