/* -*- mode: c; c-basic-offset: 3; tab-width: 3; -*- * Copyright (c) 1998 Eivind Eklund * Copyright (c) 1996, 1997 DiMaga Studios & Innerloop Technologies * All rights reserved. * * This code was originally written for DiMaga Studios by Eivind * Eklund. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Neither the name of Eivind Eklund nor the names of DiMaga * Studios or Innerloop Technologies may be used to endorse or * promote products derived from this software without specific * prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * */ #ifndef HEAP_H #define HEAP_H /* .ta T .2i */ struct Test; void Heap_Add(struct Test* pHeap, /* Pointer to array of structures to use as heap (any structure type) */ int* pnEntries, /* Pointer to entries count (any integral type) */ struct Test* pItem, /* Item to add to heap */ int SortKeyName /* Name of key to sort on (type is NOT int) */ ); #define Heap_Add(pHeap,pNumEntries,pItem,SortKey) \ do { \ size_t _AccessPoint; /* Where are we checking for order now? */ \ _AccessPoint = (*(pNumEntries))++; /* Get current last-pos, and remove */ \ (pHeap)[_AccessPoint++] = *(pItem); \ while(_AccessPoint > 1) { \ size_t _ByteCount; /* For finding number of bytes to swap */ \ char* _pUp,* _pDown; /* Which nodes in tree to swap */ \ char _SwapTemp; /* Temporary swap variable */ \ if( (pHeap)[_AccessPoint/2-1].SortKey \ < (pHeap)[_AccessPoint-1].SortKey ) \ break; /* Heap OK */ \ _pUp = (char*)((pHeap)+(_AccessPoint/2-1)); \ _pDown = (char*)((pHeap)+(_AccessPoint-1)); \ for(_ByteCount=0; _ByteCount 1) { \ size_t _ByteCount; /* For finding number of bytes to swap */ \ char* _pUp,* _pDown; /* Which nodes in tree to swap */ \ char _SwapTemp; /* Temporary swap variable */ \ if( (pHeap)[_AccessPoint/2-1].SortKey \ < (pHeap)[_AccessPoint-1].SortKey ) \ break; /* Heap OK */ \ _pUp = (char*)((pHeap)+(_AccessPoint/2-1)); \ _pDown = (char*)((pHeap)+(_AccessPoint-1)); \ for(_ByteCount=0; _ByteCount= _len || \ (((pHeap)[_i-1].SortKey <= \ (pHeap)[_i*2-1].SortKey) \ && (_i*2+1 >= _len || \ (pHeap)[_i-1].SortKey <= (pHeap)[_i*2].SortKey))); \ } /*lint -save -e717 */ while(0) /*lint -restore */ #define Heap_Remove(pHeap,pNumEntries,vEntryToRemove,SortKey) \ do { \ size_t _vRemoving = (vEntryToRemove)+1; \ size_t _len = (size_t)((*(pNumEntries))--); \ while(_vRemoving*2-1<_len) { \ if( _vRemoving*2 != _len ) { \ if( (pHeap)[_vRemoving*2-1].SortKey \ < (pHeap)[_vRemoving*2].SortKey ) { \ (pHeap)[_vRemoving-1] = (pHeap)[_vRemoving*2-1]; \ _vRemoving *= 2; \ } else { \ (pHeap)[_vRemoving-1] = (pHeap)[_vRemoving*2]; \ _vRemoving = _vRemoving*2+1; \ } \ } else { \ (pHeap)[_vRemoving-1] = (pHeap)[_vRemoving*2-1]; \ break; /* We're done - last move */ \ } \ } \ /* If we haven't just down-adjusted the last element */ \ if( _vRemoving*2 != _len) { \ /* Move previous last element here */ \ (pHeap)[_vRemoving-1] = (pHeap)[_len-1]; \ /* Re-normalize for new element in this position */ \ while(_vRemoving > 1) { \ if( (pHeap)[_vRemoving/2-1].SortKey \ < (pHeap)[_vRemoving-1].SortKey ) \ break; /* Heap OK */ \ (pHeap)[_len-1] = (pHeap)[_vRemoving-1]; \ (pHeap)[_vRemoving-1] = (pHeap)[_vRemoving/2-1]; \ (pHeap)[_vRemoving/2-1] = (pHeap)[_len-1]; \ _vRemoving /= 2; \ } \ } \ } /*lint -save -e717 */ while(0) /*lint -restore */ #define RevHeap_Add(pHeap,pNumEntries,pItem,SortKey) \ do { \ size_t _AccessPoint; /* Where are we checking for order now? */ \ _AccessPoint = (*(pNumEntries))++; /* Get current last-pos, and remove */ \ (pHeap)[_AccessPoint++] = *(pItem); \ while(_AccessPoint > 1) { \ size_t _ByteCount; /* For finding number of bytes to swap */ \ char* _pUp,* _pDown; /* Which nodes in tree to swap */ \ char _SwapTemp; /* Temporary swap variable */ \ if( (pHeap)[_AccessPoint/2-1].SortKey \ > (pHeap)[_AccessPoint-1].SortKey ) \ break; /* Heap OK */ \ _pUp = (char*)((pHeap)+(_AccessPoint/2-1)); \ _pDown = (char*)((pHeap)+(_AccessPoint-1)); \ for(_ByteCount=0; _ByteCount= _len || \ (((pHeap)[_i-1].SortKey >= \ (pHeap)[_i*2-1].SortKey) \ && (_i*2+1 >= _len || \ (pHeap)[_i-1].SortKey >= (pHeap)[_i*2].SortKey))); \ } /*lint -save -e717 */ while(0) /*lint -restore */ #define RevHeap_Remove(pHeap,pNumEntries,vEntryToRemove,SortKey) \ do { \ size_t _vRemoving = (vEntryToRemove)+1; \ size_t _len = (size_t)((*(pNumEntries))--); \ while(_vRemoving*2-1<_len) { \ if( _vRemoving*2 != _len ) { \ if( (pHeap)[_vRemoving*2-1].SortKey \ > (pHeap)[_vRemoving*2].SortKey ) { \ (pHeap)[_vRemoving-1] = (pHeap)[_vRemoving*2-1]; \ _vRemoving *= 2; \ } else { \ (pHeap)[_vRemoving-1] = (pHeap)[_vRemoving*2]; \ _vRemoving = _vRemoving*2+1; \ } \ } else { \ (pHeap)[_vRemoving-1] = (pHeap)[_vRemoving*2-1]; \ break; /* We're done - last move */ \ } \ } \ /* If we haven't just down-adjusted the last element */ \ if( _vRemoving*2 != _len) { \ /* Move previous last element here */ \ (pHeap)[_vRemoving-1] = (pHeap)[_len-1]; \ /* Re-normalize for new element in this position */ \ while(_vRemoving > 1) { \ if( (pHeap)[_vRemoving/2-1].SortKey \ > (pHeap)[_vRemoving-1].SortKey ) \ break; /* Heap OK */ \ (pHeap)[_len-1] = (pHeap)[_vRemoving-1]; \ (pHeap)[_vRemoving-1] = (pHeap)[_vRemoving/2-1]; \ (pHeap)[_vRemoving/2-1] = (pHeap)[_len-1]; \ _vRemoving /= 2; \ } \ } \ } /*lint -save -e717 */ while(0) /*lint -restore */ #define RevHeap_Make(pHeap,NumEntries,SortKey) \ do { \ size_t _AccessPoint; /* Where are we checking for order now? */ \ size_t _i; /* Iterator over elements */ \ size_t _MaxEntry = (NumEntries); \ for(_i=0; _i<_MaxEntry; _i++) { \ _AccessPoint = _i+1; \ while(_AccessPoint > 1) { \ size_t _ByteCount; /* For finding number of bytes to swap */ \ char* _pUp,* _pDown; /* Which nodes in tree to swap */ \ char _SwapTemp; /* Temporary swap variable */ \ if( (pHeap)[_AccessPoint/2-1].SortKey \ > (pHeap)[_AccessPoint-1].SortKey ) \ break; /* Heap OK */ \ _pUp = (char*)((pHeap)+(_AccessPoint/2-1)); \ _pDown = (char*)((pHeap)+(_AccessPoint-1)); \ for(_ByteCount=0; _ByteCount