static void parse_variation( utf8_string<zstring const> const &u_picture_str,
                             utf8_string<zstring const>::const_iterator *u,
                             picture *pic, QueryLoc const &loc ) {
  utf8_string<zstring const>::const_iterator &v = *u;
  if ( v == u_picture_str.end() )
    return;
  if ( *v == '(' ) {
    //
    // XQuery F&O 3.0 4.6.1: The string of characters between the parentheses,
    // if present, is used to select between other possible variations of
    // cardinal or ordinal numbering sequences. The interpretation of this
    // string is implementation-defined. No error occurs if the implementation
    // does not define any interpretation for the defined string.
    //
    utf8_string<zstring> u_pic_co_string( pic->modifier.co_string );
    while ( true ) {
      if ( ++v == u_picture_str.end() )
        throw XQUERY_EXCEPTION(
          err::FODF1310,
          ERROR_PARAMS( *u_picture_str.get(), ZED( CharExpected_3 ), ')' ),
          ERROR_LOC( loc )
        );
      unicode::code_point const cp = *v;
      if ( cp == ')' )
        break;
      u_pic_co_string += cp;
    }
    ++v;
  }
}

 void extend(const utf8_string& word){
   if (!word.empty()){
     ACNode* node = add(word.front());
     node->extend(slice_from(word, 1));
   }
   else{
     add(chars::full_stop);
   }
 }

static utf8_string split_word(const TextInfo& info,
  const utf8_string& string,
  text_lines_t& result)
{
  // Just break the word in half.
  const utf8_string half(slice_up_to(string, string.size() / 2));
  const coord width = info.GetWidth(half);
  result.push_back(TextLine::SoftBreak(width, half));
  return slice_from(string, string.size() / 2);
}

// Split the filename into root and extension, which if concatenated
// are equal to the filename.
std::pair<utf8_string, utf8_string> split_extension(const FileName& f){
  const utf8_string s = f.Str();
  auto pos = s.rfind(chars::full_stop);
  if (pos == utf8_string::npos){
    return {s, utf8_string()};
  }
  else{
    return {slice_up_to(s, pos), slice_from(s, pos)};
  }
}

shared_ptr<regex_node> csu::parse_literal(const utf8_string& regex, uint& position)
//parse a regex literal
{
    list< shared_ptr<regex_node> > chars;
    position+=1;
    while(position<regex.get_length())
    {
        if(regex[position]=="\"")
        {
            auto a=shared_ptr<regex_node>(new concat_node(chars));
            return a;
        }
        else if(regex[position]=="\\")//escape char
        {
            position+=1;
            if(position==regex.get_length())
            {
                throw gen_exception("REGEX ERROR: escape charector at end of string");
            }
            else if( regex[position]=="\"" )
            {
                shared_ptr<regex_node> new_node(new multi_span(code_point(0x0022)));
                chars.push_back(new_node);
            }
            else if(regex[position]=="\\")
            {
                shared_ptr<regex_node> new_node(new multi_span(code_point(0x005C)));
                chars.push_back(new_node);
            }
            else if(regex[position]=="n")
            {
                shared_ptr<regex_node> new_node(new multi_span(code_point(0x000A)));
                chars.push_back(new_node);
            }
            else if(regex[position]=="t")
            {
                shared_ptr<regex_node> new_node(new multi_span(code_point(0x0009)));
                chars.push_back(new_node);
            }
            else
            {
                throw gen_exception("REGEX ERROR: unrecognized escape charector");
            }
            position+=1;
        }
        else
        {
            shared_ptr<regex_node> new_node(new multi_span(regex[position]));
            chars.push_back(new_node);
            position+=1;
        }
    }

    throw gen_exception("REGEX ERROR: literal not terminated by \"");
}

void AutoComplete::add(const utf8_string& word){
  for (size_t i = 0; i != m_nodes.size(); i++){
    if (m_nodes[i]->m_char == word.front()){
      m_nodes[i]->extend(slice_from(word, 1));
      return;
    }
  }

  ACNode* node = new ACNode(word.front());
  m_nodes.push_back(node);
  node->extend(slice_from(word, 1));
}

