Thread: Remove duplicates items in list using GLib

  1. #1
    Registered User
    Join Date
    Jul 2012
    Posts
    8

    Remove duplicates items in list using GLib

    I have this structures:

    Code:
        typedef struct {
        {
                GList *presets;
        } Settings;
    
        typedef struct Preset preset;
        struct Preset
        {
                gchar *name;
                gfloat freq;
        };
    
    
        GList *node;
        Settings settings;
    
        for (node = settings.presets; node; node = node->next) {
            GtkTreeIter  iter = {0};
            preset      *ps;
            gchar       *buffer;
    
            ps = (preset *) node->data;
            buffer = g_strdup_printf ("%0.2f", ps->freq);
            gtk_list_store_append (GTK_LIST_STORE (store), &iter);
            gtk_list_store_set (GTK_LIST_STORE (store),
                                        &iter,
                                        0, ps->title,
                                        1, buffer,
                                        -1);
            g_free (buffer);
        }

    I want to remove duplicates items in list if them have same freq value.

    Example output with duplicate freq:

    PHP Code:
    name             freq

        unammed         87.80
        Radio ZU          92.20
        Napoca FM     104.50
        unammed         92.20
        Rock FM        102.20 
    Want output:

    PHP Code:
    Europa FM        92.20
              unammed          87.80
              Radio ZU           92.20
              Napoca FM       104.50
              Rock FM           102.20 
    Please help to write code to remove duplicates.
    Last edited by Buda; 08-25-2014 at 09:54 AM.

  2. #2
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    Would you not just iterate over the current list to decide whether or not to add a new frequency?
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  3. #3
    Registered User
    Join Date
    Jul 2012
    Posts
    8
    Quote Originally Posted by rogster001 View Post
    Would you not just iterate over the current list to decide whether or not to add a new frequency?


    Function to scan and append found freq to GList * stations:

    Code:
    typedef struct {
            GList *stations;
        } FreqScanData;
    
        gboolean scan_cb (gpointer data)
        {
            static gfloat  freq = FREQ_MIN - 4.0f/STEPS;
            FreqScanData  *fsd = data;
        
        g_assert (fsd);
        
            if (check_station (freq)) {
                gfloat *f;
    
                f = g_malloc (sizeof (gfloat));
            
                *f = freq;
                fsd->stations = g_list_append (fsd->stations, f);
            }
        
            freq += 1.0/STEPS;
        
            return TRUE;
        }
    Function to append freq from GList * stations to existing list GList * presets:

    Code:
    typedef struct {
        {
            GList *presets;
        } Settings;
    
        typedef struct Preset preset;
        struct Preset
        {
            gchar *name;
            gfloat freq;
        };
    
        void scan (void)
        {
            FreqScanData data;
            Settings settings;
            GList *node;
    
            for (node = data.stations; node; node = node->next) {
                preset *ps;
    
                ps = g_malloc0 (sizeof (preset));
                ps->name = g_strdup (_("unnamed"));
                ps->freq = * ((gfloat *) node->data);                        
                            
                settings.presets = g_list_append (settings.presets, ps);
                g_free (node->data);
            }
        }

    I want help with this case:

    If freq found and appended in data.stations list are already in settings.presets list, then _do not_ append them again.

    For example:

    scan data.stations list found:

    87.50
    92.20
    101.50
    104.50
    106.60



    and settings.presets list have these items:

    101.50
    92.20


    -> do not duplicate them in result list
    Last edited by Buda; 08-25-2014 at 11:27 AM.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    What have you tried? It looks like you are pretty clear on what to do, so you just need to do it and then come back here if you run into problems.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Jul 2012
    Posts
    8
    Quote Originally Posted by laserlight View Post
    What have you tried? It looks like you are pretty clear on what to do, so you just need to do it and then come back here if you run into problems.
    I try to write a function to remove duplicates from a unsorted linked list:
    Code:
    #include "glib.h"
    
    GList *remove_dup (GList *list)
    {
        GList *a, *b, *dup;
        a = list;
    
        /* Pick elements one by one */
        while (a != NULL && a->next != NULL) {
            b = a;
    
            /* Compare the picked element with rest of the elements */
            while (b->next != NULL) {
                /* If duplicate then delete it */
                if (a->data == b->next->data) {
                    /* sequence of steps is important here */
                    dup = b->next;
                    b->next = b->next->next;
                    g_list_free_1 (dup);
                } else  /* This is tricky */ {
                    b = b->next;
                }
            }
            a = a->next;
        }
    
        return list;
    }
    -> but it seems that it does not work.
    That is my mistake in this code?

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    How doesn't it work? Could you give an example of the list you input, as well as the result after you remove duplicates?

    As was mentioned before, you could also simply refuse to insert a duplicate. That is, on insert, you traverse the list, and check if the frequency already exists. If so, do nothing. If not, append.

    Also, you should take a more thorough look at the GLib reference manual (link). The g_slist_delete_link() function might be of use, but it does warn that it's not terribly efficient for repeated calls. For a small list it's probably okay, for a larger list not so much. Simply put, linked lists are just not built for operations like de-duplication. Other data structures like a binary tree or hash table may be useful here, if you care to look into them.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Well, are you going to create the list once and remove duplicates, or will you continually insert new elements and have to ensure that duplicates are removed. For the latter, combining anduril462's suggestion of using other data structures with rogster001's suggestion of not inserting duplicates to begin with should work pretty well even for long lists. For the former, sorting the list first then removing consecutive duplicates will work reasonably well for long lists, but it tends to be easier to do if your list is implemented with an array instead of a linked list.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    Hard to see any valid reason for building the list first complete with duplicates, then giving yourself, and the computer, the job of removing them. Would it outweigh the cost of checking the current list every time? It must be less expensive to do the iterations rather than build and then try and clear up the dupes. Is this a set study problem?

    Just wondering if efficiency gained with sorting routines after each conditional insert? It seems costly maybe?
    Last edited by rogster001; 08-26-2014 at 01:54 PM.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by rogster001
    Hard to see any valid reason for building the list first complete with duplicates, then giving yourself, and the computer, the job of removing them. Would it outweigh the cost of checking the current list every time? It must be less expensive to do the iterations rather than build and then try and clear up the dupes. Is this a set study problem?
    If you're doing linear search to check the current list, then a sort + remove consecutive duplicates approach is likely to be faster as the list gets bigger, as long as you only do this once. If you're using some other approach to check the current list, then I suppose it depends on the specifics.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User
    Join Date
    Jul 2012
    Posts
    8
    Quote Originally Posted by laserlight View Post
    If you're doing linear search to check the current list, then a sort + remove consecutive duplicates approach is likely to be faster as the list gets bigger, as long as you only do this once. If you're using some other approach to check the current list, then I suppose it depends on the specifics.
    Maybe best way is to puts all ps->freq from settings.presets list as key in a GhashTable

    I was wondering if it was possible to store a float as key into a GhashTable considering there is no GFLOAT_TO_POINTER macro methdod.

    I am following a tutorial I found online by IBM Manage C data using the GLib collections , but I can't seem to find a way to use an float as a key.

    Any help would be great thanks!

  11. #11
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    O_o

    You couldn't even give SO fifteen minutes?

    Soma
    “Salem Was Wrong!” -- Pedant Necromancer
    “Four isn't random!” -- Gibbering Mouther

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List (Create, Insert sorted, Remove duplicates)
    By programming123 in forum C Programming
    Replies: 6
    Last Post: 04-03-2014, 05:51 AM
  2. Two int Arrays, remove duplicates from second
    By Sorin in forum C Programming
    Replies: 5
    Last Post: 04-03-2013, 03:51 AM
  3. Strings and Structs (remove duplicates)
    By christianB in forum C Programming
    Replies: 44
    Last Post: 07-25-2011, 09:01 PM
  4. recursive remove duplicates from a string
    By transgalactic2 in forum C Programming
    Replies: 47
    Last Post: 12-20-2009, 02:02 AM
  5. Really basic remove duplicates from array
    By Chris Fowler in forum C++ Programming
    Replies: 7
    Last Post: 11-25-2002, 10:35 PM