TotalIterator

iterator.go

package main

import (
	"fmt"
)

type Iterator interface {
	GetCurrent() int
	MoveNext() bool
}

type iterator struct {
	line []int
	cur  int
}

func newIterator(in []int) *iterator {
	return &iterator{in, -1}
}

func (id *iterator) GetCurrent() int {
	if id.cur == -1 {
		return -1
	}
	return id.line[id.cur]
}

func (id *iterator) MoveNext() bool {
	if id.cur == len(id.line)-1 {
		return false
	}
	id.cur++
	return true
}

type pair struct {
	k, v int
}

type TotalIterator struct {
	lines []Iterator
	cur   int
	buf   []*pair
}

func NewTotalIterator(it [][]int) *TotalIterator {
	its := make([]Iterator, len(it))
	for k := range its {
		its[k] = newIterator(it[k])
	}
	return &TotalIterator{its, -1, make([]*pair, len(it))}
}

func (id *TotalIterator) GetCurrent() int {
	if id.cur == -1 {
		return -1
	}
	return id.lines[id.cur].GetCurrent()
}

func sort(a []*pair, length int) {
	if length <= 1 {
		return
	}
	start := 0
	end := length - 1
	value := a[0]
	for start < end {
		for ; end > start; end-- {
			if a[end].k < value.k {
				a[start] = a[end]
				break
			}
		}
		for ; start < end; start++ {
			if a[start].k > value.k {
				a[end] = a[start]
				break
			}
		}
	}
	a[start] = value
	sort(a, start)
	sort(a[start+1:], length-start-1)
}

func (id *TotalIterator) MoveNext() bool {
	if id.cur == -1 {
		r := false
		for s := range id.lines {
			r = id.lines[s].MoveNext()
			if r == true {
				id.buf[s] = &pair{id.lines[s].GetCurrent(), s}
			}
		}
		sort(id.buf, len(id.buf))
	} else {
		r := id.lines[id.cur].MoveNext()
		if r == false {
			id.buf = id.buf[1:]
		} else {
			s := &pair{id.lines[id.cur].GetCurrent(), id.cur}
			n := 1
			for n < len(id.buf) && id.buf[n].k < s.k {
				n++
			}
			for i := 0; i < n-1; i++ {
				id.buf[i] = id.buf[i+1]
			}
			id.buf[n-1] = s
		}
	}
	if len(id.buf) == 0 {
		return false
	}
	id.cur = id.buf[0].v
	return true
}

func main() {
	// s := newiterator([]int{1, 2, 3, 4, 5, 6})
	// for s.MoveNext() {
	// 	fmt.Printf("%d ", s.GetCurrent())
	// }
	t := NewTotalIterator([][]int{[]int{1, 2, 3, 4, 5}, []int{2, 3, 4, 5, 6}, []int{3, 4, 5, 6, 7}, []int{4, 5, 6, 7, 8}})
	for t.MoveNext() {
		fmt.Println(t.GetCurrent())
	}
}

iterator.py

#!/usr/bin/env python

class iterator():
    def __init__(self, line):
        self.cur = -1
        self.line = line
    def getCurrent(self):
        if self.cur != -1:
            return self.line[self.cur]
    def moveNext(self):
        if self.cur < len(self.line)-1:
            self.cur += 1
            return True
        return False

class totalit():
    def __init__(self, line):
        self.line = []
        for l in line:
            self.line.append(iterator(l))
        self.buff = []
    def getCurrent(self):
        if len(self.buff) > 0:
            return self.buff[0][0]
    def moveNext(self):
        if len(self.buff) == 0:
            for s in self.line:
                if s.moveNext() == True:
                    self.buff.append((s.getCurrent(), s))
            self.buff.sort()
        else:
            r = self.buff[0][1]
            if r.moveNext() == False:
                self.buff = self.buff[1:]
            else:
                self.buff[0] = (r.getCurrent(), r)
                self.buff.sort()
        if len(self.buff) == 0:
            return False
        return True


if __name__ == '__main__':
    t = totalit([[1,2],[20,31],[3,4,5,6,76],[33,43,54,61,76]])
    while t.moveNext():
        print t.getCurrent()