xml,scala,time-complexity , Is complexity of scala.xml.RuleTransformer really exponential?


Is complexity of scala.xml.RuleTransformer really exponential?

Question:

Tag: xml,scala,time-complexity

This is a follow-up to one of my previous posts.

I tried to understand why the RuleTransformer performance is so poor. Now I believe that it is so slow because its complexity is O(2n), where n is the height of the input XML tree.

Suppose I need to rename all labels of all elements to label "b":

import scala.xml._, scala.xml.transform._

val rule: RewriteRule = new RewriteRule() {
  override def transform(node: Node): Seq[Node] = node match {
    case e: Elem => e.copy(label = "b")
    case other => other
  }
}

def trans(node: Node): Node = new RuleTransformer(rule).apply(node)

Let's count how many times the transform visits each node in input <a3><a2><a1/></a2></a3>.
In order to count the visits we add a buffer visited, init it in the beginning, store visited nodes, and print it in the end.

import scala.collection.mutable.ListBuffer

// buffer to store visited nodes
var visited: ListBuffer[Node] = ListBuffer[Node]()

val rule: RewriteRule = new RewriteRule() {
  override def transform(n: Node): Seq[Node] = {
    visited append (n) // count this visit
    n match {
      case e: Elem => e.copy(label = "b")
      case other => other
    }
  }
}

def trans(node: Node): Node = {
  visited = ListBuffer[Node]() // init the buffer
  val r = new RuleTransformer(rule).apply(node)
  // print visited nodes and numbers of visits 
  println(visited.groupBy(identity).mapValues(_.size).toSeq.sortBy(_._2))
  r
}

Now let's run it in REPL and see the visited

scala> val a3 = <a3><a2><a1/></a2></a3>
a3: scala.xml.Elem = <a3><a2><a1/></a2></a3>

scala> trans(a3)
ArrayBuffer((<a3><b><b/></b></a3>,2), (<a2><b/></a2>,4), (<a1/>,8))
res1: scala.xml.Node = <b><b><b/></b></b>

So a1 is visited eight times.

If we transform <a4><a3><a2><a1/></a2></a3></a4> then a1 will be visited 16 times, for <a5><a4><a3><a2><a1/></a2></a3></a4></a5> -- 32, etc. So the complexity looks exponential.

Does it make sense ? How would you prove it by analysis of the code ?


Answer:

This will be not a very rigours analysis, but the problem seems to be with the BasicTransformer's transform(Seq[Node]) method[1].

The child transform method will be called twice for a node which is changed. Specifically in your example all the nodes will be called twice for this reason. And you are right in that each node at height h will be called 2^(h-1) times. Also note that at most one child of a node will be called twice because use of span and code, in the specific example all the child of the nodes will be called twice.

Just to verify this wrote these code samples for modified RulesTransformer. ( I could have overriden RulesTransformer too. But anyway)

// This is same as library RuleTransformer added with print statement
class CopiedRuleTransformer(rules: RewriteRule*) extends BasicTransformer {
    override def transform(n: Node): Seq[Node] = {
        println(n)
        rules.foldLeft(super.transform(n)) { (res, rule) => rule transform res }
    }
}

My modified RuleTransformer

class MyRuleTransformer(rules: RewriteRule*) extends BasicTransformer {
    override def transform(n: Node): Seq[Node] = {
        println(n)
        rules.foldLeft(super.transform(n)) { (res, rule) => rule transform res }
    }  
    override def transform(ns:Seq[Node]): Seq[Node] = {
        ns.flatMap(n => transform(n))
    } 
}

These codes are only for demonstrating purpose. You can call these as

new CopiedRuleTransformer(rule).apply(node)

or

new MyRuleTransformer(rule).apply(node)

[1] line : 34 https://github.com/scala/scala-xml/blob/master/src/main/scala/scala/xml/transform/BasicTransformer.scala


Related:


Convert RDD[Map[String,Double]] to RDD[(String,Double)]


scala,apache-spark,rdd
I did some calculation and returned my values in a RDD containing scala map and now I want to remove this map and want to collect all keys values in a RDD. Any help will be appreciated....

ZipList with Scalaz


