SqlQuantumLeap

SQLCLR UDA for Longest Common Substring - Source Code

Mar 11th, 2016
323
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.     This code relates to the following DBA.StackExchange answer:
  3.     http://dba.stackexchange.com/questions/131759/is-there-a-sql-server-implementation-of-the-longest-common-substring-problem/131766#131766
  4.  
  5.     A T-SQL installation script (no external DLL) containing only this User-Defined Aggregate (UDA) is located at:
  6.     http://pastebin.com/wnLwT1GM
  7.  
  8.     Date: 2016-03-16
  9.     Version: 1.0.3
  10.  
  11.     Copyright (c) 2016 Sql Quantum Leap. All rights reserved.
  12.     http://www.SqlQuantumLeap.com
  13. */
  14.  
  15. using System;
  16. using System.Collections.Generic;
  17. using System.Data.SqlTypes;
  18. using System.IO;
  19. using System.Xml;
  20. using Microsoft.SqlServer.Server;
  21.  
  22. [Serializable]
  23. [Microsoft.SqlServer.Server.SqlUserDefinedAggregate(Format.UserDefined,
  24.     IsInvariantToDuplicates = true, IsInvariantToNulls = true, IsInvariantToOrder = true,
  25.     IsNullIfEmpty = false, MaxByteSize = -1)]
  26. public struct LongestCommonSubstring : IBinarySerialize
  27. {
  28.     private bool _IsEmpty;
  29.     private string _TempFirstValue;
  30.     private bool _IsFirstComparison;
  31.     private List<string> _Matches;
  32.     private bool _HasMerged;
  33.     private bool? _ReturnAllSubstrings;
  34.  
  35.     public void Init()
  36.     {
  37.         _IsEmpty = false;
  38.         _TempFirstValue = String.Empty;
  39.         _IsFirstComparison = true;
  40.         _Matches = new List<string>();
  41.         _HasMerged = false;
  42.         _ReturnAllSubstrings = null;
  43.  
  44.         return;
  45.     }
  46.  
  47.     public void Accumulate([SqlFacet(MaxSize = 4000)] SqlString SomeString, SqlBoolean ReturnAllSubstrings)
  48.     {
  49.         // grab option on first call only to avoid potential "odd" behavior
  50.         if (!_ReturnAllSubstrings.HasValue)
  51.         {
  52.             if (ReturnAllSubstrings.IsTrue)
  53.             {
  54.                 _ReturnAllSubstrings = true;
  55.             }
  56.             else
  57.             {
  58.                 _ReturnAllSubstrings = false;
  59.             }
  60.         }
  61.  
  62.         if (SomeString.IsNull || _IsEmpty)
  63.         {
  64.             return;
  65.         }
  66.  
  67.         if (SomeString.Value.Trim() == String.Empty)
  68.         {
  69.             _IsEmpty = true;
  70.             _Matches.Clear();
  71.             _TempFirstValue = String.Empty;
  72.  
  73.             return;
  74.         }
  75.  
  76.         if (_IsFirstComparison)
  77.         {
  78.             if (_TempFirstValue == String.Empty)
  79.             {
  80.                 _TempFirstValue = SomeString.Value;
  81.  
  82.                 return;
  83.             }
  84.  
  85.             if (ExtractSubstrings(SomeString.Value, _TempFirstValue) == 0)
  86.             {
  87.                 _IsEmpty = true;
  88.             }
  89.  
  90.             _TempFirstValue = String.Empty;
  91.             _IsFirstComparison = false;
  92.  
  93.             return;
  94.         }
  95.  
  96.         RemoveMissingMatches(SomeString.Value);
  97.  
  98.         if (_Matches.Count == 0)
  99.         {
  100.             _IsEmpty = true;
  101.         }
  102.  
  103.         return;
  104.     }
  105.  
  106.     private void RemoveMissingMatches(string SearchIn)
  107.     {
  108.         for (int _Index = 0; _Index < _Matches.Count; _Index++)
  109.         {
  110.             if (SearchIn.Length >= _Matches[_Index].Length &&
  111.                 SearchIn.IndexOf(_Matches[_Index], StringComparison.InvariantCultureIgnoreCase) >= 0)
  112.             {
  113.                 continue;
  114.             }
  115.  
  116.             _Matches.RemoveAt(_Index);
  117.             _Index--; // prevent skipping due to following entries shifting down 1
  118.         }
  119.  
  120.         return;
  121.     }
  122.  
  123.     private int ExtractSubstrings(string SearchIn, string SearchFor)
  124.     {
  125.         string _TempString;
  126.         int _TempMaxLength = 0;
  127.         bool _AlreadyInCollection;
  128.  
  129.         if (SearchIn.Length < SearchFor.Length)
  130.         {
  131.             // switch
  132.             _TempString = SearchFor;
  133.             SearchFor = SearchIn;
  134.             SearchIn = _TempString;
  135.         }
  136.  
  137.         for (int _SearchForLength = SearchFor.Length; _SearchForLength > 0 ; _SearchForLength--)
  138.         {
  139.             for (int _Index = 0; (_Index + _SearchForLength) <= SearchFor.Length; _Index++)
  140.             {
  141.                 _TempString = SearchFor.Substring(_Index, _SearchForLength);
  142.  
  143.                 if (SearchIn.IndexOf(_TempString, StringComparison.InvariantCultureIgnoreCase) >= 0)
  144.                 {
  145.                     if (_TempMaxLength == 0)
  146.                     {
  147.                         _TempMaxLength = _SearchForLength;
  148.                     }
  149.  
  150.                     _AlreadyInCollection = false;
  151.                     for (int _MatchIndex = 0; _MatchIndex < _Matches.Count; _MatchIndex++)
  152.                     {
  153.                         if(_Matches[_MatchIndex].Equals(_TempString, StringComparison.InvariantCultureIgnoreCase))
  154.                         {
  155.                             _AlreadyInCollection = true;
  156.                             break;
  157.                         }
  158.                     }
  159.  
  160.                     if (!_AlreadyInCollection) // no duplicates
  161.                     {
  162.                         _Matches.Add(_TempString);
  163.                     }
  164.                 }
  165.             }
  166.         }
  167.  
  168.         return _TempMaxLength;
  169.     }
  170.  
  171.     private List<int> GetMaxLengthItems()
  172.     {
  173.         int _MaxMatchLength = 0;
  174.         List<int> _MaxLengthMatches = new List<int>();
  175.  
  176.         for (int _Index = 0; _Index < _Matches.Count; _Index++)
  177.         {
  178.             if (_Matches[_Index].Length > _MaxMatchLength)
  179.             {
  180.                 _MaxLengthMatches.Clear();
  181.                 _MaxLengthMatches.Add(_Index);
  182.                 _MaxMatchLength = _Matches[_Index].Length;
  183.  
  184.                 continue;
  185.             }
  186.  
  187.             if (_Matches[_Index].Length == _MaxMatchLength)
  188.             {
  189.                 _MaxLengthMatches.Add(_Index);
  190.             }
  191.         }
  192.  
  193.         return _MaxLengthMatches;
  194.     }
  195.  
  196.     public void Merge (LongestCommonSubstring Incoming)
  197.     {
  198.         _HasMerged = true;
  199.  
  200.         if (_IsEmpty || Incoming._IsEmpty)
  201.         {
  202.             _IsEmpty = true;
  203.             _Matches.Clear();
  204.             _TempFirstValue = String.Empty;
  205.  
  206.             return;
  207.         }
  208.  
  209.         if (_IsFirstComparison)
  210.         {
  211.             if (_TempFirstValue == String.Empty)
  212.             {
  213.                 if (Incoming._IsFirstComparison)
  214.                 {
  215.                     _TempFirstValue = Incoming._TempFirstValue;
  216.                 }
  217.                 else
  218.                 {
  219.                     _IsFirstComparison = false;
  220.                     _Matches = Incoming._Matches;
  221.                 }
  222.  
  223.                 return;
  224.             }
  225.             else
  226.             {
  227.                 if (Incoming._IsFirstComparison)
  228.                 {
  229.                     if (Incoming._TempFirstValue != String.Empty)
  230.                     {
  231.                         Accumulate(Incoming._TempFirstValue, _ReturnAllSubstrings.Value);
  232.                     }
  233.                 }
  234.                 else
  235.                 {
  236.                     string _Temp = _TempFirstValue;
  237.                     _TempFirstValue = String.Empty;
  238.                     _IsFirstComparison = false;
  239.                     _Matches = Incoming._Matches;
  240.  
  241.                     Accumulate(_Temp, _ReturnAllSubstrings.Value);
  242.                 }
  243.  
  244.                 return;
  245.             } // if (_TempFirstValue == String.Empty) else
  246.         } // if (_IsFirstComparison)
  247.         else
  248.         {
  249.             if (Incoming._IsFirstComparison)
  250.             {
  251.                 if (Incoming._TempFirstValue != String.Empty)
  252.                 {
  253.                     Accumulate(Incoming._TempFirstValue, _ReturnAllSubstrings.Value);
  254.                 }
  255.             }
  256.             else
  257.             {
  258.                 bool _MatchExists;
  259.  
  260.                 for (int _Index = 0; _Index < _Matches.Count; _Index++)
  261.                 {
  262.                     _MatchExists = false;
  263.  
  264.                     for (int _IncomingIndex = 0; _IncomingIndex < Incoming._Matches.Count; _IncomingIndex++)
  265.                     {
  266.                         if (String.Equals(_Matches[_Index], Incoming._Matches[_IncomingIndex],
  267.                             StringComparison.InvariantCultureIgnoreCase))
  268.                         {
  269.                             _MatchExists = true;
  270.                             break;
  271.                         }
  272.                     }
  273.  
  274.                     if (!_MatchExists)
  275.                     {
  276.                         _Matches.RemoveAt(_Index);
  277.                         _Index--; // prevent skipping due to following entries shifting down 1
  278.                     }
  279.                 }
  280.  
  281.                 if (_Matches.Count == 0)
  282.                 {
  283.                     _IsEmpty = true;
  284.                 }
  285.             } // if (Incoming._IsFirstComparison) else
  286.         } // if (_IsFirstComparison) else
  287.  
  288.         return;
  289.     }
  290.  
  291.     public SqlXml Terminate()
  292.     {
  293.         if (_IsEmpty)
  294.         {
  295.             return new SqlXml(XmlReader.Create(new StringReader("<Items Merged=\"" + _HasMerged.ToString() + "\"></Items>")));
  296.         }
  297.  
  298.         if (!_IsEmpty && _IsFirstComparison)
  299.         {
  300.             return SqlXml.Null;
  301.         }
  302.  
  303.         List<int> _MatchIndexesToReturn = GetMaxLengthItems();
  304.  
  305.         XmlDocument _AllItems = new XmlDocument();
  306.         XmlElement _Items = _AllItems.CreateElement("Items");
  307.         _Items.SetAttribute("Merged", _HasMerged.ToString());
  308.  
  309.         if (!_ReturnAllSubstrings.Value)
  310.         {
  311.             for (int _Index = 0; _Index < _MatchIndexesToReturn.Count; _Index++)
  312.             {
  313.                 XmlElement _TempElement = _AllItems.CreateElement("Item");
  314.                 _TempElement.InnerText = _Matches[_MatchIndexesToReturn[_Index]];
  315.                 _Items.AppendChild(_TempElement);
  316.             }
  317.         }
  318.         else
  319.         {
  320.             for (int _Index = 0; _Index < _Matches.Count; _Index++)
  321.             {
  322.                 XmlElement _TempElement = _AllItems.CreateElement("Item");
  323.                 _TempElement.InnerText = _Matches[_Index];
  324.                 _TempElement.SetAttribute("IsLongest", _MatchIndexesToReturn.Contains(_Index).ToString());
  325.                 _Items.AppendChild(_TempElement);
  326.             }
  327.         }
  328.  
  329.         _AllItems.AppendChild(_Items);
  330.  
  331.         return new SqlXml(XmlReader.Create(new StringReader(_AllItems.OuterXml)));
  332.     }
  333.  
  334.     public void Read(BinaryReader Reader)
  335.     {
  336.         _ReturnAllSubstrings = Reader.ReadBoolean();
  337.         _HasMerged = Reader.ReadBoolean();
  338.         _IsEmpty = Reader.ReadBoolean();
  339.  
  340.         // no sense in doing extra work if there can't be any matches
  341.         if (!_IsEmpty)
  342.         {
  343.             _TempFirstValue = Reader.ReadString();
  344.             _IsFirstComparison = Reader.ReadBoolean();
  345.  
  346.             int _TempMatchCount = Reader.ReadInt32();
  347.             _Matches = new List<string>();
  348.             for (int _Index = 0; _Index < _TempMatchCount; _Index++)
  349.             {
  350.                 _Matches.Add(Reader.ReadString());
  351.             }
  352.         }
  353.  
  354.         return;
  355.     }
  356.  
  357.     public void Write(BinaryWriter Writer)
  358.     {
  359.         Writer.Write(_ReturnAllSubstrings.Value); // bool
  360.         Writer.Write(_HasMerged); // bool
  361.         Writer.Write(_IsEmpty); // bool
  362.  
  363.         // no sense in doing extra work if there can't be any matches
  364.         if (!_IsEmpty)
  365.         {
  366.             Writer.Write(_TempFirstValue); // string
  367.             Writer.Write(_IsFirstComparison); // bool
  368.  
  369.             Writer.Write(_Matches.Count); // int
  370.             for (int _Index = 0; _Index < _Matches.Count; _Index++)
  371.             {
  372.                 Writer.Write(_Matches[_Index]);
  373.             }
  374.         }
  375.  
  376.         return;
  377.     }
  378. }
RAW Paste Data