imbuffer.h

Go to the documentation of this file.

/****************************************************************************
 *
 *  MODULE:     iostream
 *
 
 *  COPYRIGHT (C) 2007 Laura Toma
 *
 *
 
 *  Iostream is a library that implements streams, external memory
 *  sorting on streams, and an external memory priority queue on
 *  streams. These are the fundamental components used in external
 *  memory algorithms.
 
 * Credits: The library was developed by Laura Toma.  The kernel of
 * class STREAM is based on the similar class existent in the GPL TPIE
 * project developed at Duke University. The sorting and priority
 * queue have been developed by Laura Toma based on communications
 * with Rajiv Wickremesinghe. The library was developed as part of
 * porting Terraflow to GRASS in 2001.  PEARL upgrades in 2003 by
 * Rajiv Wickremesinghe as part of the Terracost project.
 
 *
 *  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 program 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.  *
 *  **************************************************************************/
 
#ifndef __IMBUFFER_H
#define __IMBUFFER_H
 
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
 
#include "ami_config.h" //for SAVE_MEMORY
#include "ami_stream.h"
#include "mm.h"
#include "mm_utils.h"
#include "pqheap.h"
 
/* to do: - iterative sort */
 
/*****************************************************************
 *****************************************************************
 *****************************************************************
 
 in memory buffer (level-0 buffer):
 
 Functionality:
 
 Stores an array of data in memory; when it becomes full, sorts the
 data and copies it on secondary storage in a level-1 buffer; data is
 stored contiguously from left to right;
 
 assume: class T supports < and getPriority and getValue; elements in
 buffer are sorted according to < relation
 
 *****************************************************************
 *****************************************************************
 *****************************************************************/
 
template <class T>
class im_buffer {
 
private:
    // maximum capacity of buffer
    unsigned long maxsize;
 
    // index of next empty entry in buffer; between 0 and maxsize;
    // initialized to 0
    unsigned long size;
 
    // stored data
    T *data;
 
    bool sorted; // true if it is sorted; set when the buffer is sorted
                 // to prevent sorting it twice
 
public:
    // create a buffer of maxsize n
    im_buffer(long n) : maxsize(n), size(0), sorted(false)
    {
        assert(n >= 0);
 
        char str[100];
        snprintf(str, sizeof(str), "im_buffer: allocate %ld\n",
                 (long)(maxsize * sizeof(T)));
        MEMORY_LOG(str);
 
        data = new T[maxsize];
        assert(data);
    }
 
    // copy constructor
    im_buffer(const im_buffer &b);
 
    // free memory
    ~im_buffer()
    {
        if (data)
            delete[] data;
    }
 
    // insert an item in buffer in next free position; fail if buffer full
    bool insert(T &x);
 
    // insert n items in buffer; return the number of items actually inserted
    unsigned long insert(T *x, unsigned long n);
 
    //(quick)sort (ascending order) the buffer (in place);
    // the buffer is overwritten; recursive for the time being..
    void sort();
 
    // return maxsize of the buffer (number of elements);
    unsigned long get_buf_maxlen() const { return maxsize; }
 
    // return current size of the buffer(number of elements);
    unsigned long get_buf_len() const { return size; }
 
    // return true if buffer full
    bool is_full() const { return (size == maxsize); }
 
    // return true if buffer empty
    bool is_empty() const { return (size == 0); }
 
    // return i'th item in buffer
    T get_item(unsigned long i) const
    {
        assert(i < size);
        return data[i];
    }
 
    // return data
    T *get_array() const { return data; }
 
    // write buffer to a stream; create the stream  and return it
    AMI_STREAM<T> *save2str() const;
 
    // set i'th item in buffer
    void set_item(unsigned long i, T &item)
    {
        assert((i >= 0) && (i < size));
        data[i] = item;
        sorted = false;
    }
 
    // reset buffer (delete all data); if SAVE_MEMORY is on, free also the space
    void reset()
    {
        size = 0;
        sorted = false;
#ifdef SAVE_MEMORY
        delete[] data;
        data = NULL;
#endif
    }
 
    // reset buffer (delete all data); don't delete memory
    void clear()
    {
        size = 0;
        sorted = false;
    }
 
    // reset buffer: keep n elements starting at position start
    void reset(unsigned long start, unsigned long n);
 
    // shift n items to the left: in effect this deletes the first n items
    void shift_left(unsigned long n);
 
    // print the elements in the buffer
    friend ostream &operator<<(ostream &s, const im_buffer &b)
    {
        s << "(buffer:) [";
        for (int i = 0; i < b.size; i++) {
            s << b.data[i] << ", ";
        }
        return s << "]";
    }
 
    // print range: prints the range of the items in buffer
    void print_range() const;
 
    // print
    void print() const;
 
private:
    // sort the buffer (recursively)
    void sort_rec(unsigned long start, unsigned long end);
 
    // partition the buffer and return the position of the pivot
    unsigned long partition(unsigned long start, unsigned long end);
};
 
