4 way linked list

[GuitarMan]

Hello.

Just wanted to ask if its posible to make 4-way linked lists?

http://prntscr.com/9bn826

Like this.

What i need is,i need to make multiple linked lists, but at the begining i dont know how many lists i will need, so it has to be dynamic. My idea was to make 3 way linked list. Like Starting from the 1st node, by going to the right side i would create nodes that would represent the amount of linked lists.
Is this even possible to do?
And would it be like:

struct elem
{
    int num;
    elem *next;
	elem *prev;
	elem *down;
	elem* up; 
};

The task for me is to read file line by line. Each line contains variables. Amout of variables in each line vary. I have to compare lines to see if there are any duplicate values. Also i have to be able to eliminate a line and stuff like that. So my idea was to save each line as a linked list. Each time i would have a new line, i would extend the linked list to the right side and then i would just add variables from the line downwards.

So lets say, if i had 3 lines:

1 2 3

1 2

3 4 5

My linked lists would look like this:

http://prntscr.com/9bna1w

[TheIdeasMan]

What i need is,i need to make multiple linked lists, but at the begining i dont know how many lists i will need, so it has to be dynamic.

What is the actual real life situation you are trying to model?

I came up with this:

std::vector<std::list</*type*/>> MultiList

The type could be a struct which holds the 4 pieces of info

But there might be other solutions, if we find out what it is about.

[GuitarMan]

We are not allowed to use vector. We have to make our own functions and structures. The idea is pretty much simple.

http://prntscr.com/9boe1j

So this is a basic image that im gona explain in a sec.

This is the input file:

1 A 101 4 1001 1002 1003 1004

2 A 102 4 1005 1006 1003 1004

3 A 103 3 1003 1006 1007

4 A 104 14 1020 1019 1018 1017 1016 1015 1014 1013 1012 1011

5 K 1003

Each line describes a field.

1 is just random number.
A stands for Add to add new field
101 is the ID of th field
4 stands for how many points describe the field
1001,1002 etc are the ids of the points.

K stands for coordinates. Basicly it prints out which fields contains the point
Like 5 K 1003 ould print out 101, 102 and 103.

So my idea was, if i could place each line into a linked list, i could just search for the required coordinate in the lists and print out them.

I was thinking about graphs, but i have no knowledge or understanding on how to implement them.

[GuitarMan]

It might work with my 4 way list. The thing is, i know how to make a linked list, ive no idea how to make linked list into a linked list...

[cire]

A list of lists is effectively a 4 way list.

Keep a list of field ids. With each field id keep a list of the point ids for that field.

It isn't so complicated as you make it out to be. ;)

[GuitarMan]

I'm facing a problem already.

#include <fstream>
#include <iostream>
using namespace std;

int main ()
{
    ifstream fin;
    string var;
    int Prev = 0;
    fin.open("something.txt");
    fin >> var;
    cout << var << endl;
    if(var == 'A')PrevVar = 1;
    while(fin)
    {
        fin >> var;
        if(PrevVar == 1)
        {
            cout << "ID of the field: " << var << endl
            PrevVar = 0;
        }
        if(PrevVar == 0)
        {
            cout << var << endl;
        }
    }
    fin.close();
    return 0;
}

The ID of the field comes right after letter "A" in the input file. I can't check if variable is equal to 'A' or not.. So my idea was to set PrevVar equal to 1 as soon as it finds letter A inside the text file and then in the next iterration just save the ID of the field. But yea, it wont let me to compare string to char and i cant use strcmp coz we're supposed to make our own functions...

[cire]

if (var == "A") prevVar=1;

Although, it may be simpler to extract that field as a character, since that is what it is.

[dhayden]

101 is the ID of th field
4 stands for how many points describe the field
1001,1002 etc are the ids of the points.

So you need something like this:

class Field {
public:
    unsigned ID;
    list<int> pointIDs;
};

And since your program contains a bunch of fields:
list<Field> fields;

101 is the ID of th field
4 stands for how many points describe the field
1001,1002 etc are the ids of the points.

So you need a method to read a field:

bool Field::read(istream &is)
{
    read the ID and the number of points
    for (int i = 0; i < numPoints ++i) {
        read the point id and append it to the points list.
    }
    return is.good();
}

