Sans Pareil Technologies, Inc.

Key To Your Business

Lab3 - Trie


In this lab exercise, we will develop a simple prototype auto complete service that will return matching text based on prefix text that a hypothetical user/client sends to the service. We will use the simple compressed Trie implementation which is more than sufficient for the purposes of this lab exercise (single header file include).

Note:

There are a couple of bugs in the trie header that is distributed. Edit the file and make the following changes:

  • Go to line 44 and replace the unsigned with auto.

  • Change line 491 to include a check for valid pointer
    if ( _impl && !_impl->get()->has_value() ) { ++( *this ); }

ACS 
The interface for the auto complete service. Note that this service can only match strings that start with the same case that the input string was in.

File: AutoCompleteService.h
#pragma once

#include "trie.h"

namespace csc280
{
  class AutoCompleteService
  {
  public:
    using Matches = std::vector<std::string>;

    AutoCompleteService() = default;
    ~AutoCompleteService() = default;

    AutoCompleteService( const AutoCompleteService& ) = delete;
    AutoCompleteService& operator=( const AutoCompleteService& ) = delete;

    template <typename InputIterator>
    AutoCompleteService( InputIterator begin, InputIterator end )
    {
      assign( begin, end );
    }

    AutoCompleteService( std::initializer_list<std::string> list )
    {
      assign( std::make_move_iterator( list.begin() ), std::make_move_iterator( list.end() ) );
    }

    void add( std::string word );
    Matches matches( const std::string& prefix ) const;

  private:
    template <typename InputIterator>
    void assign( InputIterator begin, InputIterator end );

    using Set = trie::trie_map<char, trie::SetCounter>;
    Set set;
  };

  template <typename InputIterator>
  void AutoCompleteService::assign( InputIterator begin, InputIterator end )
  {
    for ( auto iter = begin; iter != end; ++iter ) add( *iter );
  }
}
ACS Impl 
The implementation of the auto complete service.

File: AutoCompleteService.cpp
#include "AutoCompleteService.h"
#include <algorithm>

using csc280::AutoCompleteService;

void AutoCompleteService::add( std::string word )
{
  if ( !set.contains( word ) ) set.insert( std::move( word ) );
}

AutoCompleteService::Matches AutoCompleteService::matches( const std::string& prefix ) const
{
  Matches matches;
  auto self = const_cast<AutoCompleteService*>( this );

  for ( auto iter = self->set.find_prefix( prefix ); iter != self->set.end(); ++iter )
  {
    matches.push_back( iter.key() );
  }

  std::sort( matches.begin(), matches.end() );
  return matches;
}
CIACS 
The definition of the case insensitive auto complete service.

File: CIAutoCompleteService.h
#pragma once

#include "trie.h"

namespace csc280
{
  class CIAutoCompleteService
  {
  public:
    using Matches = std::vector<std::string>;

    CIAutoCompleteService() = default;
    ~CIAutoCompleteService() = default;

    CIAutoCompleteService( const CIAutoCompleteService& ) = delete;
    CIAutoCompleteService& operator=( const CIAutoCompleteService& ) = delete;

    template <typename InputIterator>
    CIAutoCompleteService( InputIterator begin, InputIterator end )
    {
      assign( begin, end );
    }

    CIAutoCompleteService( std::initializer_list<std::string> list )
    {
      assign( std::make_move_iterator( list.begin() ), std::make_move_iterator( list.end() ) );
    }

    void add( std::string word );
    Matches matches( std::string prefix ) const;

  private:
    template <typename InputIterator>
    void assign( InputIterator begin, InputIterator end );

    trie::trie_map<char, std::vector<std::string>> map;
  };


  template <typename InputIterator>
  void CIAutoCompleteService::assign( InputIterator begin, InputIterator end )
  {
    for ( auto iter = begin; iter != end; ++iter ) add( *iter );
  }
}
CIACS Impl 
The implementation file for the case insensitive auto complete service.

File: CIAutoCompleteService.cpp
#include "CIAutoCompleteService.h"
#include <algorithm>

using csc280::CIAutoCompleteService;

void CIAutoCompleteService::add( std::string word )
{
  auto lower = word;
  std::transform( lower.begin(), lower.end(), lower.begin(), ::tolower );

  auto iter = map.find( lower );
  if ( iter == map.end() ) map.insert( lower, { std::move( word ) } );
  else iter.value().push_back( std::move( word ) );
}

CIAutoCompleteService::Matches CIAutoCompleteService::matches( std::string prefix ) const
{
  Matches matches;
  auto self = const_cast<CIAutoCompleteService*>( this );

  std::transform( prefix.begin(), prefix.end(), prefix.begin(), ::tolower );

  for ( auto iter = self->map.find_prefix( prefix ); iter != self->map.end(); ++iter )
  {
    std::copy( iter.value().cbegin(), iter.value().cend(), std::back_inserter( matches ) );
  }

  std::sort( matches.begin(), matches.end() );
  return matches;
}
ACS Test 
A simple test suite for the auto complete service.

File: CaseSensitive.cpp
#include "catch.hpp"
#include "../main/AutoCompleteService.h"

