Anagram program implentation

#include 
using namespace std;

#include "anaword.h"

static const int ALPH_SIZE = 26;

Anaword::Anaword(const string & word)
    : myWord(word),
      myCounts(ALPH_SIZE,0)
// postcondition: constructed    
{
    normalize();
}

Anaword::Anaword()
    : myWord(""),
      myCounts(ALPH_SIZE,0)
{
    
}

void Anaword::normalize()
// postcondition: myCounts represents the letter signture of myWord
{
    
}

string Anaword::toString() const
// postcondition: return "bagel" or "gable", regular form of string
{
    return myWord;
}

ostream & operator << (ostream & out, const Anaword & a)
// postcondition: a printed t stream out, out returned    
{
    out << a.toString();
    return out;
}

bool Anaword::equal(const Anaword & rhs) const
// postcondition: returns true if and only if *this == rhs
//                canonical/normalized form of word used for comparisons    
{
    return false;
}

bool operator == (const Anaword & lhs, const Anaword & rhs)
// postcondition: returns true if and only if lhs == rhs
{
    return lhs.equal(rhs);
}

bool operator != (const Anaword & lhs, const Anaword & rhs)
// postcondition: returns true if and only if lhs != rhs
{
    return ! lhs.equal(rhs);
}


bool Anaword::less(const Anaword & rhs) const
// postcondition: returns true if and only if *this < rhs
//                canonical/normalized form of word used for comparison    
{
    return false;
}

bool operator <  (const Anaword & lhs,const Anaword & rhs)
// postcondition: returns true if and only if *this < rhs    
{
    return lhs.less(rhs);
}

bool operator <=  (const Anaword & lhs,const Anaword & rhs)
// postcondition: returns true if and only if *this <= rhs
{
    return ! rhs.less(lhs);
}

Anagram class

#ifndef _ANAWORD_H
#define _ANAWORD_H

#include 
#include 
using namespace std;
#include "tvector.h"

// Used for finding anagrams: words with the same letters
// but which are different words, e.g., "bagel" a "gable"
// author: Owen Astrachan
//
// an Anaword object prints as a regular string, but
// compares using a normalized (also called canonicalized) form
//
// Example: the Anaword version of the string "bagel"
//          prints as bagle, but will be compared with
//          other Anawords as a vector of counts
//          of one 'a', one 'b', one 'e', one 'g', one 'l'
//          Since the counts for "gable" are the same, "gable"
//          and "bagel" will be equal when compared using operator ==
//
// basically an Anaword takes a string and converts it to a twenty-six
// digit number based on the counts of a's, b's, c's, ... z's so that
// aardvark is represented as:
//
//  3 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 0 1 0 0 0 0
//
//
// operations:
//
// Anaword(const string & word)      -- construct from a string
//
// bool equal(const Anaword & rhs)   -- compare rhs for equality
// bool operator == (lhs, rhs)       -- compare Anawords lhs == rhs
//
// bool less(const Anaword & rhs)    -- compare rhs for inequality <
// bool operator < (lhs,rhs)         -- compare Anawords lhs < rhs
// bool operator <= (lhs,rhs)        -- compare Anawords lhs <= rhs
//
// string toString()                 -- returns uncanonicalized "bagel"
// ostream & << operator(ostream,    -- print using <<
//                       Anaword)

class Anaword
{
  public:
    Anaword(const string & word);             // construct from string
    Anaword();                                // default (for vector)
    bool equal(const Anaword & rhs) const;    // compare for ==
    bool less(const Anaword & rhs)  const;    // compare for <    
    string toString()               const;    // return "bagel" or "gable"

  private:  

    void normalize();                         // helper function, sorts
    string myWord;                            // regular string: "bagel"
    tvector myCounts;                    // canonicalized form
};

bool operator == (const Anaword & lhs, const Anaword & rhs);
bool operator != (const Anaword & lhs, const Anaword & rhs);
bool operator <  (const Anaword & lhs, const Anaword & rhs);
bool operator <= (const Anaword & lhs, const Anaword & rhs);
ostream & operator << (ostream & out,  const Anaword & a);

#endif 

#include 
#include 
#include 
using namespace std;

#include "anaword.h"
#include "prompt.h"
#include "tvector.h"
#include "sortall.h"



void FindAnagrams(tvector& list)
// pre: list contains list.size() elements
// post: all anagrams in list printed, one set of anagrams per line
{
    QuickSort(list,list.size());
}