Each line is basically a number, a character that defines and operation, and then operation-specific data:

int num
std::string oper;
while (cin >> num >> oper) {  // read number and operation
    if (oper == "A") {
         Field f;
         f.read(cin);    // read the field
         fields.push_back(f);   // add it to the list
    } else if oper == "K") {
         int id;
         cin << id;
         // find the fields with this point ID.
    } else {
        // bad operation, or your got out of sync with the input file.
        cout << "line " << num << ": oper " << oper << " is a bad operation\n";
    }
}

[GuitarMan]

Thanks for the idea, but i guess it wont fit for me coz, we are not allowed to use most of the libs like list<>. Also, i find it hard to understand because the code looks too advanced for me xD


Anyways, what i was trying to do here is, i made a struct for the 2 way linked list and class for it. It saves all field IDs into a linked list. Each node can point to the next node, prev node and node that is down to it.

#include <fstream>
#include <iostream>
using namespace std;

    struct node
    {
        string FieldID;
        node *next;
        node *prev;
        node *down;
        node(string ID) {FieldID = ID; next=NULL; prev = NULL;};
    };


    class HorizontalList
    {
        node *first;
        node *last;

    public:
        HorizontalList(){first = NULL; };//Constructor.

        void add(string ID)
        {
            node *n = new node(ID);
            if(first == NULL) first = last = n;
            else
            {
                n->prev = last;
                last-> next = n;
                last = n;
            }
        }
        void print()
        {
            for(node *n = first; n!=NULL; n=n->next)
            {
                cout << n->FieldID<< " ";
            }
            cout << endl;
        }



        ~HorizontalList()// destructor
        {
            while(first)
            {
                node *p = first-> next;
                delete first;
                first = p;
            }
        }
    };


int main()
{

    ifstream fin;
    string var;
    HorizontalList h;
    int PrevVar = 0;

    fin.open("parcels.i2");
    fin >> var;
    //cout << var << endl;
    if(var == "A")PrevVar = 1;
    while(fin)
    {
        fin >> var;
        if(PrevVar == 1)
        {
            //cout << "ID of the field: " << var << endl;
            h.add(var);// This would add the ID of the field to the list.
            PrevVar = 0;
        }
        if(PrevVar == 0)
        {
            if(var == "A")PrevVar = 1;
            //else
            //cout << var << endl;
        }
    }
    h.print();
    fin.close();

    return 0;
}

The question is, is it possible to add 2 way linked list to each ID field?

http://prntscr.com/9caf75

Like this?

If not, il just go for 4 way linked list...

[JayhawkZombie]

So, by that you mean you want a list of 3-way lists that each have one pointer to a 2-way list? Sure, that can be done, but now that you're incorporating different list sizes, this could start getting complicated.

I understand you aren't allowed to use most of the standard library (I hate when teachers do this, but I also understand why), so we'll have to do it with raw pointers and very careful memory allocation. A 4-way list will grow in size extremely fast, and it will have to be traversed recursively, and that recursion could get out of hand if we aren't careful. Your idea of a 3-way list where each node points to a 2-way list actually seems like it might be easier to manage than a straight 4-way list.

The Standard Template Library isn't too bad once you get used to the syntax. It's all templated, so the syntax can get kind of gross at times.

Both of the lists you suggested are possible. However, the 2-way list attached to a 3-way list implementation seems much easier, and would be less prone to runaway recursion.

[GuitarMan]

I can' t figure out how to read the info from the file the correct way.
From the code above i didnt really get it how it works.

Well ok, starting from the 1st line.

So i read the 1st number and the method. If Method equals A, it should read the amount of coords that the field has. When i know how many points are inside the field, i can just make a loop that loops x(amount of points inside a field) and reads coordinates one by one and add them into the list. So ok, i can read the 1st ID and the method by " fin >> ID >> method" Then lets say i want to read fin >> AmountOfCords; which comes right after the method.... how do i do that? And how do i move to a new line and start reading from a new line? As much as i understood fin >> id >> method would always start from the begining of the file....

int main()
{

    ifstream fin;
    int ID = 0; 
    char method;
    int FieldID = 0;
    int AmountOfCords = 0;
    int Coordinate = 0; 
    List h;
    fin.open("something.txt");
    fin >> ID >> method;
    while(fin >> ID >> method)
    {
        switch(method)
        {
            case "A"://If the Method equals A
                {
                      
                }
            break;
        }
    }
    h.print();
    fin.close();

    return 0;
}

