#ifndef LSTRING_H_
#define LSTRING_H_ 1

#include <assert.h>		// has assert()
#include <ctype.h>		// has isspace()
#include "seq.h"		// has Seq template class

class lstring {

public:

  typedef unsigned int length_pos;  // type for length or position

  // -----------------------------------------------------------------
  //
  // Constructors.
  //

  // Post:  This lstring is empty.
  lstring(void) { seq = charseq(); return; }

  // Post:  This lstring consists of single character c.
  lstring(const char c) { seq = charseq(c, charseq()); return; }
  
  // Pre:  cstr is a C-style (null-terminated) string.
  // Post:  This lstring contains characters in cstr.
  lstring(const char cstr[]) { seq = cstr_toSeq(cstr); }

  // No need for a copy constructor -- default will work for us.

  // No need for a destructor -- default will work for us.

  // -----------------------------------------------------------------
  //
  // Member functions.
  //

  // Is string empty?
  // Post:  Returns true if this lstring is empty, false otherwise.
  bool empty(void) const {
    return seq.empty();
  }

  // Length.
  // Post:  Returns length of this lstring.
  length_pos length(void) const {
    return seq.length();
  }

  // Append.
  // Post:  s has been appended to this lstring.
  void append(const lstring & s) {
    seq = cseq_concat(seq, s.seq);
    return;
  }

  // Insert.
  // Pre:  p <= length().
  // Post:  s has been inserted into this lstring before position p.
  //          (If p == length(), this is the same as append(s).)
  void insertBefore(const lstring & s, const length_pos p) {
    seq = cseq_insertBefore(seq, s.seq, p);
    return;
  }

  // Find.
  // Post:  Returns true if this lstring contains s as a substring,
  //          false otherwise.
  bool find(const lstring & s) const {
    return cseq_find(seq, s.seq);
  }

  // Retrieve i-th character.
  // Pre:  i < length().
  // Post:  Returns i-th character in this lstring.
  char getElementAt(const length_pos i) const {
    return cseq_getElementAt(seq, i);
  }

  // Replace i-th character.
  // Pre:  i < length().
  // Post:  i-th character in this lstring has been replaced with c.
  void replaceElementAt(const length_pos i, const char c) {
    seq = cseq_replaceElementAt(seq, i, c);
  }

  // -----------------------------------------------------------------
  //
  // Functions to overload operators.
  //

  // No need to overload assignment -- default will work for us.

  // Addition (in place).
  // Post:  s has been appended to this lstring.
  void operator += (const lstring & s) {
    append(s);
    return;
  }

  // Addition (binary operator).
  // Post:  Returns the concatenation of s1 and s2.
  friend lstring operator + (const lstring & s1, const lstring & s2);

  // Relational operators.
  friend bool operator == (const lstring & s1, const lstring & s2);
  friend bool operator != (const lstring & s1, const lstring & s2);
  friend bool operator < (const lstring & s1, const lstring & s2);
  friend bool operator > (const lstring & s1, const lstring & s2);
  friend bool operator <= (const lstring & s1, const lstring & s2);
  friend bool operator >= (const lstring & s1, const lstring & s2);

  // Stream input and output.
  friend istream & operator >> (istream & istr, lstring & s);
  friend ostream & operator << (ostream & ostr, const lstring & s);

private:

  typedef Seq<char> charseq;

  // -----------------------------------------------------------------
  //
  // Member variables.
  //

  charseq seq;

  // -----------------------------------------------------------------
  //
  // Helper functions.
  //

  // One more constructor, for use in the helper functions.
  // Post:  This lstring contains the characters in s.
  lstring(const charseq & s) { seq = s; return; }

  // Convert C-style string to sequence of chars.
  // Pre:  cstr is a C-style (null-terminated) string.
  // Post:  Returns sequence of chars equivalent to cstr.
  static charseq cstr_toSeq(const char cstr[]) {
    if (cstr[0] == '\0')
      return charseq();
    else
      // use "pointer arithmetic" -- not discussed yet --
      //   to call recursively with cstr minus its first
      //   character,
      return charseq(cstr[0], cstr_toSeq(cstr+1));
  }

  // Concatenation.
  // Post:  Returns the concatenation of s1 and s2.
  static charseq cseq_concat(const charseq & s1, const charseq & s2) {
    if (s1.empty())
      return s2;
    else
      return charseq(s1.hd(), cseq_concat(s1.tl(), s2));
  }

  // Insert.
  // Pre:  p <= s1.length();
  // Post:  Returns a sequence consisting of s1 with s2 inserted
  //          before position p.  (If p == s1.length(), s2 is appended 
  //          to s1.)
  static charseq cseq_insertBefore(const charseq & s1, 
				   const charseq & s2,
				   const length_pos p) {
    if (p == 0) 
      return cseq_concat(s2, s1);
    else {
      assert (!s1.empty());
      return charseq(s1.hd(), cseq_insertBefore(s1.tl(), s2, p-1));
    }
  }

