// peekToken performs lookahead of the given count on the token stream.
func (l *peekableLexer) peekToken(count int) lexeme {
	if count < 1 {
		panic(fmt.Sprintf("Expected count > 1, received: %v", count))
	}

	// Ensure that the readTokens has at least the requested number of tokens.
	if l.readTokens.Len() < count {
		for {
			l.readTokens.PushBack(l.lex.nextToken())

			if l.readTokens.Len() == count {
				break
			}
		}
	}

	// Retrieve the count-th token from the list.
	var element *list.Element
	element = l.readTokens.Front()

	for i := 1; i < count; i++ {
		element = element.Next()
	}

	return element.Value.(lexeme)
}

// listen is run in a goroutine. It reads new pull lists from its
// input queue until the queue is closed.
// listen takes ownership of the list that is passed to it.
//
// Note that the routine does not ever need to access the list
// itself once the current_item has been initialized, so we do
// not bother to keep a pointer to the list. Because it is a
// doubly linked list, holding on to the current item will keep
// it from garbage collection.
//
func (b *WorkQueue) listen() {
	var current_item *list.Element

	// When we're done, close the output channel to shut down any
	// workers.
	defer close(b.NextItem)

	for {
		// If the current list is empty, wait for a new list before
		// even checking if workers are ready.
		if current_item == nil {
			if p, ok := <-b.newlist; ok {
				current_item = p.Front()
			} else {
				// The channel was closed; shut down.
				return
			}
		}
		select {
		case p, ok := <-b.newlist:
			if ok {
				current_item = p.Front()
			} else {
				// The input channel is closed; time to shut down
				return
			}
		case b.NextItem <- current_item.Value:
			current_item = current_item.Next()
		}
	}
}

// SetAsync 设置是否异步输出,仅当之前为非异步并且设置为异步时,logList和mu有效
func (this *SimpleLogWriter) SetAsync(async bool, logList *list.List, mu *sync.Mutex) {
	if !this.async && async {
		if logList == nil || mu == nil {
			panic(ErrorLogWriterInvalidParam)
		}
		this.logList = logList
		this.logmu = mu
		go func() {
			var counter = atomic.AddInt32(&this.counter, 1)
			for this.async && counter == this.counter && !this.closed {
				if this.logList.Len() > 0 {
					var start *list.Element
					var length = 0
					this.logmu.Lock()
					if this.logList.Len() > 0 {
						start = this.logList.Front()
						length = this.logList.Len()
						this.logList.Init()
					}
					this.logmu.Unlock()
					for i := 0; i < length; i++ {
						var v, ok = start.Value.(string)
						if ok {
							this.writer.Write(v)
						}
						start = start.Next()
					}
				} else {
					time.Sleep(50 * time.Millisecond)
				}
			}
		}()
	}
	this.async = async
}

// this time eviction is called by a scheduler for background, periodic evictions
func TimeEvict(lru *LRUCache, now time.Time, ttl time.Duration) {
	lru.mu.Lock()
	defer lru.mu.Unlock()

	if lru.list.Len() < 1 {
		return
	}

	var n *entry
	var el *list.Element
	hasEvictCallback := lru.EvictCallback != nil

	el = lru.list.Back()

	for {
		if el == nil {
			break
		}
		n = el.Value.(*entry)
		if now.Sub(n.time_accessed) > ttl {
			// the Difference is greater than max TTL so we need to evict this entry
			// first grab the next entry (as this is about to dissappear)
			el = el.Prev()
			lru.remove(n.key)
			if hasEvictCallback {
				lru.EvictCallback(n.key, n.value)
			}
		} else {
			// since they are stored in time order, as soon as we find
			// first item newer than ttl window, we are safe to bail
			break
		}
	}
	lru.last_ttl_check = time.Now()
}

// AsyncWrite 异步写入日志
func (this *ConsoleLogWriter) AsyncWrite(logList *list.List, mu *sync.Mutex) {
	this.logList = logList
	this.logmu = mu
	go func() {
		for !this.closed {
			if this.logList.Len() > 0 {
				var start *list.Element
				var length = 0
				this.logmu.Lock()
				start = this.logList.Front()
				length = this.logList.Len()
				this.logList.Init()
				this.logmu.Unlock()
				for i := 0; i < length; i++ {
					var v, ok = start.Value.(string)
					if ok {
						this.Write(v)
					}
					start = start.Next()
				}
			} else {
				//暂停15毫秒
				time.Sleep(15 * time.Millisecond)
				//runtime.Gosched()
			}
		}
	}()
}

func (c *Cache) cleaner(limit int) {
	for _ = range c.clean {
		var item *list.Element
		for {
			c.lock.Lock() // X1+
			if len(c.m) < limit {
				c.lock.Unlock() // X1-
				break
			}

			if item == nil {
				item = c.lru.Front()
			}
			if p := item.Value.(*cachepage); !p.dirty {
				delete(c.m, p.pi)
				c.lru.Remove(item)
				c.Purge++
			}
			item = item.Next()
			c.lock.Unlock() // X1-
		}
		atomic.AddInt32(&c.cleaning, -1)
	}
	c.close <- true
}