int main(int argc, char * argv[])
{
    tvector list;
    ifstream input;
    string filename,word;
    // use command line argument if it exists, else prompt user
    
    if (argc > 1)
    {
 filename = argv[1];
    }
    else
    {
 filename = PromptString("enter file name "); 
    }
    
    input.open(filename.c_str());
    if (input.fail())
    {
 cerr << "could not open " << filename << endl;
 exit(1);
    }

    while (input >> word)
    {
 list.push_back(Anaword(word));
    }
    cout << endl << "read " << list.size() << " words" << endl;

    FindAnagrams(list);

    return 0;
}
 

Do not run the program as it is (without implementing) Anaword::equal and Anaword::less since the call to QuickSort will cause an infinite loop.

Program Description

You'll write a program, part of which is given to you, that reads a file of words and generates as output all the anagrams in the file. Each line of output should contain words that are anagrams of each other, for example:
gazer graze gases sages heals leash shale heaps phase shape hares hears share shear earth hater heart haste hates heats haves shave arise raise lakes leaks Your program should deal with words that contain punctuation. You can ignore these words, but your program should not die/stop if such a word is encountered. You should make your own small test files, but check your final program with the input file words accessible on acpub as ~ola/data/words. (This file is /usr/dict/words from Linux.)

Coding and Algorithm

You must use the class Anaword whose declaration is given in the file anaword.h. You will need to write the implementation of this class in the file anaword.cpp although this has been started for you. An Anaword object is constructed from a string, and prints as the string, but is compared using a normalized or canonical form created by counting the number of times each letter in the word occurs (more on this below). For example, the code fragment below prints the two lines of output shown. <br> Anaword a("bagel");<br> Anaword b("gable");<br><br> cout << a << " " << b << endl;<br> if (a == b) cout << "they're ananagrams!" << endl;<br> Output as shown:
bagel gable they're anagrams! The objects a and b are equal because the operator == is overloaded for Anaword objects and returns true for "bagel" and "gable" since both words have the same normalized/canonical form of letter-signature: 1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 which indicates one 'a', one 'b', one 'e', one 'g', and one 'l'. The signature of aardvark, for example, is 3 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 0 1 0 0 0 0 You must implement the member functions declared and described in anaword.h so that the real word (e.g., "bagel") is used for printing, but the canonical/normal form of the letter-signature is used for comparison using == and <
To do this you'll need to implement all the functions declared in anaword.hthat are not implemented in the anaword.cpp file you're given. This includes

• Anaword::normalize which creates the signature for an Anaword
• Anaword::equal which determines if two Anawords are equal
• Anaword::less which determines if one Anaword is less than another.

For your program to run efficiently your implementations of Anaword::equal and Anaword::less should return true/false after making the minimal number of comparisons possible. Treat the vector myCounts as a 26-digit number so that, for example, "egg" > "ego" since the signatures are
egg: 00001020000000000000000000 ego: 00001010000000100000000000 The determination that "egg" is larger can be made after seven comparisons (the count of g's in egg is greater than the count of g's in ego and 'g' is the seventh letter of the alphabet).

A Working Program

You'll need to add code to doana.cpp to yield a working anagram program. This requires completing the function FindAnagrams using the idea below

1. Sort the vector of Anaword objects using quicksort. You can do this with &lt;br&gt; QuickSort(list, list.size());&lt;br&gt; because Anaword ojbects can be compared using <, ==, and <=. Access to QuickSort is via #include "sortall.h".
   
2. All anagrams are now adjacent in the vector. Make one pass over the elements looking for adjacent elements that are equal. You must write code to determine when two or more adjacent words are equal and print anagrams one set per line as shown at the beginning of this assignment.

Faster Anagrams

You'll now develop another method of canonicalizing an Anaword that's faster than the letter-signature method. First, when you've got the program working, you should add code to time how long it takes to find and print all anagrams in ~ola/data/words which is words, a file of 45,402 words. Write down the name of the machine you used and the time it takes and include these in your README file you submit. You should then create copies of both anaword.h and anaword.cpp by typing cp anaword.h anawordfinger.h cp anaword.cpp anawordfinger.cpp Now you have a copy of your (hopefully) correct Anaword class and implementation. You'll be re-implementing Anaword using another technique, but you'll need to submit both versions so you must make a copy. Instead of using the letter-signature method you'll store a sorted form of the word and use this to compare Anawords. For example, the sorted form of "bagel" and "gable" is the same, it's the string "abegl". This string is used for relational comparisons. To do this you'll need to make a few changes:

1. Remove the declaration below from the private section of Anaword. &lt;br&gt; tvector&amp;amp;lt;int&amp;amp;gt; myCounts; // canonicalized form&lt;br&gt; Then you'll add a new declaration for the sorted word: &lt;br&gt; string mySortedWord; // canonicalized form&lt;br&gt;
   
2. The function Anaword::equal is now one line: &lt;br&gt; return mySortedWord == rhs.mySortedWord;&lt;br&gt;
   
3. The function Anaword::less is similar: &lt;br&gt; return mySortedWord &amp;amp;lt; rhs.mySortedWord;&lt;br&gt;
   
4. The only other change needed is the function Anaword::normalize In this function you should sort the letters in mySortedWord which is a copy of myWord. To sort, use the code from selection sort which can be found in both the Sedgwick and Astrachan texts.
   
5. Be sure to change the comments in anaword.h to reflect the new method used.

When the program works, time it again on the same machine you timed the original program. Write the time in the README file you create. You should also write a paragraph or explaining why you think the timings are different.

Grading

This assignment is worth 15 points. Style of the code/program counts for 5/15, correctness is 8/10 and the README is 2/10.

Submit

You'll submit a README that describes the timings of both versions of the program, includes information about how much time you spent on the assignment, and a list of people with whom you discussed the program. Submit all .h and .cpp files and the README file. You do not need to submit the Makefile unless you modified it.
To submit use
submit_cps100 anagram README *.h *.cpp If submit_cps100 doesn't work, try ~ola/bin/submit100

Extra Credit

This is worth four points. Instead of sorting using < and == for Anawords, create a different ordering so that when anagrams are printed shorter words are printed first and longer words printed last. To do this, create a function object as described in pages 543-549 of the Tapestry text. This object will be used when sorting the vector of Anawords, e.g., you'll write &lt;br&gt; AnaLenComparer analen;&lt;br&gt; ...&lt;br&gt; QuickSort(list,list.size(), analen);&lt;br&gt;
The struct/class AnaLenComparer should compare two Anaword objects, using the length of the strings in the objects as the first criteria of comparison, and using Anaword::less only if the strings have the same length. For example: &lt;br&gt; Anaword a("tear");&lt;br&gt; Anaword b("ace");&lt;br&gt; Anaword c("race");&lt;br&gt; Here we want b to be "less" than a since it has fewer characters, but c is less than a since although they have the same number of characters, the canonicalized forms show that "acer" < "aert".

STatic in java

Constants
Static variables are quite rare. However, static constants are more common. For example, the Math class defines a static constant:
public class Math
{
. . .
public static final double PI = 3.14159265358979323846;
. . .
}

You can access this constant in your programs as Math.PI.
If the keyword static had been omitted, then PI would have been an instance field of the Math class. That is, you would need an object of the Math class to access PI, and every Math object would have its own copy of PI.
Another static constant that you have used many times is System.out. It is declared in the System class as:
public class System
{
. . .
public static final PrintStream out = . . .;
. . .
}

As we mentioned several times, it is never a good idea to have public fields, because everyone can modify them. However, public constants (that is, final fields) are ok. Because out has been declared as final, you cannot reassign another print stream to it:
System.out = new PrintStream(. . .); // ERROR--out is final

NOTE

If you look at the System class, you will notice a method setOut that lets you set System.out to a different stream. You may wonder how that method can change the value of a final variable. However, the setOut method is a native method, not implemented in the Java programming language. Native methods can bypass the access control mechanisms of the Java language. This is a very unusual workaround that you should not emulate in your own programs.

Static Methods
Static methods are methods that do not operate on objects. For example, the pow method of the Math class is a static method. The expression:
Math.pow(x, a)

computes the power xa. It does not use any Math object to carry out its task. In other words, it has no implicit parameter.
You can think of static methods as methods that don't have a this parameter. (In a non-static method, the this parameter refers to the implicit parameter of the method—see page 112.)
Because static methods don't operate on objects, you cannot access instance fields from a static method. But static methods can access the static fields in their class. Here is an example of such a static method:
public static int getNextId()
{
return nextId; // returns static field
}

To call this method, you supply the name of the class:
int n = Employee.getNextId();

Could you have omitted the keyword static for this method? Yes, but then you would need to have an object reference of type Employee to invoke the method.
NOTE