SCENARIO( "Auto complete service returns based on words added to it" )
{
  GIVEN( "An empty auto complete service instance" )
  {
    csc280::AutoCompleteService service;

    THEN( "Empty service does not return any matches" )
    {
      const auto matches = service.matches( "an" );
      REQUIRE( matches.empty() );
    }
  }

  GIVEN( "An auto complete service with known data" )
  {
    csc280::AutoCompleteService service;
    service.add( "program" );
    service.add( "programming" );
    service.add( "programmer" );
    service.add( "iterate" );
    service.add( "iterator" );
    service.add( "iterating" );
    service.add( "language c++" );
    service.add( "language scala" );
    service.add( "language erlang" );
    service.add( "language haskell" );

    THEN( "Auto complete service finds words starting with prog" )
    {
      const auto matches = service.matches( "prog" );
      const csc280::AutoCompleteService::Matches expected{
        "program", "programmer", "programming" };
      REQUIRE( expected == matches );
    }

    AND_THEN( "Auto complete service finds words starting with iter" )
    {
      const auto matches = service.matches( "iter" );
      const csc280::AutoCompleteService::Matches expected{
        "iterate", "iterating", "iterator" };
      REQUIRE( expected == matches );
    }

    AND_THEN( "Auto complete service finds words with spaces" )
    {
      const auto matches = service.matches( "language" );
      const csc280::AutoCompleteService::Matches expected{
        "language c++", "language erlang", "language haskell", "language scala" };
      REQUIRE( expected == matches );
    }

    AND_THEN( "Auto complete service does not find words with different case" )
    {
      const auto matches = service.matches( "Lang" );
      REQUIRE( matches.empty() );
    }

    AND_THEN( "Auto complete service returns empty results for non-existent words" )
    {
      const auto matches = service.matches( "invalid" );
      REQUIRE( matches.empty() );
    }
  }
}

SCENARIO( "Auto complete service returns based on initial word list" )
{
  GIVEN( "A pre-initialized auto complete service" )
  {
    const csc280::AutoCompleteService service{
      "program", "programming", "programmer",
      "iterate", "iterator", "iterating",
      "language c++", "language scala", "language haskell", "language erlang"
    };

    THEN( "Auto complete service finds words starting with prog" )
    {
      const auto matches = service.matches( "prog" );
      const csc280::AutoCompleteService::Matches expected{
        "program", "programmer", "programming" };
      REQUIRE( expected == matches );
    }

    AND_THEN( "Auto complete service finds words starting with iter" )
    {
      const auto matches = service.matches( "iter" );
      const csc280::AutoCompleteService::Matches expected{
        "iterate", "iterating", "iterator" };
      REQUIRE( expected == matches );
    }

    AND_THEN( "Auto complete service finds words with spaces" )
    {
      const auto matches = service.matches( "language" );
      const csc280::AutoCompleteService::Matches expected{
        "language c++", "language erlang", "language haskell", "language scala" };
      REQUIRE( expected == matches );
    }

    AND_THEN( "Auto complete service does not find words with different case" )
    {
      const auto matches = service.matches( "Lang" );
      REQUIRE( matches.empty() );
    }

    AND_THEN( "Auto complete service returns empty results for non-existent words" )
    {
      const auto matches = service.matches( "invalid" );
      REQUIRE( matches.empty() );
    }
  }
}
CIACS Test 
A simple test suite for the case insensitive auto complete service.

File: CaseInsensitive.cpp
#include "catch.hpp"
#include "../main/CIAutoCompleteService.h"

SCENARIO( "Case insensitive auto complete service" )
{
  GIVEN( "A case insensitive auto complete service seed with a set of words" )
  {
    const csc280::CIAutoCompleteService service{
      "Program", "programming", "programmer",
      "iterate", "Iterator", "iterating",
      "Language c++", "language scala", "language haskell", "Language erlang"
    };

    THEN( "Auto complete service finds words starting with prog" )
    {
      const auto matches = service.matches( "prog" );
      const csc280::CIAutoCompleteService::Matches expected{
        "Program", "programmer", "programming" };
      REQUIRE( expected == matches );
    }

    AND_THEN( "Auto complete service finds words starting with Prog" )
    {
      const auto matches = service.matches( "Prog" );
      const csc280::CIAutoCompleteService::Matches expected{
        "Program", "programmer", "programming" };
      REQUIRE( expected == matches );
    }

    AND_THEN( "Auto complete service finds words starting with iter" )
    {
      const auto matches = service.matches( "iter" );
      const csc280::CIAutoCompleteService::Matches expected{
        "Iterator", "iterate", "iterating" };
      REQUIRE( expected == matches );
    }

    AND_THEN( "Auto complete service finds words with spaces" )
    {
      const auto matches = service.matches( "lang" );
      const csc280::CIAutoCompleteService::Matches expected{
        "Language c++", "Language erlang", "language haskell", "language scala" };
      REQUIRE( expected == matches );
    }

    AND_THEN( "Auto complete service returns empty results for non-existent words" )
    {
      const auto matches = service.matches( "invalid" );
      REQUIRE( matches.empty() );
    }
  }
}