func listXmpl() {
	fmt.Println("Teste Liste")
	myList := list.New()
	// einige Elemente einfügen
	myList.PushFront(element2{"a", 1})
	myList.PushFront(element2{"b", 2})
	myList.PushFront(element2{"c", 3})
	myList.PushFront(element2{"d", 4})
	myList.PushFront(element2{"e", 5})
	myList.PushFront(element2{"f", 6})

	for e := myList.Front(); e != nil; e = e.Next() {
		fmt.Println(e.Value)
	}

	// Ein Element umsortieren
	fmt.Println("Gehe zum zweiten Element")
	// erstmal den Anfang holen
	var e *list.Element = myList.Front()
	// einen Schritt weiter, zum e gehen
	e = e.Next()
	// Ausgeben zum Test
	fmt.Println("aktuell:", e.Value)
	fmt.Println("Verschiebe Element ans Listenende")
	// und e/5 ans Ende verbannen
	myList.MoveToBack(e)

	// nochmal mittels Iterator Elemente auslesen
	for e := myList.Front(); e != nil; e = e.Next() {
		fmt.Println(e.Value)
	}

}

// Returns the item after e or nil it is the last item or nil.
// The item is a *list.Element from the 'container/list' package.
// Even though it is possible to call e.Next() directly, don't. This behavior
// may not be supported moving forward.
func (q Queue) Next(e *list.Element) *list.Element {
	if e == nil {
		return e
	}

	return e.Next()
}

func TestInsertBefore(t *testing.T) {
	var e *list.Element
	l := list.New()

	for i := 0; i < 5; i++ {
		if i == 3 {
			e = l.PushFront(i)
		} else {
			l.PushFront(i)
		}
	}

	l.InsertBefore(5, e)

	if l.Len() != 6 {
		t.Errorf("length = %d", l.Len())
	}

	e = l.Front()
	for i := 0; i < 6; i++ {
		t.Logf("e = %d", e.Value)

		e = e.Next()
	}
}

// C & U
func (node Node) Update(cmp *RemoteNode) {
	bucketID := node.ID.DistanceTo(cmp.ID).GetBucketID()
	bucket := node.RoutingTable[bucketID]

	var found bool = false
	var foundElement *list.Element

	for elem := bucket.Front(); elem != nil; elem = elem.Next() {
		e, ok := elem.Value.(*RemoteNode)
		if !ok {
			continue // if it's not a NodeID, wtf is it doing in the list?? Probably should error out
		}
		if e.ID.EqualsTo(cmp.ID) || e.ID.EqualsTo(node.ID) {
			found = true
			foundElement = elem
			break
		}
	}
	if !found {
		if bucket.Len() <= BUCKET_SIZE {
			bucket.PushFront(cmp)
		}
	} else {
		foundElement.Value = cmp // update the  foundElement value
		bucket.MoveToFront(foundElement)
	}
}

func (s *Summary) incrElement(el *list.Element) {
	counter := el.Value.(*Counter)
	counter.count++

	// This element already has the largest count so it won't get moved.
	if s.list.Front() == el {
		return
	}

	// Starting at the previous element, move this element behind the first
	// element we find which has a higher count.
	moved := false
	for currEl := el.Prev(); currEl != nil; currEl = currEl.Prev() {
		if currEl.Value.(*Counter).count > counter.count {
			s.list.MoveAfter(el, currEl)
			moved = true
			break
		}
	}

	// If we didn't find an element with a higher count then this element must
	// have the highest count.  Move it to the front.
	if !moved {
		s.list.MoveToFront(el)
	}
}

/* Create tree ball list with id random. If Ball is already taked, a first ball next is taked */
func (Data *Data) Manage_magnet(requete *list.Element, Tab_wd *owm.All_data) {
	rqt := requete.Value.(*protocol.Request)
	var tab [3]int64
	list_tmp := list.New()
	var ifball Posball
	user := Data.User.Value.(*users.User)
	var answer []byte
	var eball *list.Element

	if user.MagnetisValid() == true {
		if Data.Lst_ball.Id_max > 0 {
			for i := 0; i < 3; i++ {
				tab[i] = rand.Int63n(Data.Lst_ball.Id_max)
			}
			list_tmp_2 := Data.Lst_ball.Get_ballbyid_tomagnet(tab, Data.User)
			eball = list_tmp_2.Front()
		}
		for eball != nil {
			ball := eball.Value.(*list.Element).Value.(*ballon.Ball)
			ifball.id = ball.Id_ball
			ifball.title = ball.Title
			ifball.FlagPoss = 0
			ifball.lon = ball.Coord.Value.(ballon.Checkpoint).Coord.Lon
			ifball.lat = ball.Coord.Value.(ballon.Checkpoint).Coord.Lat
			ifball.wins = ball.Wind.Speed
			ifball.wind = ball.Wind.Degress
			list_tmp.PushBack(ifball)
			eball = eball.Next()
		}
		answer = Write_nearby(requete, list_tmp, MAGNET, user)
	} else {
		answer = Data.Manage_ack(rqt.Rtype, 0, 0)
	}
	Data.Lst_asw.PushBack(answer)
}

