KKB::KKQueue< Entry > Class Template Reference

A typed container class/template that keeps track of entries via pointers only. More...

#include <KKQueue.h>

Inheritance diagram for KKB::KKQueue< Entry >:

Public Types
typedef std::vector< Entry * >::const_iterator	const_iterator
typedef std::vector< Entry * >::iterator	iterator

Public Member Functions
	KKQueue (bool _owner=true)
	KKQueue (const KKQueue &q, bool _owner)
	Constructor, similar to the Copy Constructor except that you can control whether it duplicates the contents. More...
virtual	~KKQueue ()
	Virtual destructor; if owns its contents will also call the destructor on each one entry that it contains. More...
virtual void	Add (EntryPtr _entry)
virtual void	AddFirst (EntryPtr _entry)
virtual void	AddQueue (const KKQueue &q)
	Add the contents of a separate KKQueue container to this container. More...
EntryPtr	BackOfQueue () const
void	DeleteContents ()
void	DeleteEntry (EntryPtr _entry)
void	DeleteEntry (kkuint32 _idx)
KKQueue *	DuplicateListAndContents () const
	Creates a new container including duplicating the contents, which also makes the new instance the owner of those contents. More...
template<typename Functor >
kkuint32	FindTheKthElement (kkuint32 k, Functor pred)
EntryPtr	FrontOfQueue () const
EntryPtr	GetFirst () const
EntryPtr	GetLast () const
EntryPtr	IdxToPtr (kkuint32 idx) const
kkint32	LocateEntry (EntryConstPtr _entry) const
EntryPtr	LookAtBack () const
EntryPtr	LookAtFront () const
bool	operator!= (const KKQueue< Entry > &rightSide) const
	returns False if NOT every entry in both containers point to the same elements More...
KKQueue &	operator= (const KKQueue &q)
	Assignment Operator. More...
bool	operator== (const KKQueue< Entry > &rightSide) const
	Returns True if every entry in both containers point to the same elements. More...
Entry &	operator[] (kkuint32 i) const
bool	Owner () const
void	Owner (bool _owner)
virtual EntryPtr	PopFromBack ()
virtual EntryPtr	PopFromFront ()
kkint32	PtrToIdx (EntryConstPtr _entry) const
virtual void	PushOnBack (EntryPtr _entry)
virtual void	PushOnFront (EntryPtr _entry)
kkint32	QueueSize () const
void	RandomizeOrder ()
	Randomizes the order of the vector. More...
void	RandomizeOrder (kkint64 seed)
void	RandomizeOrder (RandomNumGenerator &randomVariable)
	Randomizes the order of the vector. More...
virtual EntryPtr	RemoveFirst ()
virtual EntryPtr	RemoveLast ()
void	SetIdxToPtr (kkuint32 _idx, Entry *_ptr)
void	SwapIndexes (size_t idx1, size_t idx2)

Protected Member Functions
	KKQueue (const KKQueue &q)
	Copy Constructor creating new instance; including duplicating contents if owner set to true. More...

Detailed Description

template<class Entry>
class KKB::KKQueue< Entry >

A typed container class/template that keeps track of entries via pointers only.

Will act as an Array, Queue or Stack structure. Items are added by the 'PushOnFront' and 'PushOnBack' methods. They are removed by the 'PopFromFront' and 'PopFromBack' methods. What is important to keep in mind is that it holds pointers to its contents, not the actual instances. It is important to keep track who owns the objects you put in an instance of KKQueue. KKQueue has a 'Owner' flag that you can set. If it is set to 'true' then it will call the destructor on all its contents when you call KKQueue's destructor or the 'DestroyContents' method. When you add an element to a KKQueue container you can not delete it separately until you either remove it from KKQueue or delete the KKQueue container. If the KKQueue derived container owned its contents and you call its destructor then there is no need to delete the contents separately.

KKQueue is sub-classed from vector<Entry*> so you can use any method that is available for the vector<> template.

Template Parameters

Entry

The type of objects that are to be held in this container. When you add new instances of 'Entry', you need to add a pointer to it not the actual entry.

Definition at line 77 of file KKQueue.h.

Member Typedef Documentation

template<class Entry>

typedef std::vector<Entry*>::const_iterator KKB::KKQueue< Entry >::const_iterator

Definition at line 89 of file KKQueue.h.

template<class Entry>

typedef std::vector<Entry*>::iterator KKB::KKQueue< Entry >::iterator

Definition at line 88 of file KKQueue.h.

Constructor & Destructor Documentation

template<class Entry >

KKQueue::KKQueue

(

bool

_owner = true

)

