<![CDATA[
/*
Copyright (c) 1999, Gary Yihsiang Hsiao. All Rights Reserved.
bugs report to: ghsiao@rbcds.com or ghsiao@netzero.net
Permission to use, copy, modify, and distribute this software
for NON-COMMERCIAL purposes and without fee
is hereby granted provided that this copyright notice
appears in all copies. This software is distributed on an 'as is'
basis without warranty.
Release: 1.0 05-Sep-1999
*/
#include "objAvl.h"
// Show an objAvl and all its parts
ostream&
operator<<(ostream& os, objAvl& ob)
{
deque<objAvl::SIZE_POS> _avl = ob._avl;
os << "_max=" << ob._max << endl;
os << "_acc_size="<< ob._acc_size << endl;
os << "_pad_size=" << ob._pad_size << endl;
os << "deque(" <<_avl.size() << "):" << endl;
if(_avl.size() > 0) {
deque<objAvl::SIZE_POS>::const_iterator itr = _avl.begin();
while(itr != _avl.end()) {
objAvl::SIZE_POS ps = *itr++;
os << "size=" << ps.first << " "
<< "loc=" << ps.second << endl;
}
}
return os;
}
objAvl::objAvl():_max(3), _pad_size(0)
{
_acc_size = _max;
}
objAvl& objAvl::operator=(const objAvl& t)
{
_acc_size = t._acc_size;
_pad_size = t._pad_size;
_avl = t._avl;
return *this;
}
objAvl::~objAvl()
{
}
bool objAvl::isEmpty()
{
return _avl.empty();
}
bool objAvl::getAvl(size_t size, streampos& loc)
{
if(!_avl.size()) return false;
size_t idx;
if(!deque_best_bsearch(size, idx)) return false;
getpos(idx, size, loc);
return true;
}
bool objAvl::deque_best_bsearch(size_t size, size_t& idx)
{
if(size > _avl.back().first) return false;
if(size <= _avl.front().first) {
idx = 0;
return true;
}
int mid, lower = 0, upper = _avl.size() - 1;
while(lower <= upper) {
mid = (lower+upper)/2;
if(size == _avl[mid].first) {
idx = mid;
return true;
}
else if(size > _avl[mid].first) lower = mid + 1;
else {
upper = mid - 1;
if(size > _avl[upper].first) {
idx = mid;
return true;
}
}
}
return false;
}
void objAvl::getpos(int idx, int size, streampos& loc)
{
loc = _avl[idx].second;
if( size < _avl[idx].first ) {
_avl[idx].second += size;
_avl[idx].first -= size;
sort_by_size(0, _avl.size() - 1);
}
else { //* find exact same size
_avl.erase(_avl.begin()+idx);
}
}
void objAvl::addAvl(size_t size, streampos loc)
{
size_t idx;
SIZE_POS ps(size, loc);
if(_avl.size() > 0) {
if(!deque_best_bsearch(size, idx))
_avl.push_back(ps);
else
_avl.insert(_avl.begin()+idx, ps);
}
else _avl.push_back(ps);
}
size_t objAvl::deqsize()
{
return _avl.size();
}
objAvl::operator const string& ()
{
clear();
removepad();
if((_pad_size = _acc_size - _avl.size()) < 0) {
spaceRecollection();
if((_pad_size = _acc_size - _avl.size()) < 0) {
_acc_size += _max/2;
_pad_size = _acc_size - _avl.size();
}
}
SIZE_POS ps(0, 0);
_avl.insert(_avl.begin(), _pad_size, ps);
*this << _acc_size;
*this << _pad_size;
*this << _avl;
return getData();
}
void objAvl::operator=(const string& str)
{
putData(str);
*this >> _acc_size;
*this >> _pad_size;
*this >> _avl;
removepad();
}
void objAvl::removepad()
{
deque<SIZE_POS>::iterator itr = _avl.begin();
while(_pad_size) {
_avl.erase(itr++);
--_pad_size;
}
}
bool objAvl::isEmptySlot(streampos pos, size_t& size)
{
deque<SIZE_POS>::const_iterator itr = _avl.begin();
while(itr != _avl.end()) {
objAvl::SIZE_POS sp = *itr++;
if(sp.second == pos) {
size = sp.first;
return true;
}
}
return false;
}
void objAvl::swap(int i, int j)
{
SIZE_POS tmp = _avl[i];
_avl[i] = _avl[j];
_avl[j] = tmp;
}
// sort by the second element -- the position
void objAvl::sort_by_pos(int low, int high)
{
if(low < high) {
int lo = low;
int hi = high+1;
SIZE_POS elem = _avl[low];
for(;;) {
while(_avl[++lo].second < elem.second && lo < high) ;
while(_avl[--hi].second > elem.second && hi > 0) ;
if(lo < hi)
swap(lo, hi);
else break;
}
swap(low, hi);
sort_by_pos(low, hi-1); // divide and conquer
sort_by_pos(hi+1, high);
}
}
// sort by the first element -- the size
void objAvl::sort_by_size(int low, int high)
{
if(low < high) {
int lo = low;
int hi = high+1;
SIZE_POS elem = _avl[low];
for(;;) {
while(_avl[++lo].first < elem.first && lo < high) ;
while(_avl[--hi].first > elem.first && hi > 0) ;
if(lo < hi)
swap(lo, hi);
else break;
}
swap(low, hi);
sort_by_size(low, hi-1);
sort_by_size(hi+1, high);
}
}
size_t objAvl::spaceRecollection()
{
if(_avl.size() <= 1) return _avl.size();
sort_by_pos(0, _avl.size() - 1);
for(int i = 0; i < _avl.size() - 1; i++)
{
SIZE_POS elem = _avl[i];
if((_avl[i].first + _avl[i].second) == _avl[i+1].second) {
_avl[i].first = _avl[i].first + _avl[i+1].first;
_avl.erase(_avl.begin()+(i+1));
--i;
}
}
sort_by_size(0, _avl.size() - 1);
return _avl.size();
}
]]>