#include <stdio.h>
#include <iostream>
using namespace std;
class DLLElement {
public:
DLLElement( void *itemPtr, int sortKey ) // initialize a list element
{
item = itemPtr;
key = sortKey;
next = NULL;
prev = NULL;
}
DLLElement *next; //next element on list
//NULL if this is the last
DLLElement *prev; //previous element on list
//NULL if this is the first
int key; // priority, for a sorted list
void *item; // pointer to item on the list
};
class DLList {
private:
DLLElement *first; // head of the list, NULL if empty
DLLElement *last;
public:
DLList()
{
first = NULL;
last = NULL;
}
// initialize the list
// de-allocate the list
void Prepend(void *item) // add to head of list (setkey = min_key-1)
{
DLLElement *temp;
if(first==NULL)
{
first = new DLLElement(item,0);
last = first;
}
else
{
temp = new DLLElement(item,(first->key-1));
temp->next = first;
first->prev = temp;
first = temp;
}
}
void Append(void *item) // add to tail of list (setkey = max_key + 1)
{
DLLElement *temp;
if(last==NULL)
{
last = new DLLElement(item,0);
first = last;
}
else
{
temp = new DLLElement(item,(last->key+1));
temp->prev = last;
last->next = temp;
last = temp;
}
}
void *Remove(int *keyPtr) // remove from head of list
{
DLLElement *temp;
keyPtr = &first->key;
if(first!=NULL)
{
temp = first->next;
if(first->next!=NULL)
{
temp->prev= NULL;
}
first = temp;
}
}
// set *keyPtr to key of the removed item
// return item (or NULL if list is empty)
bool IsEmpty() // return true if list has elements
{
if (first!=NULL)
{
return true;
}
else
{
return false;
}
}
// routines to put/get items on/off list in order (sorted by key)
void SortedInsert(void *item, int sortKey)
{
DLLElement *ins;
ins = new DLLElement(item,sortKey);
DLLElement *node = first;
DLLElement *temp = NULL;
if(node==NULL)
{
first = ins;
last = ins;
}
else if(node!=NULL&&(sortKey<first->key))
{
ins->next = first;
first->prev = ins;
first = ins;
}
else if(node!=NULL && (sortKey>last->key))
{
ins->prev = last;
last->next = ins;
last = ins;
}
else{
while(node->key<sortKey)
{
temp = node;
node = node->next;
}
ins->prev = temp;
ins->prev->next = ins;
node->prev = ins;
ins->next = node;
}
}
void *SortedRemove(int sortKey)
{
DLLElement *node = first;
DLLElement *pre = NULL;
while(node->key<sortKey&&node!=NULL)
{
pre = node;
node = node->next;
}
if(node!=NULL&&(node->key=sortKey))
{
if(node->prev!=NULL){
node->prev->next= node->next;}
if(node->next!=NULL){
node->next->prev = node->prev;}
if(node->prev==NULL){
first = node->next;
}
if(node->next==NULL){
last = node->prev;
}
} // remove first item with key==sortKey
// return NULL if no such item exists
} // last element of the list, NULL if empty
};
void addN(int n,DLList *k,void *item)
{
int i = 0,j=0;
randomize();
int a[n];
for(i=0;i<n;i++){
a[i] = rand()100000 + rand()12345;
}
for(j=0;j<n;j++){
k.sortedInsert(item, a[j]);
}
}
void removeN(int n , DLList *k)
{
int i =0;
for(i=0;i<n;i++)
{
if(k.IsEmpty){
a = k.remove(l);
cout<<"a"; }
int main(){
cout<<"hi";
DLList k;
}