func expandClass(regex []int) string {
	list := New()
	list.Init()
	nextEscape := false
	escaped := false
	var toDelete *Element
	for reg_index := 0; reg_index < len(regex); reg_index++ {
		escaped = nextEscape
		nextEscape = false
		switch regex[reg_index] {
		case '\\':
			if escaped {
				escaped = false
				list.PushBack(int('\\'))
				toDelete = nil
			} else {
				nextEscape = true
				toDelete = list.PushBack(int('\\'))
			}
			break
		case '-':
			if escaped {
				escaped = false
				list.PushBack(int('-'))
				toDelete.Value = Delete
			} else {
				if reg_index > 0 && reg_index < len(regex)-1 {
					start := regex[reg_index-1]
					end := uint8(regex[reg_index+1])
					for char := uint8(start + 1); char < end; char++ {
						list.PushBack(int(char))
					}
				} else {
					//ERROR
					fmt.Println("invalid character class")
				}
			}
			break
		default:
			list.PushBack(regex[reg_index])
			break
		}
	}
	for e := list.Front(); e != nil; e = e.Next() {
		if e.Value.(int) == Delete {
			list.Remove(e)
		}
	}
	out := string(list.Remove(list.Front()).(int))
	for e := list.Front(); e != nil; e = e.Next() {
		out += string('|')
		out += string(e.Value.(int))
	}
	return out
}

func MakeList(args ...Data) List {
	list := CreateList()
	for _, arg := range args {
		list.PushBack(arg)
	}
	return list
}

// Reads a list of ASN1Cert types from |r|
func readASN1CertList(r io.Reader, totalLenBytes int, elementLenBytes int) ([]ASN1Cert, error) {
	listBytes, err := readVarBytes(r, totalLenBytes)
	if err != nil {
		return []ASN1Cert{}, err
	}
	list := list.New()
	listReader := bytes.NewReader(listBytes)
	var entry []byte
	for err == nil {
		entry, err = readVarBytes(listReader, elementLenBytes)
		if err != nil {
			if err != io.EOF {
				return []ASN1Cert{}, err
			}
		} else {
			list.PushBack(entry)
		}
	}
	ret := make([]ASN1Cert, list.Len())
	i := 0
	for e := list.Front(); e != nil; e = e.Next() {
		ret[i] = e.Value.([]byte)
		i++
	}
	return ret, nil
}

// UserList related:
func GetConnectedUsers(userList *list.List) *list.List {
	list := list.New()
	for e := userList.Front(); e != nil; e = e.Next() {
		list.PushBack(e.Value.(*User).Username)
	}
	return list
}

//==================================================
// env GODEBUG=gctrace=1,schedtrace=1000 ./grammar
//
// even one struct{xxx} nested into another struct{xxx} the gc can
// collect the memory too.
//==================================================
func memory() {
	type stdata struct {
		data [64 * 1024]byte
	}
	type stmemory struct {
		used int
		data *stdata
	}

	list := list.New()
	i := 0
	for {
		c := new(stmemory)
		d := new(stdata)
		c.data = d
		list.PushBack(c)
		time.Sleep(10 * time.Millisecond)
		if c == nil {
			break
		}
		i++
		if i%1024 == 0 {
			i = 0
			//this will cause gc to collect memory to the minimal size
			fmt.Printf("do list init\n")
			list.Init()
		}
	}
}

func (txs *txStore) Add(tx string, f *frame.Frame) error {
	if list, ok := txs.transactions[tx]; ok {
		f.Header.Del(frame.Transaction)
		list.PushBack(f)
		return nil
	}
	return txUnknown
}

func main() {
	for i := 0; i < 100000; i++ {
		list := list.New()
		for j := 0; j < 10000; j++ {
			myStruct := new(MyStruct)
			list.PushBack(myStruct)
		}
	}
}

func (ls List) Map(f func(a Data, i int) Data) List {
	list := CreateList()
	i := 0

	for e := ls.Front(); e != nil; e = e.Next() {
		switch t := e.Value.(type) {
		case Data:
			list.PushBack(f(t, i))
		}
		i++
	}

	return list
}

func MatchAll(m *Matcher, text string) []Match {
	list := list.New()
	ch := m.Match(text)
	for n := range ch {
		list.PushBack(n)
	}
	all := make([]Match, list.Len())
	idx := 0
	for e := list.Front(); e != nil; e = e.Next() {
		all[idx] = e.Value.(Match)
		idx++
	}
	return all
}

func Map(value string) *list.List {
	list := list.New()

	f := func(c rune) bool {
		return !unicode.IsLetter(c) && !unicode.IsNumber(c)
	}

	array_str := strings.FieldsFunc(value, f)
	for i := 0; i < len(array_str); i++ {
		fmt.Println("Element", i, "of array is", array_str[i])
		list.PushBack(array_str[i])
	}
	return list
}

