src/sparse-array.cpp

/* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */
/*
 * frpuniverse
 * Copyright (C) Peter L. Berghold 2008 <Peter@Berghold.net>
 * 
 * frpuniverse is free software.
 * 
 * You may 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.
 * 
 * frpuniverse 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 frpuniverse.  If not, write to:
 *      The Free Software Foundation, Inc.,
 *      51 Franklin Street, Fifth Floor
 *      Boston, MA  02110-1301, USA.
 */
#ifdef DEBUG_ON
#include <stdio.h>
#include <stdlib.h>
#endif
#include "sparse-array.hpp"

sparseArray::sparseArray(){
        root = new sparseArrayNode(-1,-1);
}


sparseArrayNode* sparseArray::insertNewColumnHead(int c){
        sparseArrayNode* p = root;
        sparseArrayNode* n = new sparseArrayNode(-1,c);

        if ( root->getRight() == 0 ) {
                root->setRight(n);
                n->setRight(0);
                n->setDown(0);
                return n;
        }
        while(p->getRight()!=0){
                if ( p->getRight()->getColumn() ==  c ) {
                        return p->getRight();
                }
                if ( p->getRight() -> getColumn() > c ) {
                        n->setRight(p->getRight());
                        p->setRight(n);
                        n->setDown(0);
                        return n;
                }
                p=p->getRight();
        }
        p->setRight(n);
        n->setRight(0);
        n->setDown(0);
        return n;
}

                        
        


//
//  MMmmmm.. fun with pointers....
//
sparseArrayNode* sparseArray::findColumnHead(int c){
        sparseArrayNode* p = root;
#ifdef DEBUG_ON
        printf("Entering sparseArray::findColumnHead([%d])\n",c);
#endif
        while(p->getRight() != (sparseArrayNode*) 0 ) {
                p = p->getRight();
#ifdef DEBUG_ON
                printf("%d ",p->getColumn());
#endif
                if ( p->getColumn() == c ) {
#ifdef DEBUG_ON
                        printf("\nReturning from sparseArray::findColumnHead()\n");
#endif
                        return p;
                }
                if ( p->getColumn() > c ) {
#ifdef DEBUG_ON
                        printf("\nNeed new column header...\n");
#endif
                        return this->insertNewColumnHead(c);
                }
                
        }
        
#ifdef DEBUG_ON
        printf("\nFall through of loop... need new column heaader...\n");
#endif
        return this->insertNewColumnHead(c);
}


void sparseArray::add(sparseArrayNode* p){
        int r=p->getRow();
        int c=p->getColumn();
        
        this->addAt(r,c,p);
        
}

void sparseArray::addAt(int row,int column,sparseArrayNode* node){
#ifdef DEBUG_ON
        printf("Entering sparseArray::addAt([%d],[%d],<ptr>)\n",row,column);
#endif
        
        sparseArrayNode* p = this->findColumnHead(column);
        node->setRow(row);
        node->setColumn(column);
        
        
        if ( p->getDown() == 0 ) {
#ifdef DEBUG_ON
                printf("\tInserting new node just below the column header\n");
#endif
                p->setDown(node);
#ifdef DEBUG_ON
                printf("Returning from sparseArray::addAt()\n");
#endif
                return;
        } else { 
                while(p->getDown() != 0 ) {
#ifdef DEBUG_ON
                        printf("\tThis is [%d,%d] and below that is [%d,%d] (Tryig to insert [%d,%d]\n",

                                   p->getRow(),p->getColumn(),
                                   p->getDown()->getRow(),p->getDown()->getColumn(),
                                   row,column
                                   );
#endif
                        if ( p->getDown()->getRow() >= row ) {
#ifdef DEBUG_ON
                                printf("\t\tInserting here!\n");
#endif
                                node->setDown(p->getDown());
                                p->setDown(p);
#ifdef DEBUG_ON
                                printf("returning.\n");
#endif
                                return;
                        }
#ifdef DEBUG_ON
                        printf("\tGoing to the next node.\n");
#endif
                        p=p->getDown();
                }
                p->setDown(node);
                node->setDown(0);
        }
        
                                
}


sparseArrayNode* sparseArray::findAt(int row,int column){
        sparseArrayNode *p = this->findColumnHead (column);
        
        while(p->getDown() != (sparseArrayNode*)0){
                p = p->getDown();
                if ( p->getRow() == row ) 
                        return p;
        }
        if ( p->getRow() != row )
                return (sparseArrayNode*)0;
        else 
                return p;
        
}

#ifdef DEBUG_ON
void sparseArray::dump(){
        sparseArrayNode* r;
        sparseArrayNode* c;
        printf("Rotated dump of the sparse array\n");
        c=root;
        while(c->getRight()!=0){
                c=c->getRight();
                r=c;
                printf("[%d,%d] ",r->getRow(),r->getColumn());
                while(r->getDown()!=0){
                        r=r->getDown();
                        printf("[%d,%d] ",r->getRow(),r->getColumn());
                }
                printf ("\n");
        }
        printf ("\n");
}

#endif

---