func findRefKClosestTo(kadems []*Kademlia, portrange int, searchID ID, KConst int) *list.List {
	var retList *list.List = list.New()
	for i := 0; i < len(kadems); i++ {
		var newNodeID ID
		var newNodeIDDist int
		newNodeID = CopyID(kadems[i].ContactInfo.NodeID)
		newNodeIDDist = newNodeID.Distance(searchID)
		var e *list.Element = retList.Front()
		for ; e != nil; e = e.Next() {
			var dist int
			dist = e.Value.(ID).Distance(searchID)
			//if responseNode is closer than node in ShortList, add it
			if newNodeIDDist < dist {
				retList.InsertBefore(newNodeID, e)
				//node inserted! getout
				break
			}
		}
		if e == nil {
			//node is farthest yet
			retList.PushBack(newNodeID)
		}
	}
	return retList
}

func compareClosestContacts(fn []FoundNode, kadems []*Kademlia, portrange int, searchID ID) {
	var closestList *list.List = findRefKClosestTo(kadems, portrange, searchID, KConst)
	/*
		var pE *list.Element = closestList.Front()
		for ; pE != nil; pE = pE.Next(){
			log.Printf("Sorted? %s %d\n", pE.Value.(ID).AsString(), pE.Value.(ID).Distance(searchID))
		}*/
	var e *list.Element = closestList.Front()
	var overlap int = 0
	//log.Printf("searching for:%s\n", searchID.AsString())
	//log.Printf("reference List: \t\t\t\t\t iterativeFound List:\n")
	for i := 0; i < len(fn); i++ {
		var id ID = e.Value.(ID)
		//log.Printf("[%d]:%s %d\t%s %d", i, id.AsString(), id.Distance(searchID), fn[i].NodeID.AsString(), fn[i].NodeID.Distance(searchID))
		if id.Equals(fn[i].NodeID) {
			overlap++
		} else {
			for k := closestList.Front(); k != nil; k = k.Next() {
				if k.Value.(ID).Equals(fn[i].NodeID) {
					overlap++
				}
			}
		}
		e = e.Next()
	}
	if overlap < 5 {
		log.Printf("overlap of %d. Out of %d total nodes\n", overlap, portrange)
		panic(1)
	}
	//return retContacts
}

func defSetup(e *list.Element, s *env.Scope) (*parse.Atom, error) {
	name := e.Next().Value.(*parse.Atom).Value.(string)
	val, err := eval(e.Next().Next().Value, s)
	if err != nil {
		return nil, err
	}
	return Def(name, val, s), nil
}

func (c *Client) requeue(cursor *list.Element) {
	// If `cursor` is not nil, this means there are notifications that
	// need to be delivered (or redelivered)
	for ; cursor != nil; cursor = cursor.Next() {
		if n, ok := cursor.Value.(Notification); ok {
			go func() { c.notifs <- n }()
		}
	}
}

func ifSetup(e *list.Element, s *env.Scope) (*parse.Atom, error) {
	test, err := eval(e.Next().Value, s)
	if err != nil {
		return nil, err
	}
	thenStmt := e.Next().Next().Value
	elseStmt := e.Next().Next().Next().Value
	return If(test, thenStmt, elseStmt, s)
}

// Removes as space map element from a space map cell and removes it,
// or return nil if not found
func (cell *SpaceMapCell) Remove(el SpaceMapElement) SpaceMapElement {
	var e *list.Element
	for e = cell.Shapes.Front(); e != nil; e = e.Next() {
		val := e.Value
		if val.(SpaceMapElement) == el {
			cell.Shapes.Remove(e)
			return el
		}
	}
	return nil
}

// ListTruncate() removes elements from `e' to the last element in list `l'.
// The range to be removed is [e, l.Back()]. It returns list `l'.
func ListTruncate(l *list.List, e *list.Element) *list.List {
	AssertNotEqual(nil, l)
	AssertNotEqual(nil, e)
	// remove `e' and all elements after `e'
	var next *list.Element
	for ; e != nil; e = next {
		next = e.Next()
		l.Remove(e)
	}
	return l
}

// Finalize and free the cached prepared statements
// To be called in Conn#Close
func (c *cache) flush() {
	if c.maxSize <= 0 {
		return
	}
	c.m.Lock()
	defer c.m.Unlock()
	var e, next *list.Element
	for e = c.l.Front(); e != nil; e = next {
		next = e.Next()
		c.l.Remove(e).(*Stmt).finalize()
	}
}