func compressSubGraph(letterCount int, subGraph map[string]*WordNode, done chan bool) {
	for _, node := range subGraph {
		list := list.New()
		for letter := 0; letter < letterCount; letter++ {
			for _, edge := range node.Edges[letter] {
				if edge != nil {
					list.PushBack(edge)
				}
			}
		}
		node.Neighbours = listToNodeSlice(list)
		node.Edges = nil
	}
	done <- true
}

func (ls List) Filter(f func(a Data, i int) bool) List {
	list := CreateList()
	i := 0

	for e := ls.Front(); e != nil; e = e.Next() {
		switch t := e.Value.(type) {
		case Data:
			if f(t, i) {
				list.PushBack(t)
			}
		}
		i++
	}

	return list
}

func (d *Discover) init() {
	//构造一个映射端口号队列列表
	list := list.New()
	startPort := 1990
	for i := 0; i < 10; i++ {
		list.PushBack(startPort)
		startPort++
	}
	d.MappingInfo = MappingInfo{OutsideMappingPort: make(map[string]int, 2), InsideMappingPort: make(map[string]int, 2)}
	d.GroupIp = "239.255.255.250:1900"
	d.DiscoverInfo = DiscoverInfo{MappingPorts: list,
		Protocols: []string{"TCP", "UDP"},
		DefaultSearchType: []string{"urn:schemas-upnp-org:service:WANIPConnection:1",
			"urn:schemas-upnp-org:service:WANPPPConnection:1",
			"urn:schemas-upnp-org:device:InternetGatewayDevice:1"}}

}

// our simplified version of MapReduce does not supply a
// key to the Map function, as in the paper; only a value,
// which is a part of the input file content. the return
// value should be a list of key/value pairs, each represented
// by a mapreduce.KeyValue.
func Map(value string) *list.List {
	list := list.New()

	f := func(c rune) bool {
		return !unicode.IsLetter(c) && !unicode.IsNumber(c)
	}

	array_str := strings.FieldsFunc(value, f)
	for i := 0; i < len(array_str); i++ {
		var kv mapreduce.KeyValue
		kv.Key = array_str[i]
		kv.Value = "1"
		list.PushBack(kv)
	}

	return list
}

func ParseTree(tree ast.ASTNode) (*list.List, error) {
	list := list.New()

	switch node := tree.(type) {
	case *ast.BlockStmt:
		previous := current
		current = newScope()
		scopes = append(scopes, current)
		for _, stmt := range node.List() {
			l, err := ParseTree(stmt)
			if err != nil {
				return nil, err
			}
			list.PushBackList(l)
		}
		current = previous
		return list, nil
	case *ast.GenDecl:
		// declarations never push back lists
		_, err := ParseTree(node.Decl)
		if err != nil {
			return nil, err
		}

		value, err := ParseTree(node.Value)
		if err != nil {
			return nil, err
		}
		list.PushBackList(value)
	case *ast.DeclObj:
		return nil, current.declVar(node.Id)
	case *ast.AsmExpr:
		asm := strings.Split(node.Asm, "\n")
		for _, asm := range asm {
			cmt := strings.Split(asm, ";")
			if len(cmt) > 0 && len(cmt[0]) > 0 && cmt[0] != ";" {
				list.PushBack(strings.TrimSpace(cmt[0]))
			}
		}
		return list, nil
	}
	return list, nil
}

// Add a new service definition to the list. If the definition is added or
// updated, return true.
func (l *serviceList) Add(service *ServiceDef) bool {
	list := (*list.List)(l)
	for iter := list.Front(); iter != nil; iter = iter.Next() {
		e := iter.Value.(*ServiceDef)
		res := service.compare(e)
		if res > 0 {
			continue
		} else if res < 0 {
			list.InsertBefore(service, iter)
			return true
		} else if e.connId == service.connId {
			// Replace the definition if it is from the same connection.
			iter.Value = service
			return true
		}
		// Equal entries but from a different connection.
		return false
	}
	list.PushBack(service)
	return true
}

func initIPv4LMap(c appengine.Context) error {
	q := datastore.NewQuery("SliverTool").Filter("status_ipv4 =", "online")
	list := list.New()
	var sliverTools []*data.SliverTool
	_, err := q.GetAll(c, &sliverTools)
	if err != nil {
		return err
	}
	for _, sl := range sliverTools {
		data := &locmap.Data{
			Status:     true,
			ResourceId: sl.ToolID,
			ServerId:   sl.SliverIPv4,
			Lat:        sl.Latitude,
			Lon:        sl.Longitude,
		}
		list.PushBack(data)
	}
	LMapIPv4.UpdateMulti(list, nil)
	return nil
}

