home *** CD-ROM | disk | FTP | other *** search
/ Chip 1999 September / CHIPCD_9_99.iso / software / uaktualnienia / OptionPackPL / iis4_07.cab / trie.h < prev    next >
C/C++ Source or Header  |  1998-04-27  |  23KB  |  939 lines
  1. // A trie is a multiway search tree (aka a radix tree).  See a good
  2. // algorithms text, like Knuth or Sedgewick, for a complete description.
  3. //
  4. // Briefly, given a list of strings such as
  5. //      cab, car, carts, cats, dog, doge, dogs
  6. // you get a trie that looks like this:
  7. //
  8. //                /-[b]
  9. //               /
  10. //        <c>--<a>--[r]--<t>--[s]
  11. //       /       \
  12. //      /         \-<t>--[s]
  13. //     *             
  14. //      \              /-[e]
  15. //       \            /
  16. //        <d>--<o>--[g]
  17. //                    \
  18. //                     \-[s]
  19. //
  20. // where `[r]' denotes the end of a word and `<a>', the middle.
  21. //
  22. // A trie has several useful properties:
  23. //  * fast
  24. //  * easily handles longest substring matches
  25. //  * fairly compact, especially when there are many overlapping strings
  26. //
  27. // The multiway tree is implemented as a binary tree with child and sibling
  28. // pointers.
  29. //
  30. // The CTrie template takes three parameters:
  31. //      class _TOKEN:        up to you
  32. //      bool  fIgnoreCase:   case-sensitivity for searches
  33. //      bool  fDeleteTokens: delete _TOKEN* when Flush() called?
  34. // and it exposes three methods:
  35. //      bool AddToken(ptszToken, _TOKEN*)
  36. //      _TOKEN* Search(ptszSearch, pctchMatched = NULL, nMaxLen = 0)
  37. //      void Flush()
  38. //
  39. // Use them like this:
  40. //      CTrie<CToken, true, true> trie;
  41. //      CToken* ptokHello = new CToken(...);
  42. //
  43. //      VERIFY(trie.AddToken(_T("Hello"), ptokHello));
  44. //
  45. //      CToken* ptok = trie.Search(_T("Goodbye"));
  46. //      if (ptok != NULL) {...}
  47. //
  48. //      if (fIniFileChanged)
  49. //      {
  50. //          trie.Flush();   // will delete all tokens
  51. //          AddTokensFromIniFile(trie);
  52. //      }
  53. //
  54. // Note: If you use DUMP(&trie) or ASSERT_VALID(&trie), your _TOKEN class must
  55. // have Dump() or AssertValid() methods, respectively, in its _DEBUG version.
  56. //
  57. //
  58. // TODO:
  59. //  * template really ought to be parameterized on ANSI/Unicode too
  60. //  * STLify it: add iterators, turn it into a container, etc
  61. //  * remove Win32 dependencies (TCHAR)
  62. //  * add operator= and copy ctor
  63. //
  64. //
  65. // George V. Reilly  <gvr@halcyon.com>  Oct 1995  Initial implementation
  66. // George V. Reilly  <gvr@halcyon.com>  Sep 1996  Add CharPresent for ANSI
  67. // George V. Reilly  <gvr@halcyon.com>  Mar 1997  Templatized; removed MFC
  68.  
  69.  
  70. #ifndef __TRIE_H__
  71. #define __TRIE_H__
  72.  
  73. #include <tchar.h>
  74. #include <limits.h>
  75. #include <malloc.h>
  76.  
  77. #include "debug.h"
  78.  
  79. // Workaround for bool being a "reserved extension" in Visual C++ 4.x
  80. #if _MSC_VER<1100
  81. # ifndef bool
  82. #  define bool  BOOL
  83. # endif
  84. # ifndef true
  85. #  define true  TRUE
  86. # endif
  87. # ifndef false
  88. #  define false FALSE
  89. # endif
  90. #endif
  91.  
  92.  
  93. // forward declaration
  94. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens> class CTrie;
  95.  
  96.  
  97. //+---------------------------------------------------------------------
  98. //  Class:      CTrieNode (tn)
  99. //      one node for each letter
  100.  
  101. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens>
  102. class CTrieNode
  103. {
  104.     friend class CTrie<_TOKEN, fIgnoreCase, fDeleteTokens>;
  105.     typedef CTrieNode<_TOKEN, fIgnoreCase, fDeleteTokens> _Node;
  106.  
  107. public:
  108.     CTrieNode();
  109.  
  110.     CTrieNode(
  111.         _Node*        pParent,
  112.         const _TOKEN* ptok,
  113.         const TCHAR   tch,
  114.         LPCTSTR       ptszToken);
  115.  
  116.     bool
  117.     SetData(
  118.         const _TOKEN* ptok,
  119.         LPCTSTR       ptszToken);
  120.  
  121.     ~CTrieNode();
  122.  
  123. protected:
  124.     const _Node*  m_pParent;
  125.     _Node*        m_pSibling;
  126.     _Node*        m_pChild;
  127.     const _TOKEN* m_ptok;
  128. #ifdef _DEBUG
  129.     LPTSTR        m_ptszToken;
  130. #endif
  131.     const TCHAR   m_tch;
  132.     TCHAR         m_tchMaxChild;    // Maximum m_tch of child nodes (1 level)
  133.  
  134. // Diagnostics
  135. public:
  136. #ifdef _DEBUG
  137.     void
  138.     AssertValid() const;
  139.  
  140.     virtual void
  141.     Dump() const;
  142.  
  143. protected:
  144.     bool
  145.     CheckNodeToken() const;
  146. #endif
  147.  
  148. private:
  149.     // private, unimplemented copy ctor and op= to prevent
  150.     // compiler synthesizing them
  151.     CTrieNode(const CTrieNode&);
  152.     CTrieNode& operator=(const CTrieNode&);
  153. };
  154.  
  155.  
  156.  
  157. //+---------------------------------------------------------------------
  158. //  Class:      CTrie (trie)
  159.  
  160. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens>
  161. class CTrie
  162. {
  163.     typedef CTrieNode<_TOKEN, fIgnoreCase, fDeleteTokens> _Node;
  164.  
  165. public:
  166.     CTrie();
  167.  
  168.     virtual
  169.     ~CTrie();
  170.  
  171.     virtual bool
  172.     AddToken(
  173.         LPCTSTR             ptszToken,
  174.         const _TOKEN* const ptok);
  175.  
  176.     virtual const _TOKEN*
  177.     Search(
  178.         LPCTSTR   ptszSearch,
  179.         int*      pctchMatched = NULL,
  180.         const int nMaxLen = 0) const;
  181.  
  182.     virtual void
  183.     Flush();
  184.  
  185. protected:
  186.     _Node  m_tnRoot;
  187.     TCHAR  m_tchMinChild;
  188.     TCHAR  m_tchMaxChild;
  189.  
  190.     void
  191.     _DeleteTrie(
  192.         _Node* ptn);
  193.  
  194. #ifndef _UNICODE
  195.     // bit array for first letter of all tokens
  196.     BYTE  m_afCharPresent[(CHAR_MAX - CHAR_MIN + 1 + 7) / 8];
  197.  
  198.     bool
  199.     _CharPresent(
  200.         CHAR ch) const;
  201.  
  202.     void
  203.     _SetCharPresent(
  204.         CHAR ch,
  205.         bool f);
  206. #endif // !UNICODE
  207.  
  208.  
  209. // Diagnostics
  210. public:
  211. #ifdef _DEBUG
  212.     virtual void
  213.     AssertValid() const;
  214.  
  215.     virtual void
  216.     Dump() const;
  217.  
  218. protected:
  219.     int   m_ctchMaxTokenLen;    // length of longest token string
  220.  
  221.     void
  222.     _AssertWalk(
  223.         _Node* ptn,
  224.         LPTSTR ptszName,
  225.         int    iLevel) const;
  226.  
  227.     void
  228.     _DumpWalk(
  229.         _Node* ptn,
  230.         LPTSTR ptszName,
  231.         int    iLevel,
  232.         int&   rcNodes,
  233.         int&   rcTokens) const;
  234. #endif
  235.  
  236. private:
  237.     // private, unimplemented copy ctor and op= to prevent
  238.     // compiler synthesizing them
  239.     CTrie(const CTrie&);
  240.     CTrie& operator=(const CTrie&);
  241. };
  242.  
  243.  
  244.  
  245. #ifdef _UNICODE
  246. # define TCHAR_MIN L'\0'
  247. #else // !UNICODE
  248. # define TCHAR_MIN CHAR_MIN
  249. #endif // !UNICODE
  250.  
  251.  
  252.  
  253. //-----------------------------------------------------------------------------
  254. // CTrieNode implementation
  255.  
  256. // CTrieNode::CTrieNode
  257. //      default ctor (needed for CTrie::m_tnRoot)
  258.  
  259. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens>
  260. CTrieNode<_TOKEN, fIgnoreCase, fDeleteTokens>::CTrieNode()
  261.     : m_pParent(NULL),
  262.       m_pSibling(NULL),
  263.       m_pChild(NULL),
  264.       m_ptok(NULL),
  265. #ifdef _DEBUG
  266.       m_ptszToken(NULL),
  267. #endif
  268.       m_tch(TCHAR_MIN),
  269.       m_tchMaxChild(TCHAR_MIN)
  270. {
  271. }
  272.  
  273.  
  274.  
  275. // CTrieNode::CTrieNode
  276. //      ctor
  277.  
  278. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens>
  279. CTrieNode<_TOKEN, fIgnoreCase, fDeleteTokens>::CTrieNode(
  280.     _Node*        pParent,
  281.     const _TOKEN* ptok,
  282.     const TCHAR   tch,
  283.     LPCTSTR       ptszToken)
  284.     : m_pParent(pParent),
  285.       m_pSibling(NULL),
  286.       m_pChild(NULL),
  287.       m_ptok(ptok),
  288. #ifdef _DEBUG
  289.       m_ptszToken(NULL),
  290. #endif
  291.       m_tch(tch),
  292.       m_tchMaxChild(TCHAR_MIN)
  293. {
  294.     ASSERT(m_pParent != NULL);
  295.     ASSERT(m_tch > TCHAR_MIN);
  296.     
  297.     _Node* ptnPrev = NULL;
  298.     _Node* ptn = m_pParent->m_pChild;
  299.         
  300.     // find where in the list of pParent's children to insert `this'
  301.     while (ptn != NULL  &&  ptn->m_tch < m_tch)
  302.     {
  303.         ptnPrev = ptn;
  304.         ptn = ptn->m_pSibling;
  305.     }
  306.     
  307.     ASSERT(ptn == NULL  ||  ptn->m_tch != m_tch);
  308.     
  309.     if (ptnPrev == NULL)
  310.     {
  311.         ASSERT(pParent->m_pChild == ptn);
  312.         pParent->m_pChild = this;
  313.     }
  314.     else
  315.         ptnPrev->m_pSibling = this;
  316.  
  317.     this->m_pSibling = ptn;
  318.  
  319.     if (pParent->m_tchMaxChild < m_tch)
  320.         pParent->m_tchMaxChild = m_tch;
  321.  
  322. #ifdef _DEBUG
  323.     if (ptszToken != NULL)
  324.     {
  325.         ASSERT(m_ptok != NULL);
  326.         m_ptszToken = new TCHAR [_tcslen(ptszToken) + 1];
  327.         _tcscpy(m_ptszToken, ptszToken);
  328.     }
  329. #endif
  330. }
  331.  
  332.  
  333.     
  334. // CTrieNode::SetData
  335. //      sets the data if it's NULL.  Needed if you do
  336. //      AddToken("foobar", &tokFoobar) and then AddToken("foo", &tokFoo)
  337. //      to set the data for tokFoo.
  338.  
  339. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens>
  340. bool
  341. CTrieNode<_TOKEN, fIgnoreCase, fDeleteTokens>::SetData(
  342.     const _TOKEN* ptok,
  343.     LPCTSTR       ptszToken)
  344. {
  345.     // Don't set data if ptok is NULL
  346.     if (ptok == NULL)
  347.         return false;
  348.     
  349.     // overwrite m_ptok only if it is NULL
  350.     if (m_ptok == NULL)
  351.     {
  352.         m_ptok = ptok;
  353. #ifdef _DEBUG
  354.         ASSERT(m_ptszToken == NULL);
  355.         ASSERT(ptszToken != NULL);
  356.         m_ptszToken = new TCHAR [_tcslen(ptszToken) + 1];
  357.         _tcscpy(m_ptszToken, ptszToken);
  358. #endif
  359.     }
  360.  
  361.     return true;
  362. }
  363.  
  364.  
  365.  
  366. // CTrieNode::~CTrieNode
  367. //      dtor
  368.  
  369. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens>
  370. CTrieNode<_TOKEN, fIgnoreCase, fDeleteTokens>::~CTrieNode()
  371. {
  372. #ifdef _DEBUG
  373.     delete [] m_ptszToken;
  374. #endif
  375.  
  376.     // Is this an auto-delete trie, i.e., do we take care of deleting
  377.     // the _TOKENs?
  378.     if (fDeleteTokens)
  379.     {
  380.         // cast away constness so that delete will work
  381.         delete const_cast<_TOKEN*> (m_ptok);
  382.     }
  383.  
  384.     ASSERT(m_pChild == NULL);
  385. }
  386.  
  387.  
  388.     
  389. //-----------------------------------------------------------------------------
  390. // CTrieNode diagnostics
  391.  
  392. #ifdef _DEBUG
  393.  
  394. // CTrieNode::CheckNodeToken
  395. //      Do the real work of validating a CTrieNode object
  396.  
  397. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens>
  398. bool
  399. CTrieNode<_TOKEN, fIgnoreCase, fDeleteTokens>::CheckNodeToken() const
  400. {
  401.     // If there's no m_ptok, it's automatically valid
  402.     if (m_ptok == NULL)
  403.         return true;
  404.  
  405.     ASSERT(m_ptszToken != NULL);
  406.     const int cLen = _tcslen(m_ptszToken);
  407.     const _Node* ptn = this;
  408.  
  409.     ASSERT((m_pChild == NULL  &&  m_tchMaxChild == TCHAR_MIN)
  410.            ||  (m_pChild != NULL  &&  m_tchMaxChild > TCHAR_MIN));
  411.  
  412.     // Walk back up towards CTrie::m_tnRoot
  413.     for (int i = cLen;  --i >= 0;  )
  414.     {
  415.         ASSERT(ptn != NULL);
  416.         ASSERT(ptn->m_tch != TCHAR_MIN);
  417.  
  418.         const TCHAR tch = (fIgnoreCase
  419.                            ? (TCHAR) _totlower(this->m_ptszToken[i])
  420.                            : this->m_ptszToken[i]);
  421.  
  422.         if (ptn->m_tch != tch)
  423.             ASSERT(false);
  424.  
  425.         ASSERT(ptn->m_pParent != NULL  &&  ptn->m_pParent->m_pChild != NULL);
  426.  
  427.         const _Node* ptn2;
  428.  
  429.         // check to see if ptn really is a child of its parent
  430.         for (ptn2 = ptn->m_pParent->m_pChild;
  431.              ptn2 != ptn  &&  ptn2 != NULL;
  432.              ptn2 = ptn2->m_pSibling)
  433.         {}
  434.         ASSERT(ptn2 == ptn);
  435.  
  436.         // check that ptn->m_pParent->m_tchMaxChild is correct
  437.         for (ptn2 = ptn->m_pParent->m_pChild;
  438.              ptn2->m_pSibling != NULL;
  439.              ptn2 = ptn2->m_pSibling)
  440.         {
  441.             ASSERT(ptn2->m_tch > TCHAR_MIN
  442.                    &&  ptn2->m_tch < ptn2->m_pSibling->m_tch);
  443.         }
  444.         ASSERT(ptn->m_pParent->m_tchMaxChild == ptn2->m_tch);
  445.  
  446.         ptn = ptn->m_pParent;
  447.         ASSERT(ptn->m_ptok != this->m_ptok);
  448.     }
  449.  
  450.     // check to see if ptn == CTrie::m_tnRoot
  451.     ASSERT(ptn->m_pParent == NULL  &&  ptn->m_pSibling == NULL
  452.            &&  ptn->m_tch == TCHAR_MIN  &&  ptn->m_ptok == NULL);
  453.  
  454.     return true;
  455. }
  456.  
  457.  
  458.  
  459. // CTrieNode::AssertValid
  460. //      Validate a CTrieNode object
  461.  
  462. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens>
  463. void
  464. CTrieNode<_TOKEN, fIgnoreCase, fDeleteTokens>::AssertValid() const
  465. {
  466.     ASSERT(CheckNodeToken());
  467. }
  468.  
  469.  
  470.  
  471. // CTrieNode::Dump
  472. //      Dump a CTrieNode object
  473.  
  474. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens>
  475. void
  476. CTrieNode<_TOKEN, fIgnoreCase, fDeleteTokens>::Dump() const
  477. {
  478.     // TODO: flesh out
  479. }
  480.  
  481. #endif // _DEBUG
  482.  
  483.  
  484.  
  485. //-----------------------------------------------------------------------------
  486. // CTrie implementation
  487.  
  488. // CTrie::CTrie
  489. //      ctor
  490.  
  491. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens>
  492. CTrie<_TOKEN, fIgnoreCase, fDeleteTokens>::CTrie()
  493. {
  494.     Flush();
  495. }
  496.  
  497.  
  498.  
  499. // CTrie::~CTrie
  500. //      dtor
  501.  
  502. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens>
  503. CTrie<_TOKEN, fIgnoreCase, fDeleteTokens>::~CTrie()
  504. {
  505.     Flush();
  506. }
  507.  
  508.  
  509.  
  510. #ifndef _UNICODE
  511.  
  512. // CTrie::_CharPresent
  513.  
  514. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens>
  515. inline bool
  516. CTrie<_TOKEN, fIgnoreCase, fDeleteTokens>::_CharPresent(
  517.     CHAR ch) const
  518. {
  519.     ASSERT(CHAR_MIN <= ch  &&  ch <= CHAR_MAX);
  520.     const UINT i = ch - CHAR_MIN;   // CHAR_MIN is -128 for `signed char'
  521.  
  522.     return m_afCharPresent[i >> 3] & (1 << (i & 7))  ?  true  :  false;
  523. }
  524.  
  525.  
  526.  
  527. // CTrie::_SetCharPresent
  528.  
  529. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens>
  530. inline void
  531. CTrie<_TOKEN, fIgnoreCase, fDeleteTokens>::_SetCharPresent(
  532.     CHAR ch,
  533.     bool f)
  534. {
  535.     ASSERT(CHAR_MIN <= ch  &&  ch <= CHAR_MAX);
  536.     const UINT i = ch - CHAR_MIN;
  537.  
  538.     if (f)
  539.         m_afCharPresent[i >> 3] |=  (1 << (i & 7));
  540.     else
  541.         m_afCharPresent[i >> 3] &= ~(1 << (i & 7));
  542. }
  543.  
  544. #endif // !UNICODE
  545.  
  546.  
  547.  
  548. // CTrie::AddToken
  549. //      Add search string `ptszToken' to trie, which will return `ptok'
  550. //      if searched for in Search().
  551.  
  552. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens>
  553. bool
  554. CTrie<_TOKEN, fIgnoreCase, fDeleteTokens>::AddToken(
  555.     LPCTSTR             ptszToken,
  556.     const _TOKEN* const ptok)
  557. {
  558.     if (ptok == NULL  ||  ptszToken == NULL  ||  *ptszToken == _T('\0'))
  559.     {
  560.         ASSERT(false);
  561.         return false;
  562.     }
  563.  
  564.     const int cLen = _tcslen(ptszToken);
  565.     _Node* ptnParent = &m_tnRoot;
  566.     
  567.     for (int i = 0;  i < cLen;  ++i)
  568.     {
  569.         ASSERT(ptnParent != NULL);
  570.         
  571.         _Node* ptn = ptnParent->m_pChild;
  572.         const TCHAR tch = (fIgnoreCase
  573.                            ? (TCHAR) _totlower(ptszToken[i])
  574.                            : ptszToken[i]);
  575.         const _TOKEN* ptok2 = (i == cLen - 1)  ?  ptok       :  NULL;
  576.         LPCTSTR ptsz2 =       (i == cLen - 1)  ?  ptszToken  :  NULL;
  577.  
  578.         while (ptn != NULL  &&  ptn->m_tch < tch)
  579.             ptn = ptn->m_pSibling;
  580.             
  581.         if (ptn == NULL  ||  ptn->m_tch > tch)
  582.         {
  583.             ptnParent = new _Node(ptnParent, ptok2, tch, ptsz2);
  584.         }
  585.         else
  586.         {
  587.             ASSERT(ptn->m_tch == tch);
  588.             
  589.             ptn->SetData(ptok2, ptsz2);
  590.             ptnParent = ptn;
  591.         }
  592.  
  593.         ASSERT(ptnParent->CheckNodeToken());
  594.     }
  595.  
  596.     m_tchMinChild = m_tnRoot.m_pChild->m_tch;
  597.     m_tchMaxChild = m_tnRoot.m_tchMaxChild;
  598. #ifdef _DEBUG
  599.     m_ctchMaxTokenLen = max(m_ctchMaxTokenLen, cLen);
  600. #endif
  601.  
  602.     ASSERT(TCHAR_MIN < m_tchMinChild  &&  m_tchMinChild <= m_tchMaxChild);
  603.  
  604. #ifndef _UNICODE
  605.     // Keep a map of the initial letter of each token, to speed up searches
  606.     if (fIgnoreCase)
  607.     {
  608.         _SetCharPresent(tolower(ptszToken[0]), true);
  609.         _SetCharPresent(toupper(ptszToken[0]), true);
  610.     }
  611.     else
  612.         _SetCharPresent(ptszToken[0], true);
  613. #endif // !UNICODE
  614.  
  615. #ifdef _DEBUG
  616.     int nTemp;
  617.     const _TOKEN* ptok2 = Search(ptszToken, &nTemp);
  618.  
  619.     ASSERT(ptok2 == ptok  &&  nTemp == cLen);
  620. #endif // _DEBUG
  621.  
  622.     return true;
  623. }
  624.  
  625.  
  626.  
  627. // CTrie::Search
  628. //      Search trie for `ptszSearch', returning count of characters
  629. //      matched in `pctchMatched' (if non-NULL), matching at most `nMaxLen'
  630. //      characters, if nMaxLen != 0, or _tcslen(ptszSearch) otherwise.
  631.  
  632. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens>
  633. const _TOKEN*
  634. CTrie<_TOKEN, fIgnoreCase, fDeleteTokens>::Search(
  635.     LPCTSTR   ptszSearch,
  636.     int*      pctchMatched /* = NULL */,
  637.     const int nMaxLen /* = 0 */) const
  638. {
  639.     // Set count of matched characters
  640.     if (pctchMatched != NULL)
  641.         *pctchMatched = 0;
  642.  
  643. #ifndef _UNICODE
  644.     if (! _CharPresent(ptszSearch[0]))
  645.         return NULL;
  646.  
  647.     TCHAR tch;
  648. #else    // UNICODE
  649.     TCHAR tch = fIgnoreCase ? (TCHAR) _totlower(ptszSearch[0]) : ptszSearch[0];
  650.  
  651.     if (tch < m_tchMinChild  ||  m_tchMaxChild < tch)
  652.         return NULL;
  653. #endif // UNICODE
  654.  
  655.     // For some uses (e.g., ptszSearch is not '\0'-terminated), nMaxLen is
  656.     // specified.  If it's not specified, use the length of the string.
  657.     const int cLen = (nMaxLen != 0)  ?  nMaxLen  :  _tcslen(ptszSearch);
  658.     ASSERT(0 < cLen);
  659.  
  660.     bool fOvershot = true;
  661.     const _Node* ptnParent = &m_tnRoot;
  662.     const _Node* ptn = NULL;
  663.     int i;
  664.  
  665.     // Find the longest approximate match.  For example, if we have "foo"
  666.     // and "foobar" in the trie and we're asked to match "fool", we'll work
  667.     // our way down to "foob", then backtrack up to "foo".
  668.  
  669.     for (i = 0;  i < cLen;  ++i)
  670.     {
  671.         ASSERT(ptnParent != NULL);
  672.  
  673.         ptn = ptnParent->m_pChild;
  674.         ASSERT(ptn != NULL  &&  ptn->m_pParent == ptnParent);
  675.  
  676.         tch = fIgnoreCase ? (TCHAR) _totlower(ptszSearch[i]) : ptszSearch[i];
  677.         ASSERT(tch >= TCHAR_MIN);
  678.  
  679.         if (ptnParent->m_tchMaxChild < tch)
  680.         {
  681.             ASSERT(i > 0);
  682.             break;
  683.         }
  684.         
  685.         while (ptn != NULL  &&  ptn->m_tch < tch)
  686.             ptn = ptn->m_pSibling;
  687.  
  688.         // failed to match?
  689.         if (ptn == NULL  ||  ptn->m_tch > tch)
  690.         {
  691.             ASSERT(ptn == NULL  ||  ptn->m_tch <= ptnParent->m_tchMaxChild);
  692.             
  693.             if (i == 0)
  694.                 return NULL;
  695.             break;
  696.         }
  697.         else
  698.         {
  699.             ASSERT(ptn->m_tch == tch);
  700.             ASSERT(ptn->m_pParent->m_tchMaxChild >= tch);
  701.  
  702.             if (ptn->m_pChild == NULL)
  703.             {
  704.                 ASSERT(ptn->m_ptok != NULL);
  705.                 fOvershot = false;
  706.                 break;
  707.             }
  708.  
  709.             ptnParent = ptn;
  710.         }
  711.     }
  712.  
  713.     if (fOvershot)
  714.     {
  715.         --i;  ptn = ptnParent;  // back up one character
  716.     }
  717.     else
  718.         ASSERT(ptn->m_pChild == NULL);
  719.  
  720.     ASSERT(0 <= i  &&  i < cLen);
  721.     ASSERT(ptn != NULL  &&  ptn != &m_tnRoot);
  722.     
  723.     // we've found an approximate match; backtrack until we find an exact match
  724.     do
  725.     {
  726.         ASSERT(ptn != NULL);
  727.         ASSERT(ptn->m_tch == (fIgnoreCase
  728.                               ? (TCHAR) _totlower(ptszSearch[i])
  729.                               : ptszSearch[i]));
  730.         ASSERT(ptn->CheckNodeToken());
  731.         
  732.         const _TOKEN* const ptok = ptn->m_ptok;
  733.  
  734.         if (ptok != NULL)
  735.         {
  736.             ASSERT(i == (int) _tcslen(ptn->m_ptszToken) - 1);
  737.  
  738.             if (pctchMatched != NULL)
  739.                 *pctchMatched = i+1;
  740.  
  741.             return ptok;
  742.         }
  743.  
  744.         ptn = ptn->m_pParent;
  745.     } while (--i >= 0);
  746.  
  747.     return NULL;
  748. }
  749.  
  750.  
  751.  
  752. // CTrie::Flush
  753. //      flush all nodes leaving an empty trie
  754.  
  755. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens>
  756. void
  757. CTrie<_TOKEN, fIgnoreCase, fDeleteTokens>::Flush()
  758. {
  759.     if (m_tnRoot.m_pChild != NULL)
  760.         _DeleteTrie(m_tnRoot.m_pChild);
  761.  
  762.     m_tnRoot.m_pChild = NULL;  // or ~CTrieNode will ASSERT
  763.     m_tnRoot.m_tchMaxChild = TCHAR_MIN;
  764.  
  765.     m_tchMinChild = m_tchMaxChild = TCHAR_MIN;
  766. #ifdef _DEBUG
  767.     m_ctchMaxTokenLen = 0;
  768. #endif
  769. #ifndef _UNICODE
  770.     memset(m_afCharPresent, 0, sizeof(m_afCharPresent));
  771. #endif
  772. }
  773.  
  774.  
  775.  
  776. // CTrie::_DeleteTrie
  777. //      recursively delete a subtrie
  778.  
  779. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens>
  780. void
  781. CTrie<_TOKEN, fIgnoreCase, fDeleteTokens>::_DeleteTrie(
  782.     _Node* ptn)
  783. {
  784.     if (ptn == NULL)
  785.     {
  786.         ASSERT(false);
  787.         return;
  788.     }
  789.     
  790.     do
  791.     {
  792.         if (ptn->m_pChild != NULL)
  793.         {
  794.             _DeleteTrie(ptn->m_pChild);
  795.             ptn->m_pChild = NULL;   // or ~CTrieNode will ASSERT
  796.         }
  797.  
  798.         _Node* ptnSibling = ptn->m_pSibling;
  799.         delete ptn;
  800.         ptn = ptnSibling;   // tail recursion
  801.     } while (ptn != NULL);
  802. }
  803.  
  804.  
  805.  
  806. //-----------------------------------------------------------------------------
  807. // CTrie diagnostics
  808.  
  809. #ifdef _DEBUG
  810.  
  811. // CTrie::AssertValid
  812.  
  813. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens>
  814. void
  815. CTrie<_TOKEN, fIgnoreCase, fDeleteTokens>::AssertValid() const
  816. {
  817.     TCHAR* ptszName = static_cast<TCHAR*>
  818.                         (_alloca(sizeof(TCHAR) * (m_ctchMaxTokenLen+1)));
  819.     *ptszName = _T('\0');
  820.  
  821.     ASSERT_VALID(&m_tnRoot);
  822.     ASSERT(m_tnRoot.m_tchMaxChild == m_tchMaxChild);
  823.  
  824.     if (m_tnRoot.m_pChild != NULL)
  825.     {
  826.         ASSERT(m_tchMinChild == m_tnRoot.m_pChild->m_tch);
  827.         ASSERT(m_ctchMaxTokenLen > 0);
  828.         _AssertWalk(m_tnRoot.m_pChild, ptszName, 0);
  829.     }
  830.     else
  831.     {
  832.         ASSERT(m_tchMinChild == TCHAR_MIN && m_tchMinChild == m_tchMaxChild);
  833.         ASSERT(m_ctchMaxTokenLen == 0);
  834.     }
  835. }
  836.  
  837.  
  838.  
  839. // CTrie::_AssertWalk
  840. //      recursively validate a subtrie
  841.  
  842. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens>
  843. void
  844. CTrie<_TOKEN, fIgnoreCase, fDeleteTokens>::_AssertWalk(
  845.     _Node* ptn,
  846.     LPTSTR ptszName,
  847.     int    iLevel) const
  848. {
  849.     ASSERT(iLevel < m_ctchMaxTokenLen);
  850.     
  851.     do
  852.     {
  853.         ASSERT_VALID(ptn);
  854.         
  855.         ptszName[iLevel] = ptn->m_tch;
  856.         ptszName[iLevel+1] = _T('\0');
  857.  
  858.         if (ptn->m_ptok != NULL)
  859.         {
  860.             ASSERT(ptn->m_ptszToken != NULL);
  861.             if (fIgnoreCase)
  862.                 ASSERT(_tcsicmp(ptszName, ptn->m_ptszToken) == 0);
  863.             else
  864.                 ASSERT(_tcscmp(ptszName, ptn->m_ptszToken) == 0);
  865.             ASSERT_VALID(ptn->m_ptok);
  866.         }
  867.         
  868.         if (ptn->m_pChild != NULL)
  869.             _AssertWalk(ptn->m_pChild, ptszName, iLevel+1);
  870.  
  871.         ptn = ptn->m_pSibling;   // tail recursion
  872.     } while (ptn != NULL);
  873. }
  874.  
  875.  
  876.  
  877. // CTrie::Dump
  878.  
  879. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens>
  880. void
  881. CTrie<_TOKEN, fIgnoreCase, fDeleteTokens>::Dump() const
  882. {
  883.     int cNodes = 0, cTokens = 0;
  884.     TCHAR* ptszName = static_cast<TCHAR*>
  885.                         (_alloca(sizeof(TCHAR) * (m_ctchMaxTokenLen+1)));
  886.     *ptszName = _T('\0');
  887.  
  888.     TRACE0("Dumping trie...\n");
  889.  
  890.     if (m_tnRoot.m_pChild != NULL)
  891.         _DumpWalk(m_tnRoot.m_pChild, ptszName, 0, cNodes, cTokens);
  892.  
  893.     TRACE2("%d nodes, %d tokens\n", cNodes, cTokens);
  894. }
  895.  
  896.  
  897.  
  898. // CTrie::_DumpWalk
  899. //      recursively dump a subtrie
  900.  
  901. template <class _TOKEN, bool fIgnoreCase, bool fDeleteTokens>
  902. void
  903. CTrie<_TOKEN, fIgnoreCase, fDeleteTokens>::_DumpWalk(
  904.     _Node* ptn,
  905.     LPTSTR ptszName,
  906.     int    iLevel,
  907.     int&   rcNodes,
  908.     int&   rcTokens) const
  909. {
  910.     ASSERT(iLevel < m_ctchMaxTokenLen);
  911.  
  912.     do
  913.     {
  914.         ASSERT_VALID(ptn);
  915.         
  916.         ++rcNodes;
  917.         ptszName[iLevel] = ptn->m_tch;
  918.         ptszName[iLevel+1] = _T('\0');
  919.  
  920.         if (ptn->m_ptok != NULL)
  921.         {
  922.             ++rcTokens;
  923.             ASSERT(ptn->m_ptszToken != NULL);
  924.             TRACE2("\t%s (%s): ", ptszName, ptn->m_ptszToken);
  925.             DUMP(ptn->m_ptok);
  926.             TRACE0("\n");
  927.         }
  928.         
  929.         if (ptn->m_pChild != NULL)
  930.             _DumpWalk(ptn->m_pChild, ptszName, iLevel+1, rcNodes, rcTokens);
  931.  
  932.         ptn = ptn->m_pSibling;   // tail recursion
  933.     } while (ptn != NULL);
  934. }
  935.  
  936. #endif // _DEBUG
  937.  
  938. #endif // __TRIE_H__
  939.