|
25 Years of Programming
An open source source for C, C++, OWL, BASIC, MDB, XLS, DOT, and more... |
Home Projects Up Sitemap Search Blog Forum+Chat About Us Privacy Terms of Use Feedback FAQ Images Services Ads Donate Humor |
|
|
Object counter C++ template class SFreqArrayA Borland C++ 4.0 template class that holds only unique array elements, along with the frequency count of each (how many times you have the added an identical item to the array). The first time you add a unique object to the array, it adds it. Each time you add an identical object, it only increments the count for that object. Works for any object that has
It is turning out to be fairly easy to port old Borland C++ code to Visual C++, but I haven't rewritten this class yet. I think it will mostly involve changing the TIArrayAsVector to an STL vector. The two vector types have equivalent methods, and some functions can be "converted" with a text search and replace. |
|
/* freqaray.h 2-21-04
Copyright (C)1997, 2004, 2006 by Steven Whitney
Intitially published by http://25yearsofprogramming.com
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
Version 3 as published by the Free Software Foundation.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
------
A generalized template class that holds only unique array elements,
along with the frequency count of each (how many times you have the added an identical item
to the array).
Developed using Borland C++ 4.0, it uses Borland's iostream classes,
stream manipulators, and BIDS template container class library.
It doesn't appear to contain any operating system dependent code, and should work under
MSDOS, Windows (any version), and probably any other platform.
------
Notes:
Because this file defines a template class, using all template code, it MUST be #included
in every source file where it is used, so the compiler knows how to create the class.
It can be precompiled. (#include this file AFTER my.h and mylib.cpp ??)
You cannot put this file in a separate library.cpp module, and there is no point
in putting the code in a .cpp file separate from this .h file.
class T can be any type, but must have:
copy constructor
operator == that does NOT use (&other == this)
stream operator <<
(operator <) this is not currently required, but will be,
but doesn't have to be meaningful.
You can get more interesting statistics on the frequency counts
by tallying the counts into an SStatsArray.
*/
#if !defined(__FREQARAY_H)
#define __FREQARAY_H
#include <fstream.h>
#include <classlib\arrays.h>
#include "c:\bcs\my.h"
//////////////////////////////////////////////////////////////////////////////
// A generalized template class that holds only unique array elements
// with a tally of how many times each has occurred.
template <class T> class SFreqArray
{
public:
SFreqArray() : Array(20,0,10) { sorted = TRUE; }
SFreqArray(int upper, int lower = 0, int delta = 10);
SFreqArray(const SFreqArray& other);
~SFreqArray();
friend ostream& operator << (ostream& os, const SFreqArray<T>&); // write to stream
// added 2/11/04; use ONLY for making a copy of obj: (yourcopy = xxarray[i]).
const T& operator [](int loc) { return Array[loc]->obj; }
BOOL Add(const T& t, int startcount = 1); // tally an occurrence (adding, if necessary)
BOOL Contains(const T& t); // identical object already in the array?
int Cull(int mincount = 2); // remove all objects whose count < mincount
BOOL Decrement(const T& t); // if matching object exists, decrement count
BOOL SetCount(const T& t, int newcount); // if matching object exists, set its count
// not written: each should call Cull() with increasing mincount until target is reached
int CullToPercent(double target = .5); // cull until only target % elements remain
int CullToCount(int target); // cull until only target # of elements remain
BOOL Destroy(const T& t); // delete array entry matching t
void Flush() { Array.Flush(TShouldDelete::Delete); }
unsigned GetItemsInContainer() { return(Array.GetItemsInContainer()); }
int HighCount(); // highest frequency
const T& ItemWithCount(int count, int occurrence); // Nth obj having specified count
int LowCount(); // lowest frequency
int NumberWithCount(int count); // number of elements that have specified count
void Sort(); // sort in descending order, by count
void mSort() { if(!sorted) Sort(); } // sort if necessary
// holds a copy of an item given to it, plus a slot for the occurrence count
// 2-11-04 move this class to outside of SFreqArray (before it) as a
// standalone template class (note that here it is not).
// it has potential other uses.
// wait until I'm more familiar and confident in how to move it.
struct ObjCounter
{
ObjCounter() {}
ObjCounter(const ObjCounter& other) : obj(other.obj), count(other.count) {}
ObjCounter(const T& t, int startcount = 1) : obj(t), count(startcount) {}
BOOL operator == (const ObjCounter& other) const
{ return(obj == other.obj); } // unique: count doesn't matter
// this should sort first by count, then by T operator <, for compound sorting.
BOOL operator < (const ObjCounter& other) const
{ return(count > other.count); } // backwards (descending)
T obj;
int count;
};
// indirect array: direct requires a single block big enough for N objects. Indirect
// requires only a block for N pointers, with the allocated objects scattered
// throughout memory as needed. Also, Flush, Cull, etc. actually will free up space.
TIArrayAsVector<ObjCounter> Array;
BOOL sorted;
};
//----------------------------------------------------------------------------
template <class T> SFreqArray<T>::SFreqArray(int upper, int lower, int delta)
: Array(upper, lower, delta)
{
sorted = TRUE; // no elements, so it's sorted
}
//----------------------------------------------------------------------------
// make an exact duplicate with Array only the exact size needed.
// doubtful usefulness, since using it at all requires available memory of 2 * the size
// of all objects in the array, and the indirect container isn't that wasteful, anyway.
template <class T> SFreqArray<T>::SFreqArray(const SFreqArray& other)
: Array(other.Array.GetItemsInContainer(), 0, 10)
{
int N = other.Array.GetItemsInContainer();
for(int i = 0 ; i < N ; i++)
Array.Add(new ObjCounter(*other.Array[i]));
sorted = FALSE;
}
//----------------------------------------------------------------------------
// destructor
template <class T> SFreqArray<T>::~SFreqArray()
{
Flush(); // the objects will be deleted
}
//----------------------------------------------------------------------------
// output the entire array to a stream
template <class T> ostream& operator << (ostream& os, const SFreqArray<T>& s)
{
int N = s.Array.GetItemsInContainer();
for(int i = 0 ; i < N ; i++)
// most of this should be in ObjCounter operator <<
os << setw(4) << setfill('0') << s.Array[i]->count << " " << s.Array[i]->obj << endl;
return(os);
} // <<
//----------------------------------------------------------------------------
// if an identical one is not already in the array, add it with specified starting count;
// if one exists, increment the count.
// startcount is useful if you aren't adding items to the array
// until you've already determined their count exceeds some minimum.
// returns TRUE if element was already there, FALSE if it had to be added.
template <class T> BOOL SFreqArray<T>::Add(const T& t, int startcount)
{
int N = Array.GetItemsInContainer();
for(int i = 0 ; i < N ; i++)
if(Array[i]->obj == t)
{
Array[i]->count++;
return(TRUE);
}
Array.Add(new ObjCounter(t,startcount));
sorted = FALSE;
return(FALSE);
} // Add
//----------------------------------------------------------------------------
// looks to see if an identical T object is already in the array, without incrementing count
template <class T> BOOL SFreqArray<T>::Contains(const T& t)
{
int N = Array.GetItemsInContainer();
for(int i = 0 ; i < N ; i++)
if(Array[i]->obj == t)
return(TRUE);
return(FALSE);
} // Contains
//----------------------------------------------------------------------------
// remove all objects whose count < mincount. It doesn't reduce the array size, but
// it does free up memory, since the objects are deleted.
// returns the number of items remaining
template <class T> int SFreqArray<T>::Cull(int mincount)
{
for(int i = 0 ; i < Array.GetItemsInContainer() ; )
if(Array[i]->count < mincount)
Array.Destroy(i); // reuse i: it's now the next element
else
i++;
return(Array.GetItemsInContainer());
} // Cull
//----------------------------------------------------------------------------
// if matching object exists, decrement count
// returns TRUE if object was there, FALSE if not
template <class T> BOOL SFreqArray<T>::Decrement(const T& t)
{
int N = Array.GetItemsInContainer();
for(int i = 0 ; i < N ; i++)
if(Array[i]->obj == t)
{
Array[i]->count--; // allows count < 0
// Array[i]->count = max(Array[i]->count,0); // enable to prevent < 0
return(TRUE);
}
return(FALSE);
} //Decrement
//----------------------------------------------------------------------------
// if matching object exists, set its count
// returns TRUE if object was there, FALSE if not
template <class T> BOOL SFreqArray<T>::SetCount(const T& t, int newcount)
{
int N = Array.GetItemsInContainer();
for(int i = 0 ; i < N ; i++)
if(Array[i]->obj == t)
{
Array[i]->count = newcount;
return(TRUE);
}
return(FALSE);
} //SetCount
//----------------------------------------------------------------------------
// search Array for an item, and delete it if found.
// Similar to Cull, but where you want to specify exactly which item(s) to delete.
// returns TRUE if object was deleted, FALSE if not found.
template <class T> BOOL SFreqArray<T>::Destroy(const T& t)
{
int N = Array.GetItemsInContainer();
for(int i = 0 ; i < N ; i++)
if(Array[i]->obj == t)
{
Array.Destroy(i);
return(TRUE);
}
return(FALSE);
} // Destroy
//----------------------------------------------------------------------------
// sort in descending order, by count
template <class T> void SFreqArray<T>::Sort()
{
int N = Array.GetItemsInContainer();
// Found a note that says: "This poses a problem for SGiantArray use."
// though I also decided that using SGiantArray was pointless.
TISArrayAsVector<ObjCounter> Sorted(N,0,1);
for(int i = 0 ; i < N ; i++) // copy into the sorted container
Sorted.Add(Array[i]);
Array.Flush(TShouldDelete::NoDelete);
for(i = 0 ; i < N ; i++) // copy back into the real container
Array.Add(Sorted[i]);
Sorted.Flush(TShouldDelete::NoDelete);
sorted = TRUE;
} // Sort
//----------------------------------------------------------------------------
// highest frequency
template <class T> int SFreqArray<T>::HighCount()
{
int N = Array.GetItemsInContainer();
int number = 0;
for(int i = 0 ; i < N ; i++)
number = max(Array[i]->count,number);
return(number);
} // HighCount
//----------------------------------------------------------------------------
// return the Nth (N=0,1,2...) obj encountered in the array whose count == count.
// you must immediately make a copy: T yourobj = ItemWithCount();
// there is no guarantee that the T& returned will continue to reference the same obj,
// or even remain valid.
// If the array has no elements, or there aren't as many occurrences as you think,
// your program will crash. (Call NumberWithCount(count) first.)
template <class T> const T& SFreqArray<T>::ItemWithCount(int count, int occurrence)
{
int index = 0; // counts occurrences
int N = Array.GetItemsInContainer();
for(int i = 0 ; i < N ; i++)
if(Array[i]->count == count)
if(index++ == occurrence)
break;
return(Array[i]->obj);
} //ItemWithCount
//----------------------------------------------------------------------------
// lowest frequency
template <class T> int SFreqArray<T>::LowCount()
{
int N = Array.GetItemsInContainer();
int number = 0;
for(int i = 0 ; i < N ; i++)
number = min(Array[i]->count,number);
return(number);
} // LowCount
//----------------------------------------------------------------------------
// number of elements that have specified count
template <class T> int SFreqArray<T>::NumberWithCount(int count)
{
int N = Array.GetItemsInContainer();
int number = 0;
for(int i = 0 ; i < N ; i++)
if(Array[i]->count == count)
number++;
return(number);
} // NumberWithCount
//----------------------------------------------------------------------------
// end class SFreqArray
//////////////////////////////////////////////////////////////////////////////
#endif (__FREQARAY_H)
|
|
|
|