func loadList(path string) *list.List {
	// Check if file exists
	var f *os.File
	var err error
	if _, err = os.Stat(path); os.IsNotExist(err) {
		// Create list file
		f, err = os.Create(path)
		if err != nil {
			log.Fatal(err)
		}
	} else {
		// Open list file
		f, err = os.Open(path)
		if err != nil {
			log.Print(err)
		}
	}
	defer f.Close()

	// Make list
	list := list.New()

	// Read task list
	dec := json.NewDecoder(f)
	for {
		var item ListItem
		err = dec.Decode(&item)
		if err != nil {
			if err == io.EOF {
				break
			}
			log.Fatal(err)
		}
		list.PushBack(item)
	}
	return list
}

// InsertAt attempts to insert the value v at the given logical index i. It
// returns false if i is out of bounds. Note that a value of i equal to the
// length of this GapSlice is not considered out of bounds; it is handled as
// a special case of appending to this GapSlice.
func (s *GapSlice) InsertAt(i int, v interface{}) (success bool) {
	if i > s.size {
		return false
	}

	list := s.list

	// Special case: inserting in the very end of this gap slice.
	if i == s.size {
		list.PushBack(v)
		s.size += 1
		return true
	}

	e, offset := s.locate(i)
	if e == nil {
		return false
	}

	if slice, isSlice := e.Value.(gapSliceChunk); isSlice {
		if offset == 0 {
			list.InsertBefore(v, e)
		} else {
			a, b := slice[:offset], slice[offset:]
			e.Value = a
			e = list.InsertAfter(v, e)
			list.InsertAfter(b, e)
		}
		s.size += 1
		return true
	}

	list.InsertBefore(v, e)
	s.size += 1
	return true
}

func ExpectationSyntaxSpec(c gospec.Context) {

	c.Specify("Objects can be compared for equality", func() {
		c.Expect(1, Equals, 1)
		c.Expect("string", Equals, "string")

		// There are some shorthands for commonly used comparisons:
		c.Expect(true, IsTrue)
		c.Expect(false, IsFalse)
		c.Expect(nil, IsNil)
		var typedNilPointerInsideInterfaceValue *os.File
		c.Expect(typedNilPointerInsideInterfaceValue, IsNil)

		// Comparing pointer equality is also possible:
		p1 := &Point2{1, 2}
		p2 := p1
		p3 := &Point2{1, 2}
		c.Expect(p2, IsSame, p1)
		c.Expect(p3, Not(IsSame), p1)

		// Comparing floats for equality is not recommended, because
		// floats are rarely exactly equal. So don't write like this:
		c.Expect(3.141, Equals, 3.141)
		// But instead compare using a delta and write like this:
		c.Expect(3.141, IsWithin(0.001), 3.1415926535)

		// Objects with an "Equals(interface{}) bool" method can be
		// compared for equality. See "point.go" for details of how
		// the Equals(interface{}) method should be written. Special
		// care is needed if the objects are used both as values and
		// as pointers.
		a1 := Point2{1, 2}
		a2 := Point2{1, 2}
		c.Expect(a1, Equals, a2)

		b1 := &Point3{1, 2, 3}
		b2 := &Point3{1, 2, 3}
		c.Expect(b1, Equals, b2)
	})

	c.Specify("All expectations can be negated", func() {
		c.Expect(1, Not(Equals), 2)
		c.Expect("apples", Not(Equals), "oranges")
		c.Expect(new(int), Not(IsNil))
	})

	c.Specify("Boolean expressions can be stated about an object", func() {
		s := "some string"
		c.Expect(s, Satisfies, len(s) >= 10 && len(s) <= 20)
		c.Expect(s, Not(Satisfies), len(s) == 0)
	})

	c.Specify("Custom matchers can be defined for commonly used expressions", func() {
		c.Expect("first string", HasSameLengthAs, "other string")
	})

	c.Specify("Arrays/slices, lists and channels can be tested for containment", func() {
		array := []string{"one", "two", "three"}
		list := list.New()
		list.PushBack("one")
		list.PushBack("two")
		list.PushBack("three")
		channel := make(chan string, 10)
		channel <- "one"
		channel <- "two"
		channel <- "three"
		close(channel)

		c.Expect(array, Contains, "one")
		c.Expect(list, Contains, "two")
		c.Expect(channel, Contains, "three")
		c.Expect(array, Not(Contains), "four")

		c.Expect(list, ContainsAll, Values("two", "one"))
		c.Expect(list, ContainsAny, Values("apple", "orange", "one"))
		c.Expect(list, ContainsExactly, Values("two", "one", "three"))
		c.Expect(list, ContainsInOrder, Values("one", "two", "three"))
		c.Expect(list, ContainsInPartialOrder, Values("one", "three"))
	})
}