/************************************************************/
// copy constructor
template <class T>
im_buffer<T>::im_buffer(const im_buffer &b)
{
 
    MEMORY_LOG("im_buffer: copy constructor start\n");
    maxsize = b.maxsize;
    size = b.size;
    sorted = b.sorted;
    assert(data);
    for (unsigned long i = 0; i < size; i++) {
        data[i] = b.data[i];
    }
    MEMORY_LOG("im_buffer: copy constructor end\n");
}
 
/************************************************************/
// insert an item in buffer; fail if buffer full
template <class T>
bool im_buffer<T>::insert(T &x)
{
 
    if (size == maxsize) {
        return false; // buffer full
    }
#ifdef SAVE_MEMORY
    if (!data) {
        data = new T[maxsize];
    }
#endif
    assert(data);
    assert(size < maxsize);
    data[size] = x;
    size++;
    sorted = false; // not worth checking..
    return true;
}
 
/************************************************************/
// insert n items in buffer; return the number of items actually inserted
template <class T>
unsigned long im_buffer<T>::insert(T *x, unsigned long n)
{
 
    assert(x);
    for (unsigned long i = 0; i < n; i++) {
        if (!insert(x[i])) {
            return i;
        }
    }
    assert(sorted == false);
    return n;
}
 
/************************************************************/
//(quick)sort (ascending order) the buffer (in place);
// the buffer is overwritten; recursive for the time being..
template <class T>
void im_buffer<T>::sort()
{
    if (!is_empty()) {
        if (!sorted) {
            // use my quicksort - eventually must be iterative
            // sort_rec(0, size-1);
 
            // use system quicksort
            qsort((T *)data, size, sizeof(T), T::qscompare);
        }
    }
    sorted = true;
}
 
/************************************************************/
template <class T>
void im_buffer<T>::sort_rec(unsigned long start, unsigned long end)
{
    unsigned long q;
    if (start < end) {
        q = partition(start, end);
        sort_rec(start, q);
        sort_rec(q + 1, end);
    }
}
 
/************************************************************/
// partition the buffer in place and return the position of the
// pivot
template <class T>
unsigned long im_buffer<T>::partition(unsigned long start, unsigned long end)
{
    assert((start <= end) && (end < size) && (start >= 0));
    if (start == end) {
        return start;
    }
    T pivot = get_item(start), lit, rit;
    unsigned long l = start - 1, r = end + 1;
 
    while (1) {
 
        do {
            r = r - 1;
        } while (get_item(r) > pivot);
 
        do {
            l = l + 1;
        } while (get_item(l) < pivot);
 
        if (l < r) {
            lit = get_item(l);
            rit = get_item(r);
            set_item(l, rit);
            set_item(r, lit);
        }
        else {
            // printf("partition (%ld,%ld) return %ld\n", start, end, r);
            return r;
        }
    }
}
 
/************************************************************/
// reset buffer: keep n elements starting at position start
template <class T>
void im_buffer<T>::reset(unsigned long start, unsigned long n)
{
 
    if (start >= size) {
        // buffer is completely reset
        assert(n == 0);
        size = 0;
        sorted = false;
        return;
    }
    assert(start + n <= size);
    size = n;
    if (n) {
        memmove(data, data + start, n * sizeof(T));
    }
    // remains sorted
}
 
/************************************************************/
// shift n items to the left: in effect this deletes the first n items
template <class T>
void im_buffer<T>::shift_left(unsigned long n)
{
    assert(n <= size);
    // remains sorted
    if (n) {
        memmove(data, data + n, (size - n) * sizeof(T));
        size -= n;
    }
}
 
/************************************************************/
// print range of the (priority of) items in the buffer
template <class T>
void im_buffer<T>::print_range() const
{
 
    if (size == 0) {
        cout << "[]";
    }
    else {
#ifdef SAVE_MEMORY
        if (!data) {
            data = new T[maxsize];
        }
#endif
        assert(data);
 
        // determine min and  max
        T min, max;
        min = data[0];
        if (sorted) {
            max = data[size];
        }
        else {
            max = data[0];
            for (int i = 1; i < size; i++) {
                if (data[i] < min) {
                    min = data[i];
                }
                if (data[i] > max) {
                    max = data[i];
                }
            }
        }
        // print min and max
        cout << "[";
        cout << min.getPriority() << ".." << max.getPriority();
        cout << " (sz=" << size << ")"; // print also bufsize
        cout << "]";
    } // else (size==0)
}
 
/************************************************************/
// print (priority of) all items in buffer
template <class T>
void im_buffer<T>::print() const
{
    cout << "[";
    for (unsigned long i = 0; i < size; i++) {
        cout << data[i].getPriority() << ",";
    }
    cout << "]";
}
 
/************************************************************/
// write buffer to a stream; create the stream and return it;
// buffer must be sorted prior to saving (functionality of empq)
template <class T>
AMI_STREAM<T> *im_buffer<T>::save2str() const
{
 
    AMI_err ae;
 
    AMI_STREAM<T> *amis = new AMI_STREAM<T>();
    assert(amis);
 
    assert(sorted); // buffer must be sorted prior to saving;
    for (unsigned long i = 0; i < size; i++) {
        ae = amis->write_item(data[i]);
        assert(ae == AMI_ERROR_NO_ERROR);
    }
    return amis;
}
 
#endif