Definition at line 219 of file KKQueue.h.

                                      :
      owner (_owner)
  {
  }

template<class Entry >

KKQueue::KKQueue ( const KKQueue< Entry > &  q )

protected

Copy Constructor creating new instance; including duplicating contents if owner set to true.

If the parameter 'q' owns its contents then will create new instances of its contents. That is it will call the Copy Constructor for each one of the elements it contains. If 'q' does not own its contents it will just copy over the pointers from 'q', meaning that the new instance of KKQueue will point to the same locations as 'q' does.

Definition at line 227 of file KKQueue.h.

                                           :
        owner (q.Owner ())

  {
    //for  (vector<Entry*>::const_iterator x = q.begin ();  x != q.end ();  x++)
    for  (const_iterator x = q.begin ();  x != q.end ();  x++)
    {
      if  (owner)
        PushOnBack (new Entry (*(*x)));
      else
        PushOnBack (*x); 
    }
  }

template<class Entry >

KKQueue::KKQueue	(	const KKQueue< Entry > &	q,
		bool	_owner
	)

Constructor, similar to the Copy Constructor except that you can control whether it duplicates the contents.

If the '_owner' parameter is set to true then it will create new instances of the contents otherwise it will just point to the instances that already exist.

Definition at line 243 of file KKQueue.h.

                           :
        owner (_owner)

  {
    //for  (vector<Entry*>::const_iterator x = q.begin
    //  owner (_owner) ();  x != q.end ();  x++)
    for  (const_iterator x = q.begin ();  x != q.end ();  ++x)
    {
      if  (owner)
        PushOnBack (new Entry (*(*x)));
      else
        PushOnBack (*x); 
    }
  }

template<class Entry >

KKQueue::~KKQueue ( )

virtual

Virtual destructor; if owns its contents will also call the destructor on each one entry that it contains.

Definition at line 280 of file KKQueue.h.

  {
    if  (owner)
    {
      iterator  i;

      for  (i = KKQueue<Entry>::begin ();  i != KKQueue<Entry>::end (); i++)
      {
        delete *i;
        *i = NULL;
      }
    }
  }  /* ~KKQueue */

Member Function Documentation

template<class Entry >

void KKQueue::Add ( EntryPtr  _entry )

inlinevirtual

same as PushOnBack

Definition at line 339 of file KKQueue.h.

  {
    PushOnBack (_entry);
  }

template<class Entry >

void KKQueue::AddFirst ( EntryPtr  _entry )

inlinevirtual

same as PushOnFront

Definition at line 347 of file KKQueue.h.

  {
    PushOnFront (_entry);
  }

template<class Entry >

void KKQueue::AddQueue ( const KKQueue< Entry > &  q )

virtual

Add the contents of a separate KKQueue container to this container.

Be careful how the Owner flags are set; this method adds the pointers of 'q' to the end of its own container; it does not concern itself with the state of the 'Owner' flags. If you are not careful you can have both containers thinking they own the same entries. I suggest that after you add the contents of 'q' to this container that the caller set the 'owner' flag of 'q' to false.

Definition at line 355 of file KKQueue.h.

  {
    for (const_iterator x = q.begin ();  x != q.end (); x++)
      PushOnBack (*x);
    return;
  }  /* AddQueue */

template<class Entry >

KKQueue< Entry >::EntryPtr KKQueue::BackOfQueue

(

)

const

Returns pointer of last element in the container without removing it. If the container is empty will return NULL.

Definition at line 661 of file KKQueue.h.

  {
    if  (KKQueue<Entry>::size () <= 0)
      return NULL;
    return KKQueue<Entry>::back ();
  }

template<class Entry >

void KKQueue::DeleteContents

(

)

Empties the container, if 'owner' is set to true will call the destructor on each element.

Definition at line 321 of file KKQueue.h.

  {
    if  (owner)
    {
      iterator  idx;

      for  (idx = KKQueue<Entry>::begin ();  idx != KKQueue<Entry>::end ();  idx++)
      {
        delete  (*idx);
      }
    }

    KKQueue<Entry>::clear ();
  }  /* DeleteContents */

template<class Entry >

void KKQueue::DeleteEntry

(

EntryPtr

_entry

)

Removes from KKQueue the entry who's pointer = '_entry'

Definition at line 684 of file KKQueue.h.

  {
    for  (iterator y =  KKQueue<Entry>::begin (); y !=  KKQueue<Entry>::end ();  y++)
    {
      if  (*y == _entry)
      {
        KKQueue<Entry>::erase (y);
        return;
      }
    }
  }  /* DeleteEntry */