[ne555]

> We are not allowed to use vector.
> we are not allowed to use most of the libs like list<>.
> We have to make our own functions and structures.
>> so we'll have to do it with raw pointers and very careful memory allocation.
Or you can go ahead and create your own class that encapsulates the list behaviour.
Let's call it nih::list<T>

struct field{
   int id;
   nih::list< int > points;
};

nih::list< field > foo;

you can do

namespace nih{
   template <class T>
   using list = std::list< T >;
}

to test your algorithms before having to create your own list., then just make sure to make it compatible.


> K stands for coordinates. Basicly it prints out which fields contains the point
If that's what you're interested in, then you may do it backwards.
Make a dictionary where the `key' is the point and the `value' is a list of the fields that have it.


> So ok, i can read the 1st ID and the method by " fin >> ID >> method" Then
> lets say i want to read fin >> AmountOfCords; which comes right after the
> method.... how do i do that?
you may do fin >> AmountOfCords;

> And how do i move to a new line and start reading from a new line?
you know how many points will come to the end of the line, simply read those.

while(fin >> ID >> method){
   if(method == 'A'){
      fin >> AmountOfCords;
      int point;
      for(int K=0; K<AmountOfCords; ++K){
         fin>>point;
         //...
      }
   }
   else if(method == 'K'){
      //...
   }
}

[GuitarMan]

So i'm facing another problem.

http://prntscr.com/9caf75

I was trying to make the structure like this. But the problem is, when im trying to attach Vertical 2 way linked list to the horizontal 3 way linked list, it says it can not convert the nodes.