std::pair<int, int> NFA_automation::run(const utf8_string& input, bool print_status)
{
    uint position_matched=0;
    int accepting_info=-1;
    uint current_position=0;
    fill(current_states.begin(), current_states.end(), false);
    current_states[0]=true;
    while(true)
    {
        // test if we want to continue
        bool cont=false;
        for(bool in_state : current_states)
        {
            if(in_state)
            {
                cont=true;
                break;
            }
        }
        if(not cont) break; //if cont is false, then we have no active states
        if(print_status) cout<<"ITER"<<endl;

        // make epsilon transitions
        bool made_epsilon_transition=false;
        for(uint state_index=0; state_index!=num_states; state_index+=1)
        {
            if(not current_states[state_index]) continue;

            if(states[state_index]->accepting_info>-1 and (current_position>position_matched or states[state_index]->accepting_info<accepting_info ) )
            {
                position_matched=current_position;
                accepting_info=states[state_index]->accepting_info;
                if( print_status) cout<<"accepted:"<<accepting_info<<" at "<<position_matched<<endl;
            }

            if(print_status) cout<<"transitions on epsilon:"<<endl;
            made_epsilon_transition=made_epsilon_transition or enter_states(current_states, states[state_index]->get_transitions(NFA_state::epsilon) );
        }
        if(made_epsilon_transition) continue; //repeat last bit until no epsilon transitions

        //make transitions based upon next charector
        fill(new_states.begin(), new_states.end(), false);
        if(current_position<input.get_length())
        {
            for(uint state_index=0; state_index!=num_states; state_index+=1)
            {
                if(not current_states[state_index]) continue;

                if(print_status) cout<<"Transitions on "<<input[current_position]<<endl;
                enter_states(new_states, states[state_index]->get_transitions(input[current_position]));
            }
            current_position+=1;
        }

        current_states=new_states;
    }

    return make_pair(position_matched, accepting_info);
}

void ring_buffer::put(utf8_string& data)
//put data at end of buffer
{
    if(data.get_length()==0) return;

    if( (n_nodes-length_loaded)<= data.get_length())//check to see if we have enough space
    {
        add_nodes(data.get_length()-(n_nodes-length_loaded)+1);
    }

    for(auto& charector : data)
    {
        empty_node->charector=charector;
        empty_node=empty_node->next;
        length_loaded++;
    }

    has_read_EOF=false;
}

text_lines_t split_string(const TextInfo& info,
  const utf8_string& string,
  const max_width_t& maxWidth)
{
  size_t lineEnd = 0;
  size_t lineStart = 0;

  text_lines_t result;

  do {
    lineEnd = string.find(chars::eol, lineStart);
    bool softBreak = lineEnd == std::string::npos;
    if (softBreak){
      lineEnd = string.size();
    }

    const coord width = info.GetWidth(slice(string, lineStart, lineEnd));
    if (maxWidth.NotSet() || width < maxWidth.Get()){
      if (softBreak){
        result.push_back(TextLine::SoftBreak(width,
          slice(string, lineStart, lineEnd) + chars::space));
        lineStart = lineEnd + 1;
      }
      else{
        result.push_back(TextLine::HardBreak(width,
          slice(string, lineStart, lineEnd) + chars::space));
        lineStart = lineEnd + 1;
      }
    }
    else{
      split_line(info, slice(string, lineStart, lineEnd),
        maxWidth.Get(), result);
      lineStart = lineEnd;
    }
  } while (lineEnd != string.size());

  if (!result.empty()){
    // Remove trailing space from last line
    auto& last = result.back().text;
    last = slice_up_to(last, -1);
  }
  return result;
}

 binary_string_ptr prepare_frame(frame::opcode::value opcode,
                                 bool mask,
                                 const utf8_string& payload)  {
     if (opcode != frame::opcode::TEXT) {
         // TODO: hybi_legacy doesn't allow non-text frames.
         throw;
     }
     
     // TODO: mask = ignore?
     
     // TODO: utf8 validation on payload.
     
     binary_string_ptr response(new binary_string(payload.size()+2));
     
     (*response)[0] = 0x00;
     std::copy(payload.begin(),payload.end(),response->begin()+1);
     (*response)[response->size()-1] = 0xFF;
     
     return response;
 }

//functions for parsing regex into a regex AST
void csu::count_whitespace(const utf8_string& regex, uint& position)
//counts the amount of whitespace following(including) position
{
    for( ; position<regex.get_length(); position++ )
    {
        if(not (regex[position]=="\n" or  regex[position]=="\r" or regex[position]==" ") )
        {
            return;
        }
    }
}