It is legal to use an object to call a static method. For example, if harry is an Employee object, then you can call harry.getNextId() instead of Employee.getnextId(). However, we find that notation confusing. The getNextId method doesn't look at harry at all to compute the result. We recommend that you use class names, not objects, to invoke static methods.

You use static methods in two situations:
• When a method doesn't need to access the object state because all needed parameters are supplied as explicit parameters (example: Math.pow)
• When a method only needs to access static fields of the class (example: Employee.getNextId)
C++ NOTE

Static fields and methods have the same functionality in Java and C++. However, the syntax is slightly different. In C++, you use the :: operator to access a static field or method outside its scope, such as Math::PI.
The term "static" has a curious history. At first, the keyword static was introduced in C to denote local variables that don't go away when a block is exited. In that context, the term "static" makes sense: the variable stays around and is still there when the block is entered again. Then static got a second meaning in C, to denote global variables and functions that cannot be accessed from other files. The keyword static was simply reused, to avoid introducing a new keyword. Finally, C++ reused the keyword for a third, unrelated, interpretation—to denote variables and functions that belong to a class but not to any particular object of the class. That is the same meaning that the keyword has in Java.

Abstract classes

In CPP


A class that contains at least one pure virtual function is said to be abstract. Because an
abstract class contains one or more functions for which there is no definition (that is, a
pure virtual function), no objects of an abstract class may be created. Instead, an
abstract class constitutes an incomplete type that is used as a foundation for derived
classes.
Although you cannot create objects of an abstract class, you can create pointers and
references to an abstract class. This allows abstract classes to support run-time
polymorphism, which relies upon base-class pointers and references to select the
proper virtual function.

JAVA

Function overloading

Thus, the name abs represents the general action which is being
performed. It is left to the compiler to choose the right specific version for a particular
circumstance. You, the programmer, need only remember the general operation being
performed. Through the application of polymorphism, several names have been
reduced to one.

c program without main

/* prog_without_main.c */
_start()
{
_exit(my_main());
}
int my_main(void)
{
printf(“Hello\n”);
return 42;
}
And use this command (% is command prompt) to compile:
%gcc -O3 -nostartfiles prog_without_main.c

Try compiling this example:
#include
#define decode(s,t,u,m,p,e,d) m##s##u##t
#define begin decode(a,n,i,m,a,t,e)
void begin()
{
printf(“hello”);
}
here is how it works once we say define we need to understand that
#define x y
then ‘x’ ix replaced by ‘y’
similarly in this case
#define begin decode(a,n,i,m,a,t,e)
decode(a,n,i,m,a,t,e) is replaced by m##a##i##n
bcoz s is replaced by a,t by n,u by i and so on
s->a
t->n
u->i
m->m
p->a
e->t
d->e
now the statement becomes
void m##a##i##n
And u must be knowing that ## is used for string concatenation so it becomes
“main”
finally the code crops down to
void main()
{
printf(“hello”);
}

Here we are using preprocessor directive #define with arguments to give an impression that the program runs without main.But in reality it runs with a hidden main function.

The ‘##‘ operator is called the token pasting or token merging operator.That is we can merge two or more characters with it.

NOTE: A Preprocessor is program which processess the source code before compilation.

Look at the 2nd line of program-

#define decode(s,t,u,m,p,e,d) m##s##u##t

What is the preprocessor doing here.The macro decode(s,t,u,m,p,e,d) is being expanded as “msut” (The ## operator merges m,s,u & t into msut).The logic is when you pass (s,t,u,m,p,e,d) as argument it merges the 4th,1st,3rd & the 2nd characters(tokens).

Now look at the third line of the program-

#define begin decode(a,n,i,m,a,t,e)

Here the preprocessor replaces the macro “begin” with the expansion decode(a,n,i,m,a,t,e).According to the macro definition in the previous line the argument must de expanded so that the 4th,1st,3rd & the 2nd characters must be merged.In the argument (a,n,i,m,a,t,e) 4th,1st,3rd & the 2nd characters are ‘m’,'a’,'i’ & ‘n’.

So the third line “int begin” is replaced by “int main” by the preprocessor before the program is passed on for the compiler.That’s it…

The bottom line is there can never exist a C program without a main function.Here we are just playing a gimmick that makes us beleive the program runs without main function, but actually there exista a hidden main function in the program.Here we are using the proprocessor directive to intelligently replace the word begin” by “main” .In simple words int begin=int main.