fork(3) download 
  1. // -*- C++ -*-
  2.  
  3. // Copyright (C) 2005, 2006 Free Software Foundation, Inc.
  4. //
  5. // This file is part of the GNU ISO C++ Library.  This library is free
  6. // software; you can redistribute it and/or modify it under the terms
  7. // of the GNU General Public License as published by the Free Software
  8. // Foundation; either version 2, or (at your option) any later
  9. // version.
  10.  
  11. // This library is distributed in the hope that it will be useful, but
  12. // WITHOUT ANY WARRANTY; without even the implied warranty of
  13. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14. // General Public License for more details.
  15.  
  16. // You should have received a copy of the GNU General Public License
  17. // along with this library; see the file COPYING.  If not, write to
  18. // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19. // MA 02111-1307, USA.
  20.  
  21. // As a special exception, you may use this file as part of a free
  22. // software library without restriction.  Specifically, if other files
  23. // instantiate templates or use macros or inline functions from this
  24. // file, or you compile this file and link it with other files to
  25. // produce an executable, this file does not by itself cause the
  26. // resulting executable to be covered by the GNU General Public
  27. // License.  This exception does not however invalidate any other
  28. // reasons why the executable file might be covered by the GNU General
  29. // Public License.
  30.  
  31. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32.  
  33. // Permission to use, copy, modify, sell, and distribute this software
  34. // is hereby granted without fee, provided that the above copyright
  35. // notice appears in all copies, and that both that copyright notice
  36. // and this permission notice appear in supporting documentation. None
  37. // of the above authors, nor IBM Haifa Research Laboratories, make any
  38. // representation about the suitability of this software for any
  39. // purpose. It is provided "as is" without express or implied
  40. // warranty.
  41.  
  42. /**
  43.  * @file trie_prefix_search_example.cpp
  44.  * An example showing how to use a trie for searching
  45.  *    for words with a given prefix.
  46.  */
  47.  
  48. /**
  49.  * This example shows how to use a PATRICIA trie for searching
  50.  * for words with a given prefix.
  51.  */
  52.  
  53. #include <cassert>
  54. #include <iostream>
  55. #include <ext/pb_ds/assoc_container.hpp>
  56. #include <ext/pb_ds/trie_policy.hpp>
  57. #include <ext/pb_ds/tag_and_trait.hpp>
  58.  
  59. using namespace std;
  60. using namespace __gnu_pbds;
  61.  
  62. // A PATRICIA trie with a prefix-search node-updator type. Note that
  63. // since the node updator is trie_prefix_search_node_update, then the
  64. // container includes its method prefix_range.
  65. typedef null_type		mapped_type;
  66. typedef trie_string_access_traits<> 	cmp_fn;
  67. typedef pat_trie_tag 			tag_type;
  68.  
  69. typedef trie<string, mapped_type, cmp_fn, tag_type,
  70. 	     trie_prefix_search_node_update> trie_type;
  71.  
  72. // The following helper function takes a trie object and r_key, a
  73. // const reference to a string, and prints all entries whose key
  74. // includes r_key as a prefix.
  75. void
  76. print_prefix_match(const trie_type& t, const string& key)
  77. {
  78.   typedef trie_type::const_iterator 		const_iterator;
  79.   typedef pair<const_iterator, const_iterator> 	pair_type;
  80.  
  81.   cout << "All keys whose prefix matches \"" << key << "\":" << endl;
  82.  
  83.   const pair_type match_range = t.prefix_range(key);
  84.   for (const_iterator it = match_range.first; it != match_range.second; ++it)
  85.     cout << *it << ' ';
  86.   cout << endl;
  87. }
  88.  
  89. int main()
  90. {
  91.   trie_type t;
  92.  
  93.   // Insert some entries.
  94.   assert(t.insert("I").second == true);
  95.   assert(t.insert("wish").second == true);
  96.   assert(t.insert("that").second == true);
  97.   assert(t.insert("I").second == false);
  98.   assert(t.insert("could").second == true);
  99.   assert(t.insert("ever").second == true);
  100.   assert(t.insert("see").second == true);
  101.   assert(t.insert("a").second == true);
  102.   assert(t.insert("poem").second == true);
  103.   assert(t.insert("lovely").second == true);
  104.   assert(t.insert("as").second == true);
  105.   assert(t.insert("a").second == false);
  106.   assert(t.insert("trie").second == true);
  107.  
  108.   // Now search for prefixes.
  109.   print_prefix_match(t, "");
  110.   print_prefix_match(t, "a");
  111.   print_prefix_match(t, "as");
  112.   print_prefix_match(t, "ad");
  113.   print_prefix_match(t, "t");
  114.   print_prefix_match(t, "tr");
  115.   print_prefix_match(t, "trie");
  116.   print_prefix_match(t, "zzz");
  117.  
  118.   return 0;
  119. }
  120.  
  121.  
Success #stdin #stdout 0s 3476KB
comments (?)
stdin 
Standard input is empty
stdout 
All keys whose prefix matches "":
I a as could ever lovely poem see that trie wish 
All keys whose prefix matches "a":
a as 
All keys whose prefix matches "as":
as 
All keys whose prefix matches "ad":

All keys whose prefix matches "t":
that trie 
All keys whose prefix matches "tr":
trie 
All keys whose prefix matches "trie":
trie 
All keys whose prefix matches "zzz":
https://ideone.com/BpZlYO
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!