Here's my code:

   struct Hnode
    {
        int FieldID;
        Hnode *next;
        Hnode *prev;
        Hnode *down;
        Hnode(int ID) {FieldID = ID; next=NULL; prev = NULL;};
    };
    struct Vnode
    {
        int Coordinate;
        Vnode *upper;
        Vnode *lower;
        Vnode(int CoordID) {Coordinate = CoordID; upper=NULL; lower = NULL;};
    };

    class List
    {
        Hnode *first;
        Hnode *last;
        Vnode *Vfirst;
        Vnode *Vlast;

    public:
        List(){first = NULL; };//Constructor.

        void AddHorizontal(int ID)
        {
            Hnode *n = new Hnode(ID);
            if(first == NULL) first = last = n;
            else
            {
                n->prev = last;
                last-> next = n;
                last = n;
            }
        }
        void AddVertical(int ID, int CoordID)
        {
            Vnode *k = new Vnode(CoordID);
            for(Hnode *n = first; n!=NULL; n=n->next)//Goes threw the vertical list.
            {
                if(n->FieldID == ID)//If it finds the required ID
                {
                    if(n->down == NULL)//If n->Down has no value
                    {
                        k-> upper = n;// IT attaches value K to it. This is where it goes wrong.
                        Vfirst = k;
                        Vlast = k;
                    }
                    else
                    {
                        k->upper = Vlast;
                        Vlast -> lower =  k;
                        Vlast = k;
                    }


                }
            }
            if(first == NULL) first = last = n;
            else
            {
                n->prev = last;
                last-> next = n;
                last = n;
            }
        }

Error message:
cannot convert 'Hnode*' to 'Vnode*' in assignment|

[alex067]

The awesome thing about abstract data types is that.. they are abstract!

theoretically you can have a linked list point up, down, left, right, up left, down left, up right, down right, etc.. but the more pointers you have, the more management you need to do and a memory leak is gonna happen right around the corner

[GuitarMan]

Alright, i know whats wrong.
So, k-> upper = n;
K = Vnode.
N = Hnode. so yea, it wont let me to point Vnode to Hnode. What i came up with was in Struct Vnode changed Vnode upper to Hnode upper. So that the Upper actualy points to a Hnode. The problem is, i cant add any vertical nodes to it coz the Upper actualy points to Hnode not the Vnode...

http://prntscr.com/9d82id

Any possible solutions to connect Horizontal list to vertical list?

    struct Hnode
    {
        int FieldID;
        Hnode *next;
        Hnode *prev;
        Hnode *down;
        Hnode(int ID) {FieldID = ID; next=NULL; prev = NULL;};
    };

    struct Vnode
    {
        int Coordinate;
        Hnode *upper;
        Vnode *lower;
        Vnode(int CoordID) {Coordinate = CoordID; upper=NULL; lower = NULL;};
    };
    class List
    {
        Hnode *first;
        Hnode *last;
        Vnode *Vfirst;
        Vnode *Vlast;

    public:
        List(){first = NULL; };//Constructor.

        void AddHorizontal(int ID)
        {
            Hnode *n = new Hnode(ID);
            if(first == NULL) first = last = n;
            else
            {
                n->prev = last;
                last-> next = n;
                last = n;
            }
        }
        void AddVertical(int ID, int CoordID)
        {
            Vnode *k = new Vnode(CoordID);
            for(Hnode *n = first; n!=NULL; n=n->next)//Goes threw the vertical list.
            {
                if(n->FieldID == ID)//If it finds the required ID
                {
                    if(n->down == NULL)//If n->Down has no value
                    {
                        k-> upper = n;// IT attaches value K to it. This is where it goes wrong.
                        Vfirst = k;
                        Vlast = k;
                    }
                    else
                    {
                        k->upper = Vlast;
                        Vlast -> lower =  k;
                        Vlast = k;
                    }
                }
            }
            if(first == NULL) first = last = n;
            else
            {
                n->prev = last;
                last-> next = n;
                last = n;
            }
        }

[cire]

You're making this more complicated than it needs to be. As I said before, a list of lists is sufficient for your needs. A specialized data structure doesn't buy you anything but headache.

But, if you do insist on it:

struct Vnode;

struct Hnode
{
    int FieldID;
    Hnode *next;
    Hnode *prev;
    Vnode *down;
    Hnode(int ID) : FieldID(ID), next(nullptr), prev(nullptr), down(nullptr) {}
};

struct Vnode
{
    int Coordinate;
    Vnode *lower;
    Vnode(int CoordID) : Coordinate(CoordID), lower(nullptr) {}
};

class List
{
    Hnode * head;
    // possibly a tail pointer, but no pressing need for it.

    Hnode* contains(int ID) const       // utility function
    {
        Hnode* node = head;

        while (node && node->FieldID != ID)
            node = node->next;

        return node;
    }

    Hnode* add(int ID)      // utility function:
    {                       // Add an ID if it is not already in the list.
        Hnode* node = contains(ID);
        if (!node)
        {
            node = new Hnode(ID);
            node->next = head;
            if (head) head->prev = node;
            head = node;
        }

        return node;
    }

    static void add(Hnode* list, int CoordID)  // duplicates are not disallowed
    {
        Vnode * node = new Vnode(CoordID);
        node->lower = list->down;
        list->down = node;
    }

public:
    List() : head(nullptr) {}
    ~List();                    // Make sure you implement this.

    void AddHorizontal(int ID)
    {
        add(ID);
    }

    void AddVertical(int ID, int CoordID)
    {
        Hnode* hList = add(ID);
        add(hList, CoordID);
    }

    // ...
};

[GuitarMan]

Alright, thanks alot for this.
I did not use the code tho, i just took some ideas from it. I enjoy writing my own stuff. Anyways, thanks alot. I still got one last problem left.

If the input file line is like this:

3 P 101

this is what output file should look like.
3 P 101 1001 1002 1003 1004

Basicly, it prints out all the points that field with id 101 has.

So basicly yea, I cant figure out how to print out the field ids.

fout << ID << " "<< method << " "<<FieldID<<" ";So yea, this is how i can put the line w/o coordinates into the output file.

I made a function inside the class that prints out Field coordinates if there is an ID of a field given:

        void FindCord(int GivenField)
        {
            for(Hnode *n = first; n!=NULL; n=n->next)//Goes threw the vertical list.
            {
                if(n->FieldID == GivenField)//If it finds
                {
                    cout << "\n"<<GivenField<<" ";
                    for(Vnode *k = n->down; k!=NULL; k=k->lower)
                    {
                        cout << k->Coordinate<< " " ;
                    }
                }
            }
        }

This is from the main function. This part just calls the function:

       if(method == 'P')
        {
            fin >> FieldID;
            h.FindCord(FieldID);
            fout << ID << " "<< method << " "<<FieldID<<" ";
        }

So yea, basicly, if i could just somehow replace that cout << k->Coordinate<< " "; to something like fout << k->coordinate<<" "<<; That would be great, but i've no idea how to...

[cire]

        void FindCord(int GivenField)
        {
            for(Hnode *n = first; n!=NULL; n=n->next)//Goes threw the vertical list.
            {
                if(n->FieldID == GivenField)//If it finds
                {
                    cout << "\n"<<GivenField<<" ";
                    for(Vnode *k = n->down; k!=NULL; k=k->lower)
                    {
                        cout << k->Coordinate<< " " ;
                    }
                }
            }
        }

First, let me say that this is not at all intuitive. A FindCord (sic) function should find a coord. Not print something, much less somethings.

But:

        void FindCord(int GivenField, std::ostream& os)
        {
            for(Hnode *n = first; n!=NULL; n=n->next)//Goes threw the vertical list.
            {
                if(n->FieldID == GivenField)//If it finds
                {
                    // os << "\n"<<GivenField<<" ";
                    for(Vnode *k = n->down; k!=NULL; k=k->lower)
                    {
                        os << k->Coordinate<< " " ;
                    }
                }
            }
        }

       if(method == 'P')
        {
            fin >> FieldID;
            fout >> ID << ' ' << method << ' ' << FieldID << ' ';
            h.FindCord(FieldID, fout);
        }

Possibly add a default parameter (say, os = std::cout) in the class definition so you don't have to change code that expects output on std::cout.

[GuitarMan]

Thanks, that helped alot.
Now i'm really on my last task :D
I'm trying to make a function that deletes a field. So basicly, what i was trying to do is, find the ID of the field in the horizontal list(n) and delete all of its childs that goes down in vertical list from the horizontal list node(n). It seems to work fine with the vertical list, but somehow i'm getting lost wen deleting a node from the horizontal list.

        void DeleteField(int GivenField)
        {
           for(Hnode *n = first; n!=NULL; n=n->next)//Goes threw the vertical list.
            {
                if(n->FieldID == GivenField)//If it finds the ID
                {
                    while(n->down->lower != NULL)//This deletes nodes from the vertical list, works fine.
                    {
                        Vfirst = n->down;
                        Vnode *g = Vfirst->lower;
                        n->down = g;
                        delete Vfirst;
                        Vfirst = g;
                    }
                    if(n==first)// If n is the first node in the horizontal list
                    {
                        Hnode *p = first-> next;
                        delete first;//it deletes it. 
                        first = p;
                        //cout << first->FieldID<< endl;
                    }
                    else if(n!=first && n->next != NULL)//If n is between two nodes.
                    {
                        for(Hnode *Temp = first; Temp!=NULL; Temp=Temp->next)
                        {
                            if(Temp->next->FieldID == GivenField)
                            {
                                Hnode *p = Temp->next;;
                                Temp->next = Temp->next->next;
                                delete p;
                                cout << first->FieldID<< endl;
                                break;
                            }
                        }
                    }
                    else if(n!= first && n->next == NULL)//if n is the last node in the horizontal list. 
                    {
                        for(Hnode *Temp = first; Temp!=NULL; Temp=Temp->next)
                        {
                            if(Temp->next->FieldID == GivenField)
                            {
                                delete last;
                                last = Temp;
                                break;
                            }
                        }
                    }
                }
            }
        }
        void Hprint()
        {
            for(Hnode *n = first; n!=NULL; n=n->next)
            {
                 cout << n->FieldID<< " ";
            }
            cout << endl;
        }

Hprint prints out the horizontal list. So yea, if the node that i'm trying to delete is in the begining of the list, i just delete it. I even made some checks that, the 2nd element is the First element in the list after that. But the problem is, it wont print the list anymore. I guess somehow it wont point to the first element of the horizontal list and that's why i can't print the list. Same problem when im trying to delete the last node from the horizontal list or the middle node....

[cire]

This function is all kinds of weirdness. I would strongly suggest you type out some pseudo code describing what you want to do and notice how it differs from what you're actually doing.

There are two loops required for this function to do its job. You have 4.

Btw, are you still going with the doubly linked list? If so, do you plan on updating prev pointers?