  // Three-way lexicographic compare.
  // Post:  Returns a negative value if s1 < s2, zero if s1 == s2, and
  //          a positive value if s1 > s2.
  static int cseq_compare(const charseq & s1, const charseq & s2) {
    if (s1.empty() && s2.empty())
      return 0;
    else if (s1.empty())
      return -1;
    else if (s2.empty())
      return 1;
    else if (s1.hd() < s2.hd())
      return -1;
    else if (s1.hd() > s2.hd())
      return 1;
    else
      return cseq_compare(s1.tl(), s2.tl());
  }

  // Prefix?
  // Post:  Returns true if s2 is a prefix of s1, false otherwise.
  //          (If s2 is empty, returns true.)
  static bool cseq_isPrefix(const charseq & s1, const charseq & s2) {
    if (s2.empty())
      return true;
    else if (s1.empty())
      return false;
    else if (s1.hd() != s2.hd())
      return false;
    else
      return cseq_isPrefix(s1.tl(), s2.tl());
  }
    
  // Find.
  // Post:  Returns true if s2 is a substring of s1, false otherwise.
  //          (If s2 is empty, returns true.)
  static bool cseq_find(const charseq & s1, const charseq & s2) {
    if (s2.empty())
      return true;
    else if (s1.empty())
      return false;
    else if (cseq_isPrefix(s1, s2))
      return true;
    else
      return cseq_find(s1.tl(), s2);
  }

  // Read element.
  // Pre:  i < s.length().
  // Post:  Returns i-th char of s.
  static char cseq_getElementAt(const charseq & s, const length_pos i) {
    assert (!s.empty());
    if (i == 0)
      return s.hd();
    else
      return cseq_getElementAt(s.tl(), i-1);
  }

  // Replace element.
  // Pre:  i < s.length().
  // Post:  Returns a sequence equivalent to s, but with the i-th
  //          element replaced by c.
  static charseq cseq_replaceElementAt(const charseq & s, 
				       const length_pos i,
				       const char c) {
    assert (!s.empty());
    if (i == 0)
      return charseq(c, s.tl());
    else
      return charseq(s.hd(), cseq_replaceElementAt(s.tl(), i-1, c));
  }

  // Read sequence of characters from input stream.
  // (This code was adapted from the input code in unary.h, and
  //   apparent peculiarities are probably an attempt to mimic that
  //   allegedly correct code.  Caveat reader.)
  // Pre:  istr has been opened.
  //       nonempty is true if we're in the middle of reading a
  //         sequence of characters, false otherwise.  
  // Post:  Returns sequence of characters up to EOF or whitespace.
  //        Sets "failbit" on istr if we didn't read any characters at 
  //          all (copied from unary.h code).
  static charseq cseq_getUpToWS(istream & istr, const bool & nonempty) {

    char c;
    if (istr.get(c)) {
      if (!isspace(c))
	return charseq(c, cseq_getUpToWS(istr, true));
      else {			// whitespace
	istr.putback(c);
	if (!nonempty)
	  istr.setstate(std::ios::failbit);
	return charseq();
      }
    }
    else {
      if (istr.eof() && nonempty)	// string ends the input
	istr.clear(std::ios::eofbit);
      return charseq();
    }
  }

  // Write sequence of characters to output stream.
  // Pre:  ostr has been opened.
  // Post:  Characters in s have been written to ostr contiguously.
  static ostream & cseq_print(ostream & ostr, const charseq & s) {
    if (s.empty())
      return ostr;
    else 
      return cseq_print((ostr << s.hd()), s.tl());
  }
};

// -----------------------------------------------------------------
//
// Friend functions.
//

// Addition.
// Note that += is implemented as a member function.

lstring operator + (const lstring & s1, const lstring & s2) {
  return lstring(lstring::cseq_concat(s1.seq, s2.seq));
}


// Relational operators.

bool operator < (const lstring & s1, const lstring & s2) {
  return (lstring::cseq_compare(s1.seq, s2.seq) < 0);
}

bool operator > (const lstring & s1, const lstring & s2) {
  return s2 < s1;
}

bool operator != (const lstring & s1, const lstring & s2) {
  return (s1 < s2) || (s2 < s1);
}

bool operator == (const lstring & s1, const lstring & s2) {
  return !(s1 != s2);
}

bool operator <= (const lstring & s1, const lstring & s2) {
  return !(s1 > s2);
}

bool operator >= (const lstring & s1, const lstring & s2) {
  return !(s1 < s2);
}


// Stream input and output operators.

istream & operator >> (istream & istr, lstring & s) {

  // discard leading whitespace
  istr >> ws;

  // read until we reach EOF or whitespace
  lstring::charseq temp = lstring::cseq_getUpToWS(istr, false);

  // if we got something, save it
  if (!temp.empty())
    s.seq = temp;

  // return (modified) istream
  return istr;
}

ostream & operator << (ostream & ostr, const lstring & s) {
  return lstring::cseq_print(ostr, s.seq);
}

#endif // LSTRING_H_