Groovy web console

subscribe to the feed Subscribe
to this
site
Binary tree delay (corrected version) (via #groovywebconsole)
tweet this snippet Tweet
this
script

Binary tree delay (corrected version)

Published 11 months ago by Adrian McMenamin with tags queue tree binary tree recursion
Actions  ➤ Edit in console Back to console Show/hide line numbers View recent scripts
        import java.util.Random
 
 class Node {
  def above
  def leftBelow
  def rightBelow
  def packet
  static def count = 0
  def nextRight
  static levelsList = []
  
 
  Node(def currentLevel, def maxLevel, def top, def rand, def density) {
   above = top
   if (rand.nextInt(100) < density) {
    packet = true
   } else {
    packet = false
   }
   if (levelsList[currentLevel].size()) {
    levelsList[currentLevel].last().nextRight = this
   }
   levelsList[currentLevel] << this
   currentLevel++
   if (currentLevel > maxLevel) {
    return
   }
   leftBelow = new Node(currentLevel, maxLevel, this, rand, density)
   rightBelow = new Node(currentLevel, maxLevel, this, rand, density)
  }
  
  def scoreTree(def leaf)
  {
   def empties = false
   def score = 0
   def emptiesScore = 0
   def levelScore = 0
   def frees = 0
   def scoringNode = (levelsList.last())[leaf]
   def testingNode = scoringNode
   def found = true
   for (def i = levelsList.size(); i > 0; i--) {
    while (testingNode.nextRight) {
     testingNode = testingNode.nextRight
     if (testingNode.packet) {
      if (found) {
       levelScore++
      } else {
       found = true
      }
     }
    }
    if (!empties && levelScore == 0) {
     empties = true
    }
    if (empties) {
     if (levelScore == 0) {
      frees++
     } else {
      emptiesScore += levelScore
     }
    } else {
     score += levelScore
    }
    levelScore = 0
    found = false
    testingNode = scoringNode.above
    scoringNode = testingNode
   }
   def finalScore = score
   if (empties) {
    def additionalScore = emptiesScore - frees
    if (additionalScore > 0) {
     finalScore += additionalScore
    }
   }
   
   return finalScore
  }  
   
 }
 
 
 
 Random rand = new Random()
// println "How many levels?"
 //def levelStr = (System.in.newReader().readLine())
 def levels = 9 //levelStr.toInteger() 
 if (levels < 1) {
  println "You entered a bad level count $levels"
  return
 }
 
 //println "What load factor (0 to 100)?"
 //def loadFactorStr = (System.in.newReader().readLine())
 def loadFactor = 99 //loadFactorStr.toInteger()
 if (loadFactor > 100 || loadFactor < 0) {
  println "You entered a bad loadFactor $loadFactor"
  return
 }
 
 def leaves = 2 ** (levels - 1)
 //println "With $levels levels there are $leaves leaves - which one do you want to pick?"
 //def pickedLeafStr = (System.in.newReader().readLine())
 def pickedLeaf = 0 //pickedLeafStr.toInteger()
 if (pickedLeaf< 0 || pickedLeaf> leaves) {
  println "You picked a bad leaf: $pickedLeaf"
  return
 }
 
 def times = []
 
 println "Running test..."
 for (def i = 1; i <= 100; i++) {
  print "$i, "
  //build tree
  for (def j = 0; j < levels; j++) {
   Node.levelsList[j] = []
  }
  Node root = new Node(0, levels - 1, null, rand, loadFactor)
 
  times << root.scoreTree(pickedLeaf)
 }
 println ""
 
 println "The times were..."
 times.each {
  print "$it, "
 }
 println ""
 
 println "====Average delay: ${times.sum()/times.size()}===="