template<class Entry >

void KKQueue::DeleteEntry

(

kkuint32

_idx

)

Removes from KKQueue the entry who's index = '_idx'.

Definition at line 715 of file KKQueue.h.

  {
    if  ((kkuint32)_idx >=  KKQueue<Entry>::size ())
      return;

    iterator  i =  KKQueue<Entry>::begin ();

    for (kkuint32 j = 0;  ((j < _idx)  &&  (i !=  KKQueue<Entry>::end ()));  j++)
      i++;

    EntryPtr  ep = *i;
    KKQueue<Entry>::erase (i);
  }  /* DeleteEntry */

template<class Entry >

KKQueue< Entry > * KKQueue::DuplicateListAndContents

(

)

const

Creates a new container including duplicating the contents, which also makes the new instance the owner of those contents.

Definition at line 263 of file KKQueue.h.

  {
    KKQueue<Entry>*  duplicatedQueue = new KKQueue<Entry> (true, QueueSize ());

    for  (const_iterator x = KKQueue<Entry>::begin ();  x != KKQueue<Entry>::end ();  x++)
    {
      const EntryPtr e = *x;
      duplicatedQueue->PushOnBack (new Entry (*e));
    }
    
    return  duplicatedQueue;
  }  /* DuplicateListAndContents */

template<class Entry >

template<typename Functor >

kkuint32 KKQueue::FindTheKthElement	(	kkuint32	k,
		Functor	pred
	)

Definition at line 527 of file KKQueue.h.

  {
    if  ((k < 0)   ||  (K > = (kkint32)size ()))
      return -1;
    return  FindTheKthElement (k, 0, size () - 1, pred);
  }  /* FindTheKthElement */

template<class Entry >

KKQueue< Entry >::EntryPtr KKQueue::FrontOfQueue

(

)

const

Returns a pointer to the element that is at from of the queue with out removing it from the queue.

Definition at line 673 of file KKQueue.h.

  {
    if  ( KKQueue<Entry>::size () <= 0)
       return NULL;

    return * KKQueue<Entry>::begin ();
  }

template<class Entry >

KKQueue< Entry >::EntryPtr KKQueue::GetFirst ( ) const

inline

Same as FrontOfQueue.

Definition at line 366 of file KKQueue.h.

  {
    return  FrontOfQueue ();
  }

template<class Entry >

KKQueue< Entry >::EntryPtr KKQueue::GetLast ( ) const

inline

Same as BackOfQueue.

Definition at line 374 of file KKQueue.h.

  {
    return  BackOfQueue ();
  }

template<class Entry >

KKQueue< Entry >::EntryPtr KKQueue::IdxToPtr

(

kkuint32

idx

)

const

Returns back a pointer to the element who's index is 'idx'. If 'idx' is less than 0 or >= QueueSize() will return NULL.

Definition at line 732 of file KKQueue.h.

  {
    if  (idx >= KKQueue<Entry>::size ())
      return NULL;

    return  &((*this)[idx]);
    //return  (typename Entry*)(vector<Entry*>::operator[] (idx));
  }  /* IdxToPtr */

template<class Entry >

kkint32 KKQueue::LocateEntry

(

EntryConstPtr

_entry

)

const

Returns the index of the element who's address is '_entry'. If not found in container will return back -1.

Definition at line 745 of file KKQueue.h.

  {
    kkint32  i = 0; 

    for  (const_iterator j = KKQueue<Entry>::begin ();  j != KKQueue<Entry>::end (); j++)
    {
      if  (*j == _entry)
        return i;
      i++;
    }
    return -1;
  }  /* LocateEntry */

template<class Entry >

KKQueue< Entry >::EntryPtr KKQueue::LookAtBack

(

)

const

Same as BackOfQueue.

Definition at line 627 of file KKQueue.h.

  {
    if  (this->size () <= 0)
      return NULL;

    return  KKQueue<Entry>::back ();
  }

template<class Entry >

KKQueue< Entry >::EntryPtr KKQueue::LookAtFront

(

)

const

Same as FrontOfQueue.

Definition at line 638 of file KKQueue.h.

  {
    if  (this->size () <= 0)
      return NULL;
    return  *KKQueue<Entry>::begin ();
  }

template<class Entry>

bool KKQueue::operator!=

(

const KKQueue< Entry > &

rightSide

)

const

returns False if NOT every entry in both containers point to the same elements

Definition at line 457 of file KKQueue.h.

  {
    return  !((*this) == rightSide);
  } /* operator!= */

template<class Entry >

KKQueue< Entry > & KKQueue::operator=

