ordered_list.cpp

Go to the documentation of this file.

#ifndef ORDERED_LIST_IMPLEMENTATION_FILE
#define ORDERED_LIST_IMPLEMENTATION_FILE

/*****************************************************************************\
*                                                                             *
*  Name   : ordered_list                                                      *
*  Author : M McLeod                                                          *
*                                                                             *
*******************************************************************************
* Copyright (c) 2000-$now By Author.  This program 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 2 of   *
* the License or (at your option) any later version.  This is online at:      *
*     http://www.fsf.org/copyleft/gpl.html                                    *
* Please send any updates to: fred@gruntose.com                               *
\*****************************************************************************/

#include "ordered_list.h"

namespace nodes {

bool ordered_list::insert(ordered_node *new_node, int compare_mode, bool duplicates) {
// Uses the ordered_node's compare function to find where to insert.
// returns false if insert fails due to invalid parameter or unexpected condition.
    
    if (!new_node)
        return false;

    iterator iter = head();
    bool found = false;
    while (!found && !iter.is_tail()) {
        
        const node *cur_node = iter.observe();
        if (!cur_node) // list is empty
            found = true;
        else {
            const ordered_node *cur_onode = dynamic_cast<const ordered_node*>(cur_node);
            if (!cur_onode)
                return false;

            int cmp = cur_onode -> compare(*new_node, compare_mode);
            if (cmp < 0)
                found = true;
            else if (cmp == 0 && !duplicates) {
                delete new_node;    // I own it and I'm not going to insert it.
                return true;        // don't insert duplicate
            } else
                iter++;
        }
    }
    list::insert(iter, new_node);
    return true;
}


const ordered_node *ordered_list::find( const ordered_node *to_find, 
                                        int compare_mode,
                                        list::iterator *use_iter) const
{
// Attempts to find a match for "to_find" and returns a pointer to it if successful.
// "compare_mode" will be passed to ordered_node::compare() while searching.
// If "use_iter" is non-null, search will occur using the provided iterator and
// the returned node will be the closest one found to the iterator's current position.
// Otherwise, search begins at the head.

    if (!to_find)
        return NULL;

    iterator iter = head();            
    if (!use_iter)
        use_iter = &iter;

    while (true) {
        
        const node *cur_node = use_iter -> observe();
        if (!cur_node)
            return NULL; // list is empty.            
        
        const ordered_node *cur_onode = dynamic_cast<const ordered_node*>(cur_node);
        if (!cur_onode)
            return NULL; // cast failed.

        int cmp = cur_onode -> compare(*to_find, compare_mode);

        if (cmp == 0)
            return cur_onode;

        if (cmp < 0) {
            (*use_iter)--;
            if (use_iter -> is_head())
                return NULL;
        } else {
            (*use_iter)++;
            if (use_iter -> is_tail())
                return NULL;
        }
    }
}

} // namespace.

#endif //ORDERED_LIST_IMPLEMENTATION_FILE

---