stringset.cpp

C++&datastructure书籍源码,以前外教提供现在与大家共享

#include "stringset.h"


StringSet::StringSet(int isize)
 : myCount(0),
   myList(isize)
{
    // all work done in initializer list
}

StringSet::StringSet()
   : myCount(0)
{
    // all work done in initializer list
}

int StringSet::search(const string & key) const
// postcondition: returns index at which key occurs in myList
//                returns -1 if key does not occur     
{
    int low = 0;
    int high = myCount-1;
    int mid;                          // middle of current range
    while (low <= high)
    {
        mid = (low + high)/2;
        if (myList[mid] == key)       // found key, exit
        {   return mid;
        }
        else if (myList[mid] < key)   // key in upper half
        {   low = mid + 1;
        }
        else                          // key in lower half
        {   high = mid - 1;
        }
    }
    return -1;
}

void StringSet::insert(const string & word)
// postcondition: inserts word (only if not present)
{
    int loc = search(word);
    if (loc == -1)                 // not already in list
    {
        if (myCount >= myList.capacity())
        {
            myList.resize(myList.capacity()*2 + 1);
        }
        loc = myCount - 1;         // shift structs right
        while (0 <= loc && word < myList[loc])
        {   myList[loc+1] = myList[loc];
            loc--;
        }
        myList[loc+1]= word;
        myCount++;
    }
}

void StringSet::erase(const string & word)
// postcondition: remove word (if present)
{
    int loc = search(word);
    if (loc != -1)
    {
		while (loc < myCount-1)
		{   myList[loc] = myList[loc+1];
		    loc++;
		}
		myCount--;
    }
}

void StringSet::clear()
// postcondition: set is empty
{
    myCount = 0;
}

bool StringSet::contains(const string& s) const
// postcondition: returns true iff s in set
{
    return search(s) != -1;
}

int StringSet::size() const
// postcondition: returns number of elements in set
{
    return myCount;
}


StringSetIterator::StringSetIterator(const StringSet& s)
  : mySet(s),
    myIndex(0)
{
    
}

void StringSetIterator::Init() const
{
    myIndex = 0;
}

bool StringSetIterator::HasMore() const
{
    return myIndex < mySet.size();
}

void StringSetIterator::Next() const
{
    myIndex++;
}
    
string StringSetIterator::Current() const
{
    if (HasMore())
    {   return mySet.myList[myIndex];
    }
    cerr << "StringSetIterator Current() called with no elements" << endl;
    return "";
}