(

const KKQueue< Entry > &

q

)

Assignment Operator.

1) Destroy's its current contents by calling 'DeleteContents'.
2) If 'q' owns its contents 
     create new instances of 'q's contents and add to its self  then set 'owner' flag to true.
   else 
     Copy over 'q's pointers to self and then set 'owner' flag to false.

Definition at line 415 of file KKQueue.h.

  {
    DeleteContents ();

    if  (q.Owner ())
    {
      for  (const_iterator  x = q.begin ();  x < q.end (); x++)
        push_back (new Entry (**x));
      this->Owner (true);
    }
    else
    {
      for  (const_iterator  x = q.begin ();  x < q.end (); x++)
        push_back (*x);
      this->Owner (false);
    }
    return *this;
  }  /* operator= */

template<class Entry>

bool KKQueue::operator==

(

const KKQueue< Entry > &

rightSide

)

const

Returns True if every entry in both containers point to the same elements.

Definition at line 438 of file KKQueue.h.

  {
    if  (QueueSize () != rightSide.QueueSize ())
      return false;

    for (kkint32 x = 0;  x < QueueSize ();  x++)
    {
      Entry*  left  = IdxToPtr (x);
      Entry*  right = rightSide.IdxToPtr (x);
      if  (!((*left) == (*right)))
        return false;
    }

    return true;
  } /* operator== */

template<class Entry >

Entry & KKQueue::operator[]

(

kkuint32

i

)

const

Returns a reference to element indexed by 'i'; similar to IdxToPtr except tat it returns a reference rather than a pointer.0

Definition at line 802 of file KKQueue.h.

  {
    //KKQueue<Entry>::Entry*  entry;

    if  ((idx < 0)  ||  (idx >= KKQueue<Entry>::size ()))
    {
      std::cerr << std::endl 
                << "*** ERROR ***   KKQueue<Entry>::operator[], Index [" << idx << "] out of bounds." << std::endl
                << std::endl;
      exit (-1);
    }

    return  (Entry&)*(std::vector<Entry*>::operator[] (idx));
  }  /* operator[] */

template<class Entry >

bool KKQueue::Owner

(

)

const

Definition at line 305 of file KKQueue.h.

  {
    return  (owner != 0);
  }

template<class Entry >

void KKQueue::Owner

(

bool

_owner

)

You can specify who owns the contents of the container. '_owner' == true means when the container is deleted it will also call the destructor for each element it contains.

Definition at line 297 of file KKQueue.h.

  {
    owner = _owner;
  }

template<class Entry >

KKQueue< Entry >::EntryPtr KKQueue::PopFromBack ( )

virtual

Removes the last element in the container and returns its pointer. If the container is empty will return NULL.

Reimplemented in KKMLL::MLClassList, KKMLL::GrayScaleImagesFVList, and KKB::XmlAttributeList.

Definition at line 648 of file KKQueue.h.

  {
    if  (KKQueue<Entry>::size () <= 0)
      return NULL;

    Entry*  e = KKQueue<Entry>::back ();
    KKQueue<Entry>::pop_back ();
    return e;
  }

template<class Entry >

KKQueue< Entry >::EntryPtr KKQueue::PopFromFront ( )

virtual

Removes the first element in the container and returns its pointer. If the container is empty will return NULL.

Reimplemented in KKMLL::MLClassList.

Definition at line 596 of file KKQueue.h.

  {
    if  (KKQueue<Entry>::size () <= 0)
    {
      return NULL;
    }

    iterator beg = KKQueue<Entry>::begin ();
    Entry*  e = *beg;
    KKQueue<Entry>::erase (beg);
    return  e;
  }

template<class Entry >

kkint32 KKQueue::PtrToIdx

(

EntryConstPtr

_entry

)

const

returns the index of the 'entry' that has the same pointer as '_entry', if none found returns -1

Definition at line 761 of file KKQueue.h.

  {
    return  LocateEntry (_entry);
  }

template<class Entry >

void KKQueue::PushOnBack ( EntryPtr  _entry )

virtual

Adds '_entry' to the End of the container.

Reimplemented in KKB::XmlAttributeList.

Definition at line 398 of file KKQueue.h.

  {
    this->push_back (_entry);

    EntryPtr  e = KKQueue<Entry>::back ();

    if  (e != _entry)
    {
      std::cerr << "KKQueue<Entry>::PushOnBack   ***ERROR***    Operation Failed!!!" << std::endl;
    }
    //vector<Entry*>  x;
  }

template<class Entry >

void KKQueue::PushOnFront ( EntryPtr  _entry )

