Class: Coopy::Mover

Inherits:
Object
  • Object
show all
Defined in:
lib/coopy/mover.rb

Class Method Summary collapse

Class Method Details

.move_units(units) ⇒ Object 



4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
# File 'lib/coopy/mover.rb', line 4

def self.move_units(units)
  isrc = []
  idest = []
  len = units.length
  ltop = -1.0
  rtop = -1
  in_src = {}
  in_dest  = {}
  (0..len-1).each do |i| 
    unit = units[i]
    if (unit.l>=0 && unit.r>=0) 
      ltop = unit.l if (ltop<unit.l) 
      rtop = unit.r if (rtop<unit.r)
      in_src[unit.l] = i
      in_dest[unit.r] = i
    end
  end
  v = nil
  (0...ltop+1).each do |i| 
    v = in_src[i]
    isrc.push(v) if v
  end
  (0...rtop+1).each do |i|
    v = in_dest[i]
    idest.push(v) if v
  end
  return move_without_extras(isrc,idest)
end

.move_with_extras(isrc, idest) ⇒ Object 



33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
# File 'lib/coopy/mover.rb', line 33

def self.move_with_extras(isrc, idest)
  # First pass: eliminate non-overlapping elements (inserts+deletes)
  len = isrc.length
  len2 = idest.length
  in_src = {}
  in_dest = {}
  (0..len-1).each do |i| 
    in_src[isrc[i]] = i
  end
  (0..len2-1).each do |i| 
    in_dest[idest[i]] = i
  end
  src = []
  dest = []
  v = nil
  (0..len-1).each do |i| 
    v = isrc[i]
    src << v if (in_dest.has_key?(v))
  end
  (0..len2-1).each do |i|
    v = idest[i]
    dest << v if (in_src.has_key?(v))
  end
  return move_without_extras(src,dest)
end

.move_without_extras(src, dest) ⇒ Object 



59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
 
# File 'lib/coopy/mover.rb', line 59

def self.move_without_extras(src, dest)
  return nil if (src.length!=dest.length) 
  return [] if (src.length<=1)
  
  len = src.length
  in_src = {}
  blk_len = {}
  blk_src_loc = {}
  blk_dest_loc = {}
  (0...len).each do |i|
    in_src[src[i]] = i
  end
  ct = 0
  in_cursor = -2
  out_cursor = 0
  nxt = nil
  blk = -1
  v = nil
  while (out_cursor<len)
    v = dest[out_cursor]
    nxt = in_src[v]
    if (nxt != in_cursor+1) 
      blk = v
      ct = 1
      blk_src_loc[blk] = nxt
      blk_dest_loc[blk] = out_cursor
    else 
      ct+=1
    end
    blk_len[blk] = ct
    in_cursor = nxt
    out_cursor+=1
  end

  blks = blk_len.keys
  blks.sort!{ |a,b| blk_len[a] <=> blk_len[b] }

  moved = []

  while (blks.length>0) 
    blk = blks.shift
    blen = blks.length
    ref_src_loc = blk_src_loc[blk]
    ref_dest_loc = blk_dest_loc[blk]
    i = blen-1
    while (i>=0) 
      blki = blks[i]
      blki_src_loc = blk_src_loc[blki]
      to_left_src = blki_src_loc < ref_src_loc
      to_left_dest = blk_dest_loc[blki] < ref_dest_loc
      if (to_left_src!=to_left_dest) 
        ct = blk_len[blki]
        (0..ct-1).each do |j| 
          moved.push(src[blki_src_loc])
          blki_src_loc+=1
        end
        blks.splice(i,1)
      end
      i-=1
    end
  end
  return moved
end