list,scala,scalaz,applicative
Suppose I have a list of numbers and list of functions to apply to numbers: val xs: List[Int] = List(1, 2, 3) val fs: List[Int => Int] = List(f1, f2, f3) Now I would like to use an Applicative to apply f1 to 1, f2 to 2, etc. val ys:...

XSL transformation outputting multiple times and other confusion


xml,xslt,xpath
I'm attempting to transform a section of an XML document (which is mostly HTML) with a templated piece of markup should a particular pattern be matched. I'm inexperienced with XSLT (I've only used xpath, really) and online documentation is sparse so I'm struggling with it... To the following XML document:...

Collect strings after a foreach loop


c#,xml,foreach
Is it possible to collect the strings after a foreach loop? For example: StringCollection col = new StringCollection(); XmlNodeList skillNameNodeList=SkillXML.GetElementsByTagName("name"); foreach (XmlNode skillNameNode in skillNameNodeList) { skillsName=skillNameNode.Attributes["value"].Value; } col.Add(skillsName); //Return System.Collections.Specialized.StringCollection I want to collect each skillsName and put them in a collection or a list so that I can...

Sequence number for static and dynamic rows in XSLT 2.0


xml,xslt-2.0
I'm trying to generate sequence number for my input xml with some static and dynamic rows combination. input xml: (Edited) <data> <oldLine>dat1</oldLine> <modLine>dat2</modLine> <line>para1</line> <line>para2</line> <line>para3</line> </data> <data> <oldLine>dat3</oldLine> <modLine>dat4</modLine> <line>para4</line> <line>para5</line> </data> I need to add three fixed records after every "data" tag in the loop...

Scala (Slick) HList splitting to case classes


scala,slick
currently I have a HList with more than 22 fields and now I want to split it to 2-3 case classes, is there an easy functional way to do it? Currently I use the following syntax: CaseClass1(c.head, c.tail.head, c.tail.tail.head, etc...) However that doesn't seem to be right since I have...

Load XML to list using LINQ [duplicate]


c#,xml,linq
This question already has an answer here: XDocument to List of object 1 answer I have following XML: <?xml version="1.0" encoding="utf-8"?> <start> <Current CurrentID="5"> <GeoLocations> <GeoLocation id="1" x="78492.61" y="-80973.03" z="-4403.297"/> <GeoLocation id="2" x="78323.57" y="-81994.98" z="-4385.707"/> <GeoLocation id="3" x="78250.57" y="-81994.98" z="-4385.707"/> </GeoLocations> <Vendors> <Vendor id = "1" x="123456" y="456789" z="0234324"/>...

Scala first program issue


scala,recursion,case,frequency
I have just started to learn Scala after some experience with functional programming in other languages. def freq(c:Char, y:String, list:List[(Char,Int)]): List[(Char,Int)] = list match{ case _ => freq(c, y.filter(_ == c), list :: List((count(c,y),c))) case nil => list } In the above code I am getting an error when trying...

List view not returning to original state after clearing search


java,android,xml,android-activity,android-listfragment
I'm trying to get my list to show all my items again whenever I cancel a search from my search view but for some strange reason, the list gets stuck with the results only from the previous search. Does anyone know what is wrong with my code and how to...

Multiply arrays by arrays in JAVA


java,arrays,xml,permutation
I have for example three arrays (but I can have more) with some values like this: table_1 = [a,b,c]; //three elements table_2 = [d]; //one elements table_3 = [e,f]; //two elements and I want to get that output <test> <test_1>a</test_1> <test_2>d</test_2> <test_3>e</test_3> </test> <test> <test_1>a</test_1> <test_2>d</test_2> <test_3>f</test_3> </test> <test> <test_1>b</test_1>...

Retrieving TriangleCount


scala,apache-spark,spark-graphx
I'm trying to retrieve the amount of triangles from a graph using graphX. As I'm new to both Scala and graphX, I'm currently quite stuck. I'm creating a graph from an edgefile: 1 2 1 3 2 3 This should be 1 triangle. Next I'm using the build in function...

Scala running issue on eclipse


eclipse,scala
I configured everthing within eclipse for scala. I create a snippet to show you the issue, i can't see in run options run as scala application, i also tried to find my main class under build configuration option but i can't find it. How i can solve it?...

odoo v8 - Field(s) `arch` failed against a constraint: Invalid view definition


python,xml,view,odoo,add-on
I want to create a new view with a DB-view. When I try to install my app, DB-view was created then I get error: 2015-06-22 12:59:10,574 11988 ERROR odoo openerp.addons.base.ir.ir_ui_view: Das Feld `datum` existiert nicht Fehler Kontext: Ansicht `overview.tree.view` [view_id: 1532, xml_id: k. A., model: net.time.overview, parent_id: k. A.] 2015-06-22...

group siblings by identifying the first node of a certain type in sequence


xml,xslt,xpath
Not sure if that description is the best...but given this xml: <?xml version="1.0"?> <root> <type1 num="1" first="1"/> <type1 num="2" /> <type2 num="3" /> <type2 num="4" /> <type1 num="5" first="2"/> <type1 num="6" /> <type2 num="7" /> <type2 num="8" /> <type1 num="9" first="3"/> <type1 num="10" /> <type2 num="11" /> <type2 num="12" />...

About sorting based on the counting of subelements


xml,xslt
i have an xml document with properties that belong to agencies: <agency name="Century 42" num="Century42" mail="[email protected]"/> <property agency="Century42" ....> ... I would like to print the info of all agencies. The agencies should be sorted by the number of properties that they own. I tried this but it does not...

PlayFramework: value as is not a member of Array[Byte]


scala,playframework
I want to make file download from a database using Play framework. But when I use this code I get this message: value as is not a member of Array[Byte] And if I change Ok(bytOfImage.as("image/jpg")) to Ok(bytOfImage) it works good but I get a file with a name: secondindex without...

How to effectively get indices of 1s for given binary string using Scala?


scala,functional-programming,higher-order-functions
Suppose we have a binary string such as 10010010. All I want is a function returning indices of 1s for that string: indicesOfOnes("10010010") -> List(0, 3, 6) indicesOfOnes("0") -> List() And what I implemented is: def indicesOfOnes(bs: String): List[Int] = { val lb = ListBuffer[Int]() bs.zipWithIndex.foreach { case (v, i)...

Operand order in Scala List.prepend (::)


list,scala,operators
Odersky has brilliantly optimized Java syntax, enabling object calls without dots and parenthesis. I.e. instead of list.prepend(item), you now simply write list :: item, which also turns language operators into simple object methods. Here, List defines :: (prepend) operator. However, you normally write it vice-verse in Scala, using item ::...

C# XML: System.InvalidOperationException


c#,xml
I have been learning C#'s XML with a project however I keep getting the InvalidOperationException. I have put the code below XmlTextWriter writer = new XmlTextWriter(path, System.Text.Encoding.UTF8); writer.WriteStartDocument(true); writer.Formatting = Formatting.Indented; writer.Indentation = 4; writer.WriteStartElement("User Info"); writer.WriteStartElement("Name"); writer.WriteString(userName); writer.WriteEndElement(); writer.WriteStartElement("Tutor Name"); writer.WriteString(tutorName); writer.WriteEndElement();...

Zipping two arrays together with index in Scala?


arrays,scala,zip
I have two arrays populated with integers. They are the same size (val array1 and val array2). I want to fuse them together into tuples with their index as the third element. For example if we have val array1 = Array(5,2,6,2) and val array2 = Array(9,8,3,4) then I want to...

Convert contents of an XmlNodeList to a new XmlDocument without looping


c#,xml,xpath,xmldocument,xmlnodelist
I have Xml that I filter using XPath (a query similar to this): XmlNodeList allItems = xDoc.SelectNodes("//Person[not(PersonID = following::Person/PersonID)]"); This filters all duplicates from my original Persons Xml. I want to create a new XmlDocument instance from the XmlNodeList generated above. At the minute, the only way I can see...

Unable to construct Document object from xml string


java,xml,xpath,xml-parsing
I have xml string coming to my appliaction like follows <?xml version="1.0" encoding="UTF-8"?><loc:getLocation xmlns:loc="http://www.csapi.org/schema/parlayx/terminal_location/v2_3/local"> <loc:address>tel:+919420161525</loc:address> <loc:requestedAccuracy>500</loc:requestedAccuracy> <loc:acceptableAccuracy>500</loc:acceptableAccuracy> </loc:getLocation> I want to construct Document object from this so that using XPath, I can retrieve required data. I tried following code...

xpath query seem to be failing


xml,xpath
Can someone tell me the reason for the failure of this xpath query: //Pages/*[(name() = 'Home') or following-sibling::Home] on this xml structure: <Pages> <copyright>me inc. 2015,</copyright> <author>Me</author> <lastUpdate>2/1/1999</lastUpdate> <Home>--------------------</Home> <About>--------------------</About> <Contact>------------------</Contact> </Pages> only returned copyright element, which is against my targets (To grab all element between Pages and...

How to generalize the round methods


scala
I have the following four methods, using BigDecimal to round a number: private def round(input: Byte, scale: Int): Byte = { BigDecimal(input).setScale(scale, RoundingMode.HALF_UP).byteValue() } private def round(input: Short, scale: Int): Short = { BigDecimal(input).setScale(scale, RoundingMode.HALF_UP).shortValue() } private def round(input: Int, scale: Int): Int = { BigDecimal(input).setScale(scale, RoundingMode.HALF_UP).intValue() } private def...

How to use the Akka ask pattern without blocking


scala,asynchronous,akka,future
Hi I have a actor which is responsible for fetching data from a database, turning it into a list and sending it back to the sender. I am using the ask pattern to receive response from my actor, because I don't want to use await.result because this approach will block...

Future yielding with flatMap


scala
Given Futures fa, fb, fc, I can use f: Function1[(A,B,C), Future[D]], to return a Future[D] either by: (for { a <- fa b <- fb c <- fc } yield (a,b,c)).flatMap(f) which has the unenviable property of declaring the variables a,b,c twice. or a.zip(b).zip(c).flatMap{ case (a, (b, c)) => f(a,...

Get XML node value when previous node value conditions are true (without looping)


xml,vb.net,linq-to-xml
Sample XML - <?xml version="1.0"?> <Root> <PhoneType dataType="string"> <Value>CELL</Value> </PhoneType> <PhonePrimaryYn dataType="string"> <Value>Y</Value> </PhonePrimaryYn> <PhoneNumber dataType="string"> <Value>555-555-5554</Value> </PhoneNumber> <PhonePrimaryYn dataType="string"> <Value>Y</Value> </PhonePrimaryYn> <PhoneType dataType="string"> <Value>HOME</Value> </PhoneType>...

XElement.Value is stripping XML tags from content


c#,.net,xml,xml-parsing,xelement
I have the following XML: <Message> <Identification>c387e36a-0d79-405a-745c-7fc3e1aa8160</Identification> <SerializedContent> {"Identification":"81d090ca-b913-4f15-854d-059055cc49ff","LogType":0,"LogContent":"{\"EntitiesChanges\":\" <audit> <username>acfc</username> <date>2015-06-04T15:15:34.7979485-03:00</date> <entities> <entity> <properties> <property> <name>DepId</name> <current>2</current> </property>...

How to extract efficientely content from an xml with python?


python,xml,python-2.7,pandas,lxml
I have the following xml: <?xml version="1.0" encoding="UTF-8" standalone="no"?><author id="user23"> <document><![CDATA["@username: That boner came at the wrong time ???? http://t.co/5X34233gDyCaCjR" HELP I'M DYING ]]></document> <document><![CDATA[Ugh ]]></document> <document><![CDATA[YES !!!! WE GO FOR IT. http://t.co/fiI23324E83b0Rt ]]></document> <document><![CDATA[@username Shout out to me???? ]]></document> </author> What is the most efficient...

XML-XSLT-XPATH : How to convert multiple XML elements to a string, separated by semicolon


xml,xslt,xpath,xslt-2.0
I have just demonstrated my question as an input and output format as below. I have an input as xml document which consist of following data <Users> <user> <name>Mark Curtain</name> <email>[email protected]</email> <username>mark</username> </user> <user> <name>Zuke Gossip</name> <email>[email protected]</email> <username>zuke</username> </user> <user> <name>Villan Kiosk</name> <email>[email protected]</email>...

Scala unapplySeq extractor syntax


scala,pattern-matching,scala-2.11
I (inadvertently) came across a bit of pattern matching syntax I did not expect to compile and now cannot figure out. It appears related to unapplySeq. Note the case x List(_,_) part in this simple example: val xs = List(1, 2, 3) //> xs : List[Int] = List(1, 2, 3)...

XMLPullParser black diamond question marks with certain characters


android,xml,character-encoding,xmlpullparser,questionmark
I'm making an android app, that needs to fetch and parse XML. The class for that was made following the instructions from here http://www.tutorialspoint.com/android/android_rss_reader.htm and the fetcher method looks like this: public void fetchXML() { Thread thread = new Thread(new Runnable() { @Override public void run() { try { URL...

Is this definition of a tail recursive fibonacci function tail-recursive?


scala,f#,functional-programming,tail-recursion,continuation-passing
I've seen around the following F# definition of a continuation-passing-style fibonacci function, that I always assumed to be tail recursive: let fib k = let rec fib' k cont = match k with | 0 | 1 -> cont 1 | k -> fib' (k-1) (fun a -> fib' (k-2)...

How to calculate max string-length of a node-set?


xml,xslt,xslt-1.0,libxslt
I am trying to use XSLT to turn an XML document into plain text tables for human consumption. I am using xsltproc, which only implements XSLT 1.0 (so max is from EXSLT actually). I tried the below, but the commented-out definition fails because string-length returns only a single value (the...

Fixed element in android?


android,xml,android-fragments
I am using a FAB(Floating action button) and a ViewPager that has a list inside a fragment. The ViewPager stops due to the FAB block and each are blocks the ViewPager being on top of the FAB activity_main.xml <LinearLayout xmlns:android="http://schemas.android.com/apk/res/android" xmlns:tools="http://schemas.android.com/tools" xmlns:fab="http://schemas.android.com/apk/res-auto" android:layout_width="match_parent" android:layout_height="match_parent" android:orientation="vertical" android:fitsSystemWindows="true">...

XSLT How to remove style from div and td tags


xml,xslt
I am new to XSLT. I got stuck while removing style attributes from div, td or li tags. Input XML: <?xml version="1.0" encoding="UTF-8"?> <div xmlns="http://www.w3.org/1999/xhtml"> <table style="BORDER-BOTTOM: medium none; BORDER-LEFT: medium none; WIDTH: 606px; BORDER-COLLAPSE: collapse; WORD-WRAP: break-word; TABLE-LAYOUT: fixed; BORDER-TOP: medium none; BORDER-RIGHT: medium none" class="MsoNormalTable msoUcTable" tabIndex="-1" border="1"...

Ruby- get a xml node value


ruby,xml
can someone help me in extracting the node value for the element "Name". Type 1: I am able to extract the "name" value for the below xml by using the below code <Element> <Details> <ID>20367</ID> <Name>Ram</Name> <Name>Sam</Name> </Details> </Element> doc = Nokogiri::XML(response.body) values = doc.xpath('//Name').map{ |node| node.text}.join ',' puts values...

Error when building an XDocument


c#,xml,linq,xpath,linq-to-xml
Using the following example xml containing one duplicate: <Persons> <Person> <PersonID>7506</PersonID> <Forename>K</Forename> <Surname>Seddon</Surname> <ChosenName /> <MiddleName /> <LegalSurname /> <Gender>Male</Gender> </Person> <Person> <PersonID>6914</PersonID> <Forename>Clark</Forename> <Surname>Kent</Surname> <ChosenName>Clark</ChosenName> <MiddleName />...

Tagging values in HTML document for automated extraction


html,xml,html5
We have a series of documents that are being converted to HTML for web access. The documents are operating instructions that list actions people have to do as well as distinct requirements. We wanted to put a tag around each requirement so it can be automatically extracted using some code....

finding file in root of wpf application


c#,xml,wpf,visual-studio,relative-path
I'm trying to load a file with pack://application: The file is situated in the root of my project but I keep getting a null reference error. However When I do an absolute reference it finds the file and loads just fine. What am I missing here? This doesn't work var...

XSLT for-each statement not iterating proper amount of times


xml,xslt
I am having trouble with my XSLT for-each statements. When I run the XML through the XSLT, it only comes up with the first iteration of the list, and then stops. It doesn't post the values either. Here is the XML code. <?xml version="1.0" encoding="UTF-8"?> <template> <L> <Q>Hey</Q> <Q>There</Q> <Q>Thank...

Spray microservice assembly deduplicate


scala,sbt,akka,spray,microservices
I'm using this template to develop a microservice: http://www.typesafe.com/activator/template/activator-service-container-tutorial My sbt file is like this: import sbt._ import Keys._ name := "activator-service-container-tutorial" version := "1.0.1" scalaVersion := "2.11.6" crossScalaVersions := Seq("2.10.5", "2.11.6") resolvers += "Scalaz Bintray Repo" at "https://dl.bintray.com/scalaz/releases" libraryDependencies ++= { val containerVersion = "1.0.1" val configVersion = "1.2.1"...

SCALA: change the separator in Array


arrays,string,scala,delimiter
I have an Array like this. scala> var x=Array("a","x,y","b") x: Array[String] = Array(a, x,y, b) How do I change the separator comma in array to a :. And finally convert it to string like this. String = "a:x,y:b" My aim is to change the comma(separators only) to other separator(say,:), so...

type conversion performance optimizable?


c#,xml,csv,optimization,type-conversion
The following snippet converts xml data to csv data in a data processing application. element is a XElement. I'm currently trying to optimize the performance of the application and was wondering if I could somehow combine the two operations going on below: Ultimately I still want access to the string...

Extracting XML data from CLOB


sql,xml,oracle
How can I extract Food ItemID and Food Item Name and Quantity from the data as mentioned below. This is in clob column in plsql. <ServiceDetails> <FoodItemDetails> <FoodItem FoodItemID="6486" FoodItemName="CARROT" Quantity="2" Comments="" ServingQuantityID="142" ServingQuantityName="SMALL GLASS" FoodItemPrice="50" ItemDishPriceID="5336" CurrencyName="INR" Currency Id="43"/> </FoodItemDetails> <BillOption> <Bill Details Total Price="22222" BillOption="cash"/> </BillOption> <Authoritativeness/>...

XML Schema 1.0 “All” with multiple same elements?


xml,schema
What I want to validate is the XML looks like below: <A></A> <B></B> <C></C> <D></D> <E></E> <E></E> A,B,C,D just have zero or one. And they don't have sequence. It could be D,C,B,A. And in the very end, there are one or more E element(s). I have tried multiple ways, but...

Parsing XML array using Jquery


javascript,jquery,xml,jquery-mobile
I have stuck up with an issue of passing XML using Jquery. I am getting empty array while traversing to jquery.Please help me how to get datas from XML array. I have mentioned my code below. XML <?xml version="1.0" encoding="UTF-8"?> <json> <json> <CustomerName>999GIZA MID INSURANCEAND SERVICES PVT LTD</CustomerName> <mobiLastReceiptDate>null</mobiLastReceiptDate> </json>...

HTMLPurifier without XML declaration


php,xml,htmlpurifier
I am using HTMLPurifier on PHP to clean some dirty HTML, as follows: $H=new HTMLPurifier() $content_text_fixHTML = $H->purify($content_text); Note: Omited encoding set up, because it is UTF-8 But, it will output the XML encoding declaration at the top. <?xml encoding="utf-8" ?> I do not want it. How do I prevent...

How to instantiate lexical.Scanner in a JavaTokenParsers class?


scala,parsing,lexical-scanner
I am writing a parser which inherits from JavaTokenParsers in that I have a function as follow: import scala.util.parsing.combinator.lexical._ import scala.util.parsing._ import scala.util.parsing.combinator.RegexParsers; import scala.util.parsing.combinator.syntactical.StdTokenParsers import scala.util.parsing.combinator.token.StdTokens import scala.util.parsing.combinator.lexical.StdLexical import scala.util.parsing.combinator.lexical.Scanners import scala.util.parsing.combinator.lexical.Lexical import...