virtual

Adds '_entry' to the Front of the container.

Reimplemented in KKB::XmlAttributeList.

Definition at line 383 of file KKQueue.h.

  {
    KKQueue<Entry>::insert (KKQueue<Entry>::begin (), _entry);

    Entry*  e = *KKQueue<Entry>::begin ();

    if  (e != _entry)
    {
      std::cout << "Error " << std::endl;
    }

  }

template<class Entry >

kkint32 KKQueue::QueueSize

(

)

const

Same as calling vector<>::size(); returns the number of elements in KKQueue

Definition at line 313 of file KKQueue.h.

  {
    return  (kkint32)this->size ();
  }

template<class Entry >

void KKQueue::RandomizeOrder

(

)

Randomizes the order of the vector.

Implements the "Fisher-Yates Uniform Random Sort"; this implementation was done by Sergiy Fefilatyev (2011-01-27)

Definition at line 469 of file KKQueue.h.

  {
    kkint32  i, j;
    kkuint32  numEntries = KKQueue<Entry>::size ();
    if  (numEntries < 2)
      return;

    i = numEntries - 1;
    while (true)  
    {
      j = LRand48() % (i + 1);
      SwapIndexes  (i, j );
      if  (i < 1)
        break;
      i--;
    }
  }  /* RandomizeOrder */

template<class Entry >

void KKQueue::RandomizeOrder

(

kkint64

seed

)

Definition at line 490 of file KKQueue.h.

  {
    SRand48 (seed);
    RandomizeOrder ();
  }  /* RandomizeOrder */

template<class Entry >

void KKQueue::RandomizeOrder

(

RandomNumGenerator &

randomVariable

)

Randomizes the order of the vector.

Implements the "Fisher-Yates Uniform Random Sort"; this implementation was done by Sergiy Fefilatyev (2011-01-27)

Definition at line 504 of file KKQueue.h.

  {
    kkint32  i, j;
    kkuint32  numEntries = KKQueue<Entry>::size ();
    if  (numEntries < 2)
      return;

    i = numEntries - 1;
    while (true)  
    {
      j = randomVariable.Next () % (i + 1);
      SwapIndexes  (i, j );
      if  (i < 1)
        break;
      i--;
    }
  }  /* RandomizeOrder */

template<class Entry >

KKQueue< Entry >::EntryPtr KKQueue::RemoveFirst ( )

inlinevirtual

same as PopFromFront

Definition at line 611 of file KKQueue.h.

  {
    return  PopFromFront ();
  }

template<class Entry >

KKQueue< Entry >::EntryPtr KKQueue::RemoveLast ( )

inlinevirtual

same as PopFromBack

Definition at line 619 of file KKQueue.h.

  {
    return  PopFromBack ();
  }

template<class Entry>

void KKQueue::SetIdxToPtr	(	kkuint32	_idx,
		Entry *	_ptr
	)

Definition at line 700 of file KKQueue.h.

  {
    if  ((kkuint32)_idx >=  KKQueue<Entry>::size ())
      return;
    
    std::vector<Entry*>::operator[] (_idx) = _ptr;
  }  /* SetIdxToPtr */

template<class Entry >

void KKQueue::SwapIndexes	(	size_t	idx1,
		size_t	idx2
	)

Definition at line 769 of file KKQueue.h.

  {
    if  ((idx1 < 0)  ||  (idx1 >= KKQueue<Entry>::size ())  ||
         (idx2 < 0)  ||  (idx2 >= KKQueue<Entry>::size ())
        )
    {
      std::cerr << std::endl;

      std::cerr << "  ***  ERROR  ***  (KKQueue::SwapIndexes)  Indexes[" 
                << (kkint32)idx1 << ", " << (kkint32)idx2 << "] Out of Range."
                << std::endl;

      std::cerr << "                   KKQueue Size[" << (kkint32)KKQueue<Entry>::size () << "]." 
                << std::endl
                << std::endl;

      exit (1);
    }

    //vector<typename Entry*>&  us (*this);
    EntryPtr  tempPtr = std::vector<Entry*>::operator[] (idx1);

    // (*this)[idx1];

    std::vector<EntryPtr>::operator[] (idx1) = std::vector<EntryPtr>::operator[] (idx2);
    std::vector<EntryPtr>::operator[] (idx2) = tempPtr;
    //(*this)[idx1] = (*this)[idx2];
    //(*this)[idx2] = tempPtr;
  }  /* SwapIndexes */

---

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

• C:/Users/Kurt/GitHub/KSquareLibraries/KKBase/KKQueue.h