Words AutoComplete::match(const utf8_string& str){
  WordsImpl* w = new WordsImpl();
  w->m_node = nullptr;

  if (str.empty()){
    return Words(w);
  }

  for (size_t i = 0; i != m_nodes.size(); i++){
    ACNode* node = m_nodes[i];
    if (node->m_char == str.front()){
      ACNode* found = node->find(str);
      if (found != nullptr){
        w->m_node = found;
        w->m_base = str;
        break;
      }
    }
  }
  return Words(w);
}

// Split a line at suitable positions to make it shorter than
// maxWidth. The line should not contain embedded line breaks.
static void split_line(const TextInfo& info,
  const utf8_string& string,
  coord maxWidth, text_lines_t& result)
{
  size_t wordStart = 0;
  size_t wordEnd = 0;

  utf8_string line;
  do {
    wordEnd = string.find(chars::space, wordStart);
    if (wordEnd == std::string::npos){
      wordEnd = string.size();
    }
    utf8_string word = slice(string, wordStart, wordEnd);
    const coord width = info.GetWidth(line + chars::space + word);
    if (!line.empty() && width > maxWidth){
      result.push_back(TextLine::SoftBreak(width, line + chars::space));
      line.clear();
    }

    if (info.GetWidth(word) > maxWidth){
      word = split_word(info, word, result);
    }

    if (!line.empty()){
      line += chars::space;
    }

    line += word;
    wordStart = wordEnd + 1;
  } while (wordEnd != string.size());

  if (line.size() > 1){
    const utf8_string last(line + chars::space);
    const coord width = info.GetWidth(last);
    result.push_back(TextLine::SoftBreak(width, last));
  }
}

bool ts::server::is_builtin_asset(const utf8_string& path_string)
{
    boost::filesystem::path data = config::data_directory;
    boost::filesystem::path sounds = config::sound_directory;

    for (boost::filesystem::path path = path_string.string(); !path.empty(); path = path.parent_path())
    {
        if (equivalent(path, data) || equivalent(path, sounds))
        {
            return true;
        }
    }

    return false;  
}

shared_ptr<regex_node> csu::parse_concat_node(const utf8_string& regex, uint& position)
//parses a series of regex nodes, forming them into a concat_node Will raise a gen_exception if regex can't be read
{
    shared_ptr<concat_node> ret(new concat_node());

    while(position<regex.get_length())
    {
        if(regex[position]==")")
        {
            break;
        }
        shared_ptr<regex_node> out=parse_single_node(regex, position);
        if(not out)
        {
            return out;
        }
        ret->add_node(out);
    }

    return ret;
}

void ring_buffer::insert(utf8_string& data)
//place data before end_node
{
    if(data.get_length()==0) return;

    //create new nodes and insert charectors
    auto previous_node=end_node->previous;
    auto before_data=previous_node;
    for(auto& charector : data)
    {
        ring_buffer_node* new_node=new ring_buffer_node();
        new_node->charector=charector;
        previous_node->next=new_node;
        new_node->previous=previous_node;
        previous_node=new_node;
        length_loaded++;
    }
    previous_node->next=end_node;
    end_node->previous=previous_node;
    end_node=before_data->next;
    has_read_EOF=false;
}

