#pragma once
#include "LinkedList.h"
// WARNING: THIS CLASS DOES NO MEMORY ALLOCATION CHECKING
// ======================================================================================== //
// Group List Node class template
// 'T' is type that will be used for 'group id'
// 'U' is the item type stored in each Node.
// ======================================================================================== //
template <class T, class U> class GroupedListNode
{
public:
GroupedListNode( ) { list_ptr = NULL; };
~GroupedListNode( ) {};
// Linked list belonging to this group.
LinkedList<U> *list_ptr;
// ID of this group.
T group_id;
};
// ======================================================================================== //
// Grouped List class template. This will create and manage a bunch of lists of items
// with increasing 'group_id' values.
//
// 'T' is type that will be used for 'group id'
// 'U' is the item type stored in each Node.
// ======================================================================================== //
template <class T, class U> class GroupedLists
{
public:
GroupedLists( unsigned int groups_to_preallocate = 10, unsigned int entries_per_list_to_preallocate = 100 );
~GroupedLists( void );
unsigned int getNumberOfGroups();
LinkedListNode<GroupedListNode<T,U>>* getGroup( T group_id );
LinkedListNode<GroupedListNode<T,U>>* getHeadGroup();
LinkedList<U>* getGroupsList( T group_id );
void insertIntoGroup( LinkedListNode<GroupedListNode<T,U>> *group_ptr, LinkedListNode<U> *this_node );
void removeGroup( LinkedListNode< GroupedListNode<T,U> > *group_ptr );
void removeGroup( T group_id );
void removeAllGroups( );
void purgeFreeGroups( );
private:
LinkedListNode<GroupedListNode<T,U>>* obtainNewGroup( );
void allocateNextListsBlock( );
LinkedList<GroupedListNode<T,U>> *group_list;
LinkedList<U> *preallocated_lists_mem;
LinkedList<U> **linked_list_blocks;
unsigned int entries_in_each_list;
};
template <class T, class U>
GroupedLists<T,U>::GroupedLists( unsigned int groups_to_preallocate/*=10*/, unsigned int entries_per_list_to_preallocate/*=100*/ )
{
// Preallocate the list objects, this also preallocates the lists for each group
group_list = new LinkedList<GroupedListNode<T,U>>( groups_to_preallocate );
// This is number of nodes to preallocate for each of the groups lists,
// note that these lists only get allocated as new groups are requested.
entries_in_each_list = entries_per_list_to_preallocate;
};
template <class T, class U>
GroupedLists<T,U>::~GroupedLists( )
{
// Go through current groups, deleting their lists
LinkedListNode<GroupedListNode<T,U>> *cur_node_ptr = group_list->getHeadPtr();
while ( cur_node_ptr )
{
delete cur_node_ptr->item.list_ptr;
cur_node_ptr = cur_node_ptr->next;
}
// There might have been some previously released groups with lists still attached.
// Go through those groups as well and delete their lists. We can stop as soon as first
// group with no list is encountered, since preallocation works like a stack.
cur_node_ptr = group_list->getFreeListPtr();
while ( (cur_node_ptr) && (cur_node_ptr->item.list_ptr) )
{
delete cur_node_ptr->item.list_ptr;
cur_node_ptr = cur_node_ptr->next;
}
// Delete the group list
delete group_list;
};
// ----------------------------------------------------------------------------------------
// Returns number of groups
// ----------------------------------------------------------------------------------------
template <class T, class U> inline
unsigned int GroupedLists<T,U>::getNumberOfGroups()
{
return group_list->getSize();
}
// ----------------------------------------------------------------------------------------
// Returns pointer to head group
// ----------------------------------------------------------------------------------------
template <class T, class U>
LinkedListNode<GroupedListNode<T,U>>* GroupedLists<T,U>::getHeadGroup( )
{
return group_list->getHeadPtr();
}
// ----------------------------------------------------------------------------------------
// Returns pointer to a new group list
// ----------------------------------------------------------------------------------------
template <class T, class U>
LinkedListNode<GroupedListNode<T,U>>* GroupedLists<T,U>::obtainNewGroup( )
{
LinkedListNode<GroupedListNode<T,U>> *new_group_ptr = group_list->getNewNode( );
// If a new group with no preallocated list was obtained, allocate a list for it.
if ( new_group_ptr->item.list_ptr == NULL )
{
new_group_ptr->item.list_ptr = new LinkedList<U>( entries_in_each_list );
}
return new_group_ptr;
}
// ----------------------------------------------------------------------------------------
// Returns pointer to specified group
// ----------------------------------------------------------------------------------------
template <class T, class U>
LinkedListNode<GroupedListNode<T,U>>* GroupedLists<T,U>::getGroup( T group_id )
{
LinkedListNode<GroupedListNode<T,U>> *cur_group_ptr = group_list->getTailPtr();
// Quick check to see if new ID is larger than max, for efficient new end of list
// additions in linear lists
if ( (cur_group_ptr) && (cur_group_ptr->item.group_id >= group_id) )
{
cur_group_ptr = group_list->getHeadPtr();
while ( cur_group_ptr != NULL )
{
// If current group has a larger id, a new group needs to be inserted before current
if ( cur_group_ptr->item.group_id > group_id )
{
LinkedListNode<GroupedListNode<T,U>> *new_group_ptr = obtainNewGroup();
new_group_ptr->item.group_id = group_id;
group_list->insertBefore( cur_group_ptr, new_group_ptr );
return new_group_ptr;
}
// If current node has same id, simply return it
if ( cur_group_ptr->item.group_id == group_id )
{
return cur_group_ptr;
}
// Go on to the next group
cur_group_ptr = cur_group_ptr->next;
}
}
// If we get this far, we need to insert a group at the very end
LinkedListNode<GroupedListNode<T,U>> *new_group_ptr = obtainNewGroup();
new_group_ptr->item.group_id = group_id;
group_list->insertAtEnd( new_group_ptr );
return new_group_ptr;
};
// ----------------------------------------------------------------------------------------
// Inserts node at start of the desired group
// ----------------------------------------------------------------------------------------
template <class T, class U>
void GroupedLists<T,U>::insertIntoGroup( LinkedListNode< GroupedListNode<T,U> > *group_ptr, LinkedListNode<U> *this_node )
{
group_ptr->item.list_ptr->insertAtStart( this_node );
};
// ----------------------------------------------------------------------------------------
// Returns the specified group to available list
// ----------------------------------------------------------------------------------------
template <class T, class U>
void GroupedLists<T,U>::removeGroup( LinkedListNode< GroupedListNode<T,U> > *group_ptr )
{
// We will remove the group and empty its list, but keep the list allocated incase it is reused
group_ptr->item.list_ptr->removeAllNodes();
group_list->removeNode( group_ptr );
};
// ----------------------------------------------------------------------------------------
// Returns the specified group id to available list
// ----------------------------------------------------------------------------------------
template <class T, class U>
void GroupedLists<T,U>::removeGroup( T group_id )
{
Linked_List_Node<GroupedListNode<T,U>> *cur_group = group_list->getHead();
// Go through list of groups until correct group is encountered
while ( cur_group != NULL )
{
if ( cur_group->item.group_id == group_id )
{
// Delete the group and all of it's items
group_list->removeNode( cur_group );
return;
}
cur_group = cur_group->next;
}
};
// ----------------------------------------------------------------------------------------
// Returns all groups to available list, along with the sublists
// ----------------------------------------------------------------------------------------
template <class T, class U>
void GroupedLists<T,U>::removeAllGroups( )
{
LinkedListNode<GroupedListNode<T,U>> *cur_group = group_list->getHeadPtr();
// We need to go through entire group list and release the individual
// item list from them
while ( cur_group != NULL )
{
cur_group->item.list_ptr->removeAllNodes( );
cur_group = cur_group->next;
}
// After they are all removed, we can remove the group list
group_list->removeAllNodes( );
};
// ----------------------------------------------------------------------------------------
// Returns all groups to available list, along with the sublists
// ----------------------------------------------------------------------------------------
template <class T, class U>
void GroupedLists<T,U>::purgeFreeGroups( )
{
group_list->purgeFreeList();
};