sequence.cpp

Go to the documentation of this file.

#ifndef SEQUENCE_IMPLEMENTATION
#define SEQUENCE_IMPLEMENTATION

/*****************************************************************************\
*                                                                             *
*  Name   : sequence                                                          *
*  Author : Chris Koeritz                                                     *
*                                                                             *
*******************************************************************************
* Copyright (c) 1989-$now By Author.  This program is free software; you can  *
* redistribute it and/or modify it under the terms of the GNU General Public  *
* License as published by the Free Software Foundation; either version 2 of   *
* the License or (at your option) any later version.  This is online at:      *
*     http://www.fsf.org/copyleft/gpl.html                                    *
* Please send any updates to: fred@gruntose.com                               *
\*****************************************************************************/

#include "array.cpp"
#include "function.h"
#include "guards.h"
#include "sequence.h"

template <class contents>
int sequence<contents>::comparator(const sequence &s2) const
{
  if (!this->length() && !s2.length()) return 0;
  for (int i = 0; i < minimum(this->length(), s2.length()); i++) {
    if (this->get(i) < s2.get(i)) return -1;
    else if (s2.get(i) < this->get(i)) return 1;
  }
  if (this->length() < s2.length()) return -1;
  else if (this->length() > s2.length()) return 1;
  else return 0;
}

template <class contents>
int sequence<contents>::find(const contents &to_find, int &position,
    outcome &outcome) const
{
  outcome = common::OUT_OF_RANGE;
  bounds_return(position, 0, this->last(), 0);
  for (int i = position; i < this->length(); i++)
    if (this->get(i) == to_find) {
      position = i;
      outcome = common::OKAY;
      return i;
    }
  outcome = common::NOT_FOUND;
  return 0;
}

template <class contents>
int sequence<contents>::find(const sequence &to_find, int &position,
    outcome &outcome) const
{
  outcome = common::OUT_OF_RANGE;
  bounds_return(position, 0, this->length() - to_find.length(), 0);
//hmmm: there is a better way to do this loop in terms of the number of
//      comparisons performed!  knuth morris pratt algorithm?
  for (int i = position; i < this->length() - to_find.length() + 1; i++) {
    sequence<contents> chopped = this->subarray(i, i + to_find.last());
    if (chopped == to_find) {
      position = i;
      outcome = common::OKAY;
      return i;
    }
  }
  outcome = common::NOT_FOUND;
  return 0;
}

#endif

---