/// Convert UTF-8 to UTF-16.
utf16_string Halyard::utf16_from_utf8(const utf8_string &utf8) {
    utf16_string result;
    result.reserve(utf8.size());

    // Suppress GCC warning about possibly undefined variable.
    wchar_t wc = 0;

    size_t i = 0;
    while (i < utf8.size()) {
        char init = utf8[i];
        if ((init & 0x80) == 0x00) {
            // Convert ASCII character to wide character.
            wc = init;
            i++;
        } else {
            
            // Look up the length of this UTF-8 sequence.
            size_t length = utf8_seq_length[(unsigned char) init];
            
            // Check to make sure we have enough bytes to convert.
            CHECK(i + length <= utf8.size(), "Truncated UTF-8 sequence");
            
            // Decode a multibyte UTF-8 sequence.
            char con1;
            char con2;
            switch (length) {
                case 0:
                    THROW("Invalid UTF-8 initial byte");
                    
                case 2:
                    // 110xxxxx 10xxxxxx
                    con1 = utf8[i+1];
                    CHECK(IS_CONTINUATION(con1), "UTF-8 sequence too short");
                    wc = ((((wchar_t) (init & 0x1F)) <<  6) |
                          (((wchar_t) (con1 & 0x3F))));
                    break;
                    
                case 3:
                    // 1110xxxx 10xxxxxx 10xxxxxx
                    con1 = utf8[i+1];
                    con2 = utf8[i+2];
                    CHECK(IS_CONTINUATION(con1) && IS_CONTINUATION(con2),
                          "UTF-8 sequence too short");
                    wc = ((((wchar_t) (init & 0x0F)) << 12) |
                          (((wchar_t) (con1 & 0x3F)) <<  6) |
                          (((wchar_t) (con2 & 0x3F))));
                    break;
                    
                case 4:
                    // 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
                case 5:
                    // 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
                case 6:
                    // 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
                    THROW("UCS-4 characters not supported");
                    
                default:
                    gLog.Fatal("halyard", "Error in UTF-8 decoder tables");
            }
            
            // Advance to the end of the sequence.
            i += length;
            
            // Check for illegal UCS-2 characters.
            CHECK(wc <= UCS2_MAX_LEGAL_CHARACTER,
                  "UCS-2 characters > U+FFFD are illegal");
            
            // Check for UTF-16 surrogates.
            CHECK(wc < UTF16_FIRST_SURROGATE || UTF16_LAST_SURROGATE < wc,
                  "UTF-16 surrogates may not appear in UTF-8 data");
            
            // Check for overlong sequences.
            CHECK(wc >= utf8_min_char_for_length[length],
                  "Overlong UTF-8 sequence not allowed");
        }
        
        // Append the decoded character to our result.
        result.push_back(wc);
    }
    return result;
}

shared_ptr<regex_node> csu::parse_class(const utf8_string& regex, uint& position)
//parse a regex class
{
    uint regex_len=regex.get_length();
    //bool invert=false;
    list<code_point> span_begin;
    list<code_point> span_end;

    count_whitespace(regex, position);

    if(position==regex_len)
    {
        throw gen_exception("REGEX ERROR: class not terminated by ]");
    }

    //if(regex[position]=="^")
    //{
        //position+=1;
        //invert=false;
    //}
    //else

    //check charectors at beginning
    bool in_beginning=true;
    while(in_beginning)
    {
        in_beginning=false;
        if(regex[position]=="-" or regex[position]=="]") //special literal charectors
        {
            span_begin.push_back(regex[position]);
            span_end.push_back(regex[position]);
            position+=1;
            in_beginning=true;
        }
        else if(regex[position]=="#")//special span
        {
            auto A=code_point(0xC0);
            auto B=code_point(0x1FFFFF);
            span_begin.push_back( A );
            span_end.push_back( B );
            position+=1;
            in_beginning=true;
        }
    }

    while(position<regex_len)
    {
        count_whitespace(regex, position);

        //check end
        if(regex[position]=="]")
        {
            //need to do invert here
            return shared_ptr<regex_node>(new multi_span(span_begin, span_end));
        }

        //check range
        else if((not ((position+2)>=regex_len )) and regex[position+1]=="-")
        {
            const code_point& first_char( regex[position] );
            const code_point& second_char( regex[position+2] );

            if(second_char>first_char)
            {
                span_begin.push_back(first_char);
                span_end.push_back(second_char);
                position+=3;
            }
            else
            {
                throw gen_exception("REGEX ERROR: range start is after range end in class");
            }
        }

        //everything else
        else
        {
            span_begin.push_back( regex[position] );
            span_end.push_back( regex[position] );
            position+=1;
        }
    }

    throw gen_exception("REGEX ERROR: class not terminated by ]");
}

ts::resources::Resource_config_exception::Resource_config_exception(const utf8_string& resource_name)
: runtime_error("could not load '" + std::string(script_config_file_name) + "' in resource '" + resource_name.string() + "'")
{
}

ts::utf8_string ts::resources::resource_car_directory(const utf8_string& resource_root_directory)
{
    boost::filesystem::path path(resource_root_directory.string());
    path /= "cars";
    return path.string();
}