Fib Problem

main.cpp

#include <iostream>
#include <cstdlib>

using namespace std;

class Node
{
   private:
      int data;
      Node * next;
      Node * previous;

   public:
      Node();
      Node* getNext();
      Node* getPrevious();
      int getData();
      void setData(int item);
      void setNext(Node* node);
      void setPrevious(Node* node);
};

class List
{
   private:
      int numItems;
      Node * firstNode;
  
   public:
      List();
      ~List();
      List(const List &listToCopy);
      List& operator = (const List &rightSide);
      void insert(int item, int pos = 0);
      void remove(int pos);
      int lookup(int item) const;
      int getData(int pos) const;
      int empty(void) const;
      int getNumItems(void) const;
};

class Giant
{
   private:
      List chunks;
      int chunkSize;

   public:
      Giant();
      Giant(const Giant & listToCopy);
      Giant(int data);
      Giant & operator = (Giant rightSide);
      Giant operator + (const Giant & rightSide);
      //Giant & operator + (int rightSide);
      friend ostream & operator << (ostream & out, const Giant & giant);
};

/*******************************************************************
 * Initializes a node
 *******************************************************************/
Node::Node()
{
   data = 0;
   next = NULL;
}

/*******************************************************************
 * Returns the next node
 *******************************************************************/
Node * Node::getNext()
{
   return next;
}

/*******************************************************************
 * Returns the previous node
 *******************************************************************/
Node * Node::getPrevious()
{
   return previous;
}

/*******************************************************************
 * Returns the data of this node
 *******************************************************************/
int Node::getData()
{
   return data;
}

/*******************************************************************
 * Sets the data of this node
 *******************************************************************/
void Node::setData(int item)
{
   data = item;
}

/*******************************************************************
 * Sets the next node for this node
 *******************************************************************/
void Node::setNext(Node * node)
{
   next = node;
}

/*******************************************************************
 * Sets the previous node for this node
 *******************************************************************/
void Node::setPrevious(Node * node)
{
   previous = node;
}

/*******************************************************************
 * Initializer for a list
 *******************************************************************/
List::List()
{
   numItems = 0;
   firstNode = 0;
}

/*******************************************************************
 * Destructor for a list
 *******************************************************************/
List::~List()
{
   Node * p = firstNode;
   while(p)
   {
      Node * temp = p;
      p = p->getNext();
      delete temp;
   }
}

/*******************************************************************
 * Copy Constructor for a list
 *******************************************************************/
List::List(const List & rightSide)
{
   // Set the size
   numItems = rightSide.numItems;

   // Set the first node
   Node * node = new Node();
   node->setData(rightSide.firstNode->getData());
   firstNode = node;

   // Track the last
   Node * lastNode = node;

   // Append the nodes to the end
   for(Node * p = rightSide.firstNode->getNext(); p; p = p->getNext())
   {
      Node * newNode = new Node();
      newNode->setData(p->getData());
      lastNode->setNext(newNode);
      newNode->setPrevious(lastNode);
      lastNode = newNode;
   }
}

/*******************************************************************
 * Assignment Operator for a list
 *******************************************************************/
List & List::operator = (const List &rightSide)
{
   // Delete all the old data:
   if (firstNode != 0)
   {
      Node * p = firstNode;
      while(p)
      {
         Node * temp = p;
         p = p->getNext();
         delete temp;
      }
   }

   // Copy all the new...

   // Set the size
   numItems = rightSide.numItems;

   // Set the first node
   Node * node = new Node();
   node->setData(rightSide.firstNode->getData());
   firstNode = node;

   // Track the last
   Node * lastNode = node;

   // Append the nodes to the end
   for(Node * p = rightSide.firstNode->getNext(); p; p = p->getNext())
   {
      Node * newNode = new Node();
      newNode->setData(p->getData());
      lastNode->setNext(newNode);
      newNode->setPrevious(lastNode);
      lastNode = newNode;
   }
}

/*******************************************************************
 * Insertion function for a list
 *   Inserts an Node who's data is item at the pos
 *******************************************************************/
void List::insert(int item, int pos)
{
   Node * node = new Node();
   node->setData(item);

   if (pos > numItems)
      pos = numItems;
   if (pos < 0)
      pos = 0;

   if (numItems == 0)
   {
      // No Index needed for the first node
      firstNode = node;
   }
   else if (pos == 0)
   {
      // Inserting to the head changes the head
      node->setNext(firstNode);
      firstNode = node;
   }
   else if (pos == numItems)
   {
      // Inserting to the end
      Node * previous = firstNode;
      for(Node * p = firstNode->getNext(); p; p = p->getNext())
         previous = p;
      previous->setNext(node);
      node->setPrevious(previous);
   }
   else
   {
      // Inserting in the middle
      int count = 1;
      Node * previous = firstNode;
      for(Node * p = firstNode->getNext(); p; p = p->getNext())
      {
         if (pos == count)
         {
            previous->setNext(node);
            node->setPrevious(previous);
            node->setNext(p);
            p->setPrevious(node);
            break;
         }
         previous = p;
         count += 1;
      }
   }
   // Sanity
   numItems += 1;
}

/*******************************************************************
 * Remove function for a list
 *   Removes a node at the pos
 *******************************************************************/
void List::remove(int pos)
{
   // Restrict the bounds
   if (pos > numItems)
      pos = numItems;
   if (pos < 0)
      pos = 0;

   if (numItems == 1)
      // No Index needed for the first node
      delete firstNode;
   else if (pos == 0)
   {
      // Deleting from the head changes the head
      Node * temp = firstNode;
      firstNode = firstNode->getNext();
      firstNode->setPrevious(NULL);
      delete temp;
   }
   else
   {
      // Removing from the middle
      int count = 1;
      Node * previous = firstNode;
      for(Node * p = firstNode->getNext(); p; p = p->getNext())
      {
         if (pos == count)
         {
            previous->setNext(p->getNext());
            p->getNext()->setPrevious(previous);
            delete p;
            break;
         }
         previous = p;
         count += 1;
      }
   }
   numItems -= 1;
}

/*******************************************************************
 * Finds the index of an item in a list
 *******************************************************************/
int List::lookup(int item) const
{
   int count = 0;
   for(Node * p = firstNode; p; p = p->getNext())
   {
      if (p->getData() == item)
         return count;
      count++;
   }
   return -1;
}

/*******************************************************************
 * Finds the data for a node at pos
 *******************************************************************/
int List::getData(int pos) const
{
   int count = 0;
   for(Node * p = firstNode; p; p = p->getNext())
   {
      if (count == pos)
      {
         return p->getData();
      }
      count++;
   }
}

/*******************************************************************
 * Returns true if this list is empty
 *******************************************************************/
int List::empty() const
{
   return numItems == 0;
}

/*******************************************************************
 * Returns the number of items in the list
 *******************************************************************/
int List::getNumItems() const
{
   return numItems;
}

Giant::Giant()
{
   chunkSize = 1000000000;
}

Giant::Giant(const Giant & rightSide)
{
   chunkSize = rightSide.chunkSize;
   chunks = List(rightSide.chunks);
}

Giant::Giant(int data)
{
   chunkSize = 1000000000;
   chunks.insert(data);
}

Giant & Giant::operator = (Giant rightSide)
{
   chunks = rightSide.chunks;
   chunkSize = rightSide.chunkSize;
   return (*this);
}

Giant Giant::operator + (const Giant & rightSide)
{
   Giant returned;
   int extra = 0;

   for(int i = 0;
      i < chunks.getNumItems() && i < rightSide.chunks.getNumItems(); i++)
   {
      int num = chunks.getData(i) + rightSide.chunks.getData(i);
      returned.chunks.insert((num % chunkSize) + extra,
         returned.chunks.getNumItems());
      extra = num / chunkSize;
   }

   if (extra != 0)
   {
      returned.chunks.insert(extra, returned.chunks.getNumItems());
   }

   if(chunks.getNumItems() > rightSide.chunks.getNumItems())
   {
      for(int i = rightSide.chunks.getNumItems();
         i < chunks.getNumItems(); i+=1)
      {
         returned.chunks.insert(chunks.getData(i),
            returned.chunks.getNumItems());
      }
   }
   else if(chunks.getNumItems() < rightSide.chunks.getNumItems())
   {
      for(int i = chunks.getNumItems();
            i < rightSide.chunks.getNumItems(); i+=1)
      {
         returned.chunks.insert(rightSide.chunks.getData(i),
            returned.chunks.getNumItems());
      }
   }

   return returned;
}

ostream & operator << (ostream & out, const Giant & giant)
{
   for(int i = giant.chunks.getNumItems() - 1;
      i >= 0; i -= 1)
   {
      out << giant.chunks.getData(i);
   }
   return out;
}

Giant fib(int index)
{
   Giant first = 0;
   Giant second = 1;
   Giant next = 0;

   for(int i = 0; i < index; i += 1)
   {
      first = second;
      second = next;
      next = first + second;
   }

   return next;
}

int main()
{
   int i = 261;
   cout << i << ": " << fib(i) << endl;
   return 0;
}