OrderedList< T > Class Template Reference

Doubly-linked ordered list implementation with dynamic memory allocation. More...

#include <OrderedList.hpp>

Inheritance diagram for OrderedList< T >:

Collaboration diagram for OrderedList< T >:

Public Member Functions
string	getName ()
	Provides the name of the data structure as a string representation. More...
	OrderedList (std::function< int(T, T)> compareFunc)
	Creates the structure. More...
	OrderedList (const T data[], std::function< int(T, T)> compareFunc)
	create the structure and populate it with the data from the array More...
void	insert (T val)
	Insert an element at its position on the list. More...
void	insert (T val, int index)
	Insert an element at the specified position in the list. More...
int	indexOf (T val)
	Finds an element in the ordered list and returns its index. More...
bool	contains (T val)
	Answers whether the ordered list contains an enemy. More...
T	remove (int index)
	Remove an element from the list. More...
T	get (int index)
	Get the element at the specified position in the list, without removing it. More...
Public Member Functions inherited from LinkedList< T >
	LinkedList ()
	LinkedList (T data[])
	create the structure and populate it with the data from the array More...
Iterator< T >	iterator ()
	Creates an Iterator, an object that allows the sequential access of values in a Linked List without the search overhead. More...
Public Member Functions inherited from ProtectedLinkedList< T >
	ProtectedLinkedList ()
	~ProtectedLinkedList ()
int	getSize ()
	Outputs the number of elements stored in the structure. More...
bool	isEmpty ()
	Check whether the structure is empty. More...
bool	isFull ()
	Check whether the structure is full. More...

Private Attributes
function< int(T, T)>	compare

Additional Inherited Members
Protected Member Functions inherited from ProtectedLinkedList< T >
Node< T > *	getNode (int index)
	ProtectedLinkedList (const T data[])
	create the structure and populate it with the data from the array More...
Node< T > *	getFirst () const
Node< T > *	getLast () const

Detailed Description

template<class T>
class OrderedList< T >

Doubly-linked ordered list implementation with dynamic memory allocation.

This class searches for the appropriate place to insert an element keeping the array sorted ata ll times, much like insertion sort.

Template Parameters

T	The type of object the data structure will contain

Definition at line 17 of file OrderedList.hpp.

Constructor & Destructor Documentation

OrderedList() [1/2]

template<class T>

OrderedList< T >::OrderedList ( std::function< int(T, T)>  compareFunc )

inlineexplicit

Creates the structure.

Parameters

compareFunc

a C++ 11 compliant function parameter that allows comparation between template objects

Definition at line 28 of file OrderedList.hpp.

                                                           : compare(compareFunc) {
  }

OrderedList() [2/2]

template<class T>

OrderedList< T >::OrderedList ( const T  data[], std::function< int(T, T)>  compareFunc  )

inlineexplicit

create the structure and populate it with the data from the array

Parameters

data	an array with data with which the structure will be initialized
compareFunc	a C++ 11 compliant function parameter that allows comparation between template objects

Definition at line 34 of file OrderedList.hpp.

                                                                           : compare(compareFunc) {
    for (int i = 0; i <= (sizeof(data) / sizeof(data[0])); i ++) {
      // use this class implementation of insert() to ensure order
      insert(data[i]);
    }
  }

Member Function Documentation

contains()

template<class T>

bool OrderedList< T >::contains ( T  val )

inline

Answers whether the ordered list contains an enemy.

Parameters

val	the element to be found

Returns

true if there is at least one element where compareFunc(val, element) == 0, otherwise false

Definition at line 81 of file OrderedList.hpp.

                       {
    return indexOf(val) != - 1;
  }

Here is the call graph for this function:

get()

template<class T>

T OrderedList< T >::get ( int  index )

inlinevirtual

Get the element at the specified position in the list, without removing it.

Parameters

index

index of the desired element

Reimplemented from LinkedList< T >.

Definition at line 89 of file OrderedList.hpp.

                   {
    return LinkedList<T>::get(index);
  }

getName()

template<class T>

string OrderedList< T >::getName ( )

inlinevirtual

Provides the name of the data structure as a string representation.

Returns

name of the data structure

Reimplemented from LinkedList< T >.

Definition at line 22 of file OrderedList.hpp.

{ return "Ordered List"; }

indexOf()

template<class T>

int OrderedList< T >::indexOf ( T  val )

inline

Finds an element in the ordered list and returns its index.

Parameters

val	the element to be found

Returns

The index of the first element where compareFunc(val, element) == 0

Definition at line 65 of file OrderedList.hpp.

                     {
    Node<T> *tmp = LinkedList<T>::getFirst();
    int index = 0;
    while (tmp != NULL && compare(val, tmp->getValue()) >= 0) {
      if (compare(val, tmp->getValue()) == 0)
        return index;
      index ++;
      tmp = tmp->getNext();
    }

    return - 1;
  }

Here is the caller graph for this function:

insert() [1/2]

template<class T>

void OrderedList< T >::insert ( T  val )

inlinevirtual

Insert an element at its position on the list.

Parameters

val	the value to be inserted

Reimplemented from LinkedList< T >.

Definition at line 43 of file OrderedList.hpp.

                     {
    if (LinkedList<T>::isEmpty()) {
      LinkedList<T>::insert(val);
    }
    else {
      Node<T> *tmp = LinkedList<T>::getFirst();
      int index = 0;
      while (tmp != NULL && compare(val, tmp->getValue()) < 0) {
        index ++;
        tmp = tmp->getNext();
      }
      LinkedList<T>::insert(val, index);
    }
  }

insert() [2/2]

template<class T>

void OrderedList< T >::insert ( T  val, int  index  )

inlinevirtual

Insert an element at the specified position in the list.

Parameters

val	the value to be inserted
index	position of the list that the element will be inserted on

Reimplemented from LinkedList< T >.

Definition at line 58 of file OrderedList.hpp.

                                {
    insert(val);
  }

remove()

template<class T>

T OrderedList< T >::remove ( int  index )

inlinevirtual

Remove an element from the list.

Parameters

index

position of the element to be removed

Returns

the element that is being removed

Reimplemented from LinkedList< T >.

Definition at line 85 of file OrderedList.hpp.

                      {
    return LinkedList<T>::remove(index);
  }

Field Documentation

compare

template<class T>

function<int(T, T)> OrderedList< T >::compare

private

Definition at line 19 of file OrderedList.hpp.

---

The documentation for this class was generated from the following file:

• include/OrderedList.hpp