Linked queue BST

[HG319]

I am given this assignment and was wondering if someone can help me with the add function.

An important document is given to you and your job is to create an online index of it so as to be able to find any word's location in the text quickly. You have decided that the best way to do this is to create a binary search tree, with each node containing the word you are searching for along with a linked list (or queue) that contains the line number of the transcript where the word occurs. This way, you can know at what line(s) in the text a word occurs. You must make sure that your program filters the words on input to treat upper and lower case as the same, remove punctuation marks, and not store numerical data as words.

I already wrote the part that reads the file and ignores the numbers and punctuation and also read upper to lower. I was just hoping someone can help me with the add function because I also have to add the line number with it.

Here is what we were given for the add function:

template<class ItemType, class OtherType>
bool BinarySearchTree<ItemType, OtherType>::Add(const ItemType& new_item, const OtherType& new_other)
{
   BinaryNode<ItemType, OtherType>* new_node = new BinaryNode<ItemType, OtherType>(new_item);
   new_node->SetOther(new_other);
   root_ = InsertInorder(root_, new_node);
   return true;
}  // end add
template<class ItemType, class OtherType>
BinaryNode<ItemType, OtherType>* BinarySearchTree<ItemType, OtherType>::InsertInorder(BinaryNode<ItemType, OtherType>* subTreePtr,
										      BinaryNode<ItemType, OtherType>* newNodePtr)
{
 //finish the function
  return NULL;
}  // end insertInorder 

[ne555]

> because I also have to add the line number with it.
just add the word.
Use the word to retrieve the node and access its queue, where you'll push the line number.

[HG319]

thanks. Can you explain a little more?
Just to clarify this is what my private variables have to look like
BinaryNode<ItemType, OtherType>* left;
BinaryNode<ItemType, OtherType>* right;

SO they will contain the word and line number

[ne555]

while( line>>word ){
   node *n = tree.search(word);
   if(n==NULL) n = tree.insert(word);
   n->get_other().push(line_number);
}
++line_number;

[HG319]

I am going to show you what I have so far in the main file. Here are also the headerfiles that I am given. I just need to write the actual statement for some functions, which you saw

int main() {
  ifstream input_file("test_file.txt");
  string line;
  if (input_file.is_open()) {
      int counter = 0;
      while (input_file.good()) {
        getline(input_file,line);
        counter++;
        stringstream word(line);
        while(word>>line){
            for(int i=0; i<line.length(); i++){
                line[i]=tolower(line[i]);
                if(checks if it is a digit))
                   line[i]=' ';
                else if(checks if it is a punctuation)
                   line[i]=' ';
            }
            //BinarySearchTree<string, int> binary_tree(line,counter);//not sure if this is right
            }//end while
      }//end while openfile
      input_file.close();
  } else { cout << "Can't open file" << endl; }
  return 0;
}

for the BST cpp

template<class ItemType, class OtherType>
bool BinarySearchTree<ItemType, OtherType>::Add(const ItemType& new_item, const OtherType& new_other)
{
   BinaryNode<ItemType, OtherType>* new_node = new BinaryNode<ItemType, OtherType>(new_item);
   new_node->SetOther(new_other);
   root_ = InsertInorder(root_, new_node);
   return true;
}  // end add
template<class ItemType, class OtherType>
BinaryNode<ItemType, OtherType>* BinarySearchTree<ItemType, OtherType>::InsertInorder(BinaryNode<ItemType, OtherType>* subTreePtr,
										      BinaryNode<ItemType, OtherType>* newNodePtr)
{
 //finish the function
  return NULL;
}  // end insertInorder  

BinaryNode.h

template<class ItemType, class OtherType>
class BinaryNode
{
public:
   BinaryNode();
   BinaryNode(const ItemType& an_item);
   void SetItem(const ItemType& an_item);
   void SetOther(const OtherType& other);
   ItemType GetItem() const;
   OtherType GetOther() const;
   OtherType &GetOtherReference();
   bool IsLeaf() const;
   BinaryNode<ItemType, OtherType>* GetLeftPtr() const;
   BinaryNode<ItemType, OtherType>* GetRightPtr() const;

   void SetLeftPtr(BinaryNode<ItemType, OtherType>* leftPtr);
   void SetRightPtr(BinaryNode<ItemType, OtherType>* rightPtr);

 private:
   ItemType   item_;  //key 
   OtherType  other_;  //value
   BinaryNode<ItemType, OtherType>* left_ptr;   
   BinaryNode<ItemType, OtherType>* right_ptr;  
}; // end BinaryNod 

BST.h

template<class ItemType, class OtherType>
  class BinarySearchTree : public BinaryTreeInterface<ItemType, OtherType>
{
 public:
 BinarySearchTree(): root_(NULL) { };

  BinarySearchTree(const BinarySearchTree<ItemType, OtherType>& tree);
  BinarySearchTree& operator=(const BinarySearchTree<ItemType, OtherType>& right_hand_side);
  virtual ~BinarySearchTree();


  bool IsEmpty() const;
  int GetHeight() const;
  int GetNumberOfNodes() const;
  bool Add(const ItemType& item, const OtherType& other);
  bool Remove(const ItemType& data); // Removes a node
  void Clear();

  OtherType GetOther(const ItemType& an_item) const throw(NotFoundException);
  OtherType &GetOtherReference(const ItemType& an_item) throw(NotFoundException);
  bool Contains(const ItemType& an_item) const;
 void PreorderTraverse(void visit(ItemType&)) const;
  void InorderTraverse(void visit(ItemType&)) const;
  void PostorderTraverse(void visit(ItemType&)) const;
private:
  BinaryNode<ItemType, OtherType>* root_;

  int GetHeightHelper(BinaryNode<ItemType, OtherType>* node_ptr) const;
  int GetNumberOfNodesHelper(BinaryNode<ItemType, OtherType>* node_ptr) const;
 void DestroyTree(BinaryNode<ItemType, OtherType>* node_ptr);
 BinaryNode<ItemType, OtherType>* InsertInorder(BinaryNode<ItemType, OtherType>* subTreePtr,	 BinaryNode<ItemType, OtherType>* newNode);
BinaryNode<ItemType, OtherType>* RemoveValue(BinaryNode<ItemType, OtherType>* subTreePtr, const ItemType target, bool& success);
BinaryNode<ItemType, OtherType>* RemoveNode(BinaryNode<ItemType, OtherType>* nodePtr);
 BinaryNode<ItemType, OtherType>* RemoveLeftmostNode(BinaryNode<ItemType, OtherType>* subTreePtr, ItemType& inorderSuccessor);
BinaryNode<ItemType, OtherType>* FindNode(BinaryNode<ItemType, OtherType>* treePtr,			const ItemType& target) const;
BinaryNode<ItemType, OtherType>* CopyTree(const BinaryNode<ItemType, OtherType>*node_ptr) const;
  void Preorder(void visit(ItemType&), BinaryNode<ItemType, OtherType>* node_ptr) const;
  void Inorder(void visit(ItemType&), BinaryNode<ItemType, OtherType>* node_ptr) const;
  void Postorder(void visit(ItemType&), BinaryNode<ItemType, OtherType>* node_ptr) const;

the snippet of